LeetCodee

268. Missing Number

Jump to Solution: Python Java C++ JavaScript C#

Problem Description

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.

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⁴
  • 0 <= nums[i] <= n
  • All the numbers of nums are unique

Follow up:

Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

Solution

Python Solution

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        # XOR all numbers from 0 to n with all numbers in array
        result = n  # Start with n since it's not in array
        for i in range(n):
            result ^= i ^ nums[i]
        return result

Time Complexity: O(n)

We need to traverse the array once.

Space Complexity: O(1)

Only uses a constant amount of extra space.

Java Solution

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        // XOR all numbers from 0 to n with all numbers in array
        int result = n;  // Start with n since it's not in array
        for (int i = 0; i < n; i++) {
            result ^= i ^ nums[i];
        }
        return result;
    }
}

Time Complexity: O(n)

We need to traverse the array once.

Space Complexity: O(1)

Only uses a constant amount of extra space.

C++ Solution

class Solution {
public:
    int missingNumber(vector& nums) {
        int n = nums.size();
        // XOR all numbers from 0 to n with all numbers in array
        int result = n;  // Start with n since it's not in array
        for (int i = 0; i < n; i++) {
            result ^= i ^ nums[i];
        }
        return result;
    }
};

Time Complexity: O(n)

We need to traverse the array once.

Space Complexity: O(1)

Only uses a constant amount of extra space.

JavaScript Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
    const n = nums.length;
    // XOR all numbers from 0 to n with all numbers in array
    let result = n;  // Start with n since it's not in array
    for (let i = 0; i < n; i++) {
        result ^= i ^ nums[i];
    }
    return result;
};

Time Complexity: O(n)

We need to traverse the array once.

Space Complexity: O(1)

Only uses a constant amount of extra space.

C# Solution

public class Solution {
    public int MissingNumber(int[] nums) {
        int n = nums.Length;
        // XOR all numbers from 0 to n with all numbers in array
        int result = n;  // Start with n since it's not in array
        for (int i = 0; i < n; i++) {
            result ^= i ^ nums[i];
        }
        return result;
    }
}

Time Complexity: O(n)

We need to traverse the array once.

Space Complexity: O(1)

Only uses a constant amount of extra space.

Approach Explanation

The solution uses the XOR operation to find the missing number:

  1. Key Insight:
    • XOR has these properties:
      • a ^ a = 0
      • a ^ 0 = a
      • a ^ b ^ b = a
    • XORing all numbers from 0 to n with array elements leaves missing number
  2. Algorithm Steps:
    • Start with n (since it's not in array indices)
    • XOR with each index and array value
    • Result is the missing number

Example walkthrough for nums = [3,0,1]:

  • n = 3, result = 3
  • i = 0: result = 3 ^ 0 ^ 3
  • i = 1: result = (3 ^ 0 ^ 3) ^ 1 ^ 0
  • i = 2: result = (3 ^ 0 ^ 3 ^ 1 ^ 0) ^ 2 ^ 1
  • Final result = 2 (missing number)

Alternative Approaches:

  • Sum formula: n*(n+1)/2 - sum(nums)
  • Using set/hash table (O(n) space)
  • Sorting (O(n log n) time)
  • Binary search (if array is sorted)

Edge Cases:

  • Missing number is n
  • Missing number is 0
  • Array of length 1
  • Maximum array length