Follow

Follow

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

go4fun.fun
·Jan 2, 2023·

### 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).

Rust Playground with this code