0268 - Missing Number

Difficulty

Easy

Language

Python

URL

https://leetcode.com/problems/missing-number/

Solution 1 - Sorting

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. Sort the array, then iterate through it. If the value at index i doesn't equal i, that index is the missing number. If all match, the missing number is n.

TimeComplexity: O(n \log n)

SpaceComplexity: O(1)

""" 0268.1 - Missing Number - Solution 1 - Sorting """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def missingNumber(self, nums: List[int]) -> int:
        """Missing Number Function"""
        nums.sort()
        for i in range(len(nums)):
            if nums[i] != i:
                return i
        return len(nums)


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().missingNumber([3, 0, 1]))       # Expected: 2
    print(Solution().missingNumber([0, 1]))           # Expected: 2
    print(Solution().missingNumber([9, 6, 4, 2, 3, 5, 7, 0, 1]))  # Expected: 8
    print(Solution().missingNumber([0]))              # Expected: 1


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 2 - Gauss' Formula (Sum)

The sum of the first n natural numbers is n * (n + 1) / 2. Subtract the actual sum of the array from the expected sum to find the missing number.

TimeComplexity: O(n)

SpaceComplexity: O(1)

""" 0268.2 - Missing Number - Solution 2 - Gauss' Formula (Sum) """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def missingNumber(self, nums: List[int]) -> int:
        """Missing Number Function"""
        n = len(nums)
        expected_sum = n * (n + 1) // 2
        actual_sum = sum(nums)
        return expected_sum - actual_sum


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().missingNumber([3, 0, 1]))       # Expected: 2
    print(Solution().missingNumber([0, 1]))           # Expected: 2
    print(Solution().missingNumber([9, 6, 4, 2, 3, 5, 7, 0, 1]))  # Expected: 8
    print(Solution().missingNumber([0]))              # Expected: 1


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 3 - XOR (Bit Manipulation)

XOR all indices 0 to n with all values in the array. Since x ^ x = 0 and x ^ 0 = x, every number that appears both as an index and a value cancels out, leaving only the missing number.

TimeComplexity: O(n)

SpaceComplexity: O(1)

""" 0268.3 - Missing Number - Solution 3 - XOR (Bit Manipulation) """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def missingNumber(self, nums: List[int]) -> int:
        """Missing Number Function"""
        xor = len(nums)
        for i, num in enumerate(nums):
            xor ^= i ^ num
        return xor


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().missingNumber([3, 0, 1]))       # Expected: 2
    print(Solution().missingNumber([0, 1]))           # Expected: 2
    print(Solution().missingNumber([9, 6, 4, 2, 3, 5, 7, 0, 1]))  # Expected: 8
    print(Solution().missingNumber([0]))              # Expected: 1


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()