Xor-sequence
Xor-sequence
+ 16 comments here is my O(1) solution
#include <bits/stdc++.h> using namespace std; long long G(long long x){ long long a = x % 8; if(a == 0 || a == 1) return x; if(a == 2 || a == 3) return 2; if(a == 4 || a == 5) return x+2; if(a == 6 || a == 7) return 0; return 0; } int main(){ int q; cin >> q; while(q--){ long long l, r, ans; cin >> l >> r; ans = G(r)^G(l-1); cout << ans << endl; } return 0; }
+ 1 comment Sometimes i feel reference solutions are more confusing and its better to design your own solution once you understand what's going on.
+ 4 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] = 0Example: 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 0For 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
+ 0 comments This has been one of my favorite questions on this site. It's all about the properties of XOR and finding patterns. Feels great after solving it.
+ 3 comments Have been strugling with this question for a while, and suddenly it hit me how simple it is. Try to extend given list of array and find pattern in it, that's all it requires.
Sort 133 Discussions, By:
Please Login in order to post a comment