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.

36 lines
898B

  1. """
  2. This would have been fairly easy without the time limit but of course we must do
  3. some XOR regression bs to get it working.
  4. This was actually fairly simple maths once you think about it! XOR is a rotary
  5. operator when dealing with lists of following integer, ie:
  6. >>> 1
  7. 1
  8. >>> 1^2
  9. 3
  10. >>> 1^2^3
  11. 0
  12. >>> 1^2^3^4
  13. 4
  14. >>> 1^2^3^4^5
  15. 1
  16. [...]
  17. And thus we can deduce a pattern, noted below as the xor_rotation.
  18. Thanks to that and XOR properties we can reduce the complexity of the original
  19. dumb "XOR EVERYTHING" down to an O(1) for each array, so we end up roughly
  20. having an O(length) complexity
  21. """
  22. def xor(a, b):
  23. if(a%2==0):
  24. xor_rotation = [b, 1, b+1, 0]
  25. else:
  26. xor_rotation= [a, a^b, a-1, (a-1)^b]
  27. return xor_rotation[(b-a)%4]
  28. def answer(start, length):
  29. res=0
  30. for i in range(0, length):
  31. res ^= xor(start+(length*i), start+(length*i)+(length-i)-1)
  32. return res