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. You are given an array where every element appears exactly three times except for one element which appears only once. Which approach guarantees an optimal solution with O(n) time and O(1) space complexity?

easy

A. Use a hash map to count occurrences of each element and return the one with count 1.

B. Use bitwise operations to track bits appearing once and twice, resetting bits appearing thrice.

C. Sort the array and scan to find the unique element by checking neighbors.

D. Use a dynamic programming approach to track counts of elements modulo 3.

Solution

1. Step 1: Understand the problem constraints

   The problem requires identifying the unique element appearing once while others appear thrice, with optimal time and constant space.

2. Step 2: Evaluate approaches

   Hash map uses extra space, sorting is O(n log n), DP is not straightforward here. Bitwise FSM approach tracks bits efficiently in O(n) time and O(1) space.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Bitwise FSM approach is known optimal for this problem [OK]

Hint: Bitwise FSM tracks counts mod 3 in constant space [OK]

Common Mistakes:

• Thinking sorting or hash map is optimal for space
• Confusing DP applicability here

2. Consider the following code snippet that finds the single number in an array using XOR. What is the value of result after processing the third element in the input [2, 3, 2]?

easy

A. 3

B. 1

C. 0

D. 2

Solution

1. Step 1: Trace result after first element (2)

   result = 0 · 2 = 2

2. Step 2: Trace result after second element (3)

   result = 2 · 3 = 1

3. Step 3: Trace result after third element (2)

   result = 1 · 2 = 3

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Final XOR result is 3, the unique element [OK]

Hint: XOR accumulates unique element progressively [OK]

Common Mistakes:

• Off-by-one in loop iteration
• Confusing XOR with addition
• Misreading variable updates

3. What is the time complexity of the optimal bitwise AND range algorithm that repeatedly clears the rightmost set bit of the upper bound until it is less than or equal to the lower bound?

medium

A. O(n), where n = right - left

B. O(1), constant time regardless of input size

C. O(k), where k is the number of differing bits between left and right

D. O(log n), where n = right

Solution

1. Step 1: Understand the loop behavior

   Each iteration clears the rightmost set bit of right, reducing the number of set bits.

2. Step 2: Count iterations

   The loop runs at most as many times as there are set bits in the difference between right and left, i.e., the differing bits.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Time depends on differing bits, not full range size [OK]

Hint: Loop runs per differing set bit, not per number in range [OK]

Common Mistakes:

• Assuming linear in range size
• Confusing log n with bit count
• Ignoring bit-clearing effect

4. What is the time complexity of generating all permutations of n elements using bitmask DP with iterative tabulation as shown in the code snippet? Assume appending to lists is O(1) amortized.

medium

A. O(n!)

B. O(n * n!)

C. O(n^2 * 2^n)

D. O(2^n * n!)

Solution

1. Step 1: Identify number of states and transitions

   There are 2^n bitmask states. Each state has up to n transitions to add an unused element.

2. Step 2: Calculate total permutations generated

   Total permutations are n!; each permutation is built by adding elements one by one, so total operations ~ n * n!.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Time complexity is O(n * n!) due to building all permutations incrementally [OK]

Hint: Generating all permutations requires at least O(n * n!) time [OK]

Common Mistakes:

• Confusing 2^n states with n! permutations
• Ignoring the cost of building each permutation step

5. What is the time complexity of the optimal bitmasking solution that sorts words by length and prunes pairs early when finding the maximum product of word lengths with no common letters?

medium

A. O(n^3) due to triple nested loops over words and characters

B. O(n^2 * k) because each pair requires checking all characters

C. O(n^2 + n*k + n log n) where n is number of words and k is average word length

D. O(n log n) since sorting dominates the runtime

Solution

1. Step 1: Analyze preprocessing steps

   Computing bitmasks takes O(n*k) where k is average word length. Sorting masks by length takes O(n log n).

2. Step 2: Analyze nested loops with pruning

   Nested loops run O(n^2) in worst case, but pruning reduces unnecessary checks. Bitwise AND checks are O(1).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Combining all steps yields O(n^2 + n*k + n log n) [OK]

Hint: Bitmask checks are O(1), pruning reduces pairs [OK]

Common Mistakes:

• Assuming O(n^2*k) due to character checks per pair
• Ignoring sorting cost
• Confusing recursion stack space with iterative solution