×

Contest

MEDIUM

Trie

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);


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);
}


SIMILAR PROBLEM:

XORSUM ACM AMRITA'09

This question is marked "community wiki".

3.0k93163187
accept rate: 12%

 1 @sp1rs, level'th bit means the level'th most significant bit. Each node in the trie has possibly two nodes (left and right). Going to left means evaluating from that node for the next bit. Try to simulate, you'll get to know what's happening. Example n=3 suppose, a) we insert 0 in the trie, then we have x=f(1,1) and count how many numbers already present in the trie which when taken xor with x return a number less than K. and then we insert x in the trie. b) then we insert x=f(1,2) count how many numbers already present in the trie which when taken xor with x return a number less than K. and then we insert x in the trie. c) then we insert x=f(1,3) count how many numbers already present in the trie which when taken xor with x return a number less than K. and then we insert x in the trie.  What does the point c) help us? it tells us how many of subarrays ( [1,3],[2,3] ) satisfy the given condition. Similarily b) tells us how many of subarrays ( [1,2]) satisfy the condition. answered 11 Feb '14, 09:09 3.0k●93●163●187 accept rate: 12%
 0 I have two questions - 1.) What does it qualitatively mean to go left or right from a node in the trie? It's unclear. 2.) Can you please explain atleast with an example how you compute f(L, R) from the trie? I understand that f(L, R) = f(1, L-1) xor f(1, R), but I don't see how this fact comes into play when we use the trie. I would be very glad if someone could give just one example. answered 10 Feb '14, 16:15 81●1●4 accept rate: 9%
 0 What is level'th in the bit ?? answered 11 Feb '14, 01:20 2★sp1rs 963●5●13●27 accept rate: 0%
 0 @darkshadows How the tree is working, do you have any tutorial about the details of the trie used in the problem, I found one of your link broken.:( answered 22 Aug '15, 17:00 187●2●13 accept rate: 0% http://threads-iiith.quora.com/Tutorial-on-Trie-and-example-problems (22 Aug '15, 19:15)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,026
×2,481
×154
×9

question asked: 07 Feb '14, 03:04

question was seen: 10,295 times

last updated: 09 Sep, 18:33