LeetCode #268: Missing Number

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

There are multiple approaches that we can take to solve this problem. One of the most straightforward approaches is to create a set of all the numbers in the range [0, n] and then iterate over the given array nums to check which number is missing. We can also use the sum formula to calculate the sum of all the numbers in the range [0, n] and subtract the sum of the given array nums from it. The result would be the missing number.

Another approach is to use the XOR operator. We can XOR all the numbers in the range [0, n] with all the numbers in the given array nums. The result would be the missing number.

1. Create a variable missing and initialize it with the length of the given array nums.
2. Iterate over the given array nums and XOR each element with its index and with the missing variable.
3. After the loop, missing variable would have the missing number.

Here is the solution in python3:

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

Time and Space Complexity

The time complexity of the solution is O(n) as we need to iterate over the input array once to calculate the sum and then again to subtract it from the expected sum.

The space complexity of the solution is O(1) as we are not using any additional data structures to store the input or the result.