# Rust Interview Puzzles: Find the missing natural number in a vector

### Problem

In a provided vector `vec`

of distinct natural numbers `[1, 2, 3...]`

we need to find *one* missing number.

#### Examples:

Input `vec` | Output |

`[1, 2, 3, 5, 6, 7]` | `4` |

`[2, 3]` | `1` |

`[1, 3]` | `2` |

`[2]` | `1` |

### Solution

```
fn find_missing_number_in_vector(vec: &Vec<i32>) -> i32 {
let sum_vec: i32 = vec.iter().sum();
let n = (vec.len() + 1) as i32;
let sum_nat = n * (n + 1) / 2;
sum_nat - sum_vec
}
```

### Explanation

As per the puzzle definition, we know that *exactly one* number is missing in the input vector `vec`

. Also, we know that according to Arithmetic progression formulas, we could calculate the sum of `n`

first natural numbers using the formula: `1 + 2 + 3 + … + n = n * (n + 1) / 2`

. It means that if we calculate the sum of all numbers `sum_vec`

provided in the vector `vec`

and then calculate the expected sum of natural numbers `sum_nat`

using the formula, then the difference between the latter and the former would give us the missing number.

### Complexity

The time complexity of this solution is `O(n)`

(where `n`

is the size of the input vector).