Given an array of numbers, how do we find the minimum number of changes(additions/subtractions) to the elements so that each number in the array is same or equal.
For example given the array {1, 2, 3, 4}, the minimum number of changes are 3. i.e we can choose any of the four elements and make the other three elements equal to the chosen element.
Similarly given the array {56, 29, 112, 29}, the minimum number of changes to make is 2. We can choose 29 as the common element and change the other two elements.
This problem is from recently concluded Codechef contest. Click on this link to read the complete problem statement.
The solution is evident from the second example. This is the problem of finding the number of occurrences of a most frequently appearing number (mode) and subtracting it from the total number of elements.
There are at least two different approaches to implement the solution.
One is to sort the array (takes O(n log n) time) first and find the maximum frequency in O(n) time.
The other is a map based approach to store the frequencies of elements while iterating through all the elements and find the maximum among them. This will take O(n) time bust consumes O(n) extra space.
Below is the C++ implementation of the first strategy. Read my previous post for the implementation of map based method.