Last Updated: 18 Aug, 2022

Make the Equal

Moderate

Solve now

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.

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

Solve now

Approaches

01 Approach

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

Initialize an integer ‘ans’ with the value ‘1e9’.
Find the minimum element of the array ‘ARR’ and store it in ‘minElement’.
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.
Return ‘ans’

Solve now