Python XOR Fast Algorithm

Question

There is a programming task that requires the creation of an XOR checksum based on the sequence start number and interval length.

This requires you to repeat the sequence based on the length of the interval, and at each iteration continue to reduce the number of elements selected to calculate the checksum.

Example:

---

if the starting number is 0 , and the length of the interval is 3 , the process will look like this:

0 1 2 /

3 4/5

6/7 8

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

Similarly, if the beginning is 17 and the length of the interval is 4 , the process will look like this:

17 18 19 20 /

21 22 23/24

25 26/27 28

29/30 31 32

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

My approach to solving

---

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 work fast enough.

They are great for trivial calculations, for example, in examples, but take much longer when the interval is long, for example 1000

Questions

• What computer science concepts are being tested with this problem?
• What is the correct algorithmic approach?
• What are the correct data structures?

I need to understand why my solution does not work well and which algorithms and data structures correspond to this problem.

Answer 1

I suggest a simple optimization of your solution.

Use this method to get the xor of the 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 calculate the 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

Denote by f (n) = 1⊕2⊕3⊕ ⋯ ⊕n, where ⊕ denotes the operation XOR. XOR of all numbers between A and B can be represented as f (B) ⊕f (A - 1), because x⊕x = 0

Now we can easily find out,

Time Difficulty - O (1)

link

Link two