algoadvance

You have been given an array containing n distinct numbers taken from the range [0, n]. Since the array contains n numbers, exactly one number is missing from the range. Your task is to find and return that missing number.

Example:

Input: [3,0,1]
Output: 2

Input: [0,1]
Output: 2

Input: [9,6,4,2,3,5,7,0,1]
Output: 8

Clarifying Questions

  1. Are the numbers always distinct?
    • Yes, we are given that the numbers in the array are distinct.
  2. Is there a specific space or time complexity requirement?
    • The optimal solution would ideally run in linear time and use constant extra space, though not explicitly stated.
  3. Can the array be empty?
    • No, if the array is empty, the input constraints are violated because it should contain numbers from [0, n] where n is at least 1.

Strategy

Given the problem, we can use the following approach:

  1. Sum Formula Approach: The sum of the first n natural numbers can be computed using the formula: [ \text{Sum} = \frac{n \times (n + 1)}{2} ]
    • We can calculate this expected sum for the range [0, n].
    • Then, we can subtract the sum of the array elements from this expected sum to get the missing number.
  2. XOR Approach: Another clever way is using XOR. This approach is also efficient and uses constant space but might be overkill for this problem. The sum formula approach is simpler and equally efficient in this context.

Code

Here’s the implementation using the sum formula approach:

def missingNumber(nums):
    n = len(nums)
    total_sum = n * (n + 1) // 2
    array_sum = sum(nums)
    return total_sum - array_sum

Time Complexity

This code effectively calculates the missing number by leveraging the mathematical properties of the sum of the first n natural numbers.

Try our interview co-pilot at AlgoAdvance.com