XOR Problems using Trie

A Trie because of its reTrieVal property can be used to solve many problems that require to find the maximum XOR values or problems involving XOR. In this post, we will discuss similar problems where Trie can be used to solve them.

Reference Links:


 Lets Jump to some questions :
Question 1: MAX_XOR

Given an array of integers, we have to find two elements whose XOR is maximum.

Explanation:

We First insert our numbers as bits in the Trie as we go. Now for finding the max XOR we start from the MSB and check along. 

Let's say our number Y is b1,b2...bn, where b1,b2.. are binary bits. We start from b1. Now for the XOR to be maximum, we'll try to make most significant bit 1 after taking XOR. So, if b1 is 0, we'll need a 1 and vice versa. In the trie, we go to the required bit side. If favorable option is not there, we'll go other side. Doing this all over for i=1 to n, we'll get the maximum XOR possible.



Solution:


#include <bits/stdc++.h>
using namespace std;

#define INT_SIZE 32
#define BITS_SIZE 2

struct TrieNode {
 int value; 
 TrieNode* children[BITS_SIZE];
};

TrieNode* getNode()
{
 TrieNode* pNode = new TrieNode;
 pNode->value = 0;
 for (int i = 0; i < BITS_SIZE; i++)
        pNode->children[i] = NULL;
 return pNode;
}

void insert(TrieNode* root, int key)
{
 TrieNode* temp = root;
 
 for (int i = INT_SIZE - 1; i >= 0; i--) {
  
  bool current_bit = (key & (1 << i));

  if (temp->children[current_bit] == NULL)
   temp->children[current_bit] = getNode();

  temp = temp->children[current_bit];
 }

 temp->value = key;
}

int search(TrieNode* root, int key)
{
 TrieNode* temp = root;

 for (int i = INT_SIZE - 1; i >= 0; i--) {
  
  bool current_bit = (key & (1 << i));

  if (temp->children[1-current_bit] != NULL)
   temp = temp->children[1-current_bit];

  else if (temp->children[current_bit] != NULL)
   temp = temp->children[current_bit];
 }

 return key ^ temp->value;
}

int maxXOR(int arr[], int n)
{
 int max_xor = INT_MIN; 

 TrieNode* root = getNode();
 insert(root, arr[0]);

 for (int i = 1; i < n; i++) {

  max_xor = max(max_xor, search(root, arr[i]));
  insert(root, arr[i]);
  
 }
 return max_xor;
}

int main()
{
 int n,t;
 cin>>t;
 while(t--){
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++)
   cin>>a[i];
  cout << maxXOR(a, n) << endl;
 }
 return 0;
}


Question 2: XOR_SUM_ICPC

Given an array of integers, find the subarray with maximum XOR.

Explanation:

Let's say F(L,R) is XOR of subarray from L to R.

Here we use the property that F(L,R)=F(1,R) XOR F(1,L-1). 

Let's say our subarray with maximum XOR ended at position i. Now, we need to maximise F(L,i) ie. F(1,i) XOR F(1,L-1) where L<=i. Suppose, we inserted F(1,L-1) in our trie for all L<=i, then it's just question 1.



Solution:


#include<bits/stdc++.h>
using namespace std;

#define INT_SIZE 32
#define BITS_SIZE 2

struct TrieNode {
 int value; 
 TrieNode* children[BITS_SIZE];
};

TrieNode* getNode()
{
 TrieNode* pNode = new TrieNode;
 pNode->value = 0;
 for (int i = 0; i < BITS_SIZE; i++)
  pNode->children[i] = NULL;
 return pNode;
}

void insert(TrieNode* root, int key)
{
 TrieNode* temp = root;
 
 for (int i = INT_SIZE - 1; i >= 0; i--) {
  
  bool current_bit = (key & (1 << i));

  if (temp->children[current_bit] == NULL)
   temp->children[current_bit] = getNode();

  temp = temp->children[current_bit];
 }

 temp->value = key;
}

int search(TrieNode* root, int key)
{
 TrieNode* temp = root;

 for (int i = INT_SIZE - 1; i >= 0; i--) {
  
  bool current_bit = (key & (1 << i));

  if (temp->children[1-current_bit] != NULL)
   temp = temp->children[1-current_bit];

  else if (temp->children[current_bit] != NULL)
   temp = temp->children[current_bit];
 }

 return key ^ temp->value;
}

int maxSubArrayXOR(int arr[], int n)
{
 TrieNode *root = getNode();
 insert(root, 0);

 int res = INT_MIN, pre_xor =0;

 for (int i=0; i<n; i++)
 {
  pre_xor = pre_xor^arr[i];
  insert(root, pre_xor);

  res = max(res, search(root, pre_xor));
 }
 return res;
}

int main()
{
 int n,t;
 cin>>t;
 while(t--){
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++)
   cin>>a[i];
  cout << maxSubArrayXOR(a, n) << endl;
 }
 return 0;
}



Question 3: SUBXOR

Given an array of positive integers you have to print the number of subarrays whose XOR is less than K.

Explanation:


If xor[i, j] represents the xor of all elements in the subarray a[i, j], then at an index i what we have is, a trie which has xor[1:1], xor[1:2]…..xor[1:i-1] already inserted. Now we somehow count how many of these (numbers in trie) are such that its xor with xor[1:i] is smaller than k. This will cover all the subarrays ending at the index i and having xor i.e. xor[j, i] <=k;

Now the problem remains, how to count the numbers with xor smaller than k. So, for example take the current bit of the ith index element is p, current bit of number k be q and the current node in trie be node.
Take the case when p=1, k=1. Then if we go to the right child the current xor would be 0 (as the right child means 1 and p=1, 1(xor)1=0).As k=1, all the numbers that are to the right child of this node would give xor value smaller than k. So, we would count the numbers that are right to this node.
If we go to the left child, the current xor would be 1 (as the left child means 0 and p=1, 0(xor)1=1). So, if we go to the left child we can still find number with xor smaller than k, therefore we move on to the left child.
So, to count the numbers that are below a given node, we modify the trie and each node will also store the number of leafs in that subtree and this would be modified after each insertion.
Other three cases for different values of p and k can be solved in the same way to the count the number of numbers with xor less than k.
Solution:
#include <bits/stdc++.h>
using namespace std;

const int INT_SIZE = 32;
const int BIT_SIZE = 2;

struct TrieNode {
   int value;    // value at leaf node
   struct TrieNode* children[BIT_SIZE];
};

struct TrieNode *getNode(void)
{
    struct TrieNode *pNode =  new TrieNode;
    pNode->value = 0;
    for (int i = 0; i < BIT_SIZE; i++)
        pNode->children[i] = NULL;
    return pNode;
}

void insert(struct TrieNode *root, int key)
{
    struct TrieNode *pCrawl = root;
 
    for (int i=INT_SIZE-1; i>=0; i--) 
    {
        bool current_bit = (key >> i & 1);
        if (!pCrawl->children[current_bit])
            pCrawl->children[current_bit] = getNode();
          
        pCrawl->value++;
        pCrawl = pCrawl->children[current_bit];
    }
    pCrawl->value++;
}


int search(struct TrieNode* root, int key, int k)
{
  struct TrieNode* temp = root;
 
  int res=0;

  for (int i = INT_SIZE-1; i >= 0 && temp; i--) {
 
     if (k >> i & 1) {
         const int need = key >> i & 1;
         res += (temp->children[need] ? temp->children[need]->value : 0);
     }
     temp = temp->children[(k >> i & 1) ^ (key >> i & 1)];
  }
  return res;
}

long long int SubarrayXOR(int arr[], int n, int k)
{
   int pre_xor = 0, cnt=0; 
   long long int res=0;

   struct TrieNode* root = getNode();
   insert(root, 0);

   for (int i = 0; i < n; i++) {
  
    pre_xor = pre_xor^arr[i];
  
    res+=search(root, pre_xor , k);
    insert(root, pre_xor);

   }
   return res;
}

int main()
{
   int t,k;
   cin>>t;
   while(t--){
     int arr[111000];
     int n;
     cin>>n>>k;
     for(int i=0;i<n;i++)
       cin>>arr[i];
   
       cout << SubarrayXOR(arr, n, k) << endl;
   }
   return 0;
}

 Practice Problems:
  1. XOR_QUERIES
  2. XOR_MST
  3. MINXOR
  4. XOR_KEY













Comments

Post a Comment

Popular posts from this blog

Lazy Propagation - Too lazy to update all at a time

Image
Sometimes problems will ask you to update an interval from  l to r , instead of a single element. One solution is to update all the elements one by one. Complexity of this approach will be  O(N)  per operation since where are  N  elements in the array and updating a single element will take  O(logN)  time. To avoid multiple call to update function, we can modify the update function to work on an interval. For example consider the node with value 27 in above diagram, this node stores sum of values at indexes from 3 to 5. If our update query is for range 2 to 5, then we need to update this node and all descendants of this node. With Lazy propagation, we update only node with value 27 and postpone updates to its children by storing this update information in separate nodes called lazy nodes or values. We create an array lazy[] which represents lazy node. Size of lazy[] is same as array that represents segment tree, which is tree[] in below cod...
Read more

Combinatorial Game Theory

Image
Sometimes we find questions where two Players say A and B play a game optimally and we have to find out who ultimately is going to win the game provided there are some constraints. These questions are generally branched under the topic Combinatorial Game Theory. And the speciality about these is that the coding part is relatively very small and easy. The key to the Game Theory problems is the hidden observations which can be sometimes very hard to find. First, we will look at the basic division of positions to winning and losing . Question:  Two players are playing a game with n stones where player 1 always plays first. The two players move in alternating turns and play optimally. In a single move, a player can remove either 1, 3 or 4 stones from the pile of stones. If a player is unable to make a move then that player loses the game. Given the number of stones, find and print the name of the winner. Approach:  As we can see positions 1, 3 and 4 are winning positions ...
Read more

Bit Manipulation Problems

We may face many Interview Questions which can ask us to find the Sum of XOR of all pairs of the array OR  Sum of XOR of all subsets   Generally, the constraints for these questions are very high with the value of each array element to be as large as 10^18. So that is a catch to use Bit manipulation method to solve the questions. We will be discussing some of these questions in this post.   Question  1:  Sum of XOR of all possible subsets   Given an array arr[] of size n, we need to find sum of all the values that comes from XORing all   the elements of the subsets.   Input                                                Output  3                                             ...
Read more