Last Updated: 1 Dec, 2021

Minimum Moves to Equal Array Elements

Moderate
Asked in companies
TwitterMorgan StanleyAdobe

Problem statement

Ninja has given an array 'ARR' containing 'N' integers; he can perform several moves on that array. In one move, he can increment any 'N' - 1 element of it by 1.

Ninja wants to make all elements of the array equal by performing some finite number of moves. As Ninjas friend, your task is to tell the Ninja that the minimum number of moves is needed to make all array elements equal.

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

It is possible to make all elements of the given array equal by three moves only. There is no possible solution that can perform the task in minimum moves than 3.
[1, 2, 3] => [2, 3, 3] => [3, 4, 3] => [4, 4, 4]
Input Format :
The first line of input contains an integer 'T', denoting the number of test cases. 

For each test case, the first line contains a single integer 'N' number of array elements, and the next line contains 'N' elements the array elements. 
Output format :
For each test case, print the minimum number of moves needed to make all array elements equal.

Output for each test case will be printed in a separate line.
Note :
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= ‘T’ <= 10
2 <= 'N' <= 10^4
0 <= 'ARR[i]'<= 10^9

Approaches

01 Approach

Approach:  Here, the observation is: adding 1 to 'N - 1' elements is equivalent to subtracting 1 from one of the elements and adding 1 to all the elements.

 

Adding 1 to all elements does not change anything in terms of equality. So we must find the minimum number of moves. The only way to make all elements equal this way is to make them equal to the array's minimum element.

 

Hence, the minimum number of moves will be equal to the sum of whole array elements - 'N' * min_element.

 

Algorithm : 

 

  1. If 'N' is 2 then return 0.
  2. Initialize the variable 'sum' with 0 and 'minimum' with ‘ARR[0]’
  3. Loop ‘i’ over all the array elements and add each 'ARR[i]' to the 'sum' and update the 'minimum' with the minimum of all array elements.
  4. Initialize the variable 'answer' and update it with the 'sum' - 'N' * 'minimum'
  5. Return 'answer'.