How to solve this problem http://www.codechef.com/CDCRFT14/problems/SUBBXOR
I solved this problem with O(n^2) but got TLE . Please explain the efficient algorithm used in this problem .
2 Likes
you can use trie to solve this problem
Trie? How?
i can’t submit my code, but my solution passed the sample test case and it complexity is O(NlogN), that is, we can get an array which sum[i] = a[1] xor a[2] xor … a[i]
then, the problem transform to find how many pairs that sum[i] xor sum[j] < k
to each i, we count the ways and push sum[i] into Trie