DSAPrep
EasyBit Manipulation

Missing Number

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^4
  • 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?
View original on LeetCode ↗

nums has n elements drawn from the n + 1 values 0..n, so exactly one value is missing. Sorting or hashing solves it, but both cost more than necessary — the missing value can be recovered directly by comparing nums against what a complete 0..n range would look like.

Sorting

Time O(n log n)Space O(1) extra

Sort nums, then walk it looking for the first index where the value does not match the index. If every value matches its index all the way through, the missing number is n (it fell off the end).

class Solution:
    def missingNumber(self, nums: list[int]) -> int:
        nums.sort()
        for i, num in enumerate(nums):
            if num != i:
                return i
        return len(nums)

Sorting dominates the cost → O(n log n) time, O(1) extra space if the sort is in-place (ignoring the sort’s own recursion stack).

Expected Sum Minus Actual Sum

Time O(n)Space O(1)

If nothing were missing, nums would contain every value from 0 to n, which sums to n * (n + 1) / 2. Subtracting the actual sum of nums from that expected total leaves exactly the missing value, since every present number cancels out and only the absent one remains.

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

Complexity: one pass to sum nums → O(n) time, O(1) space. Correct, but relies on arithmetic (large sums can overflow in fixed-width integer languages, which XOR avoids).

XOR of Indices and Values

OptimalTime O(n)Space O(1)

The same cancellation idea works with XOR instead of addition, and sidesteps any overflow concern. XOR together every index 0..n and every value in nums. Each value that is actually present pairs up with its matching index and cancels to 0 (x ^ x = 0); the one index with no matching value survives.

class Solution:
    def missingNumber(self, nums: list[int]) -> int:
        result = len(nums)  # accounts for index n, which has no array slot
        for i, num in enumerate(nums):
            result ^= i ^ num
        return result

Tracing nums = [3, 0, 1] (so n = 3, starting result = 3):

i
3
0
0
1
1
2
result = 0
1 / 3
resultcurrent

result = 3 ^ (0 ^ 3) = 3 ^ 3 = 0.

Correctness: every present value v at some index gets XORed in twice overall (once as an index somewhere in 0..n, once as the array value) and cancels; the single index in 0..n with no matching array value survives the cancellation and is exactly the missing number.

Complexity: one pass, O(1) work per element → O(n) time, O(1) space — meeting the follow-up exactly, with no risk of integer overflow since XOR never grows the value beyond the input’s bit width.