Last Updated: 30 Sep, 2020
Day 10 : Minimum Operations
Easy
Asked in companies
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
Approaches
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:
- Initialize a variable ‘MAXFREQ’ to 0, which will store the frequency of the most occurring element.
- Iterate on each element, and initialise a variable ‘FREQ’ which will store the frequency of the current element.
- 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’.
- For every element update the ‘MAXFREQ’ with the maximum of ‘MAXFREQ’ and ‘FREQ’.
- Return the ‘N’ - ‘MAXFREQ’.
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:
- Sort the given array in increasing order.
- Initialize a variable ‘MAXFREQ’ by 0 that will store the frequency of the most occurring element.
- Run a while loop.
- For each unique element, initialize a variable ‘FREQ’ as 1 and check the frequency of the element by running a nested while loop that will run until the elements are the same and keep incrementing ‘FREQ’.
- For every element update the ‘MAXFREQ’ with the maximum of 'MAXFREQ' and 'FREQ'.
- Return the ‘N’ - ‘MAXFREQ’.
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:
- Create a map that will store the frequency of each element of the array.
- The key of the map will be the element of the array and its corresponding value will be the frequency.
- For each element, check if it is already present in the map if it is present then increment the frequency of the element by 1, otherwise store the element in the map with frequency as 1.
- Initialize a variable ‘MAXFREQ’ by 0 that will store the frequency of the most occurring element.
- For each keyset in the map, retrieve its frequency and update the ‘MAXFREQ’ as the maximum of ‘MAXFREQ’ and frequency.
- Return the ‘N’ - ‘MAXFREQ’.