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;
 }

• Gerard: What is the processing time limit?
• Innat3: I'm not entirely sure, the site performs several checks, not just the one I posted, with much larger arrays. The time limit seems to be 1-2 seconds at most. I feel like the only way to achieve this is without iterating through the array more than once, but I can't come up with a way.
• Eric Lippert: The problem is the same as "... where a move is decrementing a single element by one". Do you see why? Is it easier to see the answer when you re-cast the problem in this way?
• Andrew Savinykh: To me it looks like incrementing n-1 element equals decrementing 1 element. That is [1,2,3] => [2,3,3] is equivalent to [1,2,3] => [2,3,2], and the whole sequence then looks like this: [1,2,3] => [1,2,2] => [1,2,1] => [1,1,1]
• Eric Lippert: @AndrewSavinykh: I think you meant to say "incrementing n-1 elements equals decrementing one element" -- but yes, we are having the same thought at the same time here. :)

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

• Michael McGriff: Always thought you should be a teacher, between the MSDN articles, blog and answers across the StackExchange, I think you'd be very good at it. You always have a way of getting readers to come to the solution on their own, instead of just spelling it out at the beginning.
• Eric Lippert: @MichaelMcGriff: Thanks, I appreciate the kind words.
• Gerard: Very nice. Does this solution/technique have a generic name?
• Eric Lippert: @Gerard: I'm not aware of a name for this specific solution. The general technique of writing methods that read like items.Select(...).Where(...).Unique().Sum() -- that is, where operations in a workflow are easily-understood English words and each element in the workflow reads clearly left-to-right is called "fluent programming". en.wikipedia.org/wiki/Fluent_interface
• RobH: I eventually got to this point but it took me ages and I was getting increasingly frustrated with the "easy" label on leetcode. One thing to note is that leetcode use test cases like new[] {1, 1, int.MaxValue } which would cause an overflow in the one liner. Also second @MichaelMcGriff's comment :)

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;
}

• Gerard: Output shows 2, which seems correct. Here is the fiddle for testing: jsfiddle.net/g60t3LL0 (see browser developer console for output)
• RobH: This solution appears to be correct and is accepted by leetcode. Would be interested in seeing the proof ;)
• paparazzo: Couldn't you just skip sum and do lastSum =+ delta. And I think you need to remover duplicate from input.
• Gerard: Not sure what you entirely mean, but lastSum is cached because I don't want to accumulate the sum of sums (recursively), so to speak. An other answer to this question already made that mistake.
• Eric Lippert: Let's examine your answer a little closer. Let's suppose that we have 4 elements x0, x1, x2, x3, and we number each mutation of variables s and m. We have s1 = x1 - x0, m1 = s1, which is x1 - x0. Then s2 = x2 - x1 + s1, which is x2 - x1 + x1 - x0, which is x2 - x0. Then m2 = m1 + s1, which is x1 - x0 + x2 - x0. And so on; we see that m3 = x1 - x0 + x2 - x0 + x3 - x0. You are doing an awful lot of adding and subtracting in order to compute (x1 + x2 + x3) - 3 (x0)!

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.

• Gerard: You can further optimize this by setting min = max = num[0] and maxIX = 0 and then starting the loop with int i = 1.
• Dmitry: You missed else before the second if. Should be: else if (nums[i] < min). It's because both min and max are initialized with the same value, so both conditions can't be true.
• Innat3: @Paparazzi, you are absolutely right, I keep using these methods separately out of habit because I find them visually attractive, but doing all three in one go is the right way to go