My solutions for google foobar
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

35 lines
898 B

This would have been fairly easy without the time limit but of course we must do
some XOR regression bs to get it working.
This was actually fairly simple maths once you think about it! XOR is a rotary
operator when dealing with lists of following integer, ie:
>>> 1
>>> 1^2
>>> 1^2^3
>>> 1^2^3^4
>>> 1^2^3^4^5
And thus we can deduce a pattern, noted below as the xor_rotation.
Thanks to that and XOR properties we can reduce the complexity of the original
dumb "XOR EVERYTHING" down to an O(1) for each array, so we end up roughly
having an O(length) complexity
def xor(a, b):
xor_rotation = [b, 1, b+1, 0]
xor_rotation= [a, a^b, a-1, (a-1)^b]
return xor_rotation[(b-a)%4]
def answer(start, length):
for i in range(0, length):
res ^= xor(start+(length*i), start+(length*i)+(length-i)-1)
return res