Calculate XOR of many consecutive and non-consecutive numbers question:

answer(start,length)


#start is the starting number of the matrix
 #length is number of rows.

example 1:

answer(0,3)

0 1 2 /
3 4 / 5
6 / 7 8


where the answer is 2 (by using  XOR (^) checksum is 0^1^2^3^4^6 == 2.)
example 2:

answer(17,4)

17 18 19 20 / 
21 22 23 / 24 
25 26 / 27 28 
29 / 30 31 32


which produces the checksum 17^18^19^20^21^22^23^25^26^29 == 14.

All numbers are between 0 and 2000000000 inclusive, and the length of checkpoint line will always be at least 1.

input

(int) start = 0  
(int) length = 3  


Output:

(int) 2  


Inputs:

(int) start = 17  
(int) length = 4  


Output:

(int) 14      


my code:

def answer(start,length):
    num = start
    temp_len = length
    j = 0
    result = 0
    while num &lt; (num+(length*length)) and temp_len &gt; 0:
        #if required condition is not satisfied (when it reaches '/' in every row)  
        if j == temp_len:   
            j = 0
            num += length - temp_len
            temp_len -= 1
        #if required condition is satisfied
        else:
            j += 1
            #calculating XOR 
            result ^= num
            num += 1
     return result
The problem with the code is that you are processing \$\sum _{ k=1 }^{ n }{ k } \$ (or \$1+2+3+(...)+n=\frac { n(n+1) }{ 2 }\$ ) integers. At most, you'll be processing 2 billion integers. A brute force method, such as the one you presented in your code, is inefficient and slow.

What you could do is take a different approach. Instead of XORing each integer, you could exploit a pattern that is present when XORing numbers. You exploit the pattern in each row, and then just XOR all the XOR sums you get from each processed row to get the checksum you need.



The XOR Pattern

Let us start by XORing numbers 0 to 3.

Obviously, XORing zero on its own gives us zero. Now, let's XOR 0 and 1 (0 ^ 1). We would get 1. XORing 0, 1, and 2 would give us 3. Lastly, XORing 0 to 3 would give us 0. Here's a visualization to make things simpler. Take note of the Output table.

0 =&gt; 0    0000 (0)    0000 (0)    0000 (0)        Output (0 to n)
        ^ 0001 (1)    0001 (1)    0001 (1)        -----------------
        ----------  ^ 0010 (2)    0010 (2)        (0 to 0) 0000 (0) # Equals to n
          0001 (1)  ----------  ^ 0011 (3)        (0 to 1) 0001 (1)
                      0011 (3)  ----------        (0 to 2) 0011 (3) # Equals to n + 1 (2 + 1)
                                  0000 (0)        (0 to 3) 0000 (0)


Let's now try XORing from 4 to 7. XORing 0 to 4 gives us 4. 0 to 5 gives us 1 (noticed anything yet?). 0 to 6 gives us 7. And lastly, 0 to 7 gives us 0.

  0000 (0)    0000 (0)    0000 (0)    0000 (0)    Output (0 to n)
  0001 (1)    0001 (1)    0001 (1)    0001 (1)    ---------------
  0010 (2)    0010 (2)    0010 (2)    0010 (2)    (0 to 4) 0100 (4) # Its' equal to n! (&lt;= not a factorial)
  0011 (3)    0011 (3)    0011 (3)    0011 (3)    (0 to 5) 0001 (1) # Here goes this one again!
^ 0100 (4)    0100 (4)    0100 (4)    0100 (4)    (0 to 6) 0111 (7) # And it's equal to n + 1
----------  ^ 0101 (5)    0101 (5)    0101 (5)    (0 to 7) 0000 (0) # And this zero.
  0100 (4)  ----------  ^ 0110 (6)    0110 (6)
              0001 (1)  ----------  ^ 0111 (7)
                          0111 (7)  ----------
                                      0000 (0)


Have you noticed the pattern? It's right in front of you! We could definitely see that the pattern repeats every 4 numbers. Inferring from our output table, XORing to 0 and every fifth number would give us the fifth number; XORing to 1 and every sixth number would give us 1; XORing to 2 and every seventh number would give us 2 and the every seventh number plus one; and, XORing to 4 and every eigth number would give us 0.

From there, we easily get a pattern of n, 1, n + 1, 0. This also proves 200_success's answer where XORing to every fourth number (we're starting from 0) gives us 0.



Now that we have a pattern, we just need to create a function that will get the XOR sum from 0 to n. For this answer, let's call the function, f(). I'll leave the implementation to you as that is part of the challenge. We start at zero because the pattern starts at zero and could break if we start somewhere else. To get the XOR from a range (a to b), we just do f(b) ^ f(a - 1). Why it works? Read on.



Why Does \$f(b) \oplus f(a - 1)\$ Work?

The simple answer is that \$f(a - 1)\$ cancels out \$0 \oplus (...) \oplus (a - 1)\$ from \$f(b)\$ which is just \$0 \oplus (...) \oplus b\$.

Proof on why \$a \oplus (a + 1) \oplus (...) \oplus (b - 1) \oplus b = f(b) \oplus f(a - 1)\$

First of all, remember that XOR operations are associative, commutative, and reversable.

Let

$$n = a \oplus (a+1) \oplus (...) \oplus (b-1) \oplus (b) = 0$$

where \$a, b \in Z^{+}\$ and \$ a &lt; b \$. \$n\$ is the XOR sum from \$a\$ to \$b\$.

Let us have a function \$f(b)\$ that gets the XOR sum from \$0\$ to \$b\$.

$$f(b) = 0 \oplus 1 \oplus 2 \oplus (...) \oplus b$$

Since \$a\$ is less than \$b\$ and XOR operations is associative, we can safely assume that

$$f(b) = (0 \oplus 1 \oplus (...) \oplus (a-1)) \oplus (a \oplus (a+1) \oplus (...) \oplus b)$$

Since \$(0 \oplus 1 \oplus (...) \oplus (a-1))\$ is equal to \$f(a-1)\$, and \$(a \oplus (a+1) \oplus (...) \oplus b)\$ is equal to \$n\$, we can simplify the equation above to

$$f(b) = f(a-1) \oplus n$$

Finally, since XOR operations are reversable, we get

$$n = f(a-1) \oplus f(b)$$

Through the commutative property of XOR operations, we finally get

$$n = f(b) \oplus f(a-1)$$



After getting the XOR sum of each row using f(b) ^ f(a - 1), we XOR all the XOR sums from each row, and we get the checksum that the problem requires.

Using the method I mentioned above, I can process answer(0, 50000) in approximately 0.08 seconds on my laptop with a Core i3 processor, and 4GB RAM.

Side note: These questions (1 and 2) can help you as well. I used the answers in those questions as a source for this answer, and in solving the same problem a few days ago (relative to writing this answer).