Finding the minimum number of moves to achieve equal array elements Long story short, the other day I discovered the site LeetCode and started solving some of its problems until I stumbled onto this one.

I'll paste the description here:


  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.
  
  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]


The problem is, the solution I am trying to submit always exceeds the allowed processing time limit and I feel like I've reached a dead end. Can anyone suggest a way to improve my code?

 static void Main()
    {
        int res = MinMoves(new int[] { 1, 2, 3 });
    }
    public static int MinMoves(int[] nums)
    {
        if (nums.Length &lt; 2)
            return 0;

        int moves = 0;
        int diff = 0;
        int min = 0;
        int max = 0;
        int maxIX = 0;
        do
        {
            min = nums.Min();
            max = nums.Max();
            maxIX = Array.IndexOf(nums, max);
            diff = Math.Abs(max - min);
            moves += diff;
            for (int i = 0; i &lt; nums.Length; i++)
                if (i != maxIX)
                    nums[i] += diff;

        } while (min != max);

        return moves;
    }
The problem can be re-formulated into a much easier-to-conceptualize form.

Instead of


  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.


say instead


  where a move is decrementing a single element by 1


Do you see why these are the same?  Suppose we start with 1, 2, 3.  Adding 1, 1, 0 produces 2, 3, 3.  Adding 0, 0, -1 produces 1, 2, 2, which is effectively the same thing. However many moves it takes to make 2, 3, 3 all equal is surely the same number of moves as it takes to make 1, 2, 2, all equal, or 0, 1, 1, or 1000, 1001, 1001, or whatever. Where you start is irrelevant. 

Once you know that the problem is actually "how many single decrements does it take to get all the elements equal?" the answer is easily seen. There is never any point in decrementing the smallest element, and every element will have to eventually equal the smallest element. Therefore the answer is: it's the sum of the differences of every element from the minimal element. 

That's a trivial program in C#:

var min = nums.Min();
return nums.Select(x =&gt; x - min).Sum();


Or alternatively, in a single line:

return nums.Sum() - nums.Length * nums.Min();


(Though as noted in the comments, this second version can overflow. Consider doing all the math in longs or BigIntegers if you're worried about overflow cases.)