Description: 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.

Brute-force Approach

For each number between 1 and n, iterate through the array and check if it exists in the array. If it does not, return it.

Time: O(n^2)

Space: O(1)

Better Approach

Sort the array. Keep a counter and iterate through the array, checking if any number is missing between 1 and n.

Time: O(nlogn)

Space: O(1)

Better Approach 2

Use an array as a hashmap to store the frequency of each number. Iterate through the array and check if any number is missing between 1 and n.

Time: O(n)

Space: O(n)

Optimal Approach 1

Calculate the sum of the first n natural numbers and subtract the sum of the array from it.

Time: O(n)

Space: O(1)

Optimal Approach 2

Since a ^ a = 0 and a ^ 0 = a, XOR all the elements of the array with the first n natural numbers, and return the result.

Time: O(n)

Space: O(1)