6
\$\begingroup\$

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;
    }
\$\endgroup\$
  • \$\begingroup\$ What is the processing time limit? \$\endgroup\$ – Gerard Nov 29 '16 at 13:34
  • \$\begingroup\$ 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. \$\endgroup\$ – Innat3 Nov 29 '16 at 13:46
  • \$\begingroup\$ 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? \$\endgroup\$ – Eric Lippert Nov 29 '16 at 18:52
  • \$\begingroup\$ 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] \$\endgroup\$ – Andrew Savinykh Nov 29 '16 at 18:52
  • \$\begingroup\$ @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. :) \$\endgroup\$ – Eric Lippert Nov 29 '16 at 18:54
18
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Michael McGriff Nov 29 '16 at 21:30
  • \$\begingroup\$ @MichaelMcGriff: Thanks, I appreciate the kind words. \$\endgroup\$ – Eric Lippert Nov 29 '16 at 21:38
  • \$\begingroup\$ Very nice. Does this solution/technique have a generic name? \$\endgroup\$ – Gerard Nov 29 '16 at 22:47
  • \$\begingroup\$ @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 \$\endgroup\$ – Eric Lippert Nov 29 '16 at 23:16
  • 1
    \$\begingroup\$ 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 :) \$\endgroup\$ – RobH Nov 30 '16 at 8:45
3
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Output shows 2, which seems correct. Here is the fiddle for testing: jsfiddle.net/g60t3LL0 (see browser developer console for output) \$\endgroup\$ – Gerard Nov 29 '16 at 16:32
  • 1
    \$\begingroup\$ This solution appears to be correct and is accepted by leetcode. Would be interested in seeing the proof ;) \$\endgroup\$ – RobH Nov 29 '16 at 16:33
  • \$\begingroup\$ Couldn't you just skip sum and do lastSum =+ delta. And I think you need to remover duplicate from input. \$\endgroup\$ – paparazzo Nov 29 '16 at 16:41
  • \$\begingroup\$ 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. \$\endgroup\$ – Gerard Nov 29 '16 at 16:46
  • 1
    \$\begingroup\$ 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)! \$\endgroup\$ – Eric Lippert Nov 29 '16 at 21:37
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You can further optimize this by setting min = max = num[0] and maxIX = 0 and then starting the loop with int i = 1. \$\endgroup\$ – Gerard Nov 29 '16 at 15:43
  • \$\begingroup\$ 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. \$\endgroup\$ – Dmitry Nov 29 '16 at 16:16
  • \$\begingroup\$ @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 \$\endgroup\$ – Innat3 Nov 29 '16 at 16:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.