Missing Number

Find the missing number in an array containing n distinct numbers taken from 0, 1, 2, ..., n.

Language Selection

Choose your preferred programming language

Showing: Python

Missing Number

Problem Statement

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Examples

Example 1:

Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 
2 is the missing number in the range since it does not appear in nums.

Example 2:

Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 
2 is the missing number in the range since it does not appear in nums.

Example 3:

Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 
8 is the missing number in the range since it does not appear in nums.

Constraints

  • n == nums.length
  • 1 <= n <= 10^4
  • 0 <= nums[i] <= n
  • All the numbers of nums are unique.

Approach 1: XOR Bit Manipulation (Optimal)

Algorithm

Use XOR properties: XOR all numbers from 0 to n with all numbers in the array. The missing number will be the result.

Steps:

  1. XOR all numbers from 0 to n
  2. XOR all numbers in the array
  3. The result is the missing number

Implementation

Python:

def missingNumber(nums):
    """
    Find missing number using XOR
    Time: O(n)
    Space: O(1)
    """
    n = len(nums)
    result = 0
    
    # XOR all numbers from 0 to n
    for i in range(n + 1):
        result ^= i
    
    # XOR all numbers in array
    for num in nums:
        result ^= num
    
    return result

# One-liner version
def missingNumber_oneliner(nums):
    n = len(nums)
    return reduce(lambda x, y: x ^ y, nums + list(range(n + 1)))

Java:

class Solution {
    /**
     * Find missing number using XOR
     * Time: O(n)
     * Space: O(1)
     */
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int result = 0;
        
        // XOR all numbers from 0 to n
        for (int i = 0; i <= n; i++) {
            result ^= i;
        }
        
        // XOR all numbers in array
        for (int num : nums) {
            result ^= num;
        }
        
        return result;
    }
}

Go:

func missingNumber(nums []int) int {
    /**
     * Find missing number using XOR
     * Time: O(n)
     * Space: O(1)
     */
    n := len(nums)
    result := 0
    
    // XOR all numbers from 0 to n
    for i := 0; i <= n; i++ {
        result ^= i
    }
    
    // XOR all numbers in array
    for _, num := range nums {
        result ^= num
    }
    
    return result
}

JavaScript:

/**
 * Find missing number using XOR
 * Time: O(n)
 * Space: O(1)
 */
function missingNumber(nums) {
    const n = nums.length;
    let result = 0;
    
    // XOR all numbers from 0 to n
    for (let i = 0; i <= n; i++) {
        result ^= i;
    }
    
    // XOR all numbers in array
    for (const num of nums) {
        result ^= num;
    }
    
    return result;
}

// One-liner version
const missingNumberOneLiner = nums => {
    const n = nums.length;
    return [...nums, ...Array.from({length: n + 1}, (_, i) => i)]
        .reduce((acc, num) => acc ^ num, 0);
};

C#:

public class Solution {
    /// <summary>
    /// Find missing number using XOR
    /// Time: O(n)
    /// Space: O(1)
    /// </summary>
    public int MissingNumber(int[] nums) {
        int n = nums.Length;
        int result = 0;
        
        // XOR all numbers from 0 to n
        for (int i = 0; i <= n; i++) {
            result ^= i;
        }
        
        // XOR all numbers in array
        foreach (int num in nums) {
            result ^= num;
        }
        
        return result;
    }
}

Complexity Analysis

  • Time Complexity: O(n) - Two passes through array
  • Space Complexity: O(1) - Only using constant extra space

Approach 2: Mathematical Formula (Gauss Formula)

Algorithm

Use the mathematical formula: sum(0 to n) - sum(array) = missing_number

Steps:

  1. Calculate expected sum using Gauss formula: n * (n + 1) / 2
  2. Calculate actual sum of array elements
  3. Return the difference

Implementation

Python:

def missingNumber_math(nums):
    """
    Find missing number using mathematical formula
    Time: O(n)
    Space: O(1)
    """
    n = len(nums)
    expected_sum = n * (n + 1) // 2
    actual_sum = sum(nums)
    return expected_sum - actual_sum

Java:

class Solution {
    /**
     * Find missing number using mathematical formula
     * Time: O(n)
     * Space: O(1)
     */
    public int missingNumberMath(int[] nums) {
        int n = nums.length;
        int expectedSum = n * (n + 1) / 2;
        
        int actualSum = 0;
        for (int num : nums) {
            actualSum += num;
        }
        
        return expectedSum - actualSum;
    }
}

Go:

func missingNumberMath(nums []int) int {
    /**
     * Find missing number using mathematical formula
     * Time: O(n)
     * Space: O(1)
     */
    n := len(nums)
    expectedSum := n * (n + 1) / 2
    
    actualSum := 0
    for _, num := range nums {
        actualSum += num
    }
    
    return expectedSum - actualSum
}

JavaScript:

/**
 * Find missing number using mathematical formula
 * Time: O(n)
 * Space: O(1)
 */
function missingNumberMath(nums) {
    const n = nums.length;
    const expectedSum = n * (n + 1) / 2;
    const actualSum = nums.reduce((sum, num) => sum + num, 0);
    
    return expectedSum - actualSum;
}

C#:

public class Solution {
    /// <summary>
    /// Find missing number using mathematical formula
    /// Time: O(n)
    /// Space: O(1)
    /// </summary>
    public int MissingNumberMath(int[] nums) {
        int n = nums.Length;
        int expectedSum = n * (n + 1) / 2;
        int actualSum = nums.Sum();
        
        return expectedSum - actualSum;
    }
}

Complexity Analysis

  • Time Complexity: O(n) - Single pass to calculate sum
  • Space Complexity: O(1) - Only using constant extra space

Approach 3: Hash Set (Alternative)

Algorithm

Use a hash set to store all numbers from 0 to n, then find which one is missing.

Steps:

  1. Create a set with all numbers from 0 to n
  2. Remove numbers that exist in the array
  3. Return the remaining number

Implementation

Python:

def missingNumber_hashset(nums):
    """
    Find missing number using hash set
    Time: O(n)
    Space: O(n)
    """
    n = len(nums)
    num_set = set(range(n + 1))
    
    for num in nums:
        num_set.remove(num)
    
    return num_set.pop()

Java:

import java.util.HashSet;
import java.util.Set;

class Solution {
    /**
     * Find missing number using hash set
     * Time: O(n)
     * Space: O(n)
     */
    public int missingNumberHashSet(int[] nums) {
        int n = nums.length;
        Set<Integer> numSet = new HashSet<>();
        
        // Add all numbers from 0 to n
        for (int i = 0; i <= n; i++) {
            numSet.add(i);
        }
        
        // Remove numbers that exist in array
        for (int num : nums) {
            numSet.remove(num);
        }
        
        // Return the remaining number
        return numSet.iterator().next();
    }
}

Go:

func missingNumberHashSet(nums []int) int {
    /**
     * Find missing number using hash set
     * Time: O(n)
     * Space: O(n)
     */
    n := len(nums)
    numSet := make(map[int]bool)
    
    // Add all numbers from 0 to n
    for i := 0; i <= n; i++ {
        numSet[i] = true
    }
    
    // Remove numbers that exist in array
    for _, num := range nums {
        delete(numSet, num)
    }
    
    // Return the remaining number
    for num := range numSet {
        return num
    }
    
    return -1 // Should never reach here
}

JavaScript:

/**
 * Find missing number using hash set
 * Time: O(n)
 * Space: O(n)
 */
function missingNumberHashSet(nums) {
    const n = nums.length;
    const numSet = new Set();
    
    // Add all numbers from 0 to n
    for (let i = 0; i <= n; i++) {
        numSet.add(i);
    }
    
    // Remove numbers that exist in array
    for (const num of nums) {
        numSet.delete(num);
    }
    
    // Return the remaining number
    return numSet.values().next().value;
}

C#:

using System.Collections.Generic;
using System.Linq;

public class Solution {
    /// <summary>
    /// Find missing number using hash set
    /// Time: O(n)
    /// Space: O(n)
    /// </summary>
    public int MissingNumberHashSet(int[] nums) {
        int n = nums.Length;
        var numSet = new HashSet<int>(Enumerable.Range(0, n + 1));
        
        // Remove numbers that exist in array
        foreach (int num in nums) {
            numSet.Remove(num);
        }
        
        // Return the remaining number
        return numSet.First();
    }
}

Complexity Analysis

  • Time Complexity: O(n) - Single pass through array
  • Space Complexity: O(n) - Hash set storage

Approach 4: Sorting (Alternative)

Algorithm

Sort the array and find the first number that doesn’t match its index.

Steps:

  1. Sort the array
  2. Check if each index matches the value
  3. Return the first mismatch

Implementation

Python:

def missingNumber_sorting(nums):
    """
    Find missing number using sorting
    Time: O(n log n)
    Space: O(1) if sorting in-place
    """
    nums.sort()
    
    # Check if 0 is missing
    if nums[0] != 0:
        return 0
    
    # Check if n is missing
    if nums[-1] != len(nums):
        return len(nums)
    
    # Check middle numbers
    for i in range(1, len(nums)):
        if nums[i] != nums[i-1] + 1:
            return nums[i-1] + 1
    
    return -1  # Should never reach here

Java:

import java.util.Arrays;

class Solution {
    /**
     * Find missing number using sorting
     * Time: O(n log n)
     * Space: O(1) if sorting in-place
     */
    public int missingNumberSorting(int[] nums) {
        Arrays.sort(nums);
        
        // Check if 0 is missing
        if (nums[0] != 0) {
            return 0;
        }
        
        // Check if n is missing
        if (nums[nums.length - 1] != nums.length) {
            return nums.length;
        }
        
        // Check middle numbers
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i - 1] + 1) {
                return nums[i - 1] + 1;
            }
        }
        
        return -1; // Should never reach here
    }
}

Go:

import "sort"

func missingNumberSorting(nums []int) int {
    /**
     * Find missing number using sorting
     * Time: O(n log n)
     * Space: O(1) if sorting in-place
     */
    sort.Ints(nums)
    
    // Check if 0 is missing
    if nums[0] != 0 {
        return 0
    }
    
    // Check if n is missing
    if nums[len(nums)-1] != len(nums) {
        return len(nums)
    }
    
    // Check middle numbers
    for i := 1; i < len(nums); i++ {
        if nums[i] != nums[i-1]+1 {
            return nums[i-1] + 1
        }
    }
    
    return -1 // Should never reach here
}

JavaScript:

/**
 * Find missing number using sorting
 * Time: O(n log n)
 * Space: O(1) if sorting in-place
 */
function missingNumberSorting(nums) {
    nums.sort((a, b) => a - b);
    
    // Check if 0 is missing
    if (nums[0] !== 0) {
        return 0;
    }
    
    // Check if n is missing
    if (nums[nums.length - 1] !== nums.length) {
        return nums.length;
    }
    
    // Check middle numbers
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] !== nums[i - 1] + 1) {
            return nums[i - 1] + 1;
        }
    }
    
    return -1; // Should never reach here
}

C#:

public class Solution {
    /// <summary>
    /// Find missing number using sorting
    /// Time: O(n log n)
    /// Space: O(1) if sorting in-place
    /// </summary>
    public int MissingNumberSorting(int[] nums) {
        Array.Sort(nums);
        
        // Check if 0 is missing
        if (nums[0] != 0) {
            return 0;
        }
        
        // Check if n is missing
        if (nums[nums.Length - 1] != nums.Length) {
            return nums.Length;
        }
        
        // Check middle numbers
        for (int i = 1; i < nums.Length; i++) {
            if (nums[i] != nums[i - 1] + 1) {
                return nums[i - 1] + 1;
            }
        }
        
        return -1; // Should never reach here
    }
}

Complexity Analysis

  • Time Complexity: O(n log n) - Due to sorting
  • Space Complexity: O(1) - If sorting in-place

Key Insights

  1. XOR Properties: a ^ a = 0, a ^ 0 = a
  2. Gauss Formula: Sum of 0 to n = n * (n + 1) / 2
  3. Mathematical Approach: Most intuitive and efficient
  4. Space Optimization: XOR and math approaches use O(1) space
  5. Range Constraint: Numbers are in range [0, n] with exactly one missing

Edge Cases

  1. Missing 0: Array starts with 1
  2. Missing n: Array ends with n-1
  3. Single Element: Array with one element
  4. Two Elements: Array with two elements
  5. Large n: Handle large values efficiently

Test Cases

def test_missingNumber():
    # Basic cases
    assert missingNumber([3, 0, 1]) == 2
    assert missingNumber([0, 1]) == 2
    assert missingNumber([9, 6, 4, 2, 3, 5, 7, 0, 1]) == 8
    
    # Edge cases
    assert missingNumber([1]) == 0
    assert missingNumber([0]) == 1
    assert missingNumber([1, 2]) == 0
    assert missingNumber([0, 1]) == 2
    
    # Test all approaches
    nums = [3, 0, 1]
    assert missingNumber(nums) == missingNumber_math(nums)
    assert missingNumber(nums) == missingNumber_hashset(nums)
    
    print("All tests passed!")

test_missingNumber()

Follow-up Questions

  1. Missing Number II: Find two missing numbers in range [1, n]?
  2. First Missing Positive: Find first missing positive integer?
  3. Find All Missing: Find all missing numbers in range [1, n]?
  4. Duplicate and Missing: Find duplicate and missing numbers?
  5. Missing Number in Sorted Array: Find missing number in sorted array?

Common Mistakes

  1. Off-by-One Error: Incorrect range calculation
  2. Integer Overflow: Not handling large sums
  3. Wrong Formula: Incorrect Gauss formula implementation
  4. Edge Cases: Not handling missing 0 or n
  5. Space Complexity: Using O(n) space when O(1) is possible

Interview Tips

  1. Start with Math: Most intuitive approach
  2. Mention XOR: Show bit manipulation knowledge
  3. Discuss Trade-offs: Compare different approaches
  4. Handle Edge Cases: Mention missing 0, n, and single element
  5. Follow-up Ready: Be prepared for variations

Concept Explanations

Gauss Formula: The sum of integers from 0 to n is n * (n + 1) / 2. This is derived from the arithmetic series formula. Since we know the expected sum and can calculate the actual sum, the difference gives us the missing number.

XOR Approach: XORing all numbers from 0 to n with all numbers in the array will cancel out all pairs except the missing number. This works because a ^ a = 0 and a ^ 0 = a.

Why These Work: Both approaches leverage the fact that we know exactly what numbers should be present (0 to n) and can detect which one is missing through mathematical or bit manipulation techniques.