Missing Number

easyFREEBit ManipulationBlind 75

Given an array containing n distinct numbers from 0, 1, 2, ..., n, find the one that is missing.

Example

Input

3,0,1

Output

Reasoning

Input: nums is $[3, 0, 1]$ , a list of distinct whole numbers. Its length is $n = 3$ , and that count fixes the range: the values are supposed to come from $\{0, 1, \dots, n\} = \{0, 1, 2, 3\}$ .
That range holds $n + 1 = 4$ candidates but the list only has $3$ entries, so exactly one candidate is absent.
Math: the answer is the single element of $\{0, 1, 2, 3\} \setminus \{3, 0, 1\}$ . Checking each candidate: $0$ is present, $1$ is present, $2$ is not, $3$ is present.
Output: the integer 2, a single number rather than a list, because there is only ever one gap.
Notice that $n$ is read from the list's length, not from its largest value. For $[0, 1]$ , $n = 2$ , so the range is $\{0, 1, 2\}$ and the missing value is 2, the top end itself, even though it is larger than every value in the list. The order of nums never affects the answer.

Constraints

n == len(nums)
0 <= nums[i] <= n
All values are unique

More from Blind 75

Alien Dictionaryhard Clone Graphmedium Combination Summedium Word Search IIhard Merge K Sorted Listshard

Concept primer

Background Knowledge

The "Missing Number" problem is a classic example of a mathematical puzzle that can be solved using various approaches. To tackle this problem, it's essential to understand the concept of sequences and series. A sequence is a set of numbers in a specific order, and a series is the sum of the terms of a sequence. In this case, we're dealing with a sequence of distinct numbers from 0 to n.

The problem can be approached using arithmetic series formulas, which describe the sum of a sequence of numbers with a common difference. The formula for the sum of an arithmetic series is $S = \frac{n}{2}(a + l)$ , where S is the sum, n is the number of terms, a is the first term, and l is the last term. Understanding this concept can help you derive a solution to find the missing number.

Another crucial concept is bit manipulation, which involves using bitwise operations to solve problems. This approach can be useful when dealing with binary representations of numbers. However, it's not the only way to solve this problem, and other methods, such as mathematical formulas or iterative approaches, can also be employed.

Algorithm/Approach

The algorithm pattern to solve this type of problem typically involves iterating over the given array and using mathematical calculations to find the missing number. The approach can be categorized into two main types: formula-based and iterative. The formula-based approach uses mathematical formulas, such as the arithmetic series formula, to calculate the missing number. The iterative approach, on the other hand, involves iterating over the array and using bitwise operations or other methods to find the missing number.

Step-by-Step Strategy

To implement the solution, follow these steps:

Calculate the total sum of numbers from 0 to n using the arithmetic series formula.
Calculate the sum of the numbers in the given array.
Find the difference between the total sum and the sum of the numbers in the array.
The difference will be the missing number.

Alternatively, you can use an iterative approach:

Initialize a variable to store the missing number.
Iterate over the array and use bitwise operations or other methods to find the missing number.

Common Pitfalls

When implementing the solution, watch out for:

Off-by-one errors when calculating the sum of numbers from 0 to n.
Incorrect usage of bitwise operations.
Failure to handle edge cases, such as an empty array.

Time & Space Complexity

The expected time complexity for this problem is O(n), where n is the number of elements in the array. The space complexity is O(1), as we only need to use a constant amount of space to store the missing number. However, the space complexity may vary depending on the implementation approach.

solution.py

Python 3.13

Test results