268_Missing Number

[Easy][Array, Math, Bit Manipulation]

Given an array containing n distinct numbers taken from0, 1, 2, ..., n, find the one that is missing from the array.

Example 1:

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

Example 2:

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

Solution 1:

Idea:

• Sort the array in ascending order.

• Loop over each element, find which element doesn't equal to it's index.

Time Complexity: $O(n \log{n})$

Space Complexity: $O(1)$

def missingNumber(nums):
    """
    :type nums: List[int]
    :rtype: int
    """        
    nums.sort()
    i = 0
    while i < len(nums):
        if i != nums[i]:
            return i
        else:
            i += 1
    return nums[-1] + 1

Solution 2:

Idea:

• Use math summation formula.

• If there is no element missing, adding from 0 to n gives $\frac{n(n+1)}{2}$.
• Loop over each element in the array to get the summation. The difference between the expected summation and real summation will be the element missing.

Time Complexity: $O(n)$

Space Complexity: $O(1)$

def missingNumber(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    sums = 0
    for i in range(len(nums)):
        sums += nums[i]

    n = len(nums)
    return n*(n+1)/2 - sums