current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 5 down vote favorite
1

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;
    }
share|improve this question
    
What is the processing time limit? – Gerard 10 hours ago
    
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. – Innat3 9 hours ago
    
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? – Eric Lippert 4 hours ago
    
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] – Andrew Savinykh 4 hours ago
    
@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. :) – Eric Lippert 4 hours ago
up vote 3 down vote accepted

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;
}
share|improve this answer
    
Output shows 2, which seems correct. Here is the fiddle for testing: jsfiddle.net/g60t3LL0 (see browser developer console for output) – Gerard 7 hours ago
1  
This solution appears to be correct and is accepted by leetcode. Would be interested in seeing the proof ;) – RobH 7 hours ago
    
Couldn't you just skip sum and do lastSum =+ delta. And I think you need to remover duplicate from input. – Paparazzi 6 hours ago
    
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. – Gerard 6 hours ago
    
I like your solution, it's very clean, I focused my code on the part of incrementing all but the maximum value element, I wasn't aware the same output could be achieved by summing the delta between pairs of array's elements – Innat3 6 hours ago
up vote 12 down vote

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();
share|improve this answer
1  
This should definitely be the accepted answer! The solution is also O(n). – mbomb007 2 hours ago
    
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. – Michael McGriff 2 hours ago
    
@MichaelMcGriff: Thanks, I appreciate the kind words. – Eric Lippert 2 hours ago
    
Very nice. Does this solution/technique have a generic name? – Gerard 51 mins ago
    
@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 – Eric Lippert 22 mins ago
up vote 2 down vote

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.

share|improve this answer
    
You can further optimize this by setting min = max = num[0] and maxIX = 0 and then starting the loop with int i = 1. – Gerard 7 hours ago
    
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. – Dmitry 7 hours ago
    
@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 – Innat3 7 hours ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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