Problem

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.

Examples

Example 1:

1
2
3
4

Input: nums = [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]

Example 2:

1
2

Input: nums = [1,1,1]
Output: 0

Solution

Method 1 - Maths

To make all elements equal by incrementing n-1 elements by 1 in each move, we can observe the following:

  • Instead of incrementing n-1 elements, an equivalent problem is to decrement one element by 1.
  • We need to make all elements equal to the minimum element in the array.
  • The number of moves required is the sum of all elements minus the product of the minimum element and the size of the array.

And the mathematical formula will be:

  • The total number of moves required: sum(nums) - n * min(nums)

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

public class Solution {
    public int minMoves(int[] nums) {
        int minNum = Integer.MAX_VALUE;
        int totalSum = 0;

        for (int num : nums) {
            minNum = Math.min(minNum, num);
            totalSum += num;
        }

        return totalSum - minNum * nums.length;
    }
}
1
2
3
4
5

class Solution:
    def minMoves(self, nums):
        min_num = min(nums)
        total_sum = sum(nums)
        return total_sum - min_num * len(nums)

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)