## 453. Minimum Moves to Equal Array Elements

Given a non-empty integer array of size n, find the minimum number of moves required to make all array elements equal, where a move is incrementing n - 1 elements by 1.

Example:

Input:
[1,2,3]

Output:
3

Explanation:
Only three moves are needed (remember each move increments two elements):

[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]


b'
\n\n

## Solution

\n
\n

#### Approach #1 Brute Force [Time Limit Exceeded]

\n

Firstly, we know that in order to make all the elements equal to each other with minimum moves, we need to do the increments in all but the maximum element of the array.\n Thus, in the brute force approach, we scan the complete array to find the maximum and the minimum element. After this, we add 1 to all the elements except the maximum element, and\nincrement the count for the number of moves done. Again, we repeat the same process, and this continues until the maximum and the minimum element become equal to each other.

\n\n

Complexity Analysis

\n
\n
• Time complexity : , where is the length of the array and is the difference between maximum element and minimum element.
• \n
• Space complexity : . No extra space required.
• \n
\n
\n

#### Approach #2 Better Brute Force[Time Limit Exceeded]

\n

Algorithm

\n

In the previous approach, we added 1 to every element in a single step. But, we can modify this approach to some extent. In order to make the minimum element equal to the maximum element, we need to add 1 atleast times,\nafter which, the maximum element could change. Thus, instead of incrementing in steps of 1,we increment in bursts, where each burst will be of size .\nThus, we scan the complete array to find the maximum and minimum element. Then, we increment every element by units and add to the count of moves. Again we\nrepeat the same process, until the maximum and minimum element become equal.

\n\n

Complexity Analysis

\n
\n
• Time complexity : . In every iteration two elements are equalized.
• \n
• Space complexity : . No extra space required.
• \n
\n
\n

#### Approach #3 Using Sorting [Accepted]

\n

Algorithm

\n

The problem gets simplified if we sort the given array in order to obtain a sorted array . Now, similar to Approach 2,we use the difference to update the elements of the array, but we need not traverse the whole array to find the maximum and minimum element every time,\nsince if the array is sorted, we can make use of this property to find the maximum and minimum element after updation in time. Further, we need not actually update all the elements of the array.\nTo understand how this works, we\'ll go in a stepwise manner.

\n

Firstly, assume that we are updating the elements of the sorted array after every step of calculating the difference . We\'ll see how to find the maximum and minimum element without\ntraversing the array. In the first step, the last element is the largest element. Therefore, . We add to all the elements except the last one i.e. .\n Now, the updated element at index 0 , will be . Thus, the smallest element is now equal to the previous largest element . Since, the\n elements of the array are sorted, the elements upto index satisfy the property . Thus, after updation, the element will become the largest element, which is obvious due to the sorted array property. Also, a\n is still the smallest element.

\n

Thus, for the second updation, we consider the difference as . After updation, will become equal to similar to the first iteration.\n Further, since and were equal. After the second updation, we get . Thus, now the largest element will be .\n Thus, we can continue in this fashion, and keep on incrementing the number of moves with the difference found at every step.

\n

Now, let\'s come to step 2. In the first step, we assumed that we are updating the elements of the array at every step, but we need not do this. This is because, even after updating\n the elements the difference which we consider to add to the number of moves required remains the same because both the elements and required to find the get updated by the\n same amount everytime.

\n

Thus, we can simply sort the given array once and use .

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . Sorting will take time.

\n
• \n
• \n

Space complexity : . No extra space required.

\n
• \n
\n
\n

#### Approach #4 Using DP [Accepted]

\n

Algorithm

\n

The given problem can be simplified if we sort the given array once. If we consider a sorted array , instead of trying to work on the complete problem of\nequalizing every element of the array, we can break the problem for array of size into problems of solving arrays of smaller sizes. Assuming, the elements upto\nindex have been equalized, we can simply consider the element at index and add the difference to the total number of moves for the array upto index to be equalized i.e. .\n But when we try to proceed with this step, as per a valid move, the elements following will also be incremented by the amount i.e. , for .\n But while implementing this approach, we need not increment all such \'s. Instead, we\'ll add the number of done so far to the current element i.e. and update it to .

\n

In short, we sort the given array, and keep on updating the required so far in order to equalize the elements upto the current index without actually changing the elements of the\n array except the current element. After the complete array has been scanned gives the required solution.

\n

The following animation will make the process more clear for this example:

\n

[13 18 3 10 35 68 50 20 50]

\n

\n !?!../Documents/453_Minimum_Moves.json:1000,563!?!

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . Sorting will take time.

\n
• \n
• \n

Space complexity : . Only single extra variable is used.

\n
• \n
\n
\n

#### Approach #5 Using Math[Accepted]

\n

Algorithm

\n

This approach is based on the idea that adding 1 to all the elements except one is equivalent to decrementing 1 from a single element, since we are interested in the relative levels of the\n elements which need to be equalized. Thus, the problem is simplified to find the number of decrement operations required to equalize all the elements of the given array.\n For finding this, it is obvious that we\'ll reduce all the elements of the array to the minimum element. But, in order to find the solution, we need not actually decrement the elements. We can find the\n number of moves required as , where is the length of the array.

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . We traverse the complete array once.

\n
• \n
• \n

Space complexity : . No extra space required.

\n
• \n
\n
\n

#### Approach #6 Modified Approach Using Maths[Accepted]

\n

Algorithm

\n

There could be a problem with the above approach. The value could be very large and hence could lead to integer overflow if the \'s are\nvery large. To avoid this problem, we can calculate the required number of on the fly. .

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . One pass for finding minimum and one pass for calculating moves.

\n
• \n
• \n

Space complexity : . No extra space required.

\n
• \n
\n
\n

Analysis written by: @vinod23

\n
'