PROBLEM LINK:
DIFFICULTY:
MEDIUM
PREREQUISITE:
[Trie][11]
[11]: http://threads-iiith.quora.com/Tutorial-on-Trie-and-example-problems
PROBLEM:
Given an array of positive integers and a number K, find the number of subarrays whose XOR is less than K. XOR of subarray is defined as XOR of all elements in it. Each element is less than 10^6. Number of elements less than 10^5.
EXPLANATION:
Normal O(N^2) solution would time out.
Let f(L,R) = XOR of subarray a[L…R], then f(L,R) = f(1,R) XOR f(1,L-1).
For each index i=1 to N, we can count how many subarrays ending at ith position satisfy the given condition.
Now, suppose, that we have a data structure that allows us to perform this two operations: insert some integer into this structure and for given two integers X and K finds the number of elements already in structure whose XOR with X is less than K.
Then we can solve the task like this:
Answer = 0;
XorOnPrefix = 0;
Structure.insert(0);
for i = 1 to n
XorOnPrefix = XorOnPrefix xor a_i;
Structure.insert(XorOnPrefix);
Answer + = Structure.query(XorOnPrefix,k);
return Answer;
Now, about the data structure. It can be implemented as trie (prefix tree), if we consider integers as binary strings of length logA = 20. Then insertion can be done in O(logA) time. But we also need to keep at each node the number of leaves we will encounter if we go to left side from that node and similarly for right.
How do we do query(x,k)?
Structure.query(root,x,k,level)
{
if level==-1 or root==NULL: return 0
q=level'th bit of k
p=level'th bit of x
if q>0:
if p==0: // means that all leaves on left of this node will always satisfy
// + queries on right side
return root.count_left + Structure.query(root.right,x,k,level-1);
else: // all leave on right of this node will always satisfy
// + queries on left of this node
return root.count_right + Structure.query(root.left,x,k,level-1);
else:
if p==0: return Structure.query(root.left,x,k,level-1);
else: return Structure.query(root.right,x,k,level-1);
}
