Where is the faulty logic in my solution to this problem?

[SlurrerOfSpeech]

I was working on https://www.hackerrank.com/contests/101hack50/challenges/even-and-odd-boxes for 2.5 hours and couldn't get it right. The programming competition is over, so now it's ok to discuss. I can't figure out where I was going wrong.

    static void OnesToFront(List<int> list)
    {
        for(int i = 0, j = list.Count - 1; i < j; )
        {
            if(list[i] == 1)
                ++i;
            else if(list[j] != 1)
                --j;
            else
            {
                int temp = list[i];
                list[i] = list[j];
                list[j] = temp;
            }
        }
    }
  
    static bool IsEven(int i) { return i % 2 == 0; }
  
    static int MinimumChocolateMoves(int n, int[] X) {
        var shouldBeEven = X.Where((x, i) => IsEven(i) && !IsEven(x)).ToList();
        var shouldBeOdd = X.Where((x, i) => !IsEven(i) && IsEven(x)).ToList();
        if(shouldBeEven.Count == shouldBeOdd.Count)
            return shouldBeEven.Count;
        OnesToFront(shouldBeEven);      
        var q1 = new Queue<int>(shouldBeEven);
        var q2 = new Queue<int>(shouldBeOdd);
        while(q1.Count > 0 && q2.Count > 0)
        {
            q1.Dequeue();
            q2.Dequeue();
        }
        int remaining = q1.Count + q2.Count;
        if(!IsEven(remaining))
            return -1;  
        if(q1.Count > 0)
        {
            int ones = q1.Count(i => i == 1);
            if(ones > q1.Count / 2)
                return -1;
        }      
        return remaining / 2;
    }

 

[jedishrfu]

With any kind of programming problem, its good to put print statements between key steps to verify that things were computed correctly.

If you have a debugger that's even better for stepping through your code.

In your case, you might want to print out snapshots of your queue to see what got added and where things got tripped up. Basically use the computer to help you debug its problem since programmers don't make mistakes right?

Its much harder for another programmer unfamiliar with your code or the problem its supposed to solve to debug it. However, by talking through your solution and verifying that the computer did it as expected you might discover it for yourself.

 

[SlurrerOfSpeech]

(I meant to post this in the Programming room)

<< moved... --mentor >>

Ok, let me explain my logic.

Let U be the set of all odds that should be even, and let V be the set of all evens that should be odd.

Fact: for any u in U and v in V, we can make u even and v odd by subtracting from one and adding to the other.

Using the above fact, if |U| = |V| we can perform exactly |U| such operations to get the desired pattern.

If |U| != |V|, we can perform exactly m = Min(|U|, |V|) operations and then we will have a surplus of s = Max(|U|, |V|) - m numbers from one of the sets. If s is odd, then we can not possibly turn those surplus items to the other side. If s is even, then we can.* For example, if we have a pair of evens, like (4,18), we can turn that odd by (4+1,18-1)=(5,17), and we can do that for every pair of evens. Or, if we have a pair of odds, like (7, 19), we can turn that even by (7-1,19+1)=(6,20), and we can do that for every pair of odds.

*Edge case: We can't turn pairs (1,1) into evens.

 

[SlowThinker]

Ok, let me explain my logic.

Did you figure it out or don't care? Anyway,
1. Write comments that explain the logic, for yourself and especially if posting it for review
2. It seems you forgot to count the chocolates moved in the Dequeue loop.
3. How do you know your program does not work? Do you have a working program to compare against? Is your program giving less or more than the correct answer, or both?