#268

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Missing Number

Find the missing number in an array containing distinct numbers in the range [0, n].

array hash table math binary search bit manipulation

Problem Statement

You are given an array nums containing n distinct numbers in the range [0, n]. Your task is to return the number in the range that is missing from the array. The array contains all but one of the numbers from 0 to n.

For example, given nums = [3, 0, 1], the missing number is 2. Similarly, for nums = [0, 1], the missing number is 2 as well. The task is to identify the missing number quickly, ensuring you choose an optimal approach.

Examples

Example 1

Input: nums = [3,0,1]

Output: 2

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

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

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 <= 104
0 <= nums[i] <= n
All the numbers of nums are unique.

Solution Approach

Array scanning plus hash lookup

By creating a hash set from the numbers in the array, you can quickly find which number is missing by scanning through the expected range [0, n]. This method ensures an O(n) time complexity.

Mathematical Sum formula

You can use the mathematical sum formula for the first n numbers: sum = n * (n + 1) / 2. Subtract the sum of elements in the array from this total to find the missing number in O(n) time with constant space.

Bit Manipulation (XOR approach)

Utilizing XOR, where the same numbers cancel out, allows you to find the missing number in O(n) time and O(1) space. XOR all numbers from 0 to n with the array elements to uncover the missing value.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity for each approach is O(n), where n is the length of the array. The space complexity varies: the hash lookup approach has O(n) space usage, while the sum and XOR approaches use O(1) space.

What Interviewers Usually Probe

Look for the candidate’s ability to use a mathematical formula or XOR manipulation for efficiency.
Observe the clarity in how the candidate justifies the choice of approach for handling time and space constraints.
Check for an understanding of array scanning and hash table concepts, especially for large inputs.

Common Pitfalls or Variants

Common pitfalls

Mistaking the problem for a simple search rather than recognizing the need for a missing number in the full range.
Choosing an approach with excessive space complexity when an O(1) space solution is possible.
Failing to handle edge cases like when n is 1, leading to incorrect results.

Follow-up variants

Allow duplicates in the array, or change the range from [0, n] to [1, n].
Handle a missing number in an array containing negative numbers in the range.
Modify the input array to become unsorted, forcing the candidate to consider sorting or hash-based solutions.

FAQ

What is the main approach for solving the Missing Number problem?

The main approach involves scanning the array while using techniques like hash lookup or XOR to identify the missing number efficiently.

How does XOR help in solving the Missing Number problem?

XOR allows you to cancel out duplicate numbers, leaving only the missing number by XORing all numbers from 0 to n with the array elements.

What is the time complexity of the Missing Number problem?

The time complexity for each approach is O(n), where n is the number of elements in the array.

What are some edge cases for the Missing Number problem?

Edge cases include when n = 1, or when the missing number is 0 or n. These cases require careful attention to the boundary conditions.

How does GhostInterview assist with solving the Missing Number problem?

GhostInterview provides immediate feedback and suggestions, helping you refine your approach using efficient techniques like XOR and mathematical summation.

terminal

Solution

Solution 1: Bitwise Operation

The XOR operation has the following properties:

1

2

3

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        return reduce(xor, (i ^ v for i, v in enumerate(nums, 1)))

Solution 2: Mathematics

We can also solve this problem using mathematics. By calculating the sum of $[0,..n]$, subtracting the sum of all numbers in the array, we can obtain the missing number.

1

2

3

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        return reduce(xor, (i ^ v for i, v in enumerate(nums, 1)))

Continue Practicing

#710 random pick with blacklist #349 intersection of two arrays #350 intersection of two arrays ii