Missing Number - LeetCode Daily Challenge

Problem Statement

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.

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

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.

Try here before watching the video.

Video Solution

Approach

A. Sorting

We can solve this problem using Sorting, where we can sort the array and then find which number is missing.
Time Complexity: O(N * logN)
Space Complexity: O(1)

B. HashMap

A brute force method for solving this problem would be to simply check for
the presence of each number that we expect to be present. The naive
implementation might use a linear scan of the array to check for containment,
but we can use a HashSet to get constant time containment queries and
overall linear runtime.
Time Complexity: O(N)
Space Complexity: O(N)

C. Bit Manipulation

Because we know that nums contains n numbers and that it is missing
exactly one number in the range [0..n−1]. We are also aware of the fact that the XOR of a number to itself is 0. Therefore, if we initialize an integer
to n and XOR it with every index and value, we will be left with the
missing number. Consider the following example:

missing = 4 ^ (0 ^ 0) ^ (1 ^ 1) ^ (2 ^ 3) ^ (3 ^ 4)
missing = 4 ^ 0 ^ 0 ^ 2 ^ (3 ^ 3) ^ 4
missing = (4 ^ 4) ^ 2 ^ (3 ^ 3)
missing = 2
Time Complexity: O(N)
Space Complexity: O(1)

Java Code

class Solution {
    public int missingNumber(int[] nums) {
        int missing = nums.length;
        for (int i = 0; i < nums.length; i++) {
            missing ^= i ^ nums[i];
        }
        return missing;
    }
}

C++ Code

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int missing = nums.size();
        for (int i = 0; i < nums.size(); i++) {
            missing ^= i ^ nums[i];
        }
        return missing;
    }
};

Python Code

class Solution:
    def missingNumber(self, nums):
        missing = len(nums)
        for i, num in enumerate(nums):
            missing ^= i ^ num
        return missing

Javascript Code

var missingNumber = function(nums) {
    let missing = nums.length;
    for (let i = 0; i < nums.length; i++) {
        missing ^= i ^ nums[i];
    }
    return missing;
};

Go Code

func missingNumber(nums []int) int {
    missing := len(nums)
    for i := 0; i < len(nums); i++ {
        missing ^= i ^ nums[i]
    }
    return missing
}

Complexity Analysis

Time Complexity: O(N)
Space Complexity: O(1)