3
\$\begingroup\$

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 < (num+(length*length)) and temp_len > 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
\$\endgroup\$
  • \$\begingroup\$ Let me guess, Google FooBar? \$\endgroup\$ – Matt Alexander Sep 24 '18 at 22:07
4
\$\begingroup\$

XOR can be thought of as a bit-cancellation operation. You can see that for any \$k\$,

$$(4k+0) \oplus (4k+1) \oplus (4k+2) \oplus (4k+3) = 0$$

… because the four occurrences of \$4k\$ cancel out, and the \$0 \oplus 1 \oplus 2 \oplus 3\$ also cancels out.

So, the XOR of any consecutive sequence can be reduced to the XOR of no more than 6 numbers. Take, for example, the XOR of the sequence from 3 to 34:

$$3 \oplus 4 \oplus 5 \oplus 6 \oplus \ldots \oplus 33 \oplus 34 \\ = 3 \oplus (4 \oplus 5 \oplus 6 \oplus 7) \oplus \ldots \oplus (28 \oplus 29 \oplus 30 \oplus 31) \oplus 32 \oplus 33 \oplus 34 \\ = 3 \oplus 32 \oplus 33 \oplus 34 \\ = 32$$

\$\endgroup\$
  • 1
    \$\begingroup\$ I may have been the first to post an answer, but @Sean explained it better. Consider accepting that answer instead. \$\endgroup\$ – 200_success Jan 22 '17 at 20:36
  • \$\begingroup\$ But do consider upvoting this answer too. This complements my answer especially on the "The XOR Pattern" section. \$\endgroup\$ – Sean Francis N. Ballais Jan 23 '17 at 3:00
  • \$\begingroup\$ what about XOR of XORS ? will this rule apply? \$\endgroup\$ – midori Mar 17 '17 at 23:41
  • \$\begingroup\$ @tinySandy Yes, it still applies. It doesn't matter what order or grouping you choose to do the XORs in. \$\endgroup\$ – 200_success Mar 18 '17 at 0:19
  • \$\begingroup\$ @200_success but in question you have to make non consecutive chunks by slicing that last part every line, so the approach only works for chunks but how to XOR it together? I can't come up with any fast solution \$\endgroup\$ – midori Mar 18 '17 at 0:21
5
\$\begingroup\$

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 => 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! (<= 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 < 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).

\$\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.