Maximum XOR using trie data structure with Java

By Lokesh Madhav S

To find the maximum xor between two numbers. The program finds the best number from the array so the xor between that number and the inputted number is maximum.

Using the brute force method Maximum Xor can be found between two numbers by using the bitwise xor operator. But if we are using the same array or a set of numbers to find maximum xor with another number our operation becomes costly.

In this tutorial, we will see how to construct a trie and find maximum xor using a trie.

eg: [1, 2, 5] is the array given and num = 2, the maximum xor is 5^2 = 7

1: construct trie of height 32 (int) for every integer the array using "insert(trie head, int num, int pos)"

2: then traverse the tree to get maximum xor using "find_max" function.

import java.util.*;

public class Maximum_xor {
  static class trie{		//class to store the number as a trie
        trie left, right;
        public trie(){
            left = null;
            right = null;
        }
    }
    
  //inserting nodes in trie
    static void insert(trie head, int num, int pos){
        trie temp = head;
        for(int i = pos; i>=0; i--){
        	//if i'th of num is 1 move right and create a new node if 
        	//no right node is present
            if( (num>>i & 1) == 1){
                if(temp.right == null)
                    temp.right = new trie();
                temp = temp.right;
            }
            //if i'th of num is 0 do the same by moving left
            else{
                if(temp.left == null)
                    temp.left = new trie();
                temp = temp.left;
            }
        }
    }
    
    //pos is (maximum bit value -1) eg. for int pos = 31
    static int find_max(trie head, int num, int pos){
        int ret = 0;	//store result
        trie node = head;
        
        for(int i = pos; i>=0; i--){
            if((num>>i&1) == 1){
            	
            	//if present binary value is 1 move
            	//left to get maximum
                if(node.left != null){ 
                    node = node.left;
                    ret += Math.pow(2, i);
                }
                //no opposite value present so 
                //xor will give 0
                else
                    node = node.right;
            }
            else{
                if(node.right != null){
                    node = node.right;
                    ret += Math.pow(2, i);
                }
                else
                    node = node.left;
            }
        } 
        return ret;   
    }
    
    public static void main(String args[]){
    	System.out.println("Enter array size: ");
        int n;
        Scanner s = new Scanner(System.in);
        n = s.nextInt();
        int[] arr = new int[n];
        
        System.out.println("Enter array: ");
        trie head = new trie();
        for(int i=0; i<n; i++){
            arr[i] = s.nextInt();
            insert(head, arr[i], 31); //int has 32 bits so pos is 31
        }
        
        int q;
        System.out.println("Enter number for maximum xor: ");
        q = s.nextInt();
        System.out.println("Maximum xor " + find_max(head, q, 31));
        
    }
}

Output:

 

Download package to get the executable jar file.