268 Missing Number

Given an array containingndistinct numbers taken from0, 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?

Approach #4 Gauss' Formula [Accepted]

Intuition

One of the most well-known stories in mathematics is of a young Gauss, forced to find the sum of the first 100 natural numbers by a lazy teacher. Rather than add the numbers by hand, he deduced aclosed-form expressionfor the sum, or so the story goes. You can see the formula below:

(1 + n) * n / 2

Other method, if space is not restricted to space complexity you could use hashset

and if time is not restricted you could sort

class Solution {
    public int missingNumber(int[] nums) {
        int total = (0 + nums.length) * (nums.length + 1) / 2;
        for (int i = 0; i < nums.length; i++) {
            total -= nums[i];
        }
        return total;
    }
}