Missing Number

Bit ManipulationArray

15 min

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

Explanation: n = 3 since there are 3 numbers, so the range is [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 the range is [0,2]. 2 is the missing number in the range since it does not appear in nums.

Solution (XOR)

This problem can be solved efficiently using the XOR bitwise operator. The key idea is that XORing a number with itself results in 0 (a ^ a = 0), and XORing a number with 0 results in the number itself (a ^ 0 = a).

Algorithm Steps

Initialize a variable missing to n (the length of the array).
Iterate from i = 0 to n-1.
In each iteration, XOR missing with the index i and the number at that index nums[i].
After the loop, missing will hold the value of the missing number. This works because every number from 0 to n will appear twice (once as an index, once as a value) except for the missing number, which appears only once as an index.

Array `nums`:

Indices:

missing: 0011 (3)

Initialize missing = n = 3

Missing Number Solution


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