Formatted question description: https://leetcode.ca/all/453.html

453. Minimum Moves to Equal Array Elements

Level

Easy

Description

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]

Solution

Incrementing n - 1 elements by 1 is equivalent to incrementing all elements by 1 and decrementing one element by 1. Since incrementing all elements by 1 doesn’t change whether the elements are equal, the procedure is equivalent to decrementing only one element by 1.

Sort the array, and since each element can only be decremented, the only way to make all elements equal is to decrement all elements to the smallest element, and thus the minimum moves can be calculated.

class Solution {
    public int minMoves(int[] nums) {
        Arrays.sort(nums);
        int min = nums[0];
        int moves = 0;
        int length = nums.length;
        for (int i = 0; i < length; i++)
            moves += nums[i] - min;
        return moves;
    }
}

All Problems

All Solutions