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]

Idea 1:

It is a math question!
let’s define sum as the sum of all the numbers, before any moves;
minNum as the min number int the list;
n is the length of the list;

After, say m moves, we get all the numbers as x , and we will get the following equation

sum + m * (n - 1) = x * n

and actually,

x = minNum + m

and finally, we will get

sum - minNum * n = m

So, it is clear and easy now.

class Solution {
    public int minMoves(int[] nums) {
        int len=nums.length;
        long sum=0;
        Arrays.sort(nums);
        if(nums[0]==nums[len-1]) return 0;
        for(int i:nums) sum+=i;
        return (int)sum-nums[0]*len;
    }
}

Idea 2:

Adding 1 to n - 1 elements is the same as subtracting 1 from one element, w.r.t goal of making the elements in the array equal.
So, best way to do this is make all the elements in the array equal to the min element.

(-)

#### Why is this correct?

Because you only care about the difference between elements instead of the final value. In the perspective of difference, add one to all the other elements is equivalent to subtract one from current element.

``` java
public class Solution {
    public int minMoves(int[] nums) {
        if (nums.length == 0) return 0;
        int min = nums[0];
        for (int n : nums) min = Math.min(min, n);
        int res = 0;
        for (int n : nums) res += n - min;
        return res;
    }
}

substract 1 on the max value, then add 1 on each element. this is the same as adding 1 to n - 1 elements.

Provof is based on solving equations:

sum(array)+m*(n-1)=n*f
f-min(array)=m

where m is min moves to take, f is the final value of the array elements. the first equation means, by adding n-1 ones for m times, we will have n array elements with value f. the second equation means, the min value always add 1 in each move (because it’s always the min value of all elements)

solve the equations we have:
m=sum(array)-n*min(array)