Find the Missing Number

📋

Problem

Imagine you have a list of student IDs from 0 to n, but one ID is missing. You want to quickly find which student is absent without sorting or extra space.

Given an array nums containing n distinct numbers taken from 0, 1, 2, ..., n, find the one number that is missing from the array. Return the missing number.

1 ≤ n ≤ 10^5All numbers in nums are distinctNumbers range from 0 to n inclusive

Edge cases: Array with only one element [0] → missing number is 1Array with only one element [1] → missing number is 0Missing number is 0 (e.g., [1,2,3]) → must detect missing start

</>

IDE

def missingNumber(nums: list[int]) -> int:public int missingNumber(int[] nums)int missingNumber(vector<int> &nums)function missingNumber(nums)

def missingNumber(nums):
    # Write your solution here
    pass

class Solution {
    public int missingNumber(int[] nums) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int missingNumber(vector<int> &nums) {
    // Write your solution here
    return 0;
}

function missingNumber(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: -1Returning -1 when missing number is 0 or not found due to incorrect initialization or XOR logic.✅ Initialize XOR accumulator to 0 and XOR all indices and array elements properly.

Wrong: n (e.g., 5) when missing number is 0Starting XOR from 1 instead of 0, missing the 0 index in XOR calculation.✅ Include 0 in the XOR range from 0 to n inclusive.

Wrong: Incorrect missing number due to off-by-one in XOR rangeXOR range excludes last index n or includes wrong indices.✅ XOR all indices from 0 to n inclusive exactly once.

Wrong: Timeout or no outputUsing sorting or nested loops causing O(n log n) or O(n^2) time complexity.✅ Use XOR approach with O(n) time complexity.

✓

Test Cases

Focus on handling boundary cases like empty or single-element arrays.

Check for off-by-one errors and input validity assumptions.

Optimize your solution to linear time using XOR to handle large inputs efficiently.

t1_01basic

Input{"nums":[3,0,1]}

Expected2

⏱ Performance - must finish in 2000ms

Numbers 0,1,3 are present, 2 is missing

💡 Consider using XOR to cancel out pairs of identical numbers.

💡 XOR all indices and all values; missing number remains after cancellations.

💡 Return XOR of all indices and array values to find missing number.

Why it failed: Incorrect output means XOR logic is flawed; ensure you XOR all indices from 0 to n and all array elements correctly.

✓ Correctly identified missing number using XOR approach.

t1_02basic

Input{"nums":[0,1,2,4,5]}

Expected3

⏱ Performance - must finish in 2000ms

Numbers 0,1,2,4,5 present; missing number is 3

💡 Try XORing all numbers from 0 to n and the array elements.

💡 Check that you include the full range 0 to n in your XOR calculation.

💡 XOR of indices 0 to 5 and array elements yields missing number 3.

Why it failed: Missing number incorrect due to incomplete XOR range or missing last index; include all indices 0 to n.

✓ XOR approach correctly finds missing number in varied input.

t2_01edge

Input{"nums":[]}

Expected0

⏱ Performance - must finish in 2000ms

Empty array means n=0, missing number is 0

💡 Consider the case when array is empty; n=0.

💡 XOR from 0 to n=0 is just 0; no elements to XOR.

💡 Return 0 when input array is empty.

Why it failed: Fails empty input; likely assumes non-empty array. Fix by handling n=0 case explicitly.

✓ Handles empty input correctly, returning 0 as missing number.

t2_02edge

Input{"nums":[0]}

Expected1

⏱ Performance - must finish in 2000ms

Array has one element 0, missing number is 1

💡 Check single element arrays carefully.

💡 XOR indices 0 to 1 and array elements to find missing.

💡 Return XOR(0,1) ^ XOR(0) = 1.

Why it failed: Fails single element input; may not handle n=1 correctly. Fix by XORing full range 0 to n.

✓ Correctly finds missing number for single element array.

t2_03edge

Input{"nums":[1]}

Expected0

⏱ Performance - must finish in 2000ms

Array has one element 1, missing number is 0

💡 Check if missing number is 0 at start of range.

💡 XOR indices 0 to 1 and array elements to find missing.

💡 Return XOR(0,1) ^ XOR(1) = 0.

Why it failed: Fails when missing number is 0; may start XOR from 1 incorrectly. Fix by including 0 in XOR range.

✓ Correctly detects missing 0 in single element array.

t3_01corner

Input{"nums":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,15]}

Expected14

⏱ Performance - must finish in 2000ms

Missing number 14 in a larger array; tests off-by-one errors

💡 Check that you XOR all indices from 0 to n inclusive.

💡 Off-by-one errors often cause missing last or middle number detection failure.

💡 Ensure XOR includes index 14 and 15 correctly.

Why it failed: Fails due to off-by-one in XOR range; fix by XORing all indices 0 to n inclusive.

✓ Correctly handles off-by-one missing number in larger array.

t3_02corner

Input{"nums":[0,0,1,2,3]}

Expected-1

⏱ Performance - must finish in 2000ms

Invalid input with duplicates; problem states distinct numbers only

💡 Input violates problem constraints; distinctness is required.

💡 Check input validation or assume input correctness.

💡 If duplicates present, XOR approach fails; ensure input validity.

Why it failed: Fails if duplicates present; XOR approach assumes distinct numbers. Validate input or document constraints.

✓ Assumes input distinctness; passes if input valid.

t3_03corner

Input{"nums":[1,2,3,4,5]}

Expected0

⏱ Performance - must finish in 2000ms

Missing number is 0 at start; tests greedy or sum-only approaches

💡 Sum approach may fail if missing number is 0.

💡 XOR approach handles missing 0 correctly.

💡 Verify XOR includes index 0 to detect missing start.

Why it failed: Fails missing 0 detection; sum approach may misinterpret. Fix by using XOR or correct sum formula.

✓ Correctly finds missing 0 at start.

t4_01performance

Input{"nums":[0,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]}

Expected99

⏱ Performance - must finish in 2000ms

n=99, O(n) XOR approach must complete within 2s

💡 Use XOR approach for O(n) time complexity.

💡 Avoid sorting or nested loops to prevent TLE.

💡 XOR all indices and array elements to find missing number efficiently.

Why it failed: TLE due to O(n log n) or O(n^2) approach; fix by using O(n) XOR method.

✓ Efficient O(n) XOR approach passes performance test.

Practice

1. Given the following code snippet, what is the output when calling findDuplicate([2, 1, 4, 3, 2])?

easy

A. 2

B. -1

C. 3

D. 1

Solution

1. Step 1: Trace initial array and i=0

   nums = [2,1,4,3,2], i=0, correct_index=1. nums[0]=2 != nums[1]=1, swap -> nums=[1,2,4,3,2]

2. Step 2: i=0 again, correct_index=0, nums[0]=1 == nums[0]=1, i=1

   i=1, correct_index=1, nums[1]=2 == nums[1]=2, i=2

3. Step 3: i=2, correct_index=3, nums[2]=4 != nums[3]=3, swap -> nums=[1,2,3,4,2]

   i=2 again

4. Step 4: i=2, correct_index=2, nums[2]=3 == nums[2]=3, i=3

   i=3, correct_index=3, nums[3]=4 == nums[3]=4, i=4

5. Step 5: i=4, correct_index=1, nums[4]=2 == nums[1]=2, i != correct_index -> duplicate found: 2

6. Final Answer:

   Option A -> Option A

7. Quick Check:

   Duplicate 2 correctly identified [OK]

Hint: Swapping places elements until duplicate found [OK]

Common Mistakes:

• Returning wrong duplicate due to off-by-one index
• Incrementing i too early causing missed duplicates
• Confusing value and index during swaps

2. Consider the following code implementing the optimal approach to find the kth missing positive number. What is the returned value when calling findKthPositive([2,3,7], 2)?

easy

A. 6

B. 5

C. 7

D. 4

Solution

1. Step 1: Trace binary search iterations

   Initial low=0, high=2 mid=1, arr[mid]=3, missing=3-(1+1)=1 < k=2 -> low=mid+1=2 mid=2, arr[mid]=7, missing=7-(2+1)=4 >= k=2 -> high=mid-1=1

2. Step 2: Compute final return value

   Return k + high + 1 = 2 + 1 + 1 = 4 Loop ends as low=2, high=1.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Binary search converges with high=1, return 4 [OK]

Hint: Calculate missing = arr[mid] - (mid+1) carefully [OK]

Common Mistakes:

• Off-by-one in missing calculation
• Returning low instead of k+high+1

3. Identify the bug in the following code snippet for finding the first missing positive integer:

medium

A. The condition in the while loop should check if nums[nums[i] - 1] != nums[i] before swapping

B. The break statement inside the while loop causes premature termination

C. The final return statement should be n instead of n + 1

D. The for loop should iterate from 1 to n instead of 0 to n-1

Solution

1. Step 1: Analyze the while loop condition and break

   The while loop runs while nums[i] is in range, but the break triggers if nums[nums[i]-1] == nums[i]. This is correct to avoid infinite swaps.

2. Step 2: Identify the subtle bug

   However, the break inside the while loop causes premature exit before all necessary swaps, leading to incorrect placement and wrong results.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Removing the break and using the while condition properly fixes the bug [OK]

Hint: Break inside while loop causes incomplete swaps [OK]

Common Mistakes:

• Misplaced break causing incomplete sorting
• Incorrect final return value
• Wrong loop boundaries

4. Suppose the input array can contain numbers from 1 to n but may have multiple duplicates and multiple missing numbers. Which of the following modifications to the cyclic sort approach correctly finds all duplicates and missing numbers efficiently?

hard

A. Modify the cyclic sort to swap only when nums[i] != nums[correct_index] and keep a separate hash set to track duplicates.

B. Run the cyclic sort as usual, then scan the array to collect all indices where nums[i] != i + 1, returning all duplicates and missing numbers.

C. Use the original cyclic sort approach repeatedly until no swaps occur, then identify duplicates and missing numbers.

D. Sort the array using built-in sort and then scan once to find all duplicates and missing numbers.

Solution

1. Step 1: Understand the problem extension

   Multiple duplicates and missing numbers require identifying all mismatches after cyclic sort.

2. Step 2: Modify cyclic sort approach

   Perform cyclic sort once to place numbers as close as possible to correct indices, then scan to collect all mismatches (duplicates and missing).

3. Step 3: Evaluate other options

   Using hash sets adds extra space; repeated cyclic sorts are inefficient; sorting is O(n log n).

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Single cyclic sort + scan finds all mismatches efficiently [OK]

Hint: Single cyclic sort pass + scan finds all mismatches [OK]

Common Mistakes:

• Trying repeated cyclic sorts wastes time
• Adding hash sets breaks O(1) space constraint
• Using sorting loses linear time advantage

5. Suppose the problem changes: the array can contain repeated numbers that can be reused infinitely many times. Which modification to the optimal approach is necessary to correctly find the first k missing positive numbers?

hard

A. Use a frequency map instead of cyclic sort to track counts and find missing numbers.

B. Keep the cyclic sort but add a visited set to avoid infinite swaps due to reuse.

C. Replace cyclic sort with a brute force check for each number from 1 upwards until k missing are found.

D. Use a priority queue to generate missing numbers dynamically considering reuse.

Solution

1. Step 1: Understand reuse impact

   Infinite reuse means cyclic sort assumptions break because numbers can appear multiple times and be reused infinitely.

2. Step 2: Identify correct approach

   A frequency map tracks counts of each number, allowing detection of missing positives even with infinite reuse.

3. Step 3: Why other options fail

   Adding visited set won't prevent infinite swaps due to reuse. Brute force is inefficient. Priority queue adds overhead without correctness guarantee.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Frequency map handles reuse correctly and efficiently [OK]

Hint: Reuse breaks cyclic sort; frequency map needed [OK]

Common Mistakes:

• Trying to patch cyclic sort with visited sets
• Assuming brute force is acceptable for large k
• Using priority queues unnecessarily