1
\$\begingroup\$

As part of a Google Foobar challenge, I'm trying to answer a rather difficult problem that involves the use of the XOR operator to calculate a checksum. While my solution works, my algorithm works in O(n) time, while the desired solution seems to need to be faster.

You can see the text of the challenge here.

While I know the help presented in that thread is valid, the solution is in Python, and I'm working in Java. Could someone explain why my solution is inefficient, and how it could be improved? I'm a self-taught coder, so some of the arcana of compsci is a mystery to me.

static int answer(int start, int length) {
    int checksum = 0;
    int dividerPos = length;
    int count = start;
    int idx = 0;

    while(true) {
        if(dividerPos == 0)
            return checksum;
        else if (idx == dividerPos) {
            count += (length - dividerPos);
            --dividerPos;
            idx = 0;

            continue;
        }

        checksum ^= count;

        ++idx;
        ++count;
    }
}
\$\endgroup\$
1
\$\begingroup\$
  • There are situations where an infinite loop while (true) is warranted, this is not one of them. The code implies that the loop shall be broken when dividerPost reaches zero. Say it explicitly:

            while (dividerPos > 0) {
                if (idx == dividerPos) {
                    count += (length - dividerPos);
                    --dividerPos;
                    idx = 0;
                    continue;
                }
    
                checksum ^= count;
    
                ++idx;
                ++count;
            }
            return checksum;
    
  • Now it is easy to see that the body of the loop is another loop in disguise. Again, be explicit:

            while (dividerPos > 0) {
                for (idx = 0; idx < dividerPos; idx++, count++) {
                    checksum ^= count;
                }   
                count += (length - dividerPos);
                --dividerPos;
            }   
    
  • Now it is clear what the code is doing, and what it is doing inefficiently. An immediately identified bottleneck is an inner loop. What it does, it compute an xor of a range of numbers The first hit for a xor of a range query is this discussion. Study it, and see how it is applicable here. That itself will give your code a boost. Then try to optimize the outer loop.

PS: It is crucial to understand that the language doesn't matter.

PPS: Sorry if I sound harsh, but when I say study, I mean study. Don't skim. Understand how it works. Prove that it works correctly.

PPPS: Both answers in the page you've linked miss the point.

\$\endgroup\$

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.