Finding the minimum number of moves to achieve equal array elements

Question

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 < 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 < nums.Length; i++)
                if (i != maxIX)
                    nums[i] += diff;

        } while (min != max);

        return moves;
    }

Answer 1

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 => 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.)

Answer 2

Firstly, identify hidden loops, such as Min, Max and IndexOf, and merge those together - as per Paparazzi's answer. There's no need to count to n 3 times in a row.

The question asks you to find the number of moves, not to actually execute the number of moves. You've already optimized this by working with diff rather than adding just 1 each time. However, this is an optimization for the best-case scenario (e.g., when diff > 1), the worst case performance remains n^2 with respect to the length of nums.

Further optimization could be achieved by removing the lowest duplicated numbers - though this once again is a best-case optimization. (e.g., when your input has few unique numbers).

Finally, rethink the whole thing. Below is what I came up with. It's based on permutations and triangular numbers. I had drafted a proof of sorts, but my lunch break was too short to finish it. Initial unit tests show the output to be identical to your implementation, but requiring just O(n log(n)) time complexity.

public static int GerardMinMoves(int[] nums) {

    // Sort in place. Assumed O(n log(n)) complexity
    Array.Sort(nums);

    int moves = 0;
    int sum = 0;

    for(int i = 1; i < nums.Length; ++i) 
    {
        // Difference beween current and previous.
        int delta = (nums[i] - nums[i - 1]);

        // Add current delta to previous deltas
        sum += delta;

        // Triangular number, accumulate.
        moves += sum;
    }

    return moves;
}

Answer 3

You don't need Math.Abs. You are making 3 passes to get min, max, and maxIX - do it in one pass and stop when min == max.

min = max = num[0];
maxIX = 0;
for (int i = 1; i < nums.Length; i++)
{
    if(nums[i] > max)
    {
        max = nums[i];
        maxIX = i;
    }
    else if (nums[i] < min)
        min = nums[i];
}
if (min != max)
{
     .... 
}

The answer may be calculated without actually processing.