LC 268 - Missing Number

Question

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.

Example 1:

Input: nums = [3,0,1]
Output: 2

Explanation:

n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

Example 2:

Input: nums = [0,1]
Output: 2

Explanation:

n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.

Example 3:

Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8

Explanation:

n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

Constraints:

• n == nums.length
• 1 <= n <= 104
• 0 <= nums[i] <= n
• All the numbers of nums are unique.

Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

Links

Question here and solution here

Solution

concept

1. we can use XOR , since anything XOR with itself will be 0 and 0 XOR with anything will return the original value. So if we XOR the given array with a array [0,1,2,...,n], what’s left is the missing number since other numbers cancel out
2. we can calculate the sum of the array [0,1,2,...,n and minus off the element in the given array, the leftover is the answer.

code

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        xor = 0
        for n in nums:
            xor ^= n
        for i in range(len(nums) + 1):
            xor ^= i
        return xor

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

Complexity

time: $O(1)$
space: $O(1)$