Question

How to find the missing number in a list containing numbers from 1 to n in O(1) time complexity with Rust

Answer 1

/*
The essence of O(1) space complexity is that the algorithm uses a fixed amount of memory,
regardless of input size. Time complexity here is O(n) because we must scan the array.
*/

fn find_missing_number(arr: &[i32]) -> i32 {
    let size = arr.len();
    // formula for the sum of the first (size+1) natural numbers
    let expected_sum: i64 = ((size + 1) * (size + 2) / 2) as i64;
    let mut actual_sum: i64 = 0;

    for &num in arr {
        actual_sum += num as i64;
    }

    (expected_sum - actual_sum) as i32
}

fn main() {
    let arr = [1, 2, 4, 5, 6];
    let missing = find_missing_number(&arr);

    println!("Missing number: {}", missing);
}



/*
run:

Missing number: 3

*/

 

70+ SQL courses for beginners and professionals