Maximum XOR
Solve a medium-level problem for finding the maximum XOR from an integer array.
Problem statement
Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where
Example 1
Sample input
nums: [2,3,5,8,10,25]
Sample output
28
Explanation
2 XOR 3 = 1
2 XOR 5 = 7
2 XOR 8 = 10
2 XOR 10 = 8
2 XOR 25 = 27
3 XOR 5 = 6
3 XOR 8 = 11
3 XOR 10 = 9
3 XOR 25 = 26
5 XOR 8 = 13
5 XOR 10 = 15
5 XOR 25 = 28
8 XOR 10 = 2
8 XOR 25 = 17
10 XOR 25 = 19
The maximum XOR value is 5 XOR 25 = 28.
Example 2
Sample input
nums: [1,2,3]
Sample output
3
Explanation
1 XOR 2 = 3
1 XOR 3 = 2
2 XOR 3 = 1
the maximum XOR value is 1 XOR 2 = 3.
Try it yourself
Try to solve the problem yourself before reading the solution.
#include <iostream>#include <vector>using namespace std;int maximumXOR(vector<int> nums) {// your code goes herereturn -1;}
Intuition
We can use bitwise tries to solve this problem. They're a special type of trie and are used to store binary prefixes efficiently. We'll convert all the numbers of the nums array ([2, 3, 5, 10, 25]) into their binary forms and insert them into the trie where each node will represent a bit of the number.
Algorithm
The summary of the algorithm is given below.
Step 1: Insertion of integers in a trie
Convert all the integers from decimal to binary form and insert the bits into the trie. This means that every trie node can have only two possible children, 0 and 1. An integer parameter value is added to the definition of the trie node to store the final integer value in the leaf node. This parameter will be helpful later to compute XOR values.
// Definition of TrieNodeclass TrieNode{public:// the integer value stored at the leaf nodeint value;// each trie node can have only two children (0 and 1)TrieNode *children[2];};
Step 2: Finding the maximum XOR
The maximum value for the XOR of any two bits is 1. This is only achievable if the two bits involved are the opposite value of each other—that is, XORing 1 with 0 and ...