Maximum XOR of Two Numbers in an Array | Set 2 | C ++ program for the above approach ; Structure of Trie ; Function to insert binary representation of element x in the Trie ; Store the head ; Find the i - th bit ; If curr -> left is NULL ; Update curr to curr -> left ; If curr -> right is NULL ; Update curr to curr -> right ; Function that finds the maximum Bitwise XOR value for all such pairs ; head Node of Trie ; Insert each element in trie ; Stores the maximum XOR value ; Traverse the given array ; Stores the XOR with current value arr [ i ] ; Finding ith bit ; Check if the bit is 0 ; If right node exists ; Update the currentXOR ; Check if left node exists ; Update the currentXOR ; Update M to M / 2 for next set bit ; Update the maximum XOR ; Return the maximum XOR found ; Driver Code ; Given array arr [ ] ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; class node { public : node * left ; node * right ; } ; void insert ( int x , node * head ) { node * curr = head ; for ( int i = 30 ; i >= 0 ; i -- ) { int val = ( x >> i ) & 1 ; if ( val == 0 ) { if ( ! curr -> left ) curr -> left = new node ( ) ; curr = curr -> left ; } else { if ( ! curr -> right ) curr -> right = new node ( ) ; curr = curr -> right ; } } } int findMaximumXOR ( int arr [ ] , int n ) { node * head = new node ( ) ; for ( int i = 0 ; i < n ; i ++ ) { insert ( arr [ i ] , head ) ; } int ans = 0 ; for ( int i = 0 ; i < n ; i ++ ) { int curr_xor = 0 ; int M = pow ( 2 , 30 ) ; node * curr = head ; for ( int j = 30 ; j >= 0 ; j -- ) { int val = ( arr [ i ] >> j ) & 1 ; if ( val == 0 ) { if ( curr -> right ) { curr_xor += M ; curr = curr -> right ; } else { curr = curr -> left ; } } else { if ( curr -> left ) { curr_xor += M ; curr = curr -> left ; } else { curr = curr -> right ; } } M /= 2 ; } ans = max ( ans , curr_xor ) ; } return ans ; } int main ( ) { int arr [ ] = { 1 , 2 , 3 , 4 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << findMaximumXOR ( arr , N ) ; return 0 ; }