💬 Discord
Sign In
NeetCode #858LC-268EasyBit ManipulationBlind 75NC 150NC 250
← Back to All Problems

#858 · #268 · Missing Number(丢失的数字)

📌 Problem Statement & Constraints

Given an array nums containing n distinct integers taken from the range [0, n], return the only number in that range that is missing. Constraints: n == nums.length, 1 <= n <= 10^4, 0 <= nums[i] <= n.

💡 Core Algorithmic Approaches

  1. The range [0, n] has n + 1 values but the array holds only n of them, so exactly one is missing.
  2. XOR the indices 0..n-1 together with the values: every present value cancels the index equal to it, leaving the missing number.
  3. Seed the accumulator with n because n itself has no index in the array but is a valid candidate.
  4. The arithmetic alternative is n * (n + 1) // 2 - sum(nums), which is equally O(n) and O(1).

💻 Benchmark Python3 Implementation

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        res = len(nums)                 # seed with n, the extra candidate
        for i, x in enumerate(nums):
            res ^= i ^ x                # a present value cancels its own index
        return res


# Arithmetic variant
class Solution2:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        return n * (n + 1) // 2 - sum(nums)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): a single pass.
💾 Space Complexity
O(1): one accumulator.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting to seed with n: the candidate set is [0, n] inclusive, so n must participate in the XOR.
  • XOR-ing only the values: without pairing each value with its index there is nothing to cancel against.
  • Sorting and scanning for the gap: O(n log n), strictly worse than the single XOR pass.
  • Assuming the array is sorted: it is not, and the algorithm does not need it to be.