Bird
Raised Fist0
Interview Prepbit-manipulationmediumAmazonGoogleFacebook

Maximum XOR of Two Numbers

Choose your preparation mode4 modes available
Try ItSolutionTrace
▶
Steps
setup

Initialize Trie and Prepare to Insert First Number (3)

Create an empty trie and prepare to insert the first number, 3, processing its bits from the 31st (MSB) to the 0th (LSB).

💡 Initializing the trie is essential to store all numbers bit-by-bit for efficient XOR queries.
Line:trie = Trie() num = 3 trie.insert(num)
💡 The trie starts empty and will be built by inserting each number's bits from MSB to LSB.
📊
Maximum XOR of Two Numbers - Watch the Algorithm Execute, Step by Step
Watching the bitwise trie construction and traversal visually reveals how XOR maximization works at the bit level, which is hard to grasp from code alone.
Step 1/18
·Active fill★Answer cell
Check MSB of 3
A
0
1
1
=3
B
💡 Starting insertion of number 3 from MSB to LSB
Insert bit 0 at position 31
A
0
1
1
=3
B
💡 Created new trie node for bit 0 at MSB
Insert bit 0 at position 30
A
0
1
1
=3
B
💡 Extended trie path with bit 0 at position 30
Insert bit 1 at position 1
A
0
1
1
=3
B
💡 Created branch for bit 1 at position 1
Insert bit 1 at position 0
A
0
1
1
=3
B
💡 Completed insertion of number 3
Check MSB of 10
A
0
1
0
1
0
=10
B
💡 Traverse existing trie node for bit 0 at MSB
Insert bit 1 at position 3
A
0
1
0
1
0
=10
B
💡 Created new trie node for bit 1 at bit 3
Check bit 31 of 5 and trie
A
0
1
0
1
=5
B
=000000000000000000000000000000000
────────────────
=
0
0
0
0
0
0
0
0
=0
💡 No opposite bit 1 at MSB, follow bit 0 path
Set bit 4 in max_xor
A
0
1
0
1
=5
B
=000010000000000000000000000000000
────────────────
=
0
0
0
0
0
0
0
0
=16
💡 Opposite bit found, XOR bit set to 1 at position 4
Set bit 3 in max_xor
A
0
1
0
1
=5
B
=000110000000000000000000000000000
────────────────
=
0
0
0
0
0
0
0
0
=24
💡 Opposite bit found, XOR bit set to 1 at position 3
Set bit 0 in max_xor
A
0
1
0
1
=5
B
=000110000000000000000000000000000
────────────────
=
0
0
0
0
0
0
0
1
=25
💡 Opposite bit found, XOR bit set to 1 at position 0
Update max_xor to 25
A
0
1
0
1
=5
B
💡 max_xor updated to 25 after traversal
Set bit 4 in max_xor
A
0
1
1
0
0
1
=25
B
=000000000000000000000000000000000
────────────────
=
0
0
0
0
0
0
0
0
=16
💡 Opposite bit found, XOR bit set to 1 at position 4
Set bit 3 in max_xor
A
0
1
1
0
0
1
=25
B
=000000000000000000000000000000000
────────────────
=
0
0
0
0
0
0
0
0
=24
💡 Opposite bit found, XOR bit set to 1 at position 3
Set bit 0 in max_xor
A
0
1
1
0
0
1
=25
B
=000000000000000000000000000000000
────────────────
=
0
0
0
0
0
0
0
1
=25
💡 Opposite bit found, XOR bit set to 1 at position 0
max_xor remains 25
A
0
1
1
0
0
1
=25
B
💡 max_xor unchanged after traversal
Set bits 4 and 3 in max_xor
A
0
1
0
1
=5
B
=000010000000000000000000000000000
────────────────
=
0
0
0
0
0
0
0
0
=28
💡 New max_xor 28 found by choosing opposite bits
Return max_xor = 28
A
0
1
1
1
0
0
=28
B
────────────
=
0
1
1
1
0
0
=28
💡 Maximum XOR of two numbers in input is 28

Key Takeaways

✓ Building a trie of bits from MSB to LSB allows efficient representation of all numbers for XOR queries.

This insight is hard to see from code alone because the trie structure and bitwise operations are abstract without visualization.

✓ During traversal, choosing the opposite bit path whenever possible maximizes the XOR bitwise.

Visualizing this choice at each bit clarifies why XOR is maximized by picking opposite bits.

✓ The maximum XOR is found by comparing XOR values obtained from traversing the trie for each number.

Seeing the max_xor update step-by-step shows how the algorithm finds the global maximum.

Practice

(1/5)
1. Consider the following code that generates all permutations of 3 elements using bitmask DP with iterative tabulation. What is the content of dp[7] after the loops finish?

def generate_permutations_iterative(n):
    dp = [[] for _ in range(1 << n)]
    dp[0] = [[]]
    for mask in range(1 << n):
        for i in range(n):
            if not (mask & (1 << i)):
                for perm in dp[mask]:
                    dp[mask | (1 << i)].append(perm + [i])
    return dp[(1 << n) - 1]

perms = generate_permutations_iterative(3)
print(perms)
easy
A. [[0,1,2], [0,2,1], [1,0,2], [1,2,0], [2,0,1], [2,1,0]]
B. [[0,1,2], [1,0,2], [2,0,1]]
C. [[0,1,2], [0,2,1], [1,0,2], [2,1,0]]
D. [[0,1,2], [1,2,0], [2,1,0], [2,0,1]]

Solution

  1. Step 1: Trace dp[0] initialization

    dp[0] starts with [[]], representing empty permutation.

  2. Step 2: Iteratively build dp for all masks

    For each mask, append unused elements to existing permutations, eventually filling dp[7] with all permutations of [0,1,2].

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    dp[7] contains all 3! = 6 permutations of [0,1,2] [OK]
Hint: dp[(1<
Common Mistakes:
  • Confusing mask indexing leading to missing permutations
  • Off-by-one errors in bitmask checks
2. Identify the bug in the following code that attempts to check if a number is a power of two: 
def isPowerOfTwo(n: int) -> bool:
    while n % 2 == 0:
        n //= 2
    return n == 1
What is the issue?
medium
A. The return statement should check n == 0 instead of n == 1
B. The loop condition should be n > 1 instead of n % 2 == 0
C. Using integer division //= 2 causes infinite loops for odd numbers
D. The code does not handle zero or negative inputs, leading to incorrect results

Solution

  1. Step 1: Analyze input handling

    The code does not check if n is positive before the loop, so zero or negative inputs cause incorrect behavior.

  2. Step 2: Consequence of missing check

    For n=0 or negative, the loop condition n % 2 == 0 may cause infinite loop or wrong return value.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Proper input validation is required to avoid incorrect results [OK]
Hint: Always check n > 0 before division loops [OK]
Common Mistakes:
  • Forgetting zero/negative input checks
  • Confusing loop condition with termination condition
3. What is the time complexity of the backtracking approach to generate all subsets of an input array of size n, assuming the array is sorted beforehand?
medium
A. O(n * 2^n)
B. O(n^2)
C. O(2^n)
D. O(n!)

Solution

  1. Step 1: Identify number of subsets generated

    There are 2^n subsets in total.

  2. Step 2: Calculate work done per subset

    Each subset can take up to O(n) time to copy or build, so total time is O(n * 2^n).

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Exponential subsets times linear work per subset [OK]
Hint: Each subset generation costs O(n), total subsets 2^n [OK]
Common Mistakes:
  • Confusing O(2^n) as total time ignoring subset size
  • Mistaking factorial or polynomial complexities
4. If the input array can contain negative numbers and the bit counting approach is used, what modification is necessary to correctly find the single number?
hard
A. Use a 32-bit mask and handle sign bit separately to avoid sign extension errors.
B. Use a hash map instead, as bit counting cannot handle negatives.
C. Convert all numbers to positive before bit counting and restore sign later.
D. No modification needed; bit counting works the same for negatives.

Solution

  1. Step 1: Understand bit counting with negative numbers

    Negative numbers use two's complement; sign bit must be handled carefully to avoid incorrect counts.

  2. Step 2: Apply 32-bit mask and handle sign bit

    Counting bits with a mask ensures correct accumulation; sign bit handled separately prevents sign extension issues.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Proper masking ensures correct bit counts for negatives [OK]
Hint: Mask bits to handle sign bit correctly in negative numbers [OK]
Common Mistakes:
  • Ignoring sign bit causes wrong results
  • Assuming negatives behave like positives
5. Suppose you want to extend the sum of two integers without using + operator to support arbitrary large integers beyond 32 bits. Which modification is necessary to ensure correctness?
hard
A. Use built-in + operator for large integers since bitwise approach only works for fixed 32-bit integers.
B. Keep masking with 0xFFFFFFFF but increase mask size dynamically based on input bit length.
C. Implement iterative approach without recursion to avoid stack overflow on large inputs.
D. Remove masking with 0xFFFFFFFF to allow Python's unlimited integer size to handle sums.

Solution

  1. Step 1: Identify recursion depth issue

    For very large integers, recursion depth grows with bit length, risking stack overflow.

  2. Step 2: Use iterative approach to handle arbitrary large integers

    Iterative bitwise sum avoids recursion stack limits and handles large inputs safely.

  3. Step 3: Masking must adapt or be removed carefully

    Masking fixed to 32 bits breaks large integer sums; iterative approach can handle masking dynamically.

  4. Final Answer:

    Option C -> Option C

  5. Quick Check:

    Iterative avoids recursion limits for large inputs [OK]
Hint: Recursion depth limits large input sums; iteration needed [OK]
Common Mistakes:
  • Removing mask blindly breaks sign handling
  • Using + operator defeats problem purpose
  • Static mask size limits input range
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard