Solution Explanation for Minimum Moves to Equal Array Elements

This problem asks for the minimum number of moves to make all elements in an array equal. In each move, we increment n-1 elements by 1, where n is the array's length. A mathematical approach provides an efficient solution.

Mathematical Approach

The core idea is that every increment operation increases the sum of the array. Let's analyze it:

• Let s be the sum of the array elements.
• Let min be the minimum element in the array.
• Let n be the length of the array.
• Let k be the minimum number of moves.

After k moves, all elements will be equal to min + k. The final sum of the array will be n * (min + k). Since each move adds n-1 to the sum, the total sum after k moves will also be s + k * (n-1).

Therefore, we can set up an equation:

s + k * (n - 1) = n * (min + k)

Solving for k:

s + k * n - k = n * min + n * k

s - n * min = k

This means the minimum number of moves (k) is simply the difference between the sum of the array and n times the minimum element.

Time and Space Complexity

• Time Complexity: O(n) - We iterate through the array once to find the sum and minimum element.
• Space Complexity: O(1) - We use only a few constant extra variables.

Code Implementation in Multiple Languages

The code implementations below directly apply the derived formula: sum(nums) - min(nums) * len(nums). They efficiently calculate the sum and minimum element and then apply the formula.

Python

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

Java

class Solution {
    public int minMoves(int[] nums) {
        int sum = 0;
        int min = Integer.MAX_VALUE;
        for (int num : nums) {
            sum += num;
            min = Math.min(min, num);
        }
        return sum - min * nums.length;
    }
}

C++

class Solution {
public:
    int minMoves(vector<int>& nums) {
        long long sum = 0;
        int min = INT_MAX;
        for (int num : nums) {
            sum += num;
            min = min(min, num);
        }
        return sum - (long long)min * nums.size();
    }
};
 

Go

func minMoves(nums []int) int {
	sum := 0
	min := math.MaxInt32
	for _, num := range nums {
		sum += num
		if num < min {
			min = num
		}
	}
	return sum - min*len(nums)
}

Javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var minMoves = function(nums) {
    let sum = 0;
    let min = Infinity;
    for (let num of nums) {
        sum += num;
        min = Math.min(min, num);
    }
    return sum - min * nums.length;
};

Typescript

function minMoves(nums: number[]): number {
    let sum = 0;
    let min = Infinity;
    for (let num of nums) {
        sum += num;
        min = Math.min(min, num);
    }
    return sum - min * nums.length;
};

All these solutions achieve the optimal time and space complexity. They directly implement the mathematical solution derived above, offering a concise and efficient approach to the problem. Note the use of long long in the C++ solution to avoid potential integer overflow issues for very large arrays. Similar considerations might be necessary in other languages depending on the input constraints.