You are given a number of queries Q and each query will be of the following types:
- Query 1 : add(x) This means add x into your data structure.
- Query 2 : maxXOR(y) This means print the maximum possible XOR of y with all the elements already stored in the data structure.
1 <= x, y <= 10^9 1 <= 10^5 <= Q The data structure begins with only a 0 in it. Example:
Input: (1 10), (1 13), (2 10), (1 9), (1 5), (2 6) Output: 7 15 Add 10 and 13 to stream. Find maximum XOR with 10, which is 7 Insert 9 and 5 Find maximum XOR with 6 which is 15.
A good way to solve this problem is to use a Trie. A prerequisite for this post is Trie Insert and Search. Each Trie Node will look following:
struct TrieNode
{
// We use binary and hence we
// need only 2 children
TrieNode* Children[2];
bool isLeaf;
};
Another thing to handle is that we have to pad the binary equivalent of each input number by a suitable number of zeros to the left before storing them. The maximum possible value of x or y is 10^9 and hence 32 bits will be sufficient. So how does this work? Assume we have to insert 3 and 7 into Trie. The Trie starts out with 0 and after these three insertions can be visualized like this: 
For simplification, the padding has been done to store each number using 3 bits. Note that in binary: 3 is 011 7 is 111 Now if we have to insert 1 into our Trie, we can note that 1 is 001 and we already have path for 00. So we make a new node for the last set bit and after connecting, we get this: 
Now if we have to take XOR with 5 which is 101, we note that for the leftmost bit (position 2), we can choose a 0 starting at the root and thus we go to the left. This is the position 2 and we add 2^2 to the answer. For position 1, we have a 0 in 5 and we see that we can choose a 1 from our current node. Thus we go right and add 2^1 to the answer. For position 0, we have a 1 in 5 and we see that we cannot choose a 0 from our current node, thus we go right. 
The path taken for 5 is shown above. The answer is thus 2^2 + 2^1 = 6.
CPP
// C++ program to find maximum XOR in// a stream of integers#include<bits/stdc++.h>using namespace std;struct TrieNode{ TrieNode* children[2]; bool isLeaf;};// This checks if the ith position in// binary of N is a 1 or a 0bool check(int N, int i){ return (bool)(N & (1<<i));}// Create a new Trie nodeTrieNode* newNode(){ TrieNode* temp = new TrieNode; temp->isLeaf = false; temp->children[0] = NULL; temp->children[1] = NULL; return temp;}// Inserts x into the Trievoid insert(TrieNode* root, int x){ TrieNode* Crawler = root; // padding upto 32 bits for (int i = 31; i >= 0; i--) { int f = check(x, i); if (! Crawler->children[f]) Crawler->children[f] = newNode(); Crawler = Crawler->children[f]; } Crawler->isLeaf = true;}// Finds maximum XOR of x with stream of// elements so far.int query2(TrieNode *root, int x){ TrieNode* Crawler = root; // Do XOR from root to a leaf path int ans = 0; for (int i = 31; i >= 0; i--) { // Find i-th bit in x int f = check(x, i); // Move to the child whose XOR with f // is 1. if ((Crawler->children[f ^ 1])) { ans = ans + (1 << i); // update answer Crawler = Crawler->children[f ^ 1]; } // If child with XOR 1 doesn't exist else Crawler = Crawler->children[f]; } return ans;}// Process x (Add x to the stream)void query1(TrieNode *root, int x){ insert(root, x);}// Driver codeint main(){ TrieNode* root = newNode(); query1(root, 10); query1(root, 13); cout << query2(root, 10) << endl; query1(root, 9); query1(root, 5); cout << query2(root, 6) << endl; return 0;} |
Java
// Java program to find maximum XOR in// a stream of integersimport java.util.ArrayList;import java.util.List;class TrieNode { TrieNode[] children = new TrieNode[2]; boolean isLeaf; TrieNode() { this.isLeaf = false; children[0] = null; children[1] = null; }}public class Main { // This checks if the ith position in // binary of N is a 1 or a 0 static boolean check(int N, int i) { return (N & (1 << i)) != 0; } // Create a new Trie node static TrieNode newNode() { return new TrieNode(); } // Inserts x into the Trie static void insert(TrieNode root, int x) { TrieNode Crawler = root; // padding upto 32 bits for (int i = 31; i >= 0; i--) { int f = check(x, i) ? 1 : 0; if (Crawler.children[f] == null) { Crawler.children[f] = newNode(); } Crawler = Crawler.children[f]; } Crawler.isLeaf = true; } // Finds maximum XOR of x with stream of // elements so far. static int query2(TrieNode root, int x) { TrieNode Crawler = root; // Do XOR from root to a leaf path int ans = 0; for (int i = 31; i >= 0; i--) { // Find i-th bit in x int f = check(x, i) ? 1 : 0; // Move to the child whose XOR with f // is 1. if (Crawler.children[f ^ 1] != null) { // update answer ans += (1 << i); Crawler = Crawler.children[f ^ 1]; } // If child with XOR 1 doesn't exist else { Crawler = Crawler.children[f]; } } return ans; } // Process x (Add x to the stream) static void query1(TrieNode root, int x) { insert(root, x); } // Driver code public static void main(String[] args) { TrieNode root = newNode(); query1(root, 10); query1(root, 13); System.out.println(query2(root, 10)); query1(root, 9); query1(root, 5); System.out.println(query2(root, 6)); }}// This code is contributed by Aman Kumar |
Python3
# Define TrieNode classclass TrieNode: def __init__(self): self.children = [None, None] self.isLeaf = False# Check if ith bit of N is 1 or 0def check(N, i): return (N & (1 << i)) != 0# Create a new TrieNodedef newNode(): return TrieNode()# Insert x into Triedef insert(root, x): crawler = root # Padding up to 32 bits for i in range(31, -1, -1): f = 1 if check(x, i) else 0 if crawler.children[f] is None: crawler.children[f] = newNode() crawler = crawler.children[f] crawler.isLeaf = True return root# Find maximum XOR of x with stream of elements so fardef query2(root, x): crawler = root # Do XOR from root to a leaf path ans = 0 for i in range(31, -1, -1): # Find ith bit in x f = 1 if check(x, i) else 0 # Move to the child whose XOR with f is 1 if crawler.children[f ^ 1] is not None: # Update answer ans += 1 << i crawler = crawler.children[f ^ 1] # If child with XOR 1 doesn't exist else: crawler = crawler.children[f] return ans# Process x (add x to the stream)def query1(root, x): return insert(root, x)# Driver coderoot = TrieNode()root = query1(root, 10)root = query1(root, 13)print(query2(root, 10))root = query1(root, 9)root = query1(root, 5)print(query2(root, 6)) |
C#
// C# program to find maximum XOR in// a stream of integersusing System;public class TrieNode {public TrieNode[] children = new TrieNode[2];public bool isLeaf;public TrieNode(){ this.isLeaf = false; children[0] = null; children[1] = null;}}public class Program {// This checks if the ith position in// binary of N is a 1 or a 0static bool Check(int N, int i){return (N & (1 << i)) != 0;}// Create a new Trie nodestatic TrieNode NewNode() { return new TrieNode(); }// Inserts x into the Triestatic void insert(TrieNode root, int x){ TrieNode Crawler = root; // padding upto 32 bits for (int i = 31; i >= 0; i--) { int f = Check(x, i) ? 1 : 0; if (Crawler.children[f] == null) { Crawler.children[f] = NewNode(); } Crawler = Crawler.children[f]; } Crawler.isLeaf = true;}// Finds maximum XOR of x with stream of// elements so far.static int query2(TrieNode root, int x){ TrieNode Crawler = root; // Do XOR from root to a leaf path int ans = 0; for (int i = 31; i >= 0; i--) { // Find i-th bit in x int f = Check(x, i) ? 1 : 0; // Move to the child whose XOR with f // is 1. if (Crawler.children[f ^ 1] != null) { // update answer ans += (1 << i); Crawler = Crawler.children[f ^ 1]; } // If child with XOR 1 doesn't exist else { Crawler = Crawler.children[f]; } } return ans;}// Process x (Add x to the stream)static void Query1(TrieNode root, int x){ insert(root, x);}// Driver codepublic static void Main(){ TrieNode root = NewNode(); Query1(root, 10); Query1(root, 13); Console.WriteLine(query2(root, 10)); Query1(root, 9); Query1(root, 5); Console.WriteLine(query2(root, 6));}}// This code is contributed by Pushpesh Raj. |
Javascript
// Define TrieNode classclass TrieNode {constructor() {this.children = [null, null];this.isLeaf = false;}}// Check if ith bit of N is 1 or 0function check(N, i) {return (N & (1 << i)) !== 0;}// Create a new TrieNodefunction newNode() {return new TrieNode();}// Insert x into Triefunction insert(root, x) {let crawler = root;// Padding up to 32 bitsfor (let i = 31; i >= 0; i--) {const f = check(x, i) ? 1 : 0;if (crawler.children[f] === null) {crawler.children[f] = newNode();}crawler = crawler.children[f];}crawler.isLeaf = true;return root;}// Find maximum XOR of x with stream of elements so farfunction query2(root, x) {let crawler = root;// Do XOR from root to a leaf pathlet ans = 0;for (let i = 31; i >= 0; i--) {// Find ith bit in xconst f = check(x, i) ? 1 : 0;// Move to the child whose XOR with f is 1if (crawler.children[f ^ 1] !== null) { // Update answer ans += 1 << i; crawler = crawler.children[f ^ 1];}// If child with XOR 1 doesn't existelse { crawler = crawler.children[f];}}return ans;}// Process x (add x to the stream)function query1(root, x) {return insert(root, x);}// Driver codelet root = new TrieNode();root = query1(root, 10);root = query1(root, 13);document.write(query2(root, 10));root = query1(root, 9);root = query1(root, 5);document.write(query2(root, 6)); |
7 15
The space taken by the Trie is O(n*log(n)). Each query of type 1 takes O(log(n)) time. Each query of type 2 takes O(log(n)) time too. Here n is the largest query number. Follow up problem: What if we are given three queries instead of two? 1) add(x) This means add x into your data structure (duplicates are allowed). 2) maxXOR(y) This means print the maximum possible XOR of y with all the elements already stored in the data structure. 3) remove(z) This means remove one instance of z from the data structure. What changes in the Trie solution can achieve this? If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
