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 Python code to generate Gray code sequence, what is the output of grayCode(2)?

easy

A. [1, 0, 3, 2]

B. [0, 1, 2, 3]

C. [0, 1, 3, 2]

D. [0, 2, 3, 1]

Solution

1. Step 1: Compute values for i in range(4)

   For i=0: 0 ^ (0>>1)=0; i=1: 1 ^ (0)=1; i=2: 2 ^ (1)=2^1=3; i=3: 3 ^ (1)=3^1=2

2. Step 2: Collect results in list

   The sequence is [0, 1, 3, 2], which matches the Gray code property.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Manual XOR calculation confirms the sequence [0,1,3,2] [OK]

Hint: XOR with right-shifted index generates Gray code directly [OK]

Common Mistakes:

• Confusing the order of XOR and shift
• Off-by-one errors in range leading to missing or extra elements
• Misinterpreting the output as binary numbers instead of integers

2. What is the time complexity of the XOR partitioning approach to find two missing numbers from 1 to n given an array of size n-2?

medium

A. O(n²) due to nested loops over the range and array

B. O(n) because it iterates over the range and array a constant number of times

C. O(n log n) due to bitwise operations on each element

D. O(1) since XOR operations are constant time

Solution

1. Step 1: Identify loops in the algorithm

   The algorithm iterates over the range 1 to n once and over the input array once, each in separate loops.

2. Step 2: Analyze operations inside loops

   Each iteration performs constant time XOR and bitwise operations, so total time is proportional to n.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two linear passes -> O(n) time [OK]

Hint: Count loops and operations per iteration carefully [OK]

Common Mistakes:

• Assuming nested loops cause O(n²)
• Thinking bitwise ops add log n factor
• Confusing constant time with O(1) overall

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

1. Step 1: Identify the operation cost

   The operation n & (n - 1) runs in constant time on fixed-width integers, such as 32-bit integers.

2. Step 2: Consider input size in bits

   Since the integer size is fixed (32 bits), the operation is O(1) constant time.

3. Final Answer:

   Option C -> Option C

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

4. The following code attempts to reverse bits of a 32-bit unsigned integer using divide and conquer masks:

def reverseBits(n: int) -> int:
    n = ((n >> 1) & 0x55555555) | ((n & 0x55555555) << 1)
    n = ((n >> 2) & 0x33333333) | ((n & 0x33333333) << 2)
    n = ((n >> 4) & 0x0f0f0f0f) | ((n & 0x0f0f0f0f) << 4)
    n = ((n >> 8) & 0x00ff00ff) | ((n & 0x00ff00ff) << 8)
    n = (n >> 16) | (n << 16)  # Bug here: missing mask
    return n

What is the bug in this code?

medium

A. Line 4: The mask 0x00ff00ff is incorrect for byte swapping.

B. Line 1: Incorrect mask 0x55555555 used for swapping bits.

C. Line 3: Left shift by 4 bits should be right shift.

D. Line 5: Missing mask after shifting left and right by 16 bits, causing overflow beyond 32 bits.

Solution

1. Step 1: Identify the last step

   The last line shifts bits by 16 left and right but does not mask the result to 32 bits.

2. Step 2: Understand impact

   Without masking, bits can overflow beyond 32 bits, causing incorrect reversal results.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Masking with 0xffffffff fixes overflow [OK]

Hint: Always mask after large shifts to keep 32-bit result [OK]

Common Mistakes:

• Forgetting to mask after left shifts
• Misusing masks in earlier steps
• Confusing left and right shifts

5. What is the time complexity of the optimal UTF-8 validation algorithm that uses a single pass with a continuation byte counter over an input array of length n?

medium

A. O(n) because each byte is processed exactly once with constant time bitwise checks

B. O(n^2) because nested checks are performed for each byte's continuation bytes

C. O(n log n) due to bitwise operations on each byte

D. O(1) since bitwise operations are constant time regardless of input size

Solution

1. Step 1: Identify the number of iterations

   The algorithm iterates over each byte exactly once, so the outer loop runs n times.

2. Step 2: Analyze operations per iteration

   Each iteration performs a fixed number of bitwise operations and conditional checks, all O(1).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass with constant work per byte -> O(n) time [OK]

Hint: Single pass with constant work per byte -> O(n) time [OK]

Common Mistakes:

• Confusing bitwise ops as log n
• Assuming nested loops cause O(n^2)