Missing Number

easy LeetCode #268
array hash-table math bit-manipulation

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 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 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 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

Complexity

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

Hints

Show Hints
Pattern
Math formula or XOR bit manipulation
Approach
Alternative: XOR all numbers 0..n with all array elements. Result is the missing number.
Complexity
Use sum formula: expected = n*(n+1)/2, missing = expected - actual_sum

Solutions

Show PY Solution 
def solution(nums: list[int]) -> int:
    got = 0
    for i in range(len(nums)):
        got += nums[i]

    expected = 0
    for v in range(1, len(nums) + 1):
        expected += v

    return expected - got