Minimum Operations
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

Question

Minimum Operations

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

Accepted Answer

Brute Force

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

Space Complexity: O(1)Explanation:

O(1).

Since only a constant extra space is required. Thus the space complexity will be O(1).

Time Complexity: O(n^2)Explanation:

O(N ^ 2), Where ‘N’ is the length of the array.

Since we are calculating the frequency of each element by traversing the whole array for each of the ‘N’ elements. Thus the time complexity will be O(N ^ 2).

Accepted Answer

Sort the array

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

Space Complexity: O(1)Explanation:

O(1).

Since only a constant extra space is required. Thus the space complexity will be O(1).

Time Complexity: O(nlogn)Explanation:

O(N * log(N)), Where ‘N’ is the length of the array.

Since we require sorting the array that will cause O(N * log(N)) running time. After that, we are traversing the whole array only once which takes O(N) time. So, the total time complexity will be O(N * log(N)).

Accepted Answer

Optimal Approach

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

Space Complexity: O(n)Explanation:

O(N), Where ‘N’ is the length of the array.

Since all elements can be unique so total ‘N’ key values pairs will get stored in the map. Thus, Space Complexity will be O(N).

Time Complexity: O(n)Explanation:

O(N), Where ‘N’ is the length of the array.

Since we only require traversing the array once i.e O(N) and the map only once, so O(Number of unique elements) and the number of unique elements won’t exceed N, thus O(N). So, the total time complexity will be O(N).

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:

Input Format:

Output Format:

Note:

Constraints:

Top TCS SDE-2 interview questions & answers

Popular interview questions of SDE-2