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. Given the following Python code that generates all subsets of nums = [1, 2, 3], what is the value of res after the function completes?

easy

A. [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

B. [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

C. [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

D. [[], [1], [1, 3], [1, 2], [1, 2, 3], [2], [2, 3], [3]]

Solution

1. Step 1: Trace backtrack calls and subsets added

   Initially, empty subset [] is added. Then 1 is added, subsets with 1 are generated, then 2, then 3, backtracking after each.

2. Step 2: Confirm order and completeness of subsets

   Subsets are generated in lexicographic order due to sorting and incremental indices: [], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3].

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Matches expected subsets order from backtracking [OK]

Hint: Backtracking adds subsets in sorted order [OK]

Common Mistakes:

• Confusing order of subsets or missing subsets

2. Given the following Python function for UTF-8 validation, what is the value of the variable remaining after processing the second byte in the input [197, 130, 1]?

def validUtf8(data):
    remaining = 0
    for byte in data:
        if remaining == 0:
            if (byte >> 5) == 0b110:
                remaining = 1
            elif (byte >> 4) == 0b1110:
                remaining = 2
            elif (byte >> 3) == 0b11110:
                remaining = 3
            elif (byte >> 7) == 0:
                remaining = 0
            else:
                return False
        else:
            if (byte >> 6) != 0b10:
                return False
            remaining -= 1
    return remaining == 0

easy

A. 2

B. 0

C. 1

D. False (function returns early)

Solution

1. Step 1: Trace first byte (197)

   197 in binary is 11000101. (197 >> 5) == 0b110, so remaining is set to 1.

2. Step 2: Trace second byte (130)

   Since remaining is 1, check if (130 >> 6) == 0b10. 130 in binary is 10000010, so condition holds and remaining is decremented to 0.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Remaining after second byte is 1 -> decremented to 0 after processing second byte [OK]

Hint: Check bit shifts and decrement continuation counter correctly [OK]

Common Mistakes:

• Off-by-one decrement of remaining
• Misinterpreting bit shifts for continuation bytes

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

4. What is the time complexity of the brute force iterative division approach to check if a number n is a power of four?

medium

A. O(1) because division is constant time

B. O(n) because it checks every number up to n

C. O(log log n) because division by 4 reduces n faster than by 2

D. O(log n) because the number is divided by 4 each iteration

Solution

1. Step 1: Analyze the loop iterations

   Each iteration divides n by 4, so the number of iterations is proportional to log base 4 of n.

2. Step 2: Express complexity in Big-O notation

   Since log base 4 of n is O(log n), the time complexity is O(log n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Loop runs ~log4(n) times, which is O(log n) [OK]

Hint: Dividing by 4 reduces n logarithmically -> O(log n)

Common Mistakes:

• Confusing division steps as O(1)
• Mistaking log log n complexity

5. Suppose the input array can contain negative integers as well as positive integers. Which modification to the trie-based maximum XOR algorithm is necessary to correctly handle negative numbers?

hard

A. No modification needed; XOR works the same for negative numbers.

B. Convert all numbers to their 32-bit unsigned representation before inserting and querying the trie.

C. Use 64-bit representation instead of 32-bit to cover sign bits.

D. Use absolute values of numbers before inserting into the trie.

Solution

1. Step 1: Understand negative number representation

   Negative numbers use two's complement, so their bit patterns differ from unsigned integers.

2. Step 2: Convert to unsigned 32-bit representation

   By masking with 0xFFFFFFFF, negative numbers become unsigned 32-bit integers, allowing consistent trie insertion and XOR calculation.

3. Step 3: Avoid using absolute values or larger bit widths

   Absolute values lose sign info; larger bit widths are unnecessary and inefficient.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Unsigned 32-bit masking ensures correct bitwise trie operations [OK]

Hint: Mask negatives to unsigned 32-bit for trie [OK]

Common Mistakes:

• Ignoring sign bits
• Using absolute values
• Assuming 64-bit needed