Skip to content

453. Minimum Moves to Equal Array Elements

DifficultyMedium

Description

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 must increment n - 1 elements of the array by 1.

 

Example 1:

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:

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

 

Constraints:

  • n == nums.length
  • 1 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • The answer is guaranteed to fit in a 32-bit integer.

Solutions

Solution 1: Mathematics

Thinking

Incrementing \(n-1\) elements is the same as decrementing the one left out, until everything equals the minimum. Simulating the increments rewrites the whole array.

The number of decrements is \(\sum \textit{nums} - n\cdot\min(\textit{nums})\).

One pass for the min and the sum is enough; the operations need not be applied.

Let the minimum value of the array \(\textit{nums}\) be \(mi\), the sum of the array be \(s\), and the length of the array be \(n\).

Assume the minimum number of operations is \(k\), and the final value of all elements in the array is \(x\). Then we have:

\[ \begin{aligned} s + (n - 1) \times k &= n \times x \\ x &= mi + k \\ \end{aligned} \]

Substituting the second equation into the first equation, we get:

\[ \begin{aligned} s + (n - 1) \times k &= n \times (mi + k) \\ s + (n - 1) \times k &= n \times mi + n \times k \\ k &= s - n \times mi \\ \end{aligned} \]

Therefore, the minimum number of operations is \(s - n \times mi\).

\(|\textit{nums}[i]|\) reaches \(10^9\) and \(n\) reaches \(10^5\), so both \(s\) and \(n \times mi\) may fall outside a 32-bit integer. The problem guarantees that their difference still fits, so the sum is computed with a 64-bit integer.

The time complexity is \(O(n)\), and the space complexity is \(O(1)\), where \(n\) is the length of the array.

1
2
3
class Solution:
    def minMoves(self, nums: list[int]) -> int:
        return sum(nums) - min(nums) * len(nums)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    public int minMoves(int[] nums) {
        long s = 0;
        int mi = nums[0];
        for (int x : nums) {
            s += x;
            mi = Math.min(mi, x);
        }
        return (int) (s - (long) mi * nums.length);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    int minMoves(vector<int>& nums) {
        long long s = 0;
        int mi = nums[0];
        int n = nums.size();
        for (int x : nums) {
            s += x;
            mi = min(mi, x);
        }
        return (int) (s - 1LL * mi * n);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func minMoves(nums []int) int {
    mi := 1 << 30
    s := 0
    for _, x := range nums {
        s += x
        if x < mi {
            mi = x
        }
    }
    return s - mi*len(nums)
}

1
2
3
4
5
6
7
8
9
function minMoves(nums: number[]): number {
    let mi = 1 << 30;
    let s = 0;
    for (const x of nums) {
        s += x;
        mi = Math.min(mi, x);
    }
    return s - mi * nums.length;
}

1
2
3
4
5
6
7
8
impl Solution {
    pub fn min_moves(nums: Vec<i32>) -> i32 {
        let (s, mi) = nums
            .iter()
            .fold((0i64, i32::MAX), |(s, mi), &x| (s + x as i64, mi.min(x)));
        (s - mi as i64 * nums.len() as i64) as i32
    }
}

Comments