Missing Number

Problem Statement

LeetCode-268: 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.

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.

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.

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

Approach

There are multiple approaches to solve the problem:

• The simplest approach to solve the problem is to use a HashSet to store the numbers in the array. We can iterate over the array and add each number to the HashSet. Then, we can iterate over the range [0, n] and check if the number is present in the HashSet. If the number is not present in the HashSet, we can return the number as the missing number.
• Another approach is to sort the array and iterate over the array to find the missing number. If the number at the current index is not equal to expected, we can return the expected as the missing number.

Another approach is to use the bit manipulation technique. The idea is to use the XOR operation to find the missing number. The XOR operation has the following properties:

1. XOR of a number with itself is 0.
2. XOR of a number with 0 is the number itself.
3. XOR is commutative and associative.

As the numbers in the array are in the range [0, n], and the array contains n-1 indices, we can use the XOR operation to find the missing number. We can initialize a variable result with the n i.e. length of the array - as n must be overriding the missing number.

Then, we can iterate over the array and perform the XOR operation as follows:

For example, consider the array `[3, 0, 1]`. The length of the array is 3. The missing number is 2. The XOR operation will be as follows:

```plaintext
// result initially = 3
// result = result ^ i ^ nums[i]
i: 0; nums[i]: 3; result: 3 ^ 0 ^ 3 = 0
i: 1; nums[i]: 0; result: 0 ^ 1 ^ 0 = 1
i: 2; nums[i]: 1; result: 1 ^ 2 ^ 1 = 2

The missing number is 2.

Another approach to solve the problem is to use the Gauss’s formula which states that the sum of the first n natural numbers is given by:

$$\frac {n \times (n + 1)}{2} $$

Once we have the sum of the first n natural numbers, we can subtract the sum of the elements in the array to find the missing number.

Implementation

Let’s first implement the solution using the bit manipulation technique:

public int missingNumber(int[] nums) {
    int n = nums.length;
    int result = n;

    for(int i=0; i < n; i++){
        result = result ^ i ^ nums[i];
    }

    return result;
}

Here is the implementation using the Gauss’s formula:

public int missingNumber(int[] nums) {
    int n = nums.length;
    return (n*(n+1)/2) - Arrays.stream(nums).sum();   
}

Complexity Analysis

The time complexity for both the approaches is $O(n)$, where $n$ is the length of the array. The space complexity is $O(1)$ as we are using a constant amount of space.

References

Gauss’s Day of Reckoning