Minimum Moves to equal array elements [Math]

XXX. Minimum Moves to Equal Array

Math

Array

Problem Statement:

Given an integer array nums, find the minimum number of moves required to make all array elements equal. In one move, you can increment n-1 elements by 1.

• Can only increment n-1 elements at a time
• Need to find minimum moves to make all elements equal
• All elements must be exactly equal at the end

Mathematical Insight:

Incrementing n-1 elements by 1 is equivalent to decrementing 1 element by 1. Therefore, all numbers must be reduced to the minimum number in the array.

Implementation:

Approach 1 (Sum-based):

public int minMoves(int[] nums) {
    int moves = 0, min = Integer.MAX_VALUE;
    
    // Calculate sum and find minimum
    for (int i = 0; i < nums.length; i++) {
        moves += nums[i];               // Sum all numbers
        min = Math.min(min, nums[i]);   // Track minimum
    }
    
    return moves - min * nums.length;   // Moves needed to equalize
}

Approach 2 (Difference-based):

public int minMovesModifiedMath(int[] nums) {
    int min = Integer.MAX_VALUE;
    int ret = 0;
    
    // Find minimum value
    for (int num : nums)
        min = Math.min(min, num);
    
    // Sum up differences from minimum
    for (int num : nums)
        ret += num - min;
    
    return ret;
}

Complexity:

Time Complexity: O(n), one or two passes through array
Space Complexity: O(1), only uses constant extra space

Example:

For array [1, 2, 3]:

• Minimum value = 1
• Differences from min: [0, 1, 2]
• Total moves = 0 + 1 + 2 = 3
• OR: Sum = 6, min * length = 1 * 3 = 3, moves = 6 - 3 = 3

Key Points:

• **Mathematical Equivalence**:
  • Adding to n-1 elements = subtracting from 1 element
  • Final value will be equal to minimum element
  • Total moves is sum of differences from minimum
• **Implementation Choices**:
  • First approach uses sum and multiplication
  • Second approach directly sums differences
  • Both give same result with slightly different logic