Reference: LeetCode

Difficulty: Easy

My Post: [Java] Summary of All Solutions Except Sorting! (also handle overflow)

## Problem

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

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

## Analysis

### Brute-Force

**Time:** $O(N^2)$**Space:** $O(1)$

### Hash Set

1 | public int missingNumber(int[] nums) { |

**Time:** $O(N)$**Space:** $O(N)$

### Bit Manipulation

It is based on the fact that `x ^ x = 0`

.

1 | // 0 ^ 0 = 0 |

**Time:** $O(N)$**Space:** $O(1)$

### Math (Gauss’ Formula)

Formula: $1 + 2 + 3 + 4 + \ldots + n = \frac{n(n + 1)}{2}$

1 | // nums = [] --> missing 0 |

**Improvement:** It can handle overflow.

1 | public int missingNumber(int[] nums) { |

**Time:** $O(N)$**Space:** $O(1)$