Home » Technical Interview Questions » Hashing Interview Questions » Minimum operation to make all elements equal in array

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

Minimum operation to make all elements equal in array

[ 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.

READ  Find four elements that sum to a given value (Hashmap)

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.

READ  Non-overlapping sum of two sets

Space Complexity

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

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!!

You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Anisha was able to crack Amazon after practicing questions from TutorialCup