## 268. Missing Number

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

Example 1

Input: [3,0,1]
Output: 2


Example 2

Input: [9,6,4,2,3,5,7,0,1]
Output: 8


Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

b'
\n\n

#### Approach #1 Sorting [Accepted]

\n

Intuition

\n

If nums were in order, it would be easy to see which number is missing.

\n

Algorithm

\n

First, we sort nums. Then, we check the two special cases that can be\nhandled in constant time - ensuring that 0 is at the beginning and that \nis at the end. Given that those assumptions hold, the missing number must\nsomewhere between (but not including) 0 and . To find it, we ensure that\nthe number we expect to be at each index is indeed there. Because we handled\nthe edge cases, this is simply the previous number plus 1. Thus, as soon as\nwe find an unexpected number, we can simply return the expected number.

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : \n

\n

The only elements of the algorithm that have asymptotically nonconstant\ntime complexity are the main for loop (which runs in time), and\nthe sort invocation (which runs in time for Python and Java).\nTherefore, the runtime is dominated by sort, and the entire runtime is\n.

\n
• \n
• \n

Space complexity : (or )

\n

In the sample code, we sorted nums in place, allowing us to avoid\nallocating additional space. If modifying nums is forbidden, we can\nallocate an size copy and sort that instead.

\n
• \n
\n
\n

#### Approach #2 HashSet [Accepted]

\n

Intuition

\n

A brute force method for solving this problem would be to simply check for\nthe presence of each number that we expect to be present. The naive\nimplementation might use a linear scan of the array to check for containment,\nbut we can use a HashSet to get constant time containment queries and\noverall linear runtime.

\n

Algorithm

\n

This algorithm is almost identical to the brute force approach, except we\nfirst insert each element of nums into a set, allowing us to later query\nfor containment in time.

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : \n

\n

Because the set allows for containment queries, the main loop\nruns in time. Creating num_set costs time, as each set insertion\nruns in amortized time, so the overall runtime is .

\n
• \n
• \n

Space complexity : \n

\n

nums contains distinct elements, so it costs space to\nstore a set containing all of them.

\n
• \n
\n
\n

#### Approach #3 Bit Manipulation [Accepted]

\n

Intuition

\n

We can harness the fact that XOR is its own inverse to find the missing\nelement in linear time.

\n

Algorithm

\n

Because we know that nums contains numbers and that it is missing\nexactly one number on the range , we know that definitely\nreplaces the missing number in nums. Therefore, if we initialize an integer\nto and XOR it with every index and value, we will be left with the\nmissing number. Consider the following example (the values have been sorted\nfor intuitive convenience, but need not be):

\n

\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
 Index Value 0 1 2 3 0 1 3 4

\n

\n\n

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : \n

\n

Assuming that XOR is a constant-time operation, this algorithm does\nconstant work on iterations, so the runtime is overall linear.

\n
• \n
• \n

Space complexity : \n

\n

This algorithm allocates only constant additional space.

\n
• \n
\n
\n

#### Approach #4 Gauss\' Formula [Accepted]

\n

Intuition

\n

One of the most well-known stories in mathematics is of a young Gauss, forced\nto find the sum of the first 100 natural numbers by a lazy teacher. Rather\nthan add the numbers by hand, he deduced a closed-form\nexpression for the sum, or so\nthe story goes. You can see the formula below:

\n

\n\n

\n

Algorithm

\n

We can compute the sum of nums in linear time, and by Gauss\' formula, we\ncan compute the sum of the first natural numbers in constant time. Therefore,\nthe number that is missing is simply the result of Gauss\' formula minus the sum of nums,\nas nums consists of the first natural numbers minus some number.

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : \n

\n

Although Gauss\' formula can be computed in time, summing nums\ncosts us time, so the algorithm is overall linear. Because we have\nno information about which number is missing, an adversary could always\ndesign an input for which any algorithm that examines fewer than \nnumbers fails. Therefore, this solution is asymptotically optimal.

\n
• \n
• \n

Space complexity : \n

\n

This approach only pushes a few integers around, so it has constant\nmemory usage.

\n
• \n
\n
\n

Analysis written by: @emptyset

\n
'