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]

Solution

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

Analysis

A move in this problem is incrementing n - 1 elements by 1
It is completely equivalent to decreasing 1 (n - (n-1) = 1) element by 1 In this situation, the problem becomes very easy to solve
We just find the min in given nums in the first loop
And get difference between min and each element in nums in the second loop
Sometimes we just need to think in a opposite way ;)

Complexity

• Time: O(n), where n the length of nums
• Space: O(1), only constant space is used