We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Even we know how to calculate the Ai value with the pattern of %4, it is still no enough to solved this problem within time limit. However, there is also a pattern for Ai⊕Ai+1⊕Ai+2⊕....⊕Ai+k. The idea is that Ai,Ai+1,Ai+2,Ai+3 can be considered as a set, where i%4 == 0. Thus, Ai⊕Ai+1⊕Ai+2⊕Ai+3 = i⊕1⊕i+2⊕0 = 2. Therefore, Ai⊕Ai+1⊕Ai+2⊕....⊕Ai+k = Al-2⊕Al-1⊕Al⊕2⊕2⊕...⊕2⊕Ar⊕Ar+1, where l is the smallest number and r is the larget number can be divided by 4 within the range of [L,R]. As a result, the key is to find the XOR at the front and end sequnce and count how many 2's in between.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Xor-sequence
You are viewing a single comment's thread. Return to all comments →
Even we know how to calculate the Ai value with the pattern of %4, it is still no enough to solved this problem within time limit. However, there is also a pattern for Ai⊕Ai+1⊕Ai+2⊕....⊕Ai+k. The idea is that Ai,Ai+1,Ai+2,Ai+3 can be considered as a set, where i%4 == 0. Thus, Ai⊕Ai+1⊕Ai+2⊕Ai+3 = i⊕1⊕i+2⊕0 = 2. Therefore, Ai⊕Ai+1⊕Ai+2⊕....⊕Ai+k = Al-2⊕Al-1⊕Al⊕2⊕2⊕...⊕2⊕Ar⊕Ar+1, where l is the smallest number and r is the larget number can be divided by 4 within the range of [L,R]. As a result, the key is to find the XOR at the front and end sequnce and count how many 2's in between.