Minimum Moves to Equal Array Elements

Moderate
0/80
profile
Contributed by
13 upvotes
Asked in companies
AdobeMorgan StanleyOptum

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]
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
3
2 3 4
4
1 1 1 1
Sample Output 1 :
3
0
Explanation Of Sample Input 1 :
For the first test case, It is possible to complete the task in 3 moves only. [2, 3, 4] => [3, 4, 4] => [4, 5, 4] => [5, 5, 5]

For the second test case, all array elements are already equal; hence there is no need to perform any move.
Sample Input 2 :
2
4
2 3 4 5
3
1 3 7
Sample Output 2 :
6
8
Hint

Can fix the number to which all elements will be transformed?

Approaches (1)
Maths Solution

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

O(N), where 'N' is the size of the input array.

 

As we are iterating over the whole array of size 'N' the time complexity will be O(N).

Space Complexity

O(1)

 

As we are using the constant extra space the space complexity will be O(1).

Code Solution
(100% EXP penalty)
Minimum Moves to Equal Array Elements
Full screen
Console