Approach #1 Sorting [Accepted]

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 $$n$$ \nis at the end. Given that those assumptions hold, the missing number must\nsomewhere between (but not including) 0 and $$n$$ . 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 : $$O(nlgn)$$ \n

  \n

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

  \n
\n
• \n

  Space complexity : $$O(1)$$ (or $$O(n)$$ )

  \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 $$O(n)$$ size copy and sort that instead.

  \n
\n

Approach #2 HashSet [Accepted]

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 $$O(1)$$ time.

Complexity Analysis

\n
• \n

  Time complexity : $$O(n)$$ \n

  \n

  Because the set allows for $$O(1)$$ containment queries, the main loop\nruns in $$O(n)$$ time. Creating num_set costs $$O(n)$$ time, as each set insertion\nruns in amortized $$O(1)$$ time, so the overall runtime is $$O(n + n) = O(n)$$ .

  \n
\n
• \n

  Space complexity : $$O(n)$$ \n

  \n

  nums contains $$n-1$$ distinct elements, so it costs $$O(n)$$ space to\nstore a set containing all of them.

  \n
\n

Approach #3 Bit Manipulation [Accepted]

Intuition

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

Algorithm

Because we know that nums contains $$n$$ numbers and that it is missing\nexactly one number on the range $$[0..n-1]$$ , we know that $$n$$ definitely\nreplaces the missing number in nums. Therefore, if we initialize an integer\nto $$n$$ 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\\begin{align}\n missing &= 4 \\wedge (0 \\wedge 0) \\wedge (1 \\wedge 1) \\wedge (2 \\wedge 3) \\wedge (3 \\wedge 4) \\\\\n &= (4 \\wedge 4) \\wedge (0 \\wedge 0) \\wedge (1 \\wedge 1) \\wedge (3 \\wedge 3) \\wedge 2 \\\\\n &= 0 \\wedge 0 \\wedge 0 \\wedge 0 \\wedge 2 \\\\ \n &= 2\n\\end{align}\n$$ \n

Complexity Analysis

\n
• \n

  Time complexity : $$O(n)$$ \n

  \n

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

  \n
\n
• \n

  Space complexity : $$O(1)$$ \n

  \n

  This algorithm allocates only constant additional space.

  \n
\n

Approach #4 Gauss\' Formula [Accepted]

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 \\sum_{i=0}^{n}i = \\frac{n(n+1)}{2}\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 $$n$$ 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 $$n$$ natural numbers minus some number.

Complexity Analysis

\n
• \n

  Time complexity : $$O(n)$$ \n

  \n

  Although Gauss\' formula can be computed in $$O(1)$$ time, summing nums\ncosts us $$O(n)$$ 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 $$n$$ \nnumbers fails. Therefore, this solution is asymptotically optimal.

  \n
\n
• \n

  Space complexity : $$O(1)$$ \n

  \n

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

  \n
\n

Analysis written by: @emptyset