Method for efficiently calculating the XOR checksum (^) based on a list of identifiers

Question

When you submitted the Python list view submission information, I was offered a google foobar call, which I have been working slowly over the past few days for fun. Last problem:

effectively causes the creation of a list of identifiers, ignoring the increasing number from each new line until there is only one ID. Then you need XOR (^) identifiers to create a checksum. I created a working program that displays the correct answer, however it is not efficient enough to transmit all test cases (6/10 pass) in the allotted time. A length of 50,000 should produce results in less than 20 seconds, but 320 is required.

Can someone direct me in the right direction, but please do not do this for me , I am pleased to push myself to this problem. Perhaps there is a data structure or algorithm that I can implement to speed up the computation time?

Code Logic:

• First, the starting identifier and length are taken in

• A list of identifiers is created, ignoring an increasing number of identifiers from each new line, starting with ignoring 0 from the first line.

• XOR - all numbers in the IDS list using a for loop

• The answer is returned as int

---

import timeit
def answer(start,length):
    x = start
    lengthmodified = length
    answerlist = []
    for i in range (0,lengthmodified): #Outter for loop runs an amount of times equal to the variable "length".
        prestringresult = 0
        templist = []
        for y in range (x,x + length): #Fills list with ids for new line
            templist.append(y)
        for d in range (0,lengthmodified): #Ignores an id from each line, increasing by one with each line, and starting with 0 for the first
            answerlist.append(templist[d])
        lengthmodified -= 1
        x += length    
        for n in answerlist: #XORs all of the numbers in the list via a loop and saves to prestringresult
            prestringresult ^= n
        stringresult = str(prestringresult) 
        answerlist = [] #Emptys list
        answerlist.append(int(stringresult)) #Adds the result of XORing all of the numbers in the list to the answer list
    #print(answerlist[0]) #Print statement allows value that being returned to be checked, just uncomment it
    return (answerlist[0]) #Returns Answer



#start = timeit.default_timer()
answer(17,4)
#stop = timeit.default_timer()
#print (stop - start) 

Answer 1

, , , . , answer(0, 50000) 2 . , , , . 1- ? ^[*] ? 1- . 2-, 4-, 8- .. 2 ³⁰ -bit. , 31 ( , ).

[*] / .

:. , , 1 (a, b). , (0, a) , (0, b). , . 1- (0, c)? : c//2 . , 1- (a, b)? b//2 - a//2 . , .

2: , , ... xor (a, b). (0, a) (0, b). Xor (0, c) , ( , c 0, 30). , answer(0, 50000) 0,04 .

Answer 2

templist answerlist . , , .

• templist . :

  templist = []
  for y in range (x,x + length):
      templist.append(y)
  

  :

  templist = list(range(x, x + length))
  

• answerlist. :

  for d in range (0,lengthmodified):
      answerlist.append(templist[d])
  

  :

  answerlist.extend(templist[:lengthmodified])
  

• , . lengthmodified -= 1 x += length, :

  templist = list(range(x, x + length))
  answerlist.extend(templist[:lengthmodified])
  
  for n in answerlist:
      prestringresult ^= n
  
  answerlist = []
  

  answerlist, , , templist.

  templist = list(range(x, x + length))
  
  for n in templist[:lengthmodified]:
      prestringresult ^= n
  

  templist, .

  for n in range(x, x + lengthmodified):
      prestringresult ^= n
  

  templist answerlist .

answerlist.append(int(stringresult)) . , .

, , for, . for, , - . Python . .

, Python .

Answer 3

, , - . . , , .

Answer 4

. ! : " XOR , ". , !

, 3-6 3 ^ 4 ^ 5 ^ 6 = 4 O (1) .

: XOR . , A ^ B ^ C B ^ A ^ C. , , XOR : ", True i.e 1, 2.

: XOR 3-6 :

3^4^5^6 = (0^1^2)^(0^1^2) ^ (3^4^5^6)
        = (0^1^2^3^4^5^6) ^ (0^1^2) (this comes from the associative nature of xor)
        = XOR betn all the numbers from (0-6) ^ XOR betn all the numbers from (0-2)...eq(1)

, XOR 0 , .

, :

. :

(0-1): 0 ^ 1 = 1 (1)
(0-2): 0 ^ 1 ^ 2 = 3 (2+1)
(0-3): 0 ^ 1 ^ 2 ^ 3 = 0 (0)
(0-4): 0 ^ 1 ^ 2 ^ 3 ^ 4 = 4 (4)

(0-5): 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 = 1 (1)
(0-6): 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 = 7 (6+1)
(0-7): 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^  7 = 0 (0)
(0-8): 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 = 8 (8)


So the pattern for finding the xor between all the integers between 0 to n is:
if n%4 == 1 then, answer = 1
if n%4 == 2 then, answer = n+1
if n%4 == 3 then, answer = 0
if n%4 == 0 then answer = n 

Therefore, XOR(0-6) becomes 7 (since 6%4 ==2) and XOR(0-2) becomes 3 (since 2%4 ==2)

Therefore, the eq(1) now becomes:
3^4^5^6 = 7 ^ 3 = 4

, - , xor , , / . python, google:

#Main Program
def answer(start, length):
    checkSum = 0
    for l in range(length, 0, -1):
        checkSum = checkSum ^ (getXor(start + l-1) ^ getXor(start-1))
        start = start + length
    return checkSum

def getXor(x):
    result = [x, 1, x+1, 0]
    return result[x % 4]