Modifying array to get equal frequency of each element!

[spam291203]

I have an array, say A which consists of N elements say: a1, a2, a3 ... aN.
The question asks me to change some elements of this array so that the frequency of each distinct element is the same.

For eg:
Let array be A{1, 2, 3, 2}.
You convert a3 to 1 to get an array A{1, 2, 1, 2}

I am having a lot of trouble implementing it. A few hints would help.

Thanks!

[helios]

What a strange problem. Are you sure you're not supposed to just remove duplicates?

[mbozzi]

What other constraints are there?

If there are none, then you can overwirite each element with some integer n. Are you supposed to change the minimum number of elements?

[spam291203]

@helios No I don't just have to remove duplicates. If there are multiple occurrences of an element that I choose to change, not all get replaced.

For eg:
A{1, 2, 2, 3, 3, 3,} would become A{1, 1, 2, 2, 3, 3}

@mbozzi Constraints say N <= 10^6. Also yes, I do need minimum number of swaps

[helios]

Do you mean {1, 2, 2, 1, 3, 3}? Incidentally, all of these would be equally acceptable solutions:
{1, 2, 2, 1, 3, 3}
{1, 2, 2, 3, 1, 3}
{1, 2, 2, 3, 3, 1}
{2, 2, 2, 3, 3, 3}

Hmm... I don't really know how to implement this, but one thing to do at the start is get the list of divisors of N. Since the frequencies have to equal, you know that the count of distinct elements (M) must be a divisor of N. As a corollary, if N is prime and M is less than N, then you know that the minimal change is to set all elements to the value of the most frequent element. Also, if N is not divisible by M then you know you'll have to remove some elements (the least frequent ones?).

[spam291203]

@helios Thanks for all the help till now. I had a doubt here.
You say that if N is not divisible by M, then I'll have to remove some elements. But the questions asks me to replace some elements. Also, do I replace the least occurring with the most occurring one? But that would result in an unequal frequency distribution!

[Grime]

No you don't have to remove anything from the array. You get the frequency of all elements first. And if the frequency 'M' is not a divisor of 'N' then that's a clue that you have to make changes with it.

How do you know what changes to make (and that it has to be the least swaps don't forget)? Well that's the question.

Hmm this is a guess: Another observation is that you might never need to add a 'new' element to the array. Even if it were legal to, it probably wouldn't be the best solution, which is a requirement for the problem.

So you know three things now.
(i) If N is prime then all elements must be the same (the most frequent element is picked because that will require the least swaps).
(ii) No new elements are to be added
(iii) If the frequency of an element does not divide N then it has to be modified.

So you need to equalize most frequent and least frequent elements such that they're multiples of N? Probably. Anyways I suck at stuff like this so I'll leave it to you to figure out ;p.

[spam291203]

@Grime Thanks! The question does not disallow adding another number as long as it is <=26.
It states that each valid Ai can be, 1<=Ai<=26.

Note that you can replace {1, 2, 3, 2} with {1, 2, 3, 4}

You say that "If the frequency of an element does not divide N then it has to be modified.".

But in the example, {1, 2, 3, 2}
The frequencies would be:

1 -> 1
2 -> 2
3 -> 1

And N would be 4.

Here frequencies for both (1 & 3) would divide N (4), but we will have to change at least one of them.

[helios]

When I said "remove an element" I was saying it as a shorthand for "overwrite all occurrences of a number with something else".

if the frequency 'M' is not a divisor of 'N' then that's a clue that you have to make changes with it

This is wrong. As I defined it above, M is the count of distinct elements, not the frequency of any element. For the array {1, 2, 3, 2}, M = 3, and 4 is not divisible by 3. Another example: {1, 1, 1, 1, 2, 3, 3, 3}. The frequency of 3 doesn't divide 8, but the element that will have to be removed (overwritten) is 2.

(i) If N is prime then all elements must be the same (the most frequent element is picked because that will require the least swaps).

Not necessarily. Reread my previous statement:

if N is prime and M is less than N, then you know that the minimal change is to set all elements to the value of the most frequent element

They must either all be the same or all be different.
input = {1, 2, 3, 4, 5, 6, 7}, output = {1, 2, 3, 4, 5, 6, 7} (note that M < N is not true)
input = {1, 1, 3, 4, 5, 6, 7}, output = {1, 1, 1, 1, 1, 1, 1}