Find Missing Number (1 to n)

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

Language Selection

Choose your preferred programming language

Showing: Python

Find Missing Number (1 to n)

Problem Statement

Given an array nums containing n distinct numbers in the range [1, n+1], return the missing number.

Constraints:

  • 1 <= n <= 10^4
  • nums.length == n
  • All numbers in nums are unique
  • 1 <= nums[i] <= n + 1

Examples:

Example 1:

Input: nums = [3,0,1]
Output: 2
Explanation: n = 3, so the array should contain [0,1,2,3]. Missing number is 2.

Example 2:

Input: nums = [0,1]
Output: 2
Explanation: n = 2, so the array should contain [0,1,2]. Missing number is 2.

Example 3:

Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n = 9, so the array should contain [0,1,2,3,4,5,6,7,8,9]. Missing number is 8.

Approach 1: Mathematical Formula

Algorithm:

  1. Calculate the expected sum of numbers from 1 to n using the formula: n * (n + 1) / 2
  2. Calculate the actual sum of all numbers in the array
  3. The missing number is the difference between expected sum and actual sum

Time Complexity: O(n)
Space Complexity: O(1)

Python:

def missingNumber(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 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;
    }
}

Go:

// missingNumber - Find missing number using mathematical formula
// Time: O(n)
// Space: O(1)
func missingNumber(nums []int) int {
    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 missingNumber(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 MissingNumber(int[] nums) {
        int n = nums.Length;
        int expectedSum = n * (n + 1) / 2;
        int actualSum = nums.Sum();
        
        return expectedSum - actualSum;
    }
}

Approach 2: XOR Bit Manipulation

Algorithm:

  1. XOR all numbers from 0 to n
  2. XOR all numbers in the array
  3. XOR the two results - the missing number will be the result

Time Complexity: O(n)
Space Complexity: O(1)

Python:

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

Java:

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

Go:

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

JavaScript:

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

C#:

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

Approach 3: Sorting

Algorithm:

  1. Sort the array
  2. Check if each index contains the correct number
  3. Return the first missing number found

Time Complexity: O(n log n)
Space Complexity: O(1)

Python:

def missingNumber(nums):
    """
    Find missing number using sorting
    Time: O(n log n)
    Space: O(1)
    """
    nums.sort()
    
    for i in range(len(nums)):
        if nums[i] != i:
            return i
    
    return len(nums)

Java:

class Solution {
    /**
     * Find missing number using sorting
     * Time: O(n log n)
     * Space: O(1)
     */
    public int missingNumber(int[] nums) {
        Arrays.sort(nums);
        
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i) {
                return i;
            }
        }
        
        return nums.length;
    }
}

Go:

// missingNumber - Find missing number using sorting
// Time: O(n log n)
// Space: O(1)
func missingNumber(nums []int) int {
    sort.Ints(nums)
    
    for i := 0; i < len(nums); i++ {
        if nums[i] != i {
            return i
        }
    }
    
    return len(nums)
}

JavaScript:

/**
 * Find missing number using sorting
 * Time: O(n log n)
 * Space: O(1)
 */
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;
}

C#:

public class Solution {
    /// <summary>
    /// Find missing number using sorting
    /// Time: O(n log n)
    /// Space: O(1)
    /// </summary>
    public int MissingNumber(int[] nums) {
        Array.Sort(nums);
        
        for (int i = 0; i < nums.Length; i++) {
            if (nums[i] != i) {
                return i;
            }
        }
        
        return nums.Length;
    }
}

Key Insights

  1. Mathematical Approach: Most efficient with O(n) time and O(1) space. Uses the sum formula for arithmetic progression.

  2. XOR Approach: Also O(n) time and O(1) space. Leverages the property that XOR of a number with itself is 0.

  3. Sorting Approach: Less efficient but intuitive. Good for understanding the problem structure.

  4. Edge Cases: The missing number could be 0, n, or any number in between.

Edge Cases

  • Array with single element: [0] → missing is 1
  • Array with single element: [1] → missing is 0
  • Array missing the last element: [0,1,2] → missing is 3
  • Array missing the first element: [1,2,3] → missing is 0

Test Cases

# Test case 1: Missing number in middle
assert missingNumber([3,0,1]) == 2

# Test case 2: Missing number at end
assert missingNumber([0,1]) == 2

# Test case 3: Missing number at beginning
assert missingNumber([1,2,3]) == 0

# Test case 4: Single element array
assert missingNumber([0]) == 1
assert missingNumber([1]) == 0

# Test case 5: Large array
assert missingNumber([9,6,4,2,3,5,7,0,1]) == 8

Follow-up Questions

  1. What if the array contains duplicates? - The problem assumes unique numbers, but with duplicates, we’d need a different approach.

  2. What if we have multiple missing numbers? - Would require a different algorithm to find all missing numbers.

  3. What if the range is not [0, n]? - Would need to adjust the expected sum calculation.

Common Mistakes

  1. Off-by-one errors in the sum formula calculation
  2. Forgetting to handle edge cases like missing 0 or n
  3. Incorrect XOR implementation - not XORing all numbers from 0 to n
  4. Sorting without considering that the missing number could be at the end

Trade-offs

  • Mathematical vs XOR: Both are optimal, mathematical is more intuitive
  • Sorting: Easier to understand but less efficient
  • Space vs Time: All approaches use O(1) space, mathematical and XOR are faster