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 .

1 Like

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