Logo
    Logo

    ©️ 2020-2026, Akhil Abraham.

    LinkedInGitHubMediumX
    Akhil Abraham
    Akhil Abraham
    /Posts
    Posts
    /LeetCode
    LeetCode
    /
    LeetCode
    /0268 - Missing Number
    0268 - Missing Number
    0268 - Missing Number
    0268 - Missing Number

    0268 - Missing Number

    Difficulty
    Easy
    Language
    Python
    URL
    https://leetcode.com/problems/missing-number/

    Solution 1 - Gauss' Formula (Math)

    Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing. Compute the expected sum of 0 to n using the formula n * (n + 1) / 2, then subtract the actual sum of the array. The difference is the missing number.

    TimeComplexity:O(n)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(1)SpaceComplexity: O(1)SpaceComplexity:O(1)

    Solution 2 - XOR Bit Manipulation

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

    TimeComplexity:O(n)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(1)SpaceComplexity: O(1)SpaceComplexity:O(1)
    """ 0268.1 - Missing Number - Solution 1 - Gauss' Formula (Math) """

#####################################################################################
# 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]))       # 2
    print(Solution().missingNumber([0, 1]))           # 2
    print(Solution().missingNumber([9, 6, 4, 2, 3, 5, 7, 0, 1]))  # 8


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

    """ 0268.2 - Missing Number - Solution 2 - XOR Bit Manipulation """

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

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

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


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


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