421. Maximum XOR of Two Numbers in an Array
Problem Description
The given problem involves finding the maximum result of nums[i] XOR nums[j]
for all pairs of i
and j
in an array of integers named nums
, where i
is less than or equal to j
. The XOR (^) is a bitwise operator that returns a number which has all the bits that are set in exactly one of the two operands. For example, the XOR of 5 (101)
and 3 (011)
is 6 (110)
. In simple terms, the task is to pick two numbers from the array such that their XOR is as large as possible, and return the value of this maximum XOR.
Intuition
To solve this problem efficiently, the solution uses a greedy approach with bitwise manipulation. The intuition is that to maximize the XOR value, we want to maximize the bit contributions from the most significant bit (MSB) to the least significant bit (LSB).
We know that if we XOR two equal bits, we get 0
, and if we XOR two different bits, we get 1
. To maximize the XOR value, we want a 1
in the MSB position of the result, which means the bits of numbers in that position should be different.
The code uses a loop that starts from the MSB (in this case, 30th bit assuming the numbers are within the range of 32-bit integers) and goes all the way down to the LSB. In each iteration of the loop, we check if there is a pair of numbers in nums
which will give us a 1
in the current bit position we are looking at, when XORed together.
Here's how it works:
-
We build a
mask
which contains the bits we've considered so far from the MSB to the current bit. At first, the mask is0
, but in each iteration, we add the current bit to the mask. -
We then create a set
s
that will contain all the unique values ofnums
elements after applying themask
. This implicitly removes all less significant bits and focuses only on the portion of the bit sequence we are interested in at each stage of the loop. -
Next, we check if we can create a new
max
value by setting the current bit (going from left to right) to1
. This is done byflag = max | current
. -
For each 'prefix' in the set
s
, we check if there's another prefix such that when XORed with theflag
, we get a result that is also in the sets
. This would mean we have two numbers that, when the MSB to the current bit is considered, would produce a1
in the current bit's position if XORed. -
If such pair exists, we update the
max
to be theflag
which has the current bit set to1
, and break since we've found the maximum possible XOR for the current bit position. -
We repeat this process for each bit, each time building on the previously established
max
to check whether the next bit can be increased.
By iteratively ensuring that we get the maximum contribution from each bit position, we eventually end up with the maximum possible XOR value of any two numbers from the array.
Learn more about Trie patterns.
Solution Approach
The implemented solution is based on a greedy algorithm with bit manipulation. The key concept is to determine, bit by bit from the most significant bit to the least significant, whether we can achieve a larger XOR value with the current set of numbers. To facilitate this process, the code utilizes the following elements:
-
Bitwise Operations: The use of bitwise operations (
^
,&
,|
) helps to isolate specific bits and manipulate them. These operations are essential for comparing bits and constructing the maximum XOR value. -
Masking: A mask is used to isolate the bits from the most significant bit to the current bit we are considering. This allows us to ignore the influence of the less significant bits which have not been considered yet.
-
Sets: Sets are used to store unique prefixes of the numbers when only the masked bits are considered. This data structure facilitates constant time access to check if a certain prefix exists, which is crucial for optimizing the solution.
-
Greedy Choice: The greedy choice is made by deciding to include the current bit into the maximum XOR value. This decision is based on whether adding a
1
on the current bit would increase the overall maximum XOR value.
To visualize the approach, let's walk through the code:
-
Initialize a variable
max
to 0 to keep track of the maximum XOR we've found so far. -
Initialize a mask to 0 to progressively include bits from the MSB to LSB into the consideration.
-
Loop from 30 down to 0, representing the bit positions from the MSB to LSB:
-
Update the mask to include the current bit position by XORing it with
1 << i
, which creates a number with only the i-th bit set. -
Create a new empty set
s
. Iterate throughnums
and add tos
the result of bitwiseAND
of each number with the mask. This captures the unique prefixes up to the current bit. -
Calculate
flag
by setting the current bit inmax
. This hypothetically represents a larger XOR if it's possible to achieve. -
Now, use a nested loop to check if any two prefixes in
s
can achieve this hypothetical XOR:-
For each prefix in
s
, calculate the result ofprefix ^ flag
. If this result is also ins
, we know that these two prefixes can achieveflag
when XORed. -
If we find such a pair, update
max
toflag
because we confirmed that setting the current bit results in a bigger XOR.
-
-
If a pair wasn't found, do nothing, and the current bit in
max
remains0
.
-
-
After the loop ends,
max
will contain the maximum XOR value possible with any two numbers innums
. -
Return the
max
value which is the answer.
This approach uses the fact that if prefix1 ^ max = prefix2
(this implies prefix1 ^ prefix2 = max
), then it stands to reason that there is a pair of numbers with the prefix1 and prefix2 that would result in max
when XORed. Thus, it guarantees that the maximum value is found considering each bit position.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Letās consider nums = [3, 10, 5, 25, 2, 8]
and walk through the solution process using the described algorithm.
Step 1: Initialize max
to 0
. This will keep track of the maximum XOR found at any step.
Step 2: Initialize mask
to 0
to include bits to the consideration progressively.
Step 3: Loop through bit positions from 30 down to 0.
For illustration, let's loop from the 4th bit position (since our largest number 25 is 11001
in binary and requires only 5 bits to represent).
i. Bit position 4 (counting from zero, so it's the fifth most significant bit)
- Update
mask
withmask = mask | (1 << 4)
, somask
becomes10000
in binary. - Create an empty set
s
and populate it with the masked elements ofnums
.- For instance,
25 & mask = 16
and8 & mask = 0
. So our sets
will be{0, 16}
.
- For instance,
- Calculate
flag = max | (1 << 4)
(flag = 10000
in binary). - Check if any two prefixes XOR together can equal
flag
(by checking for each prefix ifprefix ^ flag
exists ins
).- In this case, we check
0 ^ 16
and see that16
is ins
, and16 ^ 16
will check if0
is ins
.
- In this case, we check
- Since both
16
and0
are ins
, we can updatemax = flag
. Nowmax
is10000
in binary, or16
in decimal.
ii. Bit position 3
- Update
mask
to now include this 3rd bit:mask = mask | (1 << 3)
, somask
is now11000
. - Populate the new set
s
, which will be{0, 8, 16, 24}
. - Calculate the new
flag = max | (1 << 3)
(flag = 11000
in binary, or24
in decimal). - Check the XOR conditions as before.
- In this case,
8 ^ 24 = 16
is ins
, and so is16 ^ 24 = 8
.
- In this case,
- Update
max
toflag
. Nowmax
is24
.
iii. Bit position 2
- Repeat the process. However, for this step, letās assume that there are no two prefixes in
s
that can achieve the newflag
with XOR. - Therefore, we do not update
max
in this round.
iv. Continue looping in this manner down to bit position 0.
Step 4: After loop ends, max
holds the maximum XOR that we can find.
Given our array, the maximum XOR is between 5 (101)
and 25 (11001)
, which equals 28 (11100)
in binary notation.
Thus, the final answer returned is max
which is 28
.
Solution Implementation
1class Solution:
2 def findMaximumXOR(self, nums: List[int]) -> int:
3 maximum_xor = 0 # Initialize the maximum XOR value.
4 mask = 0 # Initialize the mask, which is used to consider bits from the most significant bit down.
5
6 # Start from the highest bit and go down to the least significant bit (31st to 0th bit).
7 for i in range(31, -1, -1):
8 mask = mask | (1 << i) # Update the mask to include the next bit.
9 prefixes = set() # Create a set to store prefixes of the current length.
10
11 # Collect all prefixes with bits up to the current bit.
12 for num in nums:
13 prefixes.add(num & mask) # Bitwise AND to isolate the prefix.
14
15 # We assume the new bit is '1' and combine it with maximum XOR so far.
16 proposed_max = maximum_xor | (1 << i)
17
18 # Check if there's a pair of prefixes which XOR equals our proposed maximum so far.
19 for prefix in prefixes:
20 if (prefix ^ proposed_max) in prefixes:
21 maximum_xor = proposed_max # Update the maximum XOR since we found a pair.
22 break # No need to check other prefixes.
23
24 # After checking all bits, return the maximum XOR we found.
25 return maximum_xor
26
1import java.util.HashSet;
2import java.util.Set;
3
4class Solution {
5
6 public int findMaximumXOR(int[] numbers) {
7 int maximumXOR = 0; // Variable to hold the maximum XOR value found
8 int mask = 0; // Variable to hold the bit mask
9
10 // Start from the highest bit position and check for each bit
11 for (int i = 30; i >= 0; i--) {
12 // Update the bit mask to include the current bit
13 mask = mask | (1 << i);
14 Set<Integer> prefixes = new HashSet<>(); // Set to store prefixes of numbers
15
16 // Collect all unique prefixes of "i" bits of all numbers
17 for (int number : numbers) {
18 // Add the prefix of current number to the set
19 prefixes.add(number & mask);
20 }
21
22 // Guess that current maximum XOR would have the current bit set
23 int guessedMaximumXOR = maximumXOR | (1 << i);
24
25 // Check if there are two prefixes that would result in the guessed maximum XOR
26 for (Integer prefix : prefixes) {
27 if (prefixes.contains(prefix ^ guessedMaximumXOR)) {
28 // If such two prefixes found, update the maximum XOR
29 maximumXOR = guessedMaximumXOR;
30 break; // No need to check other prefixes
31 }
32 }
33 }
34 // Return the maximum XOR found
35 return maximumXOR;
36 }
37}
38
1#include <vector>
2#include <string>
3#include <algorithm>
4
5// Trie class to implement the Trie data structure with binary representation
6class Trie {
7public:
8 std::vector<Trie*> children; // Children for binary digits 0 and 1
9
10 // Constructor initializes the children to hold two possible values (0 or 1)
11 Trie() : children(2, nullptr) {}
12
13 // Function to insert a number into the Trie
14 void insert(int number) {
15 Trie* node = this;
16 // Start from the most significant bit and insert the number into the Trie
17 for (int i = 30; i >= 0; --i) {
18 int bit = (number >> i) & 1; // Extract the i-th bit of the number
19 if (!node->children[bit]) { // If the bit node does not exist, create it
20 node->children[bit] = new Trie();
21 }
22 node = node->children[bit]; // Move to the corresponding child
23 }
24 }
25
26 // Function to search for the maximum XOR of a number with the existing numbers in the Trie
27 int search(int number) {
28 Trie* node = this;
29 int result = 0; // Initialize the result to 0
30 for (int i = 30; i >= 0; --i) {
31 int bit = (number >> i) & 1; // Extract the i-th bit
32 // Try to find the opposite bit in the Trie for maximized XOR
33 if (node->children[bit ^ 1]) {
34 result = (result << 1) | 1; // If found, update the result with set bit at current position
35 node = node->children[bit ^ 1]; // Move to the opposite bit child
36 } else {
37 result <<= 1; // Else, result is updated just by shifting, bit remains unset
38 node = node->children[bit]; // Move to the same bit child
39 }
40 }
41 return result; // Return the maximum XOR value found
42 }
43};
44
45// Solution class to handle the LeetCode question logic
46class Solution {
47public:
48 // Function to find the maximum XOR of any two numbers in the array
49 int findMaximumXOR(std::vector<int>& nums) {
50 Trie* trie = new Trie(); // Initialize Trie
51 int ans = 0; // Initialize answer to 0
52 for (int num : nums) {
53 trie->insert(num); // Insert each number into the Trie
54 ans = std::max(ans, trie->search(num)); // Update the answer with the maximum XOR value found so far
55 }
56 return ans; // Return the answer
57 }
58};
59
1// Node structure for Trie with an optional array that holds children nodes
2interface TrieNode {
3 children: (TrieNode | undefined)[];
4}
5
6// Initializes a Trie node with undefined children
7function createTrieNode(): TrieNode {
8 return { children: [undefined, undefined] };
9}
10
11// Inserts a number into the Trie
12function insert(trie: TrieNode, number: number): void {
13 let node = trie;
14 // Start from the most significant bit and insert the number into the Trie
15 for (let i = 30; i >= 0; --i) {
16 const bit = (number >> i) & 1; // Extract the i-th bit of the number
17 if (!node.children[bit]) { // If the bit node does not exist, create it
18 node.children[bit] = createTrieNode();
19 }
20 node = node.children[bit] as TrieNode; // Move to the corresponding child node
21 }
22}
23
24// Searches for the maximum XOR of a number with the existing numbers in the Trie
25function search(trie: TrieNode, number: number): number {
26 let node = trie;
27 let result = 0; // Initialize the result to 0
28 for (let i = 30; i >= 0; --i) {
29 const bit = (number >> i) & 1; // Extract the i-th bit
30 // Try to find the opposite bit in the Trie for maximized XOR
31 if (node.children[bit ^ 1]) {
32 result = (result << 1) | 1; // If found, update the result with set bit at current position
33 node = node.children[bit ^ 1] as TrieNode; // Move to the opposite bit child node
34 } else {
35 result <<= 1; // Else, result is updated just by shifting, bit remains unset
36 node = node.children[bit] as TrieNode; // Move to the same bit child node
37 }
38 }
39 return result; // Return the maximum XOR value found
40}
41
42// Finds the maximum XOR of any two numbers in an array
43function findMaximumXOR(nums: number[]): number {
44 const trie = createTrieNode(); // Create the root of the Trie
45 let maxResult = 0; // Initialize maxResult to 0
46
47 // Go through each number in the array
48 nums.forEach((num) => {
49 insert(trie, num); // Insert the number into the Trie
50 // Update maxResult with the maximum XOR found so far
51 maxResult = Math.max(maxResult, search(trie, num));
52 });
53
54 return maxResult; // Return the maximum XOR of two numbers in the array
55}
56
Time and Space Complexity
Time Complexity
The time complexity of the code is determined by nested loops where the outer loop runs 31 times (as bit-positions are checked from the most significant bit at index 30 down to the least significant bit at index 0) and the inner loops process each element in the list to build a set and subsequently check whether the XOR of each prefix with the candidate maximum value exists in the set.
-
The outer loop runs 31 times since we are assuming that the integers are 32-bit and we do not need to check the sign bit for XOR operations.
-
For each bit position, we iterate over all
n
numbers to add their left-prefixed bits to the sets
. This operation takesO(n)
time. -
We then iterate again through all unique prefixes, which are at most
n
in the worst case. For each prefix, we perform anO(1)
time check to see if a certain XOR-combination could exist in the set. Therefore, this operation also takesO(n)
time in the worst case.
Multiplying these together, the time complexity is O(31n)
, which simplifies to O(n)
because 31 is a constant factor which does not grow with n
.
Space Complexity
The space complexity is determined by the additional memory taken up by the set s
used to store the unique prefixes:
- The set
s
can have at mostn
elements as each number contributes a unique left-prefixed bit representation to the set. Therefore, the space required for the set isO(n)
.
Considering the space used by max
, mask
, current
, and flag
are all constant O(1)
space overheads, the total space complexity is O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".
What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?
Recommended Readings
Trie Introduction Imagine you have a magic dictionary where as soon as you start spelling a word it immediately tells you how many words that start with those letters How cool would that be This is exactly the kind of magic a data structure called trie performs What's a Trie
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!