Minimum Operations

Posted: 30 Sep, 2020
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

You are given an array 'ARR' of 'N' positive integers. You need to find the minimum number of operations needed to make all elements of the array equal. You can perform addition, multiplication, subtraction or division with any element on an array element.

Addition, Subtraction, Multiplication or Division on any element of the array will be considered as a single operation.

Example:

If the given array is [1,2,3] then the answer would be 2. One of the ways to make all the elements of the given array equal is by adding 1 to the array element with value 1 and subtracting 1 from the array element with value 3. So that final array would become [2,2,2]. 
Input Format:
The first line of input contains a single integer 'T', representing the number of test cases.

The first line of input contains an integer 'N' representing the length of the array.

The second line contains 'N' single space-separated integers representing elements of the array 'ARR'.
Output Format:
For each test case, return an integer in a single line i.e. the minimum number of operations required to make all the elements of the array equal.
Note:
You are not required to print the expected output, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 10^5
0 <= ARR[i] <= 10^5

Where 'ARR[i]' is the element of the array 'ARR' at index 'i'.

Time Limit: 1 sec
Approach 1

For making all elements equal you can select a target value and then you can make all elements equal to that. Now, for converting a single element to a target value you can perform a single operation only once. In this manner, you can achieve your task in the maximum of  ‘N’ operations but you have to minimize this number of operations and for this, your selection of target is very important because if you select a target whose frequency in the array is ‘X’ then you have to perform only ‘N’ - ‘X’ more operations as you have already ‘X’ elements equal to your target value. So finally, our task is reduced to finding the element with the maximum frequency.

 

The steps are as follows:

 

  1. Initialize a variable ‘MAXFREQ’ to 0, which will store the frequency of the most occurring element.
  2. Iterate on each element, and initialise a variable ‘FREQ’ which will store the frequency of the current element.
  3. Calculate the current frequency of the element by comparing it with all array elements using a nested loop, and if the element in the inner loop is equal to the current element then increment the ‘FREQ’.
  4. For every element update the ‘MAXFREQ’ with the maximum of ‘MAXFREQ’ and ‘FREQ’.
  5. Return the ‘N’ - ‘MAXFREQ’.
Try Problem