Skip to main content

🟩 Missing Number (#268)

🔗 Problem Link​

📋 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

Example 2​

Input: nums = [0,1]
Output: 2

Example 3​

Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8

🔑 Key Insights & Approach​

Core Observation: XOR all numbers 0 to n with all array elements. Duplicates cancel out, leaving missing number.

Why XOR?

  • O(n) time, O(1) space
  • XOR property: a ^ a = 0, a ^ 0 = a
  • Alternative: sum formula

Pattern: "XOR Properties" or "Math Sum" pattern.

🐍 Solution: Python​

Approach 1: XOR​

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

from typing import List

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        result = len(nums)

        for i, num in enumerate(nums):
            result ^= i ^ num

        return result

Approach 2: Sum Formula​

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

from typing import List

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        expected_sum = n * (n + 1) // 2
        actual_sum = sum(nums)
        return expected_sum - actual_sum

🔵 Solution: Golang​

Approach: XOR​

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

func missingNumber(nums []int) int {
    result := len(nums)

    for i, num := range nums {
        result ^= i ^ num
    }

    return result
}

📚 References​