3
\$\begingroup\$

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
\$\endgroup\$
1
2
\$\begingroup\$

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)
\$\endgroup\$
2
  • 1
    \$\begingroup\$ @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 \$\endgroup\$ Dec 17 '21 at 15:34
  • \$\begingroup\$ @SayandipDutta You're on the right path, xor of n to n+m can be done in constant time. \$\endgroup\$ Dec 17 '21 at 19:31

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.