Given an array of integers nums, return the maximum value of nums[i] XOR nums[j] for any two different indices i and j.
The goal is to pick two numbers whose bitwise XOR becomes as large as possible.
Example 1
Input: nums = [3, 10, 5, 25, 2, 8]
Output: 28
Explanation: The pair 5 and 25 gives 5 XOR 25 = 28, which is the maximum possible value here.
Example 2
Input: nums = [0, 2, 4, 7]
Output: 7
Explanation: The pair 0 and 7 gives 7, which is the largest XOR value in this array.
Brute Force Approach
The most direct idea is to try every possible pair and compute its XOR. This works because the problem only asks for the best value among all pairs, so checking all pairs will definitely find the correct answer.
Algorithm
Start with
maxXor = 0so every pair result can be compared against it.Use one loop to pick the first number of the pair and a second loop to pick the second number after it. This is done so every unique pair is checked exactly once.
Compute
nums[i] XOR nums[j]for the current pair. This value is the score that matters for the problem.If the current XOR is larger than
maxXor, replacemaxXorwith it. This step keeps track of the best pair found so far.After all pairs are checked, return
maxXor.
Dry Run
Maximum Xors of 2 Number in an Array Brute Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Returns the largest XOR value among all possible pairs in the array. */ int findMaximumXOR(vector<int>& nums) { // Stores the best XOR value found so far. int maxXor = 0; for (int i = 0; i < (int)nums.size(); i++) { for (int j = i + 1; j < (int)nums.size(); j++) { // Compute the XOR for the current pair. int currentXor = nums[i] ^ nums[j]; // Keep the larger answer because only the maximum is needed. if (currentXor > maxXor) { maxXor = currentXor; } } } return maxXor; }};// Driver code startsint main() { vector<int> nums = {3, 10, 5, 25, 2, 8}; Solution obj; cout << obj.findMaximumXOR(nums) << endl; return 0;}Complexity Analysis
Time Complexity: O(N2), the code compares every possible pair of numbers using two nested loops.
Space Complexity: O(1), because only a few variables are used.
Better Approach
The important observation is that a bigger XOR value is decided by higher bits first. That matters because if a higher bit can be made 1, that is always better than fixing lower bits later.
So instead of guessing the full answer at once, the answer can be built from left to right, one bit at a time.
For each bit position, only the prefixes of numbers up to that bit are needed. If two prefixes can produce the candidate XOR, then that bit can safely stay 1 in the answer.
Algorithm
Find the highest useful bit among the numbers. This is done so work starts from the most important bit and avoids useless leading zeros.
Keep
answer = 0in the beginning because no bit of the maximum XOR has been confirmed yet.Move from the highest bit down to bit
0. This order matters because higher bits affect the final value more strongly than lower bits.Grow a prefix mask that keeps only the left part of each number up to the current bit. This helps test whether the current answer can be improved at this bit position.
Store all masked prefixes in a hash set. The set is needed for quick lookup while checking possible XOR pairs.
Pretend the current bit can become
1by formingcandidate = answer | (1 << bit). This is the value being tested.If there exist two prefixes such that
prefix1 XOR prefix2 = candidate, then keep this bit in the answer. This works because the prefixes prove that some full numbers can support that bit choice.Continue until all bits are tested, then return the built answer.
Dry Run
Maximum Xors of 2 Number in an Array Better Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: // Returns the highest set bit position among all numbers. int getMaxBit(const vector<int>& nums) { // Stores the largest number because its highest bit is enough for the search. int maxNum = 0; // Scan all numbers to find the one with the highest useful bit. for (int num : nums) { if (num > maxNum) { maxNum = num; } } // If every number is zero, bit position zero is enough. if (maxNum == 0) { return 0; } return (int)log2(maxNum); }public: /* Builds the maximum XOR answer bit by bit using prefixes stored in a hash set. */ int findMaximumXOR(vector<int>& nums) { // The search starts from the most significant useful bit. int maxBit = getMaxBit(nums); // Stores the confirmed part of the answer. int answer = 0; // Grows from left to right so more bits are included step by step. int prefixMask = 0; // Test each bit from most significant to least significant. for (int bit = maxBit; bit >= 0; bit--) { // Extend the mask so the current bit is also included in each prefix. prefixMask |= (1 << bit); // Stores all prefixes formed up to the current bit. unordered_set<int> prefixes; // Collect the current masked prefix of every number. for (int num : nums) { prefixes.insert(num & prefixMask); } // Try to keep the current bit as 1 in the answer. int candidate = answer | (1 << bit); // Check whether any two prefixes can produce this candidate XOR. for (int prefix : prefixes) { // If the matching partner exists, this candidate is possible. if (prefixes.find(prefix ^ candidate) != prefixes.end()) { answer = candidate; break; } } } return answer; }};// Driver code startsint main() { vector<int> nums = {3, 10, 5, 25, 2, 8}; Solution obj; cout << obj.findMaximumXOR(nums) << endl; return 0;}Complexity Analysis
Time Complexity: O(N x B), where B is the number of bits processed. The outer loop runs B times (once for each bit position). In each iteration, inserting $N$ prefixes into an unordered_set takes O(N) expected time. Searching the set for matching pairs takes O(1) expected time per lookup across N prefixes, resulting in O(N) operations.
Total time = B x (O(N) + O(N)) = O(N x B). Since B <= 31, this runs in near-linear time relative to N.
Space Complexity: O(N), In every iteration of the outer loop, the unordered_set stores at most N masked prefixes. Since the set is cleared and recreated for each bit level, the maximum additional memory used at any point is proportional to N.
Optimal Approach
Instead of testing prefixes repeatedly using a hash set, we can store the binary representation of all numbers in a Bitwise Trie. Each node in the Trie represents a bit state and has at most two branches: 0 (left) and 1 (right).
By inserting all numbers into the Trie from their most significant bit down to bit 0, we form a tree of shared binary paths. To find the maximum XOR partner for any number, we traverse the Trie from high bit to low bit. At each step, we greedily try to take the opposite bit branch (bit ^ 1) because opposite bits yield a 1 in the XOR result. If the opposite branch exists, we take it and set that bit in our XOR answer; otherwise, we take the same-bit branch. This gives the optimal XOR partner in O(B) time per number.
Algorithm
Find Maximum Bit (
maxBit): Determine the highest set bit position among all numbers innumsto avoid processing unnecessary leading zeros.Build the Binary Trie: Insert every number into the Trie starting from
maxBitdown to bit0. For each bit, create a child node (children[0]orchildren[1]) if it does not already exist.Traverse and Match: For each number in
nums, start at the Trie root and traverse down to bit0:Extract the current bit of the number (
currentBit).Check if the opposite bit path (
toggledBit = currentBit ^ 1) exists in the Trie.If
children[toggledBit]is not null, take that path and set the corresponding bit to1incurrentXor.Otherwise, take the
children[currentBit]path (which contributes0tocurrentXor).
Track Maximum Result: Maintain a running global maximum (
answer) and update it withcurrentXorafter checking each number.Return Answer: Return
answeras the maximum XOR pair value.
Dry Run
Maximum Xors of 2 Number in an Array Optimal Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class TrieNode {public: TrieNode* children[2]; // Creates one trie node with no bit paths yet. TrieNode() { // Both bit directions start as empty. children[0] = children[1] = nullptr; }};class Solution {private: // Returns the highest set bit position among all numbers. int getMaxBit(const vector<int>& nums) { // Stores the largest number because its highest bit is enough for the search. int maxNum = 0; // Scan all numbers to find the one with the highest useful bit. for (int num : nums) { if (num > maxNum) { maxNum = num; } } // If every number is zero, bit position zero is enough. if (maxNum == 0) { return 0; } return (int)log2(maxNum); } // Inserts one number into the bit trie. void insertNumber(TrieNode* root, int num, int maxBit) { // Start insertion from the trie root. TrieNode* node = root; // Insert the number from the most significant useful bit to the lowest bit. for (int bit = maxBit; bit >= 0; bit--) { // Extract the current bit so the correct trie path can be chosen. int currentBit = (num >> bit) & 1; // Create a new node only when this bit path appears for the first time. if (node->children[currentBit] == nullptr) { node->children[currentBit] = new TrieNode(); } // Move deeper for the next lower bit. node = node->children[currentBit]; } } // Finds the best XOR value that the current number can make with the trie. int getBestXor(TrieNode* root, int num, int maxBit) { // Start searching from the trie root. TrieNode* node = root; // Builds the XOR value bit by bit. int currentXor = 0; // Match the current number against the trie from high bit to low bit. for (int bit = maxBit; bit >= 0; bit--) { // Extract the current bit of the number. int currentBit = (num >> bit) & 1; // The opposite bit is preferred because it creates XOR bit 1. int toggledBit = currentBit ^ 1; // Take the opposite path when it exists. if (node->children[toggledBit] != nullptr) { currentXor |= (1 << bit); node = node->children[toggledBit]; } else { // Otherwise only the same-bit path is available. node = node->children[currentBit]; } } return currentXor; }public: /* Returns the maximum XOR value by matching each number against a binary trie. */ int findMaximumXOR(vector<int>& nums) { // The trie works only across useful bits. int maxBit = getMaxBit(nums); // Root of the binary trie. TrieNode* root = new TrieNode(); // Insert every number first so all partner paths become available. for (int num : nums) { insertNumber(root, num, maxBit); } // Stores the best XOR value seen across all numbers. int answer = 0; // Check the best partner value for every number in the array. for (int num : nums) { int currentXor = getBestXor(root, num, maxBit); if (currentXor > answer) { answer = currentXor; } } return answer; }};// Driver code startsint main() {Complexity Analysis
Time Complexity: O(N x B),
Insertion Phase: Inserting a single number of length B bits into the Trie takes O(B) time. Inserting all N numbers takes O(N x B) time.
Search Phase: For each of the N numbers, traversing down the Trie to find the maximum XOR path takes O(B) steps. Searching for all N numbers takes O(N x B) time.
Total time = O(N x B) + O(N x B) = O(N x B).
Space Complexity: O(N x B x 2), In the worst case (when numbers share no common binary prefixes), each inserted number creates $B$ unique Trie nodes. For N numbers, at most N x B nodes are created.
Because every TrieNode statically allocates an array of 2 child pointers (children[0] and children[1]), the memory footprint scales directly as O(N x B x 2).
Interview follow-up Questions
Because higher bits contribute more to the final number. If a higher bit can be made 1, that choice is always more valuable than any lower-bit improvement.
Be the first to add a comment.