Minimum Moves to Equal Array Elements – LeetCode Solution [Medium]

Problem

You are given an integer array nums of size n, return the minimum number of moves required to make all array elements equal. In one move, you can increment n - 1 elements of the array by 1.

LeetCode Problem Link

Input

int vector<> nums, size[nums] = n

Output

int moves: number of moves required to make all array elements equal

Constraints

• n == nums.length
• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109

Sample Input

nums = [1,2,3]

Sample Output

3

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

Solution

This problem might sound a bit complex at first, however we could use some mathematics to solve this easily. The problem asks us to increment n - 1 elements by one in each move to make all elements in the array equal, and our task is to minimize the number of such moves.

Think about it:
Incrementing n - 1 elements by 1 is essentially the same as decrementing one element by 1. In this context, our task changes from making all elements equal by incrementing to making all elements equal by decrementing.

Relative Difference: Why this works?

Now if we need to equalise all array elements by increasing n-1 elements, we’ll do it by making all elements equal to the highest element.
When we increment n - 1 elements (excluding the highest number) in an array by 1 (with n being the array’s length), the relative difference between the highest number and all other numbers effectively decreases. That’s because the highest number remains unchanged and all other numbers increase by 1.

This scenario is analogous to decreasing the highest number by 1. If we were to decrement the highest number by 1, the relative differences between this number and all other elements would also effectively decrease, with amount of gap reduced, being equal to the first case.
That is same as the scenario in which we incremented n - 1 elements. This similarity arises because in both cases, the gap or relative difference between the highest number and all other numbers in the array is reduced by 1 each time.

We now understand that we need to decrement elements to make all of them equal. So, which number should all elements be made equal to?
To make all elements equal with the least number of decrement operations, we should aim to make all elements equal to the minimum number in the array. Therefore, our approach will be to calculate the difference between each element and the minimum element, and then sum up all these differences.

Code Implementation

def minMoves (nums):
    return sum(nums) - (min(nums) * len(nums))

The time complexity of this solution is O(n), where n is the number of elements in the array. This is because we are iterating over the entire array once to compute the sum and find the minimum element.