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.
The problems first requirement is you construct the array physically or logically. The array is not provided.
we can contruct the array functionally to calculate the outputs. We can also check some outputs to find any pattern to avoid brute force approach.
Let's look at first few digits to see if we can find any pattern!!
First column is index, second column is Array element A(i) which is xor of numbers 0 to n. And third column is xor of arrray elements A[0] to A[n]. We need to find xor of array elements in between l and r = A[l] ^ A[l+1] ^ .... ^ A[r-] ^ A[r]
Xor-sequence
You are viewing a single comment's thread. Return to all comments →
The problems first requirement is you construct the array physically or logically. The array is not provided.
we can contruct the array functionally to calculate the outputs. We can also check some outputs to find any pattern to avoid brute force approach.
Let's look at first few digits to see if we can find any pattern!! First column is index, second column is Array element A(i) which is xor of numbers
0 to n
. And third column is xor of arrray elementsA[0] to A[n]
. We need to find xor of array elements in between l and r =A[l] ^ A[l+1] ^ .... ^ A[r-] ^ A[r]
If we take a look at the above chart, we notice that for 0,8,16,24 ==> we get same. so, it revolves around 8. So, we will take reminder of 8.
finally, to find our output we do generate
left = (A[0] to A[l-1])
and right =(A[0] to A[r])
if we do xor of
left and right
, firstl-1
items gets cancelled out due to being present in both.(1^2^3) ^ (1^2^3^4^5) = (4^5)
credit goes to vineeth boopathy for the approach.