Minimum operation to make all elements equal in array

The problem “Minimum operation to make all elements equal in array” states that you are given an array with some integers in it. You have to find out the minimum operations that can be done to make an array equal.

Example

[ 1,3,2,4,1]

3

Explanation

Either 3 subtractions can be done or 3 additions can be done to make an equal array.

[5,3,2,4,1]

4

Explanation

Either 4 subtractions can be done or 4 additions can be done to make an equal array.

Algorithm to find minimum operations to make all elements equal

1. Declare a map.
2. While i < n , loop continues
   1. Store the array element and frequencies of each element into the map.
3. Set “maxCount” to 0.
4. Iterating over the loop check if “maxCount” is less than the value of key in a map
   1. If the condition satisfies, then set the “maxCount” to key’s value.
5. Return ( n – “maxCount” ).

Explanation

We have an integer array as input. Our task is to find out the minimum operations that can be done to make an array equal. We are going to use a map in it. Using a map, we can easily store the elements with their frequencies, because frequencies play a key role to find out the operations.

We are going to find out the element with maximum frequency and we return the difference between the length of the array and maximum frequency count because we have the element already in an array which is repeated so it takes fewer operations to make all the elements as same as it is rather than changing a particular and that’s why (array’s length- maximum frequency) it works here.

Let us consider an example here:

Example

arr: {1, 5, 2, 1, 3, 2, 1};

Starting from the first most element, we traverse the whole array and count the frequency of each element and store it to the map.

i=0,

arr[i]=1

countFreq=[1:1]

i=1

arr[i]=5

countFreq=[1:1,5:1]

i=2

arr[i]=2

countFreq=[1:1,5:1,2:1]

i=3

arr[i]=1

countFreq=[1:2,5:1,2:1] => Here we will find the element “1” twice so will   increase the frequency count of 1.

i=4

arr[i]=3

countFreq=[1:2,5:1,2:1,3:1]

i=5

arr[i]=2

countFreq=[1:2,5:1,2:2:3:1] => Here we will find the element “2” twice so will increase the frequency count of 2.

i=6

arr[i]=1

countFreq=[1:3,5:1,2:2:3:1] => Here we will find the element “1” thrice so will increase the frequency count of 1.

Now initialize “maxCount” to 0. And check for each frequency if it is greater than “maxCount”, if finds to be greater, then store the value of that frequency to “maxCount”

At last, we will have the greatest frequency in “maxCount”.

We return n- “maxCount” => 7-3=4, that is we should do minimum of 4 operations to make the array equal.

Code

C++ to find Minimum operation to make all elements equal in array

#include <bits/stdc++.h>
using namespace std;

int getMinimumOperation (int arr[], int n)
{
  unordered_map<int, int> countFreq;
  for (int i=0; i<n; i++)
    countFreq[arr[i]]++;

  int maxCount = 0;
  for (auto i : countFreq)
    if (maxCount < i.second)
      maxCount = i.second;

  return (n - maxCount);
}
int main()
{
  int arr[] = {1, 5, 2, 1, 3, 2, 1};
  int n = sizeof(arr) / sizeof(arr[0]);
  cout << getMinimumOperation(arr, n);
  return 0;
}

4

Java code to find Minimum operation to make all elements equal in array

import java.util.*;
class minimumOperations
{
    public static int getMinimumOperations(int arr[], int n)
    {
        HashMap<Integer, Integer> countFreq = new HashMap<Integer, Integer>();

        for (int i=0; i<n; i++)
        {
            if(countFreq.containsKey(arr[i]))
            {
                countFreq.put(arr[i], countFreq.get(arr[i])+1);
            }
            else
            {
                countFreq.put(arr[i], 1);
            }
        }
        int maxCount = 0;

        Set<Integer> s = countFreq.keySet();

        for (int i : s)
            if (maxCount < countFreq.get(i))
                maxCount = countFreq.get(i);


        return (n - maxCount);
    }
    public static void main(String[] args)
    {
        int arr[] = {1, 5, 2, 1, 3, 2, 1};
        int n = arr.length;
        System.out.println(getMinimumOperations(arr, n));
    }
}

4

Complexity Analysis

Time Complexity

O(n) where “n” is the number of elements in the array.

Space Complexity

O(n) where “n” is the number of elements in the array.