go4fun.fun
Go4Fun - Functional programming and more

Follow

Go4Fun - Functional programming and more

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

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

go4fun.fun's photo
go4fun.fun
·Jan 2, 2023·

2 min read

Problem

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

Examples:

Input vecOutput
[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

 
Share this