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

Solution

1. Step 1: Trace countBits for i=0 to 3

   i=0: binary 0, count=0; i=1: binary 1, count=1; i=2: binary 10, count=1; i=3: binary 11, count=2.

2. Step 2: Confirm final result list

   Result list is [0, 1, 1, 2].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Matches manual bit count for each number [OK]

Hint: Count bits by clearing least significant set bit [OK]

Common Mistakes:

• Off-by-one in range
• Miscounting bits for 2 or 3
• Confusing count initialization

2. Given the following code, what is the value of ones after processing the input [2, 2, 3, 2]?

easy

A. 3

B. 0

C. 2

D. 1

Solution

1. Step 1: Trace variable updates for each num

   After processing 2,2,3,2, the variable 'ones' ends up holding the unique number 3.

2. Step 2: Confirm final return value

   The function returns 'ones' which is 3, the single number appearing once.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Output matches expected unique element 3 [OK]

Hint: Final 'ones' holds the unique element after all iterations [OK]

Common Mistakes:

• Confusing 'ones' and 'twos' variables
• Off-by-one iteration errors

3. The following code attempts to generate all permutations of n elements using bitmask DP with iterative tabulation. Identify the line containing the subtle bug that causes dp[(1 << n) - 1] to remain empty.

def generate_permutations_iterative(n):
    dp = [[] for _ in range(1 << n)]
    # Missing initialization of dp[0]
    for mask in range(1 << n):
        for i in range(n):
            if not (mask & (1 << i)):
                for perm in dp[mask]:
                    dp[mask | (1 << i)].append(perm + [i])
    return dp[(1 << n) - 1]

medium

A. Line 2: dp initialization with empty lists

B. Line 7: Incorrect bitmask check condition

C. Line 5: Incorrect mask iteration range

D. Line 3: Missing dp[0] = [[]] initialization

Solution

1. Step 1: Check base case initialization

   dp[0] must be initialized to contain an empty permutation to start building others.

2. Step 2: Identify impact of missing dp[0] initialization

   Without dp[0] = [[]], dp[mask] lists remain empty, so no permutations are generated.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Adding dp[0] = [[]] fixes the empty result issue [OK]

Hint: dp[0] must be initialized to start building permutations [OK]

Common Mistakes:

• Forgetting to initialize dp[0]
• Misunderstanding bitmask iteration order

4. What is the time complexity of generating an n-bit Gray code sequence using the optimal bitwise formula [i ^ (i >> 1) for i in range(1 << n)]?

medium

A. O(n)

B. O((2^n)!)

C. O(n * 2^n)

D. O(2^n)

Solution

1. Step 1: Analyze the loop iteration count

   The list comprehension iterates over all integers from 0 to 2^n - 1, so 2^n iterations.

2. Step 2: Analyze work per iteration

   Each iteration performs constant time bitwise operations (XOR and right shift), so O(1) per iteration.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Total time is proportional to 2^n, not multiplied by n or factorial [OK]

Hint: Loop runs 2^n times with O(1) work each [OK]

Common Mistakes:

• Confusing n with 2^n and claiming O(n)
• Assuming bitwise operations cost O(n)
• Mistaking factorial complexity from brute force backtracking

5. Consider the following buggy UTF-8 validation code snippet. Which line contains the subtle bug that can cause invalid UTF-8 sequences to be accepted as valid?

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:
            # Bug: missing check for continuation byte pattern
            remaining -= 1
    return remaining == 0

medium

A. Line with 'if remaining == 0:' condition

B. Line with 'remaining -= 1' inside else block

C. Line with 'if (byte >> 5) == 0b110:' condition

D. Line with 'return remaining == 0' at the end

Solution

1. Step 1: Identify where continuation bytes are checked

   The else block handles continuation bytes, which must start with bits '10' (binary 0b10).

2. Step 2: Locate missing validation

   The code decrements remaining without checking if the byte starts with '10', allowing invalid bytes to pass.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing continuation byte pattern check causes acceptance of invalid sequences [OK]

Hint: Check continuation bytes start with '10' before decrementing [OK]

Common Mistakes:

• Forgetting continuation byte pattern check
• Miscounting remaining bytes