Find Two Missing Numbers

📋

Problem

Imagine you have a list of numbers from 1 to n, but two numbers are missing. You want to find those missing numbers efficiently without sorting or extra space.

Given an array containing n-2 distinct integers from the range 1 to n, find the two missing numbers. Input: an integer n and an array of length n-2 containing distinct integers from 1 to n except two missing numbers. Output: the two missing numbers in any order.

2 ≤ n ≤ 10^5Array length = n - 2All elements are distinct and in the range [1, n]The two missing numbers are distinct

Edge cases: n = 2, arr = [] → missing numbers are [1, 2]Missing numbers are consecutive, e.g. n=5, arr=[1,2,5] → missing [3,4]Missing numbers are at the start, e.g. n=5, arr=[3,4,5] → missing [1,2]

</>

IDE

def find_two_missing_numbers(n: int, arr: list) -> list:public int[] findTwoMissingNumbers(int n, int[] arr)vector<int> findTwoMissingNumbers(int n, vector<int>& arr)function findTwoMissingNumbers(n, arr)

def find_two_missing_numbers(n, arr):
    # Write your solution here
    pass

class Solution {
    public int[] findTwoMissingNumbers(int n, int[] arr) {
        // Write your solution here
        return new int[2];
    }
}

#include <vector>
using namespace std;

vector<int> findTwoMissingNumbers(int n, vector<int>& arr) {
    // Write your solution here
    return {};
}

function findTwoMissingNumbers(n, arr) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [1, 2]Returning first two numbers instead of actual missing numbers due to incorrect XOR or sum calculations.✅ Ensure XOR includes all numbers 1 to n and array elements, then partition by a set bit to find missing numbers.

Wrong: [3, 4]Using sum and sum of squares approach but miscalculating or integer overflow.✅ Use XOR partitioning approach to avoid overflow and simplify calculations.

Wrong: [2, 3]Greedy approach picking consecutive missing numbers incorrectly or partial XOR usage.✅ Use full XOR of 1 to n and array, then partition by rightmost set bit to separate missing numbers.

Wrong: [4, 5]Incorrect partition bit chosen causing wrong grouping of numbers.✅ Choose partition bit as rightmost set bit of XOR of missing numbers (xor_all).

Wrong: Timeout or no outputUsing O(n^2) brute force approach on large inputs.✅ Implement O(n) XOR partitioning approach to handle large inputs efficiently.

✓

Test Cases

Think about how your solution handles smallest and largest possible inputs.

Consider tricky cases where missing numbers are consecutive or far apart.

Focus on algorithmic complexity; brute force won't scale.

t1_01basic

Input{"n":6,"arr":[1,2,4,6]}

Expected[3,5]

⏱ Performance - must finish in 2000ms

Numbers 3 and 5 are missing from the array.

💡 Use XOR to combine all numbers and find the XOR of missing numbers.

💡 Partition numbers based on a set bit in the XOR to separate the two missing numbers.

💡 XOR numbers in each partition separately to find the two missing numbers.

Why it failed: Incorrect output means XOR partitioning logic is wrong; ensure you XOR all numbers from 1 to n and array elements correctly and partition by a set bit.

✓ Correctly identified the two missing numbers using XOR partitioning.

t1_02basic

Input{"n":7,"arr":[1,2,3,6,7]}

Expected[4,5]

⏱ Performance - must finish in 2000ms

Numbers 4 and 5 are missing from the array.

💡 Calculate XOR of all numbers from 1 to n and XOR of array elements.

💡 Find a set bit in the XOR result to partition numbers into two groups.

💡 XOR each group separately to find the missing numbers.

Why it failed: If output is wrong, likely missed including all numbers or partitioning incorrectly; verify XOR computations and partitioning by set bit.

✓ Correctly found missing numbers by applying XOR partitioning.

t2_01edge

Input{"n":2,"arr":[]}

Expected[1,2]

⏱ Performance - must finish in 2000ms

Empty array means both numbers 1 and 2 are missing.

💡 Check behavior when input array is empty.

💡 XOR of empty array is zero; XOR with full range gives XOR of missing numbers.

💡 Ensure code handles empty input without errors and returns both missing numbers.

Why it failed: Fails on empty array input; likely does not handle empty arr or assumes at least one element; fix by handling empty input explicitly.

✓ Correctly handles empty input and returns both missing numbers.

t2_02edge

Input{"n":5,"arr":[3,4,5]}

Expected[1,2]

⏱ Performance - must finish in 2000ms

Missing numbers are at the start of the range.

💡 Test when missing numbers are the smallest in the range.

💡 XOR partitioning should still separate missing numbers correctly.

💡 Verify partitioning bit chosen works for numbers at start of range.

Why it failed: Fails when missing numbers are smallest; likely partition bit chosen incorrectly or XOR not including full range; fix by XORing all numbers 1 to n.

✓ Correctly finds missing numbers at start of range.

t2_03edge

Input{"n":5,"arr":[1,2,3]}

Expected[4,5]

⏱ Performance - must finish in 2000ms

Missing numbers are at the end of the range.

💡 Test when missing numbers are the largest in the range.

💡 XOR partitioning must handle numbers at the end correctly.

💡 Check that partition bit is chosen from XOR of missing numbers.

Why it failed: Fails when missing numbers are largest; likely partition bit chosen incorrectly or XOR of full range incomplete; fix by including all numbers 1 to n in XOR.

✓ Correctly finds missing numbers at end of range.

t3_01corner

Input{"n":5,"arr":[1,2,5]}

Expected[3,4]

⏱ Performance - must finish in 2000ms

Missing numbers are consecutive in the middle of the range.

💡 Check if your solution assumes missing numbers are non-consecutive.

💡 XOR partitioning works regardless of consecutiveness.

💡 Ensure partition bit chosen from XOR of missing numbers, not from array elements.

Why it failed: Fails on consecutive missing numbers; likely greedy or sum-based approach used incorrectly; fix by using XOR partitioning method.

✓ Correctly handles consecutive missing numbers.

t3_02corner

Input{"n":4,"arr":[2,3]}

Expected[1,4]

⏱ Performance - must finish in 2000ms

Missing numbers are at opposite ends of the range.

💡 Check if your solution assumes missing numbers are close together.

💡 XOR partitioning handles any two missing numbers.

💡 Verify partition bit is chosen from XOR of missing numbers.

Why it failed: Fails when missing numbers are far apart; likely incorrect partition bit or sum-based approach; fix by correctly computing XOR and partitioning.

✓ Correctly finds missing numbers at opposite ends.

t3_03corner

Input{"n":6,"arr":[1,3,4,5]}

Expected[2,6]

⏱ Performance - must finish in 2000ms

Test to catch confusion between 0/1 knapsack style or greedy assumptions in XOR approach.

💡 Avoid greedy assumptions about missing numbers.

💡 XOR partitioning requires careful bit selection.

💡 Ensure XOR includes all numbers 1 to n and array elements.

Why it failed: Fails due to greedy or partial XOR usage; fix by XORing full range and array, then partitioning by rightmost set bit.

✓ Correctly handles non-greedy XOR partitioning.

t4_01performance

Input{"n":100,"arr":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98]}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with n=100 and 98 elements to test O(n) XOR partitioning performance within 2 seconds.

💡 Use XOR operations which run in O(n) time.

💡 Avoid nested loops or sum of pairs approach which is O(n^2).

💡 Efficiently compute XOR of full range and array elements.

Why it failed: TLE occurs if solution uses O(n^2) brute force; fix by implementing O(n) XOR partitioning approach.

✓ Solution runs efficiently in O(n) time for large input.

Practice

1. 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

2. Identify the bug in the following code snippet for bitwise AND of numbers range:

medium

A. The bit-clearing operation 'right = right & (right - 1)' is incorrect.

B. There is no bug; the code works correctly.

C. The function should return 'left' instead of 'right'.

D. The loop condition should be 'right > left' instead of 'right != left'.

Solution

1. Step 1: Analyze loop condition

   The loop runs while right != left, which fails if right < left, causing infinite loop or incorrect behavior.

2. Step 2: Correct condition

   Changing condition to 'right > left' ensures loop terminates when right reaches or goes below left.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Loop condition must prevent infinite loops and handle equality correctly [OK]

Hint: Loop condition must be 'right > left' to terminate properly [OK]

Common Mistakes:

• Using '!=' instead of '>' causes infinite loops
• Misunderstanding bit-clearing operation
• Returning wrong variable

3. Identify the bug in the following trie-based maximum XOR code snippet:

medium

A. Line with 'node = node.children[bit]' does not check if 'bit' exists in children.

B. Line with 'if bit not in node.children:' should check for toggled_bit instead.

C. Line with 'max_xor |= (1 << i)' should be outside the if condition.

D. Line with 'node = self.root' should be inside the for loop.

Solution

1. Step 1: Analyze traversal in findMaxXor

   When toggled_bit is not found, code moves to node.children[bit] without checking if bit exists, risking KeyError.

2. Step 2: Identify missing null check

   Should use node.children.get(bit) or check existence before accessing to avoid runtime error.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing check causes crash on inputs missing bit child [OK]

Hint: Always check child existence before traversal [OK]

Common Mistakes:

• Assuming child always exists
• Confusing toggled_bit check
• Misplacing max_xor update

4. 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

1. Step 1: Understand mask size dependency

   The masks and shifts are designed for 32-bit integers and must be extended for 64-bit integers.

2. 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.

3. Final Answer:

   Option A -> Option A

4. 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

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