Python fast XOR over range algorithm

Question

There is a programming challenge that requires one to generate an XOR checksum based on sequence start number and an interval length.

It requires you to iterate the sequence based on the interval length and at each iteration keep reducing the number of elements picked for the checksum calculation.

Example:

---

if the start number is 0 and the interval length is 3, the process would look like this:

0 1 2/

3 4 / 5

6 / 7 8

where the XOR (^) checksum is 0^1^2^3^4^6 == 2

Likewise, if the start is 17 and the interval length 4, the process would look like:

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

My solutions approach

---

Using Recursion

import operator
import sys

sys.setrecursionlimit(20000)

def answer(start, length):
    lst = [range(start+length*n, start+length*n+length) for n in xrange(length)]
    return my_reduce(lst, length)

def my_reduce(lst, length):
    if not lst: return 0
    l = lst.pop(0)
    return reduce(operator.xor, l[:length], 0) ^ my_reduce(lst, length-1)

Iterative approach using a generator

def answer(start, length):
    return reduce(operator.xor, gen_nums(start, length))


def gen_nums(start, length):
    l = length
    while l > 0:
        for x in xrange(start, start+l):
            yield x
        start = start + length
        l = l - 1

Problem

---

My two approaches do not run fast enough.

They do fine for trivial calculations e.g the ones in the examples but take significantly more time when the interval length is large e.g 1000

Questions

• What computer science concepts are being tested by this challenge?
• What is the right algorithmic approach?
• what are the right data structures to use?

I need to understand why my solution performs poorly and what algorithm and data structures fit this challenge.

Answer 1

I am suggesting a simple optimization over your solution.

Use this method to get the xor of a range[a,b]

def f(a):
     res = [a, 1, a+1, 0]
     return res[a%4]

def getXor(a, b):
     return f(b) ^ f(a-1)

Now for a given interval you can compute XOR checksum in O(n) instead of O(n^2).

def gen_nums(start, length):
    l = length
    ans = 0
    while l > 0:
        ans^= getXor(start,start+l-1)
        start = start + length
        l = l - 1
    return ans

Explanation

Let us denote f(n)=1⊕2⊕3⊕⋯⊕n, where ⊕ denotes XOR operation. The XOR of all numbers between A and B can be represented by f(B)⊕f(A−1), because x⊕x=0

Now we can find out easily that,

Time Complexity - O(1)

reference

reference two