Interview Prepbit-manipulationmediumAmazonGoogle

Find Two Missing Numbers

Choose your preparation mode4 modes available

Try It Solution Trace

▶

Steps

setup

Initialize xor_all to 0

Initialize xor_all to zero to prepare for XOR accumulation of numbers.

💡 Starting with zero allows XOR accumulation without affecting results.

Line:xor_all = 0

💡 xor_all is ready to accumulate XORs of all relevant numbers.

fill_row

XOR numbers from 1 to n (1 to 6)

XOR xor_all with each number from 1 through 6 sequentially to accumulate their combined XOR.

💡 XORing all numbers from 1 to n prepares us to cancel out numbers present in the array later.

Line:

for i in range(1, n+1):
    xor_all ^= i

💡 After this loop, xor_all holds XOR of 1^2^3^4^5^6.

fill_row

XOR xor_all with array elements [1, 2, 4, 6]

XOR xor_all with each element in the array to remove known numbers, leaving XOR of missing numbers.

💡 XORing with array elements cancels out numbers present, isolating missing numbers in xor_all.

Line:

for num in arr:
    xor_all ^= num

💡 xor_all now equals XOR of missing numbers 3 and 5.

compare

Find rightmost set bit in xor_all

Isolate the rightmost set bit of xor_all by computing xor_all & (-xor_all). This bit differs between the two missing numbers.

💡 Finding this bit lets us partition numbers into two groups to separate the missing numbers.

Line:set_bit = xor_all & (-xor_all)

💡 The rightmost set bit is 2 (binary 000...0010), indicating the bit position where missing numbers differ.

setup

Initialize x and y to 0 for partitioned XORs

Initialize two accumulators x and y to zero. They will hold XORs of numbers partitioned by the set bit.

💡 Separate XOR accumulators let us isolate each missing number by grouping numbers with and without the set bit.

Line:

x = 0
 y = 0

💡 x and y are ready to accumulate XORs of partitioned groups.

fill_cells

Partition and XOR numbers 1 to 6 by set bit

For each number from 1 to 6, check if the set bit is set. If yes, XOR it into x; otherwise, XOR it into y.

💡 Partitioning numbers by the set bit separates the missing numbers into different groups.

Line:

for i in range(1, n+1):
    if i & set_bit:
        x ^= i
    else:
        y ^= i

💡 After this loop, x and y hold XORs of partitioned full range numbers.

fill_cells

Partition and XOR array elements by set bit

For each element in the array, check the set bit and XOR it into x or y accordingly to remove known numbers.

💡 Removing known numbers from each partition isolates the missing numbers in x and y.

Line:

for num in arr:
    if num & set_bit:
        x ^= num
    else:
        y ^= num

💡 After this, x and y hold the two missing numbers separately.

reconstruct

Return the missing numbers [x, y]

Return the two missing numbers stored in x and y as the final answer.

💡 The XOR partitioning has successfully isolated the missing numbers without extra space or sorting.

Line:return [x, y]

💡 The algorithm outputs the two missing numbers found by XOR partitioning.

reconstruct

Sort missing numbers for final output

Sort the missing numbers to present them in ascending order as [3, 5].

💡 Sorting the output helps verify correctness easily.

Line:return sorted([x, y])

💡 The final output matches the expected missing numbers.

final

Final state with sorted missing numbers

The final state shows the two missing numbers sorted as [3, 5], completing the algorithm.

💡 Presenting the final sorted missing numbers confirms the correctness of the approach.

💡 The two missing numbers found are 3 and 5.

def find_two_missing_xor(n, arr):
    xor_all = 0  # STEP 1
    for i in range(1, n+1):  # STEP 2
        xor_all ^= i
    for num in arr:  # STEP 3
        xor_all ^= num

    set_bit = xor_all & (-xor_all)  # STEP 4

    x = 0  # STEP 5
    y = 0
    for i in range(1, n+1):  # STEP 6
        if i & set_bit:
            x ^= i
        else:
            y ^= i
    for num in arr:  # STEP 7
        if num & set_bit:
            x ^= num
        else:
            y ^= num
    return sorted([x, y])  # STEPS 8 & 9

if __name__ == '__main__':
    n = 6
    arr = [1, 2, 4, 6]
    print(find_two_missing_xor(n, arr))

📊

Find Two Missing Numbers - Watch the Algorithm Execute, Step by Step

Watching each XOR and bitwise operation visually helps you understand how the algorithm isolates the missing numbers without extra space or sorting.

Step 1/10

·Active fill★Answer cell

Initialize xor_all

XOR 1 to 6

💡 XOR of 1^2^3^4^5^6 = 7 (binary 000...0111)

XOR with array elements

💡 XOR of missing numbers 3 and 5 = 6 (binary 000...0110)

Find rightmost set bit

💡 Rightmost set bit isolates bit 1 (counting from 0 LSB)

Initialize x and y

Partition XOR 1 to 6

💡 x = XOR of numbers with bit 1 set; y = XOR of numbers without bit 1 set

Partition XOR with array elements

💡 x and y now hold missing numbers 5 and 3

Return missing numbers

💡 Missing numbers are 5 and 3

Sorted final answer

💡 Final missing numbers: 3 and 5

Final missing numbers

💡 The two missing numbers found are 3 and 5

Key Takeaways

✓ XORing all numbers from 1 to n and the array isolates XOR of missing numbers.

This step is hard to grasp from code alone because it relies on XOR properties that cancel out known numbers.

✓ Finding the rightmost set bit in the XOR result partitions numbers into two groups, separating missing numbers.

Visualizing the set bit helps understand how the algorithm distinguishes the two missing numbers.

✓ Partitioned XORs of full range and array elements isolate each missing number individually.

Seeing the XOR accumulators update step-by-step clarifies why this approach works without extra space.

Practice

(1/5)

1. What is the time complexity of the bit manipulation approach using n & (n - 1) to check if a number is a power of two, assuming n is a 32-bit integer?

medium

A. O(n), where n is the input number

B. O(n log n), due to repeated bit operations

C. O(1), constant time since integer size is fixed

D. O(log n), proportional to the number of bits in n

Solution

Step 1: Identify the operation cost
The operation n & (n - 1) runs in constant time on fixed-width integers, such as 32-bit integers.
Step 2: Consider input size in bits
Since the integer size is fixed (32 bits), the operation is O(1) constant time.
Final Answer:
Option C -> Option C
Quick Check:
Bitwise operations on fixed-width integers are constant time [OK]

Hint: Bit ops on fixed-width integers are O(1) [OK]

Common Mistakes:

Assuming O(log n) for fixed-width integers
Confusing numeric value with bit length

2. Consider this buggy code snippet for finding two unique numbers. Which line contains the subtle bug?

medium

A. Line 8: set_bit calculation

B. Line 6: xor calculation loop

C. Line 3: xor initialization

D. Line 12: partitioning condition

Solution

Step 1: Identify how set_bit is computed
Correct approach uses set_bit = xor & (-xor) to isolate rightmost set bit. Here, set_bit = xor misses this step.
Step 2: Understand impact of bug
Without isolating rightmost set bit, partitioning fails, XOR groups won't separate unique numbers correctly.
Final Answer:
Option A -> Option A
Quick Check:
Bug in set_bit calculation breaks partitioning [OK]

Hint: Isolate rightmost set bit with xor & (-xor) [OK]

Common Mistakes:

Using xor directly as set_bit
Breaking early before full XOR
Misusing partition 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

Step 1: Identify number of subsets generated
There are 2^n subsets in total.
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).
Final Answer:
Option A -> Option A
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. Suppose the problem is extended to find the bitwise AND of all numbers in the range [left, right], but now left and right can be negative integers. Which modification to the optimal algorithm is necessary?

hard

A. Convert negative numbers to their 2's complement positive equivalents and then apply the algorithm.

B. Use a mask to limit the bit-length and shift both numbers until equal, considering sign bits.

C. No modification needed; the existing bit-clearing approach works for negative numbers.

D. Iterate through the entire range because bitwise AND with negatives is undefined.

Solution

Step 1: Understand negative number representation
Negative integers use 2's complement, so sign bits affect bitwise AND results.
Step 2: Modify approach
Masking to limit bit-length and shifting both numbers until equal handles sign bits correctly and finds common prefix.
Step 3: Reject naive iteration
Iterating entire range is inefficient and unnecessary; direct bitwise manipulation with sign awareness is needed.
Final Answer:
Option B -> Option B
Quick Check:
Handling sign bits requires masking and shifting, not naive bit-clearing [OK]

Hint: Handle sign bits with masking and shifting for negatives [OK]

Common Mistakes:

Assuming algorithm works unchanged for negatives
Trying to convert negatives to positives incorrectly
Iterating entire range for negatives

5. Suppose you need to reverse bits of a 64-bit unsigned integer instead of 32-bit. Which modification to the optimal divide and conquer mask approach is correct?

hard

A. Extend masks to 64-bit constants and add an additional step shifting by 32 bits with proper masking.

B. Apply the 32-bit mask approach directly without changes; it works for any bit width.

C. Use the brute force bit-by-bit reversal loop since masks only work for 32 bits.

D. Use the same 32-bit masks and steps, but apply them twice to the lower and upper 32 bits separately.

Solution

Step 1: Understand mask size dependency
The masks and shifts are designed for 32-bit integers and must be extended for 64-bit integers.
Step 2: Modify masks and add step
Use 64-bit masks and add a final step shifting by 32 bits with masking to handle full 64-bit reversal.
Final Answer:
Option A -> Option A
Quick Check:
64-bit reversal requires 64-bit masks and an extra step [OK]

Hint: 64-bit reversal needs 64-bit masks and extra shift step [OK]

Common Mistakes:

Trying to reuse 32-bit masks directly
Splitting 64-bit into two 32-bit halves without merging
Assuming brute force is only option for 64-bit

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

Initialize xor_all to 0

XOR numbers from 1 to n (1 to 6)

XOR xor_all with array elements [1, 2, 4, 6]

Find rightmost set bit in xor_all

Initialize x and y to 0 for partitioned XORs

Partition and XOR numbers 1 to 6 by set bit

Partition and XOR array elements by set bit

Return the missing numbers [x, y]

Sort missing numbers for final output

Final state with sorted missing numbers

Key Takeaways

Practice

Solution

Step 1: Identify the operation cost

Step 2: Consider input size in bits

Final Answer:

Quick Check:

Solution

Step 1: Identify how set_bit is computed

Step 2: Understand impact of bug

Final Answer:

Quick Check:

Solution

Step 1: Identify number of subsets generated

Step 2: Calculate work done per subset

Final Answer:

Quick Check:

Solution

Step 1: Understand negative number representation

Step 2: Modify approach

Step 3: Reject naive iteration

Final Answer:

Quick Check:

Solution

Step 1: Understand mask size dependency

Step 2: Modify masks and add step

Final Answer:

Quick Check:

Ready to prove it?