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.
My O(1) solution:
From the index range [L, R], ignore all consecutive groups of 8 indices starting at the first multiple of 4. Then simply XOR the array values for the remaining indices. This is because each such group of 8 values will XOR to 0. The array value for an index i can be found using the following:
i%4 == 0, then a[i] = i
i%4 == 1, then a[i] = 1
i%4 == 2, then a[i] = i+1
i%4 == 3, then a[i] = 0
Example: The first few array values go like this
0 1 3 0 4 1 7 0 8 1 11 0 12 1 15 0 16 1 19 0 20 1 23 0
For the above range, L = 5, R = 18, we skip the values in italics and just XOR the remaining i.e. 1, 7, 0, 16, 1, 19
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 →
My O(1) solution: From the index range [L, R], ignore all consecutive groups of 8 indices starting at the first multiple of 4. Then simply XOR the array values for the remaining indices. This is because each such group of 8 values will XOR to 0. The array value for an index i can be found using the following:
i%4 == 0, then a[i] = i
i%4 == 1, then a[i] = 1
i%4 == 2, then a[i] = i+1
i%4 == 3, then a[i] = 0
Example: The first few array values go like this
0 1 3 0 4 1 7 0 8 1 11 0 12 1 15 0 16 1 19 0 20 1 23 0
For the above range, L = 5, R = 18, we skip the values in italics and just XOR the remaining i.e. 1, 7, 0, 16, 1, 19