Find maximum XOR of given integer in a stream of integers

0 0 8 minutes read

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 0
bool check(int N, int i)
{
    return (bool)(N & (1<<i));
}
 
// Create a new Trie node
TrieNode* newNode()
{
    TrieNode* temp = new TrieNode;
    temp->isLeaf = false;
    temp->children[0] = NULL;
    temp->children[1] = NULL;
    return temp;
}
 
// Inserts x into the Trie
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);
        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 code
int 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 integers
import 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 class
class TrieNode:
    def __init__(self):
        self.children = [None, None]
        self.isLeaf = False
 
# Check if ith bit of N is 1 or 0
def check(N, i):
    return (N & (1 << i)) != 0
 
# Create a new TrieNode
def newNode():
    return TrieNode()
 
# Insert x into Trie
def 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 far
def 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 code
root = 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 integers
using 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 0
static bool 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()
{
    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 class
class TrieNode {
constructor() {
this.children = [null, null];
this.isLeaf = false;
}
}
 
// Check if ith bit of N is 1 or 0
function check(N, i) {
return (N & (1 << i)) !== 0;
}
 
// Create a new TrieNode
function newNode() {
return new TrieNode();
}
 
// Insert x into Trie
function insert(root, x) {
let crawler = root;
 
// Padding up to 32 bits
for (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 far
function query2(root, x) {
let crawler = root;
 
// Do XOR from root to a leaf path
let ans = 0;
for (let i = 31; i >= 0; i--) {
// Find ith bit in x
const 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)
function query1(root, x) {
return insert(root, x);
}
 
// Driver code
let 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 zambiatek and would like to contribute, you can also write an article using write.zambiatek.com or mail your article to review-team@zambiatek.com. See your article appearing on the zambiatek 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.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!