LeetCode Blind 13/75: Missing Number

Problem statement

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.
Link to problem

Example 1

Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 
2 is the missing number in the range since it does not appear in nums.

Example 2

Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 
2 is the missing number in the range since it does not appear in nums.

Solutions

Approach 1: Gauss Summation

Very straightforward and simple approach where we compute the expected sum and subtract it from the actual sum.

$$ \frac{n\times(n+1)}{2} - \sum_{i=0}^{n} {numbers}[i] $$

Implementation in Rust

fn missing_number(numbers: Vec<i32>) -> i32 {
    let num_len = numbers.len() ;

    let total_sum = (num_len * (num_len + 1))/2;
    let mut num_sum = 0;

    for i in numbers {
        num_sum += i;
    }

    total_sum as i32 - num_sum

}

Time Complexity: $O(n)$
Runtime on LeetCode: $0$ms

Approach 2: Bitwise XOR

When you XOR two similar elements, they yield 0. Making use of this and applying it to the index as well as the element at that index, we could cancel out the elements that already exist.

For example: [0,1,3]

set xor_result = 3, length of array

notation will be as follows:
xor_result  ^ index ^ element at index = result

start of array
3 ^ 0 ^ 0 = 3
3 ^ 1 ^ 1 = 3
3 ^ 2 ^ 3 = 2, 3 ^ 3 cancels, 2 remains.
end of array

Hence the missing number is 2

Implementation in Rust

fn missing_number(numbers: Vec<i32>) -> i32 {
    let mut result = numbers.len() as i32;

    for i in 0..numbers.len() {
        result = result ^ i as i32;
        result = result ^ numbers[i];
    }

    result
}

Time Complexity: $O(n)$
Runtime on LeetCode: $2$ms

There are various other approaches to this problem that you could try: searching, sorting and using hashsets.