Maximum XOR of Two Numbers

📋

Problem

Imagine you have a list of secret codes represented as numbers, and you want to find the pair of codes that differ the most in their binary form to maximize security.

Given an array of integers nums, find the maximum result of nums[i] XOR nums[j] where 0 ≤ i, j < n and i != j. Return the maximum XOR value.

1 ≤ n ≤ 10^50 ≤ nums[i] < 2^31

Edge cases: Array with all zeros → maximum XOR is 0Array with one element → maximum XOR is 0 (no pair)Array with two identical elements → maximum XOR is 0

</>

IDE

def findMaximumXOR(nums: list[int]) -> int:public int findMaximumXOR(int[] nums)int findMaximumXOR(vector<int>& nums)function findMaximumXOR(nums)

def findMaximumXOR(nums):
    # Write your solution here
    pass

class Solution {
    public int findMaximumXOR(int[] nums) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int findMaximumXOR(vector<int>& nums) {
    // Write your solution here
    return 0;
}

function findMaximumXOR(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Returning 0 for all inputs due to missing pair iteration or early return.✅ Ensure you iterate over all pairs or implement the bitwise prefix set approach to find max XOR.

Wrong: Incorrect max XOR less than expectedGreedy bit setting without verifying prefix XOR pairs leads to overestimating bits.✅ At each bit, check if candidate XOR can be formed by verifying prefixes before setting bit.

Wrong: Crashes or errors on empty or single element inputNo checks for input length less than 2 causing index errors or invalid operations.✅ Add guard clause to return 0 if input length < 2.

Wrong: Wrong result due to integer overflow or sign bit issuesIncorrect handling of large 31-bit integers in bitwise operations.✅ Use unsigned or 32-bit safe bitwise operations; ensure no sign extension errors.

Wrong: TLE on large inputsUsing brute force O(n^2) approach instead of O(n log M) bitwise prefix method.✅ Implement the bitwise prefix set approach to reduce complexity to O(n log M).

✓

Test Cases

Edge cases often break assumptions; test empty and minimal inputs carefully.

Corner cases expose subtle bugs like greedy traps and misuse of problem constraints.

Performance tests require efficient algorithms; brute force won't scale.

t1_01basic

Input{"nums":[3,10,5,25,2,8]}

Expected28

⏱ Performance - must finish in 2000ms

The maximum XOR is 5 ^ 25 = 28.

💡 Consider how XOR behaves bit by bit to maximize the result.

💡 Use a prefix set to check if a candidate XOR can be formed at each bit.

💡 Try building the answer from the highest bit down, updating prefixes.

Why it failed: Incorrect maximum XOR output; likely missing the bit-by-bit greedy approach or prefix checks. Fix by implementing the prefix set method to verify candidate XORs at each bit.

✓ Correctly finds maximum XOR using bitwise prefix checks.

t1_02basic

Input{"nums":[14,70,53,83,49,91,36,80,92,51,66,70]}

Expected127

⏱ Performance - must finish in 2000ms

Maximum XOR is 36 ^ 91 = 127.

💡 Try checking prefixes of numbers at each bit to find possible XORs.

💡 Use a greedy approach to set bits from high to low if possible.

💡 Confirm candidate XOR by verifying if prefix XOR pairs exist.

Why it failed: Output too low; likely not checking all prefixes or bits properly. Fix by verifying candidate XORs using prefix sets at each bit.

✓ Correctly computes maximum XOR for varied inputs.

t2_01edge

Input{"nums":[]}

Expected0

⏱ Performance - must finish in 2000ms

Empty array has no pairs, so maximum XOR is 0.

💡 Consider what happens when the input array is empty.

💡 No pairs exist, so the maximum XOR must be zero.

💡 Return 0 immediately if array length is less than 2.

Why it failed: Function crashes or returns non-zero for empty input. Fix by adding a check for array length < 2 and return 0.

✓ Handles empty input gracefully by returning 0.

t2_02edge

Input{"nums":[0]}

Expected0

⏱ Performance - must finish in 2000ms

Single element array has no pairs, so maximum XOR is 0.

💡 With only one number, no pair exists to XOR.

💡 Maximum XOR in this case must be zero.

💡 Check for array length less than 2 and return 0.

Why it failed: Returns non-zero or crashes on single element input. Fix by returning 0 when array length < 2.

✓ Correctly returns 0 for single element input.

t2_03edge

Input{"nums":[7,7]}

Expected0

⏱ Performance - must finish in 2000ms

Two identical elements XOR to 0, which is maximum possible here.

💡 XOR of identical numbers is always zero.

💡 Check pairs carefully even if numbers are the same.

💡 Ensure algorithm does not skip pairs or miscalculate.

Why it failed: Returns non-zero for identical pairs. Fix by correctly computing XOR for all pairs including duplicates.

✓ Correctly returns 0 for identical pairs.

t2_04edge

Input{"nums":[2147483647,0]}

Expected2147483647

⏱ Performance - must finish in 2000ms

Maximum XOR is 2147483647 ^ 0 = 2147483647, testing large bit handling.

💡 Test handling of maximum 31-bit integer values.

💡 Ensure bitwise operations handle large numbers correctly.

💡 Check that no overflow or sign issues occur.

Why it failed: Incorrect result due to overflow or sign bit errors. Fix by using unsigned or 32-bit safe bitwise operations.

✓ Correctly handles maximum integer values.

t3_01corner

Input{"nums":[1,2,4,8,16]}

Expected24

⏱ Performance - must finish in 2000ms

Maximum XOR is 8 ^ 16 = 24; tests greedy bit-by-bit correctness.

💡 Beware of greedy approaches that pick bits without verifying prefix existence.

💡 Use prefix sets to confirm candidate XOR bits at each step.

💡 Fix greedy trap by checking if prefix XOR pairs exist before setting bits.

Why it failed: Greedy approach sets bits without prefix verification, resulting in wrong max XOR. Fix by verifying prefix XOR pairs before setting bits.

✓ Correctly avoids greedy trap by verifying prefixes.

t3_02corner

Input{"nums":[2,2,2,2]}

Expected0

⏱ Performance - must finish in 2000ms

All elements identical; maximum XOR is 0, tests handling of duplicates.

💡 Check that duplicates do not cause incorrect XOR calculations.

💡 Ensure algorithm considers all pairs, including duplicates.

💡 Fix by not skipping pairs with identical numbers.

Why it failed: Incorrect non-zero output due to ignoring duplicates or miscalculating. Fix by including all pairs in XOR calculation.

✓ Correctly returns 0 for all identical elements.

t3_03corner

Input{"nums":[0,1,1,3]}

Expected3

⏱ Performance - must finish in 2000ms

Tests confusion between 0/1 knapsack style and XOR problem; max XOR is 3 (0 ^ 3 or 1 ^ 3).

💡 XOR problem differs from knapsack; no repeated use of elements.

💡 Ensure pairs are distinct elements, not combinations or sums.

💡 Fix by iterating pairs, not subsets or sums.

Why it failed: Confuses XOR with subset sums or unbounded usage, producing wrong max XOR. Fix by only XORing pairs of distinct elements.

✓ Correctly distinguishes XOR pairs from subset sums.

t4_01performance

Input{"nums":[2147483647,1073741823,536870911,268435455,134217727,67108863,33554431,16777215,8388607,4194303,2097151,1048575,524287,262143,131071,65535,32767,16383,8191,4095,2047,1023,511,255,127,63,31,15,7,3,1,0,123456789,987654321,192837465,918273645,564738291,1029384756,675849302,384756192,847362514,293847561,918273645,123456789,987654321,192837465,918273645,564738291,1029384756,675849302,384756192,847362514,293847561,918273645,123456789,987654321,192837465,918273645,564738291,1029384756,675849302,384756192,847362514,293847561,918273645,123456789,987654321,192837465,918273645,564738291,1029384756,675849302,384756192,847362514,293847561,918273645,123456789,987654321,192837465,918273645,564738291,1029384756,675849302,384756192,847362514,293847561,918273645,123456789,987654321,192837465,918273645,564738291,1029384756,675849302,384756192,847362514,293847561,918273645]}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with n=100 tests O(n log M) complexity; brute force O(n^2) will time out.

💡 Brute force O(n^2) is too slow for n=100.

💡 Use bitwise greedy with prefix sets for O(n log M) performance.

💡 Avoid nested loops over all pairs; use bit manipulation tricks.

Why it failed: TLE due to O(n^2) brute force approach. Fix by implementing O(n log M) bitwise prefix set method.

✓ Efficient O(n log M) solution passes within time limit.

Practice

1. Given a string text and a list of words, you need to find all pairs of indices [i, j] such that the substring text[i:j+1] is in the list of words. Which approach guarantees an optimal solution in terms of time complexity when the list of words is large and words have varying lengths?

easy

A. Build a trie from the list of words and perform a DFS from each index in the text to find matching substrings.

B. Use dynamic programming to store whether substrings are in the word list and build results bottom-up.

C. Use a brute force nested loop to check every substring against the list of words directly.

D. Sort the list of words and use binary search to check each substring generated from the text.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding all substrings of text that match any word in a large list. Checking every substring against the list directly is expensive.

2. Step 2: Recognize the trie + DFS pattern

   Building a trie from the words allows prefix-based pruning. DFS from each index in text efficiently finds all matching substrings without redundant checks, guaranteeing optimal time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Trie + DFS prunes search space better than brute force or binary search [OK]

Hint: Trie + DFS prunes prefix search efficiently [OK]

Common Mistakes:

• Thinking brute force is efficient enough for large inputs

2. You need to design a system that receives a continuous stream of characters and must efficiently determine if any suffix of the stream matches a word from a given dictionary. Which algorithmic approach best guarantees optimal query time and memory usage?

easy

A. Build a trie of the reversed dictionary words and maintain a limited-length stream buffer to traverse the trie backwards on each query.

B. Use a brute force approach that checks all suffixes of the stream against the dictionary on every query.

C. Use a prefix trie of the dictionary words and scan the stream from the start to check for matches.

D. Apply dynamic programming to store all possible substrings of the stream and check membership in the dictionary.

Solution

1. Step 1: Understand the problem constraints

   The problem requires checking if any suffix of the stream matches a dictionary word efficiently, which suggests suffix-based matching.

2. Step 2: Evaluate approaches

   Brute force checking all suffixes is too slow. Prefix tries do not help with suffix matching. Dynamic programming for all substrings is inefficient. Building a trie of reversed words and traversing it backwards with a limited buffer optimizes both time and space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Reversed trie + limited buffer matches suffixes efficiently [OK]

Hint: Suffix matching needs reversed trie traversal [OK]

Common Mistakes:

• Using prefix trie for suffix matching
• Checking all suffixes brute force
• Using DP on all substrings

3. What is the time complexity of the optimal bitwise trie approach to count pairs with XOR in a range for an input array of size n and maximum number M (max element)?

medium

A. O(n * log M)

B. O(n^2)

C. O(n * M)

D. O(n * log n)

Solution

1. Step 1: Identify operations per element

   Each number is inserted into the trie in O(log M) time, where M is the max number (bit length).

2. Step 2: Query per element also takes O(log M)

   For each number, querying the trie for counts less than a limit also takes O(log M).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Overall complexity is O(n * log M) due to insert and query per element [OK]

Hint: Trie operations scale with bit length, not array size squared [OK]

Common Mistakes:

• Assuming O(n^2) due to pairs
• Confusing M with n in complexity
• Ignoring log factor from bit length

4. Suppose the WordDictionary is extended to support searching for words with the wildcard '*' that matches zero or more characters (instead of '.' matching exactly one). Which of the following modifications to the trie search algorithm correctly handles '*' wildcard searches?

hard

A. Use recursion or stack to explore zero or more characters by branching at current node and advancing index accordingly.

B. Treat '*' as '.' and continue with single character branching only.

C. Precompute all possible expansions of '*' and store them in the trie during addWord.

D. Ignore '*' and treat it as a literal character during search.

Solution

1. Step 1: Understand '*' wildcard semantics

   '*' matches zero or more characters, so search must explore skipping '*' or consuming characters.

2. Step 2: Identify correct search strategy

   Using recursion or stack to explore both skipping '*' (index+1) and consuming children (index unchanged) correctly handles zero or more matches.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Branching on both skipping and consuming characters handles '*' wildcard [OK]

Hint: '*' requires branching on skip or consume [OK]

Common Mistakes:

• Treating '*' like '.'
• Precomputing expansions is infeasible
• Ignoring '*' wildcard semantics

5. Suppose the Word Break problem is modified so that dictionary words can be reused unlimited times in the segmentation. Which modification to the algorithm is necessary to correctly handle this variant?

hard

A. Modify the inner loop to continue checking all prefixes even after dp[i] is set to True

B. Change dp array to count number of ways instead of boolean flags

C. Remove the dp array and use pure recursion with memoization only

D. No change needed; the original DP with trie approach already supports reuse

Solution

1. Step 1: Understand reuse impact on DP

   When reuse is allowed, multiple segmentations can overlap. The DP must consider all possible prefixes, not stop at first True.

2. Step 2: Modify inner loop behavior

   Breaking early when dp[i] is True prevents exploring all segmentations. Removing the break allows full exploration, correctly handling reuse.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Allowing all prefixes ensures reuse is handled [OK]

Hint: Breaking early blocks multiple reuse paths [OK]

Common Mistakes:

• Assuming original DP supports reuse without change
• Changing dp to count ways unnecessarily
• Removing dp and relying on recursion only