Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!
Tries Interview Questions

XOR Maximum

Harsh

Last Updated on March 23, 2022 by Ria Pathak

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.
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.

  • 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:

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

						 
#include 
#include
#include
#include

#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=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

						 
#include
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=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>t;
      while(t--)
      {
        int n;
        cin>>n;
        int num[n];
        for(int i=0;i>num[i];
        }
        cout<

						 
class TrieNode:
	def __init__(self):
		self.left = None
		self.right = None

def insert(cur, n):
	for i in range(31, -1, -1):
		b = (n >> i) & 1

		if b:
			if not cur.right:
				cur.right = TrieNode()
			cur = cur.right

		else:
			if not cur.left:
				cur.left = TrieNode()
			cur = cur.left

def find(head, nums, n):
	
	max = -float("inf")
	
	for i in range(n):
		tmp = head
		cur = 0
		for j in range(31, -1, -1):
			b = (nums[i] >> j) & 1
			if b:
				if tmp.left:
					cur += 2**j
					tmp = tmp.left
				else:
					tmp = tmp.right

			else:
				if tmp.right:
					cur += 2**j
					tmp = tmp.right
				else:
					tmp = tmp.left
		if max < cur:
			max = cur
	return max

def findMaximumXOR(nums, n):
	head = TrieNode()
	for i in range(n):
		insert(head, nums[i])

	res = find(head, nums, n)
	if res == -float("inf"):
		return 0
	return res

for _ in range(int(input())):
	n = int(input())
	nums = list(map(int,input().split()))
	print(findMaximumXOR(nums, n))

[forminator_quiz id="2281"]

More references to this problem

This article tried to discuss the concept of Trie. Hope this blog helps you understand and solve the problem. To practice more problems on Trie you can check out MYCODE | Competitive Programming.

Leave a Reply

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

Close

Related Post