What happens if you using sum and sum of squares without handling integer overflow?

Incorrect results or runtime errors on large inputs Fix: Use 64-bit integers or XOR approach to avoid overflow

What happens if you not finding the rightmost set bit correctly in xor approach?

Incorrect partitioning leading to wrong missing numbers Fix: Use xor_all & (-xor_all) to find rightmost set bit

What happens if you assuming missing numbers are consecutive in math approach?

Wrong answers when missing numbers are not consecutive Fix: Solve quadratic equations properly without assumptions

What happens if you using brute force for large n?

Time limit exceeded or very slow performance Fix: Use optimized approaches like XOR or math formulas

Interview Prepbit-manipulationmediumAmazonGoogle

Find Two Missing Numbers

Choose your preparation mode4 modes available

Try It Solution Trace

🎯

mediumBIT_MANIPULATIONAmazonGoogle

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.

💡 This problem is about using bit manipulation to find two missing numbers from a sequence. Beginners often struggle because they try to use sorting or hash sets, but the XOR approach is more optimal and elegant once understood.

📋

Problem Statement

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

💡

Example

Input"n = 6, arr = [1, 2, 4, 6]"

Output[3, 5]

Numbers 3 and 5 are missing from the array.

Input"n = 5, arr = [2, 3, 1]"

Output[4, 5]

Numbers 4 and 5 are missing.

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]
Missing numbers are at the end, e.g. n=5, arr=[1,2,3] → missing [4,5]

⚠️

Common Mistakes

Using sum and sum of squares without handling integer overflow

Incorrect results or runtime errors on large inputs

✅ Use 64-bit integers or XOR approach to avoid overflow

Not finding the rightmost set bit correctly in XOR approach

Incorrect partitioning leading to wrong missing numbers

✅ Use xor_all & (-xor_all) to find rightmost set bit

Assuming missing numbers are consecutive in math approach

Wrong answers when missing numbers are not consecutive

✅ Solve quadratic equations properly without assumptions

Using brute force for large n

Time limit exceeded or very slow performance

✅ Use optimized approaches like XOR or math formulas

🧠

Brute Force (Check All Pairs)

💡 This approach exists to build intuition by trying all possible pairs to find the missing numbers. It is straightforward but inefficient, showing why we need better methods.

Intuition

Try every pair of numbers from 1 to n and check if both are missing from the array. The pair that is missing is the answer.

Algorithm

Generate all pairs of numbers from 1 to n.
For each pair, check if both numbers are missing from the array.
Return the pair that is missing.

💡 This algorithm is easy to visualize but inefficient because it checks many pairs unnecessarily.

</>

Code

def find_two_missing_brute(n, arr):
    nums_set = set(arr)
    for i in range(1, n+1):
        for j in range(i+1, n+1):
            if i not in nums_set and j not in nums_set:
                return [i, j]

# Driver code
if __name__ == '__main__':
    n = 6
    arr = [1, 2, 4, 6]
    print(find_two_missing_brute(n, arr))

Line Notes

nums_set = set(arr)Convert array to set for O(1) membership checks

for i in range(1, n+1)Iterate over all numbers from 1 to n

for j in range(i+1, n+1)Check pairs with j > i to avoid duplicates

if i not in nums_set and j not in nums_setCheck if both numbers are missing

import java.util.*;
public class FindTwoMissing {
    public static int[] findTwoMissingBrute(int n, int[] arr) {
        Set<Integer> set = new HashSet<>();
        for (int num : arr) set.add(num);
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (!set.contains(i) && !set.contains(j)) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }
    public static void main(String[] args) {
        int n = 6;
        int[] arr = {1, 2, 4, 6};
        int[] res = findTwoMissingBrute(n, arr);
        System.out.println(Arrays.toString(res));
    }
}

Line Notes

Set<Integer> set = new HashSet<>()Use HashSet for O(1) lookups

for (int num : arr) set.add(num)Add all array elements to the set

for (int i = 1; i <= n; i++)Iterate over all numbers from 1 to n

if (!set.contains(i) && !set.contains(j))Check if both numbers are missing

#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;

vector<int> findTwoMissingBrute(int n, vector<int>& arr) {
    unordered_set<int> s(arr.begin(), arr.end());
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (s.find(i) == s.end() && s.find(j) == s.end()) {
                return {i, j};
            }
        }
    }
    return {};
}

int main() {
    int n = 6;
    vector<int> arr = {1, 2, 4, 6};
    vector<int> res = findTwoMissingBrute(n, arr);
    cout << res[0] << " " << res[1] << endl;
    return 0;
}

Line Notes

unordered_set<int> s(arr.begin(), arr.end())Create hash set for O(1) membership

for (int i = 1; i <= n; i++)Loop over all numbers from 1 to n

for (int j = i + 1; j <= n; j++)Check pairs with j > i to avoid duplicates

if (s.find(i) == s.end() && s.find(j) == s.end())Check if both numbers are missing

function findTwoMissingBrute(n, arr) {
    const set = new Set(arr);
    for (let i = 1; i <= n; i++) {
        for (let j = i + 1; j <= n; j++) {
            if (!set.has(i) && !set.has(j)) {
                return [i, j];
            }
        }
    }
}

// Test
console.log(findTwoMissingBrute(6, [1, 2, 4, 6]));

Line Notes

const set = new Set(arr)Create set for O(1) membership checks

for (let i = 1; i <= n; i++)Iterate over all numbers from 1 to n

for (let j = i + 1; j <= n; j++)Check pairs with j > i to avoid duplicates

if (!set.has(i) && !set.has(j))Check if both numbers are missing

⏱

Complexity

TimeO(n^2)

SpaceO(n)

We check all pairs (n*(n-1)/2) and use a set for O(1) lookups, so time is quadratic. Space is linear for the set.

💡 For n=1000, this means about 500,000 checks, which is too slow for large inputs.

Interview Verdict: TLE / Use only to introduce

This approach is too slow for large inputs but helps understand the problem and motivates better solutions.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	`O(n^2)`	`O(n)`	No	Yes	Mention only - never code
2. Sum and Sum of Squares	`O(n)`	`O(1)`	No	Yes	Good to mention, but careful with overflow
3. XOR Partitioning	`O(n)`	`O(1)`	No	Yes	Code this approach in 95% of interviews

Practice

(1/5)

1. Consider the following Python code that uses Brian Kernighan's bit counting trick to count set bits from 0 to n. What is the output when n = 3?

def countBits(n):
    res = []
    for i in range(n + 1):
        count = 0
        x = i
        while x:
            x &= x - 1
            count += 1
        res.append(count)
    return res

print(countBits(3))

easy

A. [1, 1, 1, 1]

B. [0, 1, 2, 2]

C. [0, 0, 1, 2]

D. [0, 1, 1, 2]

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

Intuition

Algorithm

Intuition

Algorithm

Intuition

Algorithm

How to Present

Time Allocation

What the Interviewer Tests

Common Follow-ups

When to Use

Signature Phrases

NOT This Pattern When

Similar Problems

Practice

Solution

Step 1: Trace countBits for i=0 to 3

Step 2: Confirm final result list

Final Answer:

Quick Check:

Solution

Step 1: Understand the problem constraints

Step 2: Identify the approach that uses bitmasking

Final Answer:

Quick Check:

Solution

Step 1: First call getSum(1, 2)

Step 2: Since carry is 0, return sum_ = 3

Final Answer:

Quick Check:

Solution

Step 1: Identify loops in the XOR approach

Step 2: Calculate total time complexity

Final Answer:

Quick Check:

Solution

Step 1: Understand XOR limitation

Step 2: Identify approach to find all unique elements

Step 3: Compare alternatives

Final Answer:

Quick Check:

Ready to prove it?