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}