Solution: Missing Number
Tags: algorithms, javascript, java, python
Published: 2021-03-03 08:41:02

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/missing-number/discuss/1091153).*

---

#### [Leetcode Problem #268 (*Easy*): Missing Number](https://leetcode.com/problems/missing-number/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
Given an array `nums` containing `n` distinct numbers in the range `[0, n]`, return the only number in the range that is missing from the array.
>
**Follow up**: Could you implement a solution using only `O(1)` extra space complexity and `O(n)` runtime complexity?

---

#### ***Examples:***
>
Example 1:||
|---:|---|
Input:|nums = [3,0,1]
Output:|2
Explanation:|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
Explanation:|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
Explanation:|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.
>
Example 4:||
|---:|---|
Input:|nums = [0]
Output:|1
Explanation:|n = 1 since there is 1 number, so all numbers are in the range [0,1]. 1 is the missing number in the range since it does not appear in nums.

---

#### ***Constraints:***
>
 - `n == nums.length`
 - `1 <= n <= 10^4`
 - `0 <= nums[i] <= n`
 - All the numbers of `nums` are unique.

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

The sum of the numbers from **1** to **N** is the **N**th **triangular number**, defined as **N * (N + 1) / 2**. It stands to reason, then, that we can simply find the difference between the **N**th triangular number and the sum of **nums**, which should be our missing number.

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
const missingNumber = nums =>
    nums.length * (nums.length + 1) / 2 - nums.reduce((a,c) => a + c)
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        return len(nums) * (len(nums) + 1) // 2 - sum(nums)
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    public int missingNumber(int[] nums) {
        return nums.length * (nums.length + 1) / 2 - Arrays.stream(nums).sum();
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        return nums.size() * (nums.size() + 1) / 2 - accumulate(nums.begin(), nums.end(), 0);
    }
};
```