Missing Number - Leetcode Solution

The missing number problem on LeetCode asks us to find the missing number in an array of integers that is in the range of 0 to n. Here, n is the length of the array, and only one number is missing.

A simple approach to solve this problem is to use the mathematical formula for the sum of integers from 0 to n. The formula is

Sum = n * (n + 1) / 2

We know the expected sum of all the numbers in the array, which is using this formula. Next, we iterate over the array, and we calculate the actual sum of the elements. Finally, we subtract the actual sum from the expected sum, and the result will be the missing number in the array.

Here is the Python code for this approach:

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

This solution has a time complexity of O(n) because it involves iterating over the entire array once, and a space complexity of O(1) because we are not using any extra space to store data.

Another approach to solving this problem is by using the XOR operation. We know that XORing a number with itself will always result in 0. Also, XORing a number with 0 will result in the number itself. Using these properties, we can XOR all the elements in the array from 0 to n with each of the elements in the input array. The result will be the missing number in the array.

Here is the code for this approach:

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        missing_num = len(nums)
        for i, num in enumerate(nums):
            missing_num ^= i ^ num
        return missing_num

This solution also has a time complexity of O(n) because it involves iterating over the entire array once, and a space complexity of O(1) because we are not using any extra space to store data.

1