# (Google Foobar XOR Checksum Challenge) How do i optimize this function to run for much larger values?

I wrote a function that accepts 2 integers start and length as input and returns the bitwise XOR of certain numbers as described below:

if start = 0 and length = 4, the process would look like:
0 1 2 3 /
4 5 6 / 7
8 9 / 10 11
12 / 13 14 15 16
which produces the checksum 0^1^2^3^4^5^6^8^9^12 == 10


My code works well enough for lengths below 10000, but just hangs when the length is say 44000. How do I optimize the solution?

def solution(start,length):
if length == 1:
return start
result = start ^ (start+1)
iter = 0
var = start + 1
offset = 1
while iter < (length + length**2)/2 - 2:
if (var-start)%(length-1) == 0:
var += offset
result ^= var
offset += 1
iter += 1
continue
var += 1
result ^= var
iter += 1
return result


You can try the following:

from functools import reduce
from operator import xor

def optimized_solution(start, length):
result = 0
for i in range(length, 0, -1):
result = reduce(xor, range(start, start+i), result)
start += length
return result


For optimized_solution(0, 4):

i -> 4, 3, 2, 1


For first iteration you create a range object from 0 to 0+4, and perform the xor, with result as initial value, provided as the third argument in the reduce function.

result = reduce(xor, range(0, 4), 0) # result_after_iteration_1


And then you increase start by length amount.

In the next iteration, i becomes 3, result becomes:

result = reduce(xor, range(4, 8), result_after_iteration_1) # result_after_iteration_2


And so on....

def optimized_solution(start, length):
result = 0
for i in range(length, 0, -1): # 4, 3, 2, 1
# for 1st iteration:
# xor of range(0, 0+4) => 0 ^ 1 ^ 2 ^ 3
result = reduce(xor, range(start, start+i), result)
# new start = 0 + 4 = 4
start += length
return result


Output:

>>> optimized_solution(0, 4)
10
>>> optimized_solution(1, 1)
1


Performance:

>>> %timeit solution(0, 1000)  # solution func as given in the question
364 ms ± 29.7 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
>>> %timeit optimized_solution(0, 1000)
31.5 ms ± 1.77 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)


If you are not allowed to import operator.xor or functools.reduce, a roughly equivalent version to the above solution would be:

def optimized_solution(start, length):
result = 0
for i in range(length, 0, -1):
for j in range(start, start+i):
result ^= j
start += length
return result


Performance of the above solution:

>>> %timeit optimized_solution(0, 1000)
41.7 ms ± 5.63 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

• @KellyBundy added performance for the last solution. And about linear time, still trying to figure out a formula for xor of n to n+m Dec 17 '21 at 15:34
• @SayandipDutta You're on the right path, xor of n to n+m can be done in constant time. Dec 17 '21 at 19:31