Reduce the number of distinct elements in array-CodePudding

I have an array of numbers and another number K.

My task is to reduce the number of distinct elements in the array. For that, I can update the array several times. For updating the array, I have to follow these steps:

Select an element at index i and add that element by K, and reduce all other remaining elements by K.

For updating an array I can select the same index several times.

Example:

K = 1
Array: [3,1,3]    
Answer: 3

I am picking index = 1, as [3-1, 1 1, 3-1] = [2,2,2] so we have number 2 that appears 3 times so this element occurs maximum number of times. So answer is 3.

Another example:

K = 1
Array: [1,2,2]
Answer: 2

It's not possible to make all elements same, so we have number 2 that appears 2 times, so answer is 2.

Array size can be [1, 1000], and the value of K and elements in array is in range [0, 1000]

Here is my code that I tried, my my approach is not correct.

public static int process(int K, int[] A) {
        Map<Integer, Integer> map = new TreeMap<>();
        for (int key : A) {
            map.put(key, map.getOrDefault(key, 0)   1);
        }
        int result = 0;
        boolean flag = false;
        int last = -1, cur = -1;
        for (int key : map.keySet()) {
            if (flag == false) {
                flag = true;
                last = key;
                continue;
            }
            cur = key;
            int a = map.get(last), b = map.get(cur);
            if (Math.abs(last - cur) > K) {
                result  = a   b;
            } else {
                result  = Math.max(a, b);
            }
        }
        last = cur;

        return result;
    }

CodePudding user response：

When looking at the examples with K = 1, it is clear that the answer depends on the parity of the elements. Only elements with same parity can be set to the same level, and all elements with same parity can be joined.

For example:

[2 4 6] -> [1 5 5] -> [2 4 4] -> [3 3 3]
[1 2 2] -> [2 1 1] ... no progress

With K = 1, we have to consider value modulo 2, i.e. modulo 2*K.
When K is different of one, for example K = 2, two numbers can be joined only there are separated by a distance multiple of 4, i.e. of 2*K.

[2 6 6] -> [4 4 4]

For K different from 1, instead of creating buckets for numbers with same parity, we just create buckets according to value modulo 2K.
We just have to pay attention to use the modulo and not the remainder, the values are different for negative values.

Then the answer if simply the highest size of a bucket.

Output:

K = 1  Array : 3 1 3            -> 3
K = 1  Array : 1 2 2            -> 2
K = 1  Array : 2 3 4 7 4 9 11   -> 4
K = 1  Array : -3 -1 2 3        -> 3
K = 3  Array : -7 -1 0 1 2 4 5  -> 3

Here is a simple code in C to illustrate the algorithm.

In this code, the value val_modulo modulo 2K of each element is calculated.
Then, the orresponding counter is increased

Bucket[val_modulo] = Bucket[val_modulo]   1

At the end, the highest value corresponds to the number of repetitions of the most repeated final value.

We may note that the number of non empty bucket corrresponds to the number of different final values (not used in this code).

#include <iostream>
#include <vector>
#include <string>
#include <map>

void print (const std::vector<int> &A, const std::string &after = "\n", const std::string &before = "") {
    std::cout << before;
    for (int x: A) {
        std::cout << x << " ";
    }
    std::cout << after;
}

int Modulo (int n, int mod) {
    int ans = n % mod;
    if (ans < 0) ans  = mod;
    return ans;
}

int max_equal(int K, std::vector<int> A) {
    K = std::abs(K);    // useful befoe taking the modulo
    std::map<int, int> Buckets;
    int nmax = 0;
    int mod = 2*K;
    for (int x: A) {
        
        int val_modulo = Modulo (x, mod);       // and not x*mod, as x can be negative
        Buckets[val_modulo]  ;
    }
    for (auto x: Buckets) {
        if (x.second > nmax) {
            nmax = x.second;
        }
    }
    return nmax;
}

int main() {
    std::vector<std::vector<int>> examples = {
        {3, 1, 3},
        {1, 2, 2},
        {2, 3, 4, 7, 4, 9, 11},
        {-3, -1, 2, 3},
        {-7, -1, 0, 1, 2, 4, 5}
        
    };
    std::vector<int> tab_K = {1, 1, 1, 1, 3};
    
    for (int i = 0; i < examples.size();   i) {
        std::cout << "K = " << tab_K[i] << "  Array : ";
        print (examples[i], " -> ");
        auto ans = max_equal (tab_K[i], examples[i]);
        std::cout << ans << "\n";
    }
    return 0;
}

CodePudding user response：

The problem is conceptual, and translating it in somewhat computing code.

Let's look:

We pick a number (by index, which is irrelevant), and for all the occurrences we add K. All others we subtract K And then the number of same occurrences must be maximal.

The same occurrences can only grow when the picked number K is equal to another number - K.

The data structure:

A map with the array numbers as key, and mapped to frequency (how often the number occurs in the array).

So:

pickedNumber.value K = otherNumber.value - K

=> otherNumber.value = pickedNumber.value 2*K

Note that as there is only one single otherNumber, derived from the pickedNumber. (It might occur more than once.)

And we want maximal:

pickedNumber.frequency   otherNumber.frequency maximal.

Though map is not really needed, a sorted array would do too, let's do a map:

The algorithm:

Kept simple.

    int[] numbers = {3, 1, 3};
    int index = pickedIndexOfBestSolution(numbers, 1);
    System.out.println("Index: "   index);

int pickedIndexOfBestSolution(int[] numbers, int k) {
    Map<Integer, Long> frequencyTable = IntStream.of(numbers)
            .boxed()
            .collect(Collectors.groupingBy(Function.identity(),
                     Collectors.counting()));
    int bestNumber = frequencyTable.entrySet().stream()
            .sorted(Comparator.comparingLong(e -> -e.getValue()
                    - frequencyTable.getOrDefault(e.getKey()   2*k, 0L)))
            .findFirst()
            .map(e -> e.getKey())
            .orElseThrow();
    int index = -1;
    while (numbers[  index] != bestNumber) {
    }
    return index;
}

The frequency table I filled using an IntStream and groupingBy (just as SQL). As counting is done with long, I just kept that.

To find the max I counted the new occurrence count trying to add the "other" number's frequency too; 0 when no other number. Instead of using .reverse() to reverse the comparison (largest, max, first), I took the negative value, which to me seems more calculatory. Notice that a Stream with findFirst to find the max is probably optimal too: no need that the stream creates an intermediate list.

For the index I used brute force (while loop), a kind of indexOf.

Notice if there is no other number, it returns the index of a number with the most occurrences. Which is fine.

In short:

You see the different approach. Actually simpler, and more solid. In fact applying some (minor) intelligence first. Trying to nail down the problem first.