Problem

In a provided vector vec of distinct natural numbers [1, 2, 3...] we need to find one missing number.

Examples:

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