Missing Number

Problem Statement

In this task, you're provided with an array called nums which contains n unique numbers taken from a sequential range from 0 to n. This means that the array should ideally have n + 1 numbers, but since it contains only n numbers, it's evident that exactly one number from this range is missing. The challenge is to determine which number in the range [0, n] is absent from the array.

Examples

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`.

Example 3

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`.

Constraints

• n == nums.length
• 1 <= n <= 104
• 0 <= nums[i] <= n
• All the numbers of nums are unique.

Approach and Intuition

To find the missing number efficiently, consider the properties of the range and the constraints given:

1. Since the array nums contains every number once and only one number from the sequence is missing, the sum of the sequence 0 to n (the ideal sum) can be compared against the sum of numbers in the array.
2. The formula for the sum of the first n natural numbers is ( \frac{n \times (n + 1)}{2} ). This gives the sum of the sequence [0, n].
3. Calculate the actual sum of elements in the nums array.
4. The difference between the ideal sum and the actual sum of the array gives the missing number.

Example illustrations from the provided samples:

• Example 1:

  • Input: nums = [3,0,1]
  • Calculation:
    • Ideal sum for n = 3 is ( \frac{3 \times (3 + 1)}{2} = 6 ).
    • Actual sum of array = 3 + 0 + 1 = 4.
    • Missing number = 6 - 4 = 2.
  • Hence, the output is 2.

• Example 2:

  • Input: nums = [0,1]
  • Calculation:
    • Ideal sum for n = 2 is ( \frac{2 \times (2 + 1)}{2} = 3 ).
    • Actual sum of array = 0 + 1 = 1.
    • Missing number = 3 - 1 = 2.
  • Hence, the output is 2.

• Example 3:

  • Input: nums = [9,6,4,2,3,5,7,0,1]
  • Calculation:
    • Ideal sum for n = 9 is ( \frac{9 \times (10)}{2} = 45 ).
    • Actual sum of array = 37.
    • Missing number = 45 - 37 = 8.
  • Hence, the output is 8.

Using this approach efficiently identifies the missing number, adhering to the constraints and making sure to handle up to 10,000 elements in the array by direct calculations.

Solutions

class Solution {
    public int findMissing(int[] elements) {
        int idealSum = elements.length * (elements.length + 1) / 2;
        int sum = 0;
        for (int value : elements) sum += value;
        return idealSum - sum;
    }
}

class Solution:
    def findMissing(self, numbers):
        total_nums = len(numbers)
        expected_total = total_nums * (total_nums + 1) // 2
        sum_of_numbers = sum(numbers)
        return expected_total - sum_of_numbers