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.
Xor-sequence
Xor-sequence
Sort by
recency
|
147 Discussions
|
Please Login in order to post a comment
where is an array to search or to perform a function
like zaber04 said, we need to set up an array starting from 0 to a certain number to see the pattern. The following is the code I use to set up the array and observe the pattern:
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.
Let me know if you have any questions
pretty easily question, no loops or recursion required, O(1) time