DDSA Solutions

453. Minimum Moves to Equal Array Elements

EasyView on LeetCode
ArrayMath
Time: O(n)
Space: O(1)

Problem Overview

One move increments every element except one.

Intuition

One move increments every element except one. The gaps between the numbers do not change if, instead, that one excluded element is decreased by 1. Relative to the rest of the array, the two operations are the same. Making every element equal is then the same as lowering values until they all meet the current minimum, because the minimum never needs to come down. Element i must be lowered nums[i] minus the minimum times, and each of those unit drops is one move. The total is the sum of the array minus the minimum multiplied by the length. A single pass records both the sum and the minimum. The sum is kept in a 64 bit integer, because an array of length 100000 with values near a billion overflows a 32 bit total before the subtraction. The final move count itself fits in a 32 bit integer, so that difference is returned as an int.

Algorithm

  1. 1Walk the array once.
  2. 2Add each value into a 64 bit sum and keep the smallest value seen.
  3. 3Multiply that minimum by the length in 64 bit arithmetic.
  4. 4Return the sum minus that product, as a 32 bit integer.

Example Walkthrough

Input: nums = [1, 2, 3]

  1. 1.The minimum is 1. The gaps above it are 0, 1, and 2.
  2. 2.The gaps add to 3, which is the array sum 6 minus 1 times 3.
  3. 3.The moves raise the array through [2, 3, 3] and [3, 4, 3] to [4, 4, 4].

Output: 3

Common Pitfalls

  • •A 32 bit running sum wraps on a long array of large values. The sum is a 64 bit integer.
  • •Multiply the minimum by the length as a 64 bit product before subtracting it from the sum.
  • •When every element is already equal, every gap is 0 and the answer is 0.
  • •Negative values still meet at the current minimum. A gap below that minimum does not occur.
453.cs
C#
// Approach: Raising every element except one by 1 changes the gaps the same
// way as lowering that one element by 1. The shared final value is the
// current minimum, so the number of moves is the total of every gap above
// it. One pass records the sum and the minimum in 64 bit arithmetic, then
// the result is the sum minus the minimum times the length.
// Time: O(n) Space: O(1)

public class Solution {
    public int MinMoves(int[] nums) {
        long sum = 0;
        int minValue = nums[0];
        for (int i = 0; i < nums.Length; i++) {
            int value = nums[i];
            sum += value;
            if (value < minValue)
                minValue = value;
        }
        return (int)(sum - (long)minValue * nums.Length);
    }
}
Was this solution helpful?

Related Problems