453. Minimum Moves to Equal Array Elements

Problem

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]

Problem Summary

Given a non-empty integer array of length n, find the minimum number of moves required to make all array elements equal. Each move increments n - 1 elements by 1.

Solution Approach

• Given an array, the goal is to output the minimum number of steps needed to make all elements equal. Each move increments n - 1 elements by 1.
• A math problem. If you think about this problem directly, you may consider sorting or brute-force methods. Think about it in reverse: making every element the same means reducing the differences among all elements to 0. During each move, n - 1 elements are incremented by 1, so the relative difference between the element that is not incremented and the other n - 1 elements is reduced. Therefore, the minimum number of steps to make all elements equal is equal to reducing the relative differences of all elements down to the minimum number. With this insight, the problem can be solved elegantly.

Code

package leetcode

import "math"

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