Concepts Used

Trie

Difficulty Level

Medium

Problem Statement :

Given array of N numbers, we need to find the maximum xor between any pair of the numbers.

See original problem statement here

Solution Approach :

Introduction :

Idea is to store the numbers in their binary representation. Let’s consider the X in bitwise and from the highest bit of X=>i to lowest bit 0. The remaining numbers can be divided into two set one with set(1) bit at the bit position i and the other with unset(0) bit at the bit position i, if the bit in the ith position of X is set then we would consider all the numbers with unset bit and neglect the other half similar for when ith bit in the X being unset.

Description:

We will use trie to solve this problem by learning the best online programming courses.
A Trie is a special data structure used to store strings that can be visualized like a graph. It consists of nodes and edges. Each node consists of atmost 26 children and edges connect each parent node to its children. These 26 node pointers is for 26 letters of the English alphabet. A separate edge is maintained for every edge.
We will build a trie with height being most significant bit of the largest number. To search in the Trie, we start with the first diverging point in the trie. For example, given [9, 10, 14, 13], or [1001, 1010, 1110, 1101], we start with the second bit, because all numbers is set on the first bit. The trie is also a balanced one, because each number is represented by a path whose length is equal to the trie height. For example, given [3, 10, 5, 25, 2, 8], the numbers are represented by 00011, 01010, 00101, 11001, 00010, 01000 in the trie.
Now, the starting point is the first trie node having two diverging sub-tries on the left and on the right. We try to go opposite branches(0 versus 1) in the respective sub-tries whenever possible. Sometimes we have two choices and we try them both, and sometimes we are forced to go in the same branch because that’s the only option.

Algorithm :

insert():

  • iterate for every integer i in array, arr[], and store the number in its binary representation.
  • check if the number (0 or 1) previously being inserted,
  • if not, make a new tree node for this number and add it as the children of the root.
  • if it is already present, make the child node as parent and do the same with the remaining bits .
  • After inserting the last bitr node of i in tree , update the weight of the last bit of i, (temp->value = key).

maxXOR():

  • iterate for every integer i in array, arr[],
  • for every i, find the current bit in the prefix,
  • if there is no same bit then look for opposite bits
  • else, look for prefix which has same bits.
  • return xor value of maximum bit difference value so we get maximum xor value .
  • Update xor value for every i.

Complexity Analysis :

We are inserting all the elements of array of size N, lets say. Also we are searching for N intereger values of the array at a time for a single query.
Space complexity of this data structure would be O(2*N), where N is the length of array.

Solutions:

#include <stdio.h>
#include<stdlib.h>
#include<math.h>
#include<stdio.h>

#define INT_MIN -9999


typedef struct TrieNode{
       struct TrieNode* left;
       struct TrieNode* right;
    };

    void insert(struct TrieNode* cur, int n)
    {
        for(int i=31;i>=0;i--)
        {
            int b = (n>>i)&1;
            if(b)
            {
                if(!cur->right)
                    cur->right = (struct TrieNode*)malloc(sizeof(struct TrieNode));
                cur = cur->right;
            }
            else
            {
                if(!cur->left)
                    cur->left = (struct TrieNode*)malloc(sizeof(struct TrieNode));
                cur = cur->left;
            }
        }
    }
    int find(struct TrieNode* head, int nums[],int n)
    {
        int max = INT_MIN;
        for(int i=0;i<n;i++)
        {
           struct TrieNode* tmp = head;
            int cur = 0;
            for(int j=31;j>=0;j--)
            {
                int b = (nums[i]>>j)&1;
                if(b)
                {
                    if(tmp->left)
                    {
                        cur += pow(2,j);
                        tmp = tmp->left;
                    }
                    else
                        tmp = tmp->right;
                }
                else
                {
                    if(tmp->right)
                    {
                        cur += pow(2,j);
                        tmp = tmp->right;
                    }
                    else
                        tmp = tmp->left;
                }
            }
            if(max<cur) max = cur;
        }
        return max;
    }
    int findMaximumXOR(int nums[],int n) {
        struct TrieNode* head = (struct TrieNode*)malloc(sizeof(struct TrieNode));
        for(int i=0;i<n;i++)
            insert(head,nums[i]);
        int res = find(head,nums,n);
        if(res == INT_MIN) return 0;
        return res;
    }

    int main()
    {
      int t;
      scanf("%d",&t);
      while(t--)
      {
        int n;
        scanf("%d",&n);
        int num[n];
        for(int i=0;i<n;i++)
        {
         scanf("%d",&num[i]);
        }
        printf("%d\n",findMaximumXOR(num,n));
      }
    }
#include<bits/stdc++.h>
using namespace std;

struct TrieNode{
        TrieNode* left;
        TrieNode* right;
    };
    void insert(TrieNode* cur, int n)
    {
        for(int i=31;i>=0;i--)
        {
            int b = (n>>i)&1;
            if(b)
            {
                if(!cur->right)
                    cur->right = new TrieNode();
                cur = cur->right;
            }
            else
            {
                if(!cur->left)
                    cur->left = new TrieNode();
                cur = cur->left;
            }
        }
    }
    int find(TrieNode* head, int nums[],int n)
    {
        int max = INT_MIN;
        for(int i=0;i<n;i++)
        {
            TrieNode* tmp = head;
            int cur = 0;
            for(int j=31;j>=0;j--)
            {
                int b = (nums[i]>>j)&1;
                if(b)
                {
                    if(tmp->left)
                    {
                        cur += pow(2,j);
                        tmp = tmp->left;
                    }
                    else
                        tmp = tmp->right;
                }
                else
                {
                    if(tmp->right)
                    {
                        cur += pow(2,j);
                        tmp = tmp->right;
                    }
                    else
                        tmp = tmp->left;
                }
            }
            if(max<cur) max = cur;
        }
        return max;
    }

    int findMaximumXOR(int nums[],int n) {
        TrieNode* head = new TrieNode();
        for(int i=0;i<n;i++)
            insert(head,nums[i]);

        int res = find(head,nums,n);
        if(res == INT_MIN) return 0;
        return res;
    }

    int main()
    {
      int t;
      cin>>t;
      while(t--)
      {
        int n;
        cin>>n;
        int num[n];
        for(int i=0;i<n;i++)
        {
         cin>>num[i];
        }
        cout<<findMaximumXOR(num,n)<<endl;
      }
    }
import java.util.*;

class Main 
 { 
    static final int INT_SIZE = 32; 

    // A Trie Node 
    static class TrieNode { 
        int value; 
        TrieNode[] Child = new TrieNode[2]; 

        public TrieNode() 
        { 
            value = 0; 
            Child[0] = null; 
            Child[1] = null; 
        } 
    } 
    static TrieNode root; 


    static void insert(int key) 
    { 
        TrieNode temp = root; 

        for (int i = INT_SIZE - 1; i >= 0; i--) { 

            int current_bit = (key & (1 << i)) >= 1 ? 1 : 0; 

            if (temp != null && temp.Child[current_bit] == null) 
                temp.Child[current_bit] = new TrieNode(); 

            temp = temp.Child[current_bit]; 
        } 


        temp.value = key; 
    } 

    static int maxXORUtil(int key) 
    { 
        TrieNode temp = root; 

        for (int i = INT_SIZE - 1; i >= 0; i--) 
        { 
            // Find current bit in given prefix 
            int current_bit = (key & (1 << i)) >= 1 ? 1 : 0; 


            if (temp.Child[1-current_bit] != null) 
                temp = temp.Child[1-current_bit]; 

            else if (temp.Child[ current_bit] != null) 
                temp = temp.Child[ current_bit]; 
        } 

        return key ^ temp.value; 
    } 


    static int maxXOR(int arr[], int n) 
    { 
        int max_xor = Integer.MIN_VALUE; 
        root = new TrieNode(); 
        insert(arr[0]); 


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

            max_xor = Math.max(max_xor, maxXORUtil(arr[i])); 

            insert(arr[i]); 
        } 
        return max_xor; 
    } 


    public static void main(String args[]) 
    { 
      Scanner sc = new Scanner(System.in);
      int t = sc.nextInt();
      while(t-->0)
      {
        int n = sc.nextInt();
          int []arr = new int[n];
          for(int i=0;i<n;i++)
            arr[i]= sc.nextInt();
          System.out.println(maxXOR(arr, n)); 
      }
    } 
} 

More references to this problem

Previous post Find words
Next post Consecutive Permutation

Leave a Reply

Your email address will not be published. Required fields are marked *