Make the Equal

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
1 upvote

Problem statement

You are given an array ‘ARR’ of integers of size ‘N’.

In one operation you can increase ‘N’ - 1 elements of the array by 1 or 2 or 5.

The task is to get all elements equal in the minimum number of operations.

Example: 
Input: ‘N’ = 3  ‘ARR’ = [1, 2, 3]

Output: 2
In the First operation we can increase the numbers at index 0, and 1 by 2 which makes the array [3, 4, 3].
In the second operation we increase the numbers at index 0 and 2 by 1 which makes all the elements to [4, 4, 4].
It is the optimal answer and there is no other optimal solution.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains ‘T’, denoting the number of test cases.    

The First line of each test case contains three integers ‘N’.

The Second line contains ‘N’ numbers representing elements of the ‘ARR’.
Output format : 
Return minimum number of operations required to make all the elements of the array equal.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 100   
1 <= N <= 10^4
1 <= ARR[i] <= 10^3

Time Limit: 1 sec
Sample Input 1 :
2
3 
1 2 3
5 
5 5 5 5 5

##### Sample Output 1 :

2
0
Explanation Of Sample Input 1 :
For the first test case:-
In the First operation we can increase the numbers at index 0, and 1 by 2 which makes the array [3, 4, 3].
In the second operation, we increase the numbers at index 0 and 2 by 1 which makes all the elements [4, 4, 4].
It is the optimal answer and there is no other optimal solution.


For the second test case:-
All the elements of the array are already equal so there is no operation required.
Sample Input 2 :
2
10
13 15 9 7 12 7 12 11 6 12 
7
12 7 12 14 8 6 14
Sample Output 2 :
16
12
Hint

What about reducing a number by 1 or 2 or 5?

Approaches (1)
Greedy

For an array of size ‘N’ if we increase ‘N’-1 elements by some number ‘Y’ it is similar to reducing ‘Y’ from the left number in the above operation.


 

As the increment increments the difference between the remaining number and all the other elements by ‘Y’.

Now For minimum operations, we have to reduce all the numbers of ‘ARR’ to one of the elements in the range [ ‘min’-4, ‘min’] where ‘min’ is the smallest number of the ‘ARR’.


 

Why check till ‘min-4’ because ‘min-5’ will result in the same as ‘min’ cause we can directly reduce 5. Reducing below will be wasting of operations and will not result in minimum operations.

Also consider case 2, 6, and 6 for understanding why we are not checking till only ‘min’.


 

As in 1, 2, 5 where each number if >= 2* lesser than the current number.

So if we will reduce numbers greedily from 5 to 1.


 

The steps are as follows:-

function makeEqual(int N, [int] ARR):

  1. Initialize an integer ‘ans’ with the value ‘1e9’.
  2. Find the minimum element of the array ‘ARR’ and store it in ‘minElement’.
  3. For ‘i’ in range [minElement-4, minElement]:
    1. Declare a variable ‘operation’ representing the number of operations with a value of 0.
    2. For each element ‘j’:
      • Add the number of operations required to make ‘j’ to ‘i’ and add it to ‘operation’.
    3. Update ‘ans’ with the minimum of ‘ans’ and operation.
  4. Return ‘ans’
Time Complexity

O( N ), Where ‘N’ is the number of elements in ‘ARR’. 


 

We can find out the minimum number in O( N ) time and then the outer loop runs 5 times and the inner loop runs O( N ) and for each number, the number of operations required can be calculated in constant time.

Hence the time complexity is O( N ).

Space Complexity

O( 1 ).

 

We are not using any extra space.

Hence space complexity is O( 1 ).

Code Solution
(100% EXP penalty)
Make the Equal
Full screen
Console