Find the Missing Number

🎯

Find the Missing Number

easyBIT_MANIPULATIONAmazonMicrosoftGoogle

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.

💡 This problem is about finding a missing element in a sequence. Beginners often struggle because they try to sort or use extra space, but bit manipulation offers a neat, constant-space solution.

📋

Problem Statement

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

💡

Example

Input"[3, 0, 1]"

Output2

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

Input"[0,1]"

Output2

Numbers 0 and 1 present, missing number is 2

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

⚠️

Common Mistakes

Using sum approach without considering integer overflow

Incorrect result or runtime error on large inputs

✅ Use XOR approach or long integer types

Off-by-one errors when calculating expected sum or iterating indices

Wrong missing number returned

✅ Carefully check range boundaries and formula usage

Sorting array but forgetting to check the last number n as missing

Fails when missing number is n

✅ Return n if no mismatch found during scan

Using XOR approach but XORing only array elements or only indices

Incorrect missing number because pairs don’t cancel

✅ XOR both indices and array elements

🧠

Brute Force (Sum and Check)

💡 This approach uses the formula for the sum of first n natural numbers to find the missing number. It’s intuitive and introduces the idea of using mathematical properties instead of searching.

Intuition

Sum all numbers from 0 to n using the formula n*(n+1)/2, then subtract the sum of array elements. The difference is the missing number.

Algorithm

1. Calculate expected sum = n*(n+1)/2
2. Calculate actual sum by adding all elements in the array
3. Subtract actual sum from expected sum
4. Return the difference as the missing number

💡 This algorithm is simple but requires understanding the sum formula and why subtracting the actual sum reveals the missing number.

</>

Code

def missingNumber(nums):
    n = len(nums)
    expected_sum = n * (n + 1) // 2
    actual_sum = 0
    for num in nums:
        actual_sum += num
    return expected_sum - actual_sum

# Driver code
if __name__ == '__main__':
    print(missingNumber([3,0,1]))  # Output: 2

Line Notes

n = len(nums)Determine the range size n from the array length

expected_sum = n * (n + 1) // 2Calculate sum of numbers from 0 to n using formula

for num in nums:Iterate through array to sum actual elements

return expected_sum - actual_sumDifference is the missing number

public class Solution {
    public static int missingNumber(int[] nums) {
        int n = nums.length;
        int expectedSum = n * (n + 1) / 2;
        int actualSum = 0;
        for (int num : nums) {
            actualSum += num;
        }
        return expectedSum - actualSum;
    }

    public static void main(String[] args) {
        System.out.println(missingNumber(new int[]{3,0,1})); // Output: 2
    }
}

Line Notes

int n = nums.length;Get the size of the array to know n

int expectedSum = n * (n + 1) / 2;Compute sum of 0 to n using formula

for (int num : nums) {Sum all elements in the array

return expectedSum - actualSum;Return the missing number by difference

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

int missingNumber(vector<int>& nums) {
    int n = nums.size();
    int expectedSum = n * (n + 1) / 2;
    int actualSum = 0;
    for (int num : nums) {
        actualSum += num;
    }
    return expectedSum - actualSum;
}

int main() {
    vector<int> nums = {3,0,1};
    cout << missingNumber(nums) << endl; // Output: 2
    return 0;
}

Line Notes

int n = nums.size();Determine n from vector size

int expectedSum = n * (n + 1) / 2;Calculate expected sum using formula

for (int num : nums) {Sum all elements in the vector

return expectedSum - actualSum;Return missing number as difference

function missingNumber(nums) {
    const n = nums.length;
    const expectedSum = n * (n + 1) / 2;
    let actualSum = 0;
    for (const num of nums) {
        actualSum += num;
    }
    return expectedSum - actualSum;
}

// Test
console.log(missingNumber([3,0,1])); // Output: 2

Line Notes

const n = nums.length;Get the length of the array

const expectedSum = n * (n + 1) / 2;Calculate sum of 0 to n

for (const num of nums) {Sum all numbers in the array

return expectedSum - actualSum;Return the missing number

⏱

Complexity

TimeO(n)

SpaceO(1)

We sum all elements once, so linear time. Only a few variables used, so constant space.

💡 For n=100000, this means 100000 additions, which is efficient enough for interviews.

Interview Verdict: Accepted

This approach passes all tests but can overflow with very large n or sums, so better methods exist.

🧠

XOR Approach (Optimal Bit Manipulation)

💡 This approach uses XOR properties to find the missing number without risk of overflow and with constant space. It introduces bit manipulation concepts useful in many problems.

Intuition

XOR all indices and XOR all numbers in the array. Since XOR of a number with itself is zero, all paired numbers cancel out, leaving the missing number.

Algorithm

1. Initialize a variable xor_all to 0
2. XOR xor_all with every index from 0 to n
3. XOR xor_all with every element in the array
4. Return xor_all as the missing number

💡 The key is understanding XOR cancels duplicates, so only the missing number remains after all XOR operations.

</>

Code

def missingNumber(nums):
    n = len(nums)
    xor_all = 0
    for i in range(n + 1):
        xor_all ^= i
    for num in nums:
        xor_all ^= num
    return xor_all

# Driver code
if __name__ == '__main__':
    print(missingNumber([3,0,1]))  # Output: 2

Line Notes

xor_all = 0Initialize XOR accumulator

for i in range(n + 1):XOR all indices from 0 to n

for num in nums:XOR all numbers in the array

return xor_allRemaining value is the missing number

public class Solution {
    public static int missingNumber(int[] nums) {
        int n = nums.length;
        int xorAll = 0;
        for (int i = 0; i <= n; i++) {
            xorAll ^= i;
        }
        for (int num : nums) {
            xorAll ^= num;
        }
        return xorAll;
    }

    public static void main(String[] args) {
        System.out.println(missingNumber(new int[]{3,0,1})); // Output: 2
    }
}

Line Notes

int xorAll = 0;Initialize XOR accumulator

for (int i = 0; i <= n; i++) {XOR all indices from 0 to n

for (int num : nums) {XOR all elements in the array

return xorAll;Return the missing number after cancellations

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

int missingNumber(vector<int>& nums) {
    int n = nums.size();
    int xorAll = 0;
    for (int i = 0; i <= n; i++) {
        xorAll ^= i;
    }
    for (int num : nums) {
        xorAll ^= num;
    }
    return xorAll;
}

int main() {
    vector<int> nums = {3,0,1};
    cout << missingNumber(nums) << endl; // Output: 2
    return 0;
}

Line Notes

int xorAll = 0;Initialize XOR accumulator

for (int i = 0; i <= n; i++) {XOR all indices including n

for (int num : nums) {XOR all numbers in the vector

return xorAll;Return the missing number after XOR cancellations

function missingNumber(nums) {
    const n = nums.length;
    let xorAll = 0;
    for (let i = 0; i <= n; i++) {
        xorAll ^= i;
    }
    for (const num of nums) {
        xorAll ^= num;
    }
    return xorAll;
}

// Test
console.log(missingNumber([3,0,1])); // Output: 2

Line Notes

let xorAll = 0;Initialize XOR accumulator

for (let i = 0; i <= n; i++) {XOR all indices from 0 to n

for (const num of nums) {XOR all elements in the array

return xorAll;Return the missing number after XOR operations

⏱

Complexity

TimeO(n)

SpaceO(1)

We iterate twice over n elements (indices and array), so linear time. Only a few variables used, so constant space.

💡 For n=100000, this means about 200000 XOR operations, which is very efficient.

Interview Verdict: Accepted

This is the preferred approach in interviews due to no overflow risk and constant space.

🧠

Sorting and Linear Scan

💡 This approach sorts the array and then scans to find the missing number. It’s intuitive but less optimal and uses extra time due to sorting.

Intuition

Sort the array so numbers are in order, then check each index to find where the number does not match the index, indicating the missing number.

Algorithm

1. Sort the array
2. Iterate through the array and compare each element with its index
3. If element != index, return index as missing number
4. If all match, return n as missing number

💡 This algorithm is easy to understand but less efficient due to sorting overhead.

</>

Code

def missingNumber(nums):
    nums.sort()
    for i, num in enumerate(nums):
        if i != num:
            return i
    return len(nums)

# Driver code
if __name__ == '__main__':
    print(missingNumber([3,0,1]))  # Output: 2

Line Notes

nums.sort()Sort the array to bring numbers in order

for i, num in enumerate(nums):Iterate with index and value

if i != num:Detect mismatch between index and number

return len(nums)If no mismatch, missing number is n

import java.util.Arrays;
public class Solution {
    public static int missingNumber(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i) {
                return i;
            }
        }
        return nums.length;
    }

    public static void main(String[] args) {
        System.out.println(missingNumber(new int[]{3,0,1})); // Output: 2
    }
}

Line Notes

Arrays.sort(nums);Sort the array in ascending order

for (int i = 0; i < nums.length; i++) {Iterate over indices

if (nums[i] != i) {Check if number matches index

return nums.length;If all match, missing number is n

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

int missingNumber(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] != i) {
            return i;
        }
    }
    return nums.size();
}

int main() {
    vector<int> nums = {3,0,1};
    cout << missingNumber(nums) << endl; // Output: 2
    return 0;
}

Line Notes

sort(nums.begin(), nums.end());Sort the vector in ascending order

for (int i = 0; i < nums.size(); i++) {Iterate over indices

if (nums[i] != i) {Check for mismatch between index and value

return nums.size();Return n if no mismatch found

function missingNumber(nums) {
    nums.sort((a, b) => a - b);
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== i) {
            return i;
        }
    }
    return nums.length;
}

// Test
console.log(missingNumber([3,0,1])); // Output: 2

Line Notes

nums.sort((a, b) => a - b);Sort array numerically ascending

for (let i = 0; i < nums.length; i++) {Iterate over indices

if (nums[i] !== i) {Detect mismatch between index and value

return nums.length;Return n if no mismatch found

⏱

Complexity

TimeO(n log n)

SpaceO(1) or O(n) depending on sorting implementation

Sorting dominates time complexity, linear scan is O(n). Space depends on sort implementation.

💡 For n=100000, sorting takes about 1.5 million operations, slower than linear methods.

Interview Verdict: Accepted but less optimal

This approach works but is not preferred due to higher time complexity.

📊

All Approaches - One-Glance Tradeoffs

💡 Use XOR approach in 95% of interviews for its optimal time, space, and no overflow risk.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Sum Formula)	O(n)	O(1)	No	N/A	Good to mention for intuition, but beware overflow
2. XOR Approach	O(n)	O(1)	No	N/A	Preferred approach to code in interviews
3. Sorting and Linear Scan	O(n log n)	O(1) or O(n)	No	N/A	Mention as fallback, avoid coding unless asked

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start with brute force, then optimize. Practice coding and explaining each approach.

How to Present

Step 1: Clarify problem constraints and examplesStep 2: Present brute force sum formula approachStep 3: Discuss limitations of sum approach (overflow)Step 4: Introduce XOR approach as optimalStep 5: Mention sorting as fallbackStep 6: Code chosen approach and test edge cases

Time Allocation

Clarify: 2min → Approach: 5min → Code: 8min → Test: 5min. Total ~20min

What the Interviewer Tests

Interviewer tests understanding of bit manipulation, handling edge cases, and ability to optimize from naive to optimal solutions.

Common Follow-ups

• What if multiple numbers are missing? → Use different methods like hash sets or frequency arrays
• Can you solve without extra space? → XOR approach is constant space

💡 Follow-ups test if you can generalize or optimize further beyond the base problem.

🔍

Pattern Recognition

When to Use

1) Input is a sequence with one missing element, 2) Numbers range from 0 to n, 3) Need constant space, 4) Want linear time solution

Signature Phrases

missing number from 0 to narray of distinct numbersfind the one missing

NOT This Pattern When

Problems requiring sum of subsets or multiple missing numbers without distinctness

Similar Problems

Single Number - uses XOR to find unique elementFind All Missing Numbers - extension with multiple missingMissing Number II - variant with duplicates

Practice

1. You are given an unsorted array of integers that may contain duplicates and negative numbers. Your task is to find the first k positive integers missing from the array. Which algorithmic approach guarantees an optimal time complexity while handling duplicates and negatives correctly?

easy

A. Sort the array and then scan sequentially to find missing positive numbers.

B. Use dynamic programming to build a table of present and missing numbers.

C. Use cyclic sort to place numbers in their correct indices, then identify missing positives and track extras with a boolean array.

D. Use a max-heap to extract the smallest missing positive numbers one by one.

Solution

1. Step 1: Understand problem constraints

   The array may contain duplicates and negative numbers, so naive sorting or heap approaches may be inefficient or incorrect.

2. Step 2: Identify optimal approach

   Cyclic sort places numbers in their correct indices in O(n) time, ignoring negatives and duplicates. Then, a boolean array tracks extra numbers beyond the array length to find missing positives efficiently.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Cyclic sort + boolean array handles duplicates and negatives optimally [OK]

Hint: Cyclic sort handles duplicates and negatives efficiently [OK]

Common Mistakes:

• Assuming sorting is always optimal
• Using heaps which add unnecessary overhead
• Confusing DP with presence tracking

2. Given the following code snippet implementing the optimal cyclic sort approach, what is the returned output when the input is [3, 4, -1, 1]?

def find_smallest_missing_range(nums):
    n = len(nums)
    i = 0
    while i < n:
        correct_pos = nums[i] - 1
        if 1 <= nums[i] <= n and nums[i] != nums[correct_pos]:
            nums[i], nums[correct_pos] = nums[correct_pos], nums[i]
        else:
            i += 1
    start = 1
    for i in range(n):
        if nums[i] != i + 1:
            start = i + 1
            break
    else:
        return [n + 1, n + 1]
    end = start
    while end <= n and nums[end - 1] != end:
        end += 1
    return [start, end - 1]

print(find_smallest_missing_range([3, 4, -1, 1]))

easy

A. [4, 4]

B. [1, 1]

C. [2, 2]

D. [2, 3]

Solution

1. Step 1: Trace cyclic sort swaps

   Initial array: [3,4,-1,1] - i=0: nums[0]=3, correct_pos=2; swap nums[0] and nums[2] -> [-1,4,3,1] - i=0: nums[0]=-1 (not in 1..n), i++ -> i=1 - i=1: nums[1]=4, correct_pos=3; swap nums[1] and nums[3] -> [-1,1,3,4] - i=1: nums[1]=1, correct_pos=0; swap nums[1] and nums[0] -> [1,-1,3,4] - i=1: nums[1]=-1 (not in 1..n), i++ -> i=2 - i=2: nums[2]=3, correct_pos=2; already correct, i++ -> i=3 - i=3: nums[3]=4, correct_pos=3; already correct, i++ -> i=4 (end)

2. Step 2: Find smallest missing positive range

   Array after sorting: [1, -1, 3, 4] Check indices: - i=0: nums[0]=1 correct - i=1: nums[1]=-1 != 2 -> start=2 Find end: - end=2: nums[1]=-1 != 2 -> end=3 - end=3: nums[2]=3 == 3 -> stop Return [2, 2]

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches expected missing smallest positive range [2, 2] [OK]

Hint: Trace swaps carefully to find final array state [OK]

Common Mistakes:

• Off-by-one in start or end calculation
• Ignoring negative numbers during swaps

3. Identify the bug in the following cyclic sort implementation that aims to place numbers 1 to n at their correct indices:

def cyclic_sort_buggy(arr):
    i = 0
    n = len(arr)
    while i < n:
        correct_index = arr[i] - 1
        if arr[i] != arr[correct_index]:
            arr[i], arr[correct_index] = arr[correct_index], arr[i]
        i += 1
    return arr

What is the issue causing incorrect output or infinite loops?

medium

A. Incrementing i even after a swap causes some elements to remain misplaced.

B. Not checking if arr[i] is within 1 to n causes index errors.

C. Swapping elements without a temporary variable causes data loss.

D. Using a while loop instead of a for loop causes infinite loops.

Solution

1. Step 1: Analyze loop increment

   i is incremented unconditionally even after swapping, skipping re-check of swapped element.

2. Step 2: Understand impact

   Elements swapped in may still be misplaced but are not checked again, causing incorrect final array or infinite loops.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Increment i only when no swap occurs to ensure correct placement [OK]

Hint: Only increment index if no swap occurs [OK]

Common Mistakes:

• Always incrementing index after swap
• Ignoring index bounds
• Misusing loop constructs

4. What is the time complexity of the optimal cyclic sort approach for finding all missing numbers in an array of size n, and why?

medium

A. O(n log n) because of the sorting-like swaps

B. O(n^2) because nested swaps can occur repeatedly for duplicates

C. O(n) because each element is swapped at most once to its correct position

D. O(n) but with O(n) auxiliary space for tracking swaps

Solution

1. Step 1: Analyze the while loop behavior

   Each number is swapped at most once to its correct index, so total swaps ≤ n.

2. Step 2: Confirm no nested repeated swaps

   Duplicates cause skipping increments but do not cause repeated swaps for the same element, so total operations remain linear.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Linear time due to single pass and limited swaps [OK]

Hint: Each element swaps at most once [OK]

Common Mistakes:

• Assuming sorting cost O(n log n)
• Thinking duplicates cause quadratic swaps
• Confusing auxiliary space with time

5. What is the time complexity of the optimal cyclic sort approach to find the duplicate and missing numbers in an array of size n, and why?

medium

A. O(n) because each element is swapped at most once to its correct position

B. O(n) but with O(n) extra space for auxiliary arrays

C. O(n^2) because of nested loops inside the while loop

D. O(n log n) because of sorting the array

Solution

1. Step 1: Identify the main loop behavior

   The while loop swaps elements to their correct positions. Each swap places at least one element correctly, so total swaps ≤ n.

2. Step 2: Analyze time complexity

   Since each element is moved at most once, the total operations are proportional to n, resulting in O(n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time due to limited swaps and single pass [OK]

Hint: Each element moves at most once -> O(n) time [OK]

Common Mistakes:

• Assuming sorting is involved -> O(n log n)
• Mistaking nested loops inside while as O(n^2)
• Forgetting swaps reduce total operations