This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

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#### Approach #1 Sorting [Accepted]

\n

\n#### Approach #2 HashSet [Accepted]

\n

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

\n

\n

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

\n

\n

'
\n\n

\n**Intuition**

If `nums`

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

**Algorithm**

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.

**Complexity Analysis**

- \n
- \n
Time complexity : \n

\nThe only elements of the algorithm that have asymptotically nonconstant\ntime complexity are the main

\n`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
Space complexity : (or )

\nIn the sample code, we sorted

\n`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

**Intuition**

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.

**Algorithm**

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.

**Complexity Analysis**

- \n
- \n
Time complexity : \n

\nBecause the set allows for containment queries, the main loop\nruns in time. Creating

\n`num_set`

costs time, as each set insertion\nruns in amortized time, so the overall runtime is . \n - \n
Space complexity : \n

\n

\n`nums`

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

\n

**Intuition**

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

\n**Algorithm**

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

Index | 0 | 1 | 2 | 3 |
---|---|---|---|---|

Value | 0 | 1 | 3 | 4 |

\n\n

\n\n**Complexity Analysis**

- \n
- \n
Time complexity : \n

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

\nThis algorithm allocates only constant additional space.

\n \n

\n

**Intuition**

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

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.

**Complexity Analysis**

- \n
- \n
Time complexity : \n

\nAlthough Gauss\' formula can be computed in time, summing

\n`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
Space complexity : \n

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

\n \n

\n

Analysis written by: @emptyset

\n