Day 10 : Minimum Operations

Easy
0/40
Average time to solve is 20m
22 upvotes
Asked in companies
FlipkartMicrosoftShareChat

Problem statement

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].
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
1
4
1 2 3 4
1
5
Sample Output 1:
3
0
Explanation for Sample Output 1:
In test case 1, There can be many ways by which we can convert the array elements equal, one of the way is:

1 + 2 = 3
2 + 1 = 3
4 - 1 = 3

Here the first operand is the element of the array and the second operand is the operation that we did for making all the numbers of the array equal.

Hence, we did 3 operations to change the elements of the array to 3. Hence the answer is 3.

In test case 2, There is only 1 element and hence no need to make equal and so answer is 0.
Sample Input 2:
2
3
2 4 2
5
1 2 1 4 1
Sample Output 2:
1
2
Explanation for Input 2:
In test case 1, by dividing 4 by 2 (i.e. 4 / 2) we can have all the elements equal to 2. Thus only 1 operation is performed and so answer is 1.

In test case 2, There can be many ways by which we can convert the array elements equal, one of the way is:

2 / 2 = 1
4 / 4 = 1

Here the first operand is the elements of the array and the second operand is the operation that we did for making all the numbers of the array equal.

Hence, we did 2 operations to change the elements of the array to 2. Hence the answer is 2.
Hint

Select a target value and then you can make all elements equal to that. Now, to minimize the number of operations can you think what should be the target value?

Approaches (3)
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:

 

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

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

Space Complexity

O(1).

 

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

Code Solution
(100% EXP penalty)
Day 10 : Minimum Operations
Full screen
Console