Leetcode 268. Missing Number

The "Missing Number" problem is a classic algorithmic challenge where you're given an array of distinct numbers ranging from 0 to nn. The task is to find the one number missing from this range.

Problem Explanation

Given an array nums containing n distinct numbers from the range [0, n], you need to identify the missing number. Here's how it works:

• Example 1:Input: nums = [3, 0, 1]Output: 2Explanation: The numbers should range from 0 to 3, but 2 is missing.
• Example 2:Input: nums = [0, 1]Output: 2Explanation: The range is from 0 to 2, and the missing number is 2.
• Example 3:Input: nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]Output: 8Explanation: The numbers should range from 0 to 9, with 8 missing.

Approach Using Sum Formula

Intuition:The sum of the first nn natural numbers is given by the formula n(n+1)22n(n+1). By calculating this sum and subtracting the sum of the numbers present in the array, we can find the missing number.Approach:

1. Calculate the expected sum of numbers from 0 to nn using the formula n(n+1)22n(n+1).
2. Subtract each number in the array from this expected sum.
3. The result will be the missing number.

Complexity:

• Time complexity: O(n)O(n)
• Space complexity: O(1)O(1)

class Solution(object):
    def missingNumber(self, nums):
        sum_i = (len(nums) * (len(nums) + 1)) // 2
        for num in nums:
            sum_i -= num
        return sum_i        

Approach Using XOR Operator

Intuition:The XOR operation has a unique property where a number XORed with itself results in zero and a number XORed with zero results in the number itself. This property can be used to find the missing number.Approach:

1. Initialize a variable xor_all to zero.
2. XOR all indices and all numbers in the array with xor_all.
3. The result will be the missing number since all paired indices and numbers cancel each other out.

Complexity:

• Time complexity: O(n)O(n)
• Space complexity: O(1)O(1)

class Solution(object):
    def missingNumber(self, nums):
        xor_all = len(nums)
        for i in range(len(nums)):
            xor_all ^= i ^ nums[i]
        return xor_all        

Conclusion

Both approaches efficiently solve the problem with linear time complexity and constant space usage. The sum formula approach leverages arithmetic properties, while the XOR approach uses bitwise operations for a clever solution.