Missing Number

---

Missing Number: 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 <= 10^4
• 0 <= nums[i] <= n
• All the numbers of nums are unique

---

Try this Problem on your own or check similar problems:

1. Single Number
2. Find the Duplicate Number
3. First Missing Positive

Solution:

Java

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

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function (nums) {
  let res = 0;
  for (let i = 0; i < nums.length; ++i) {
    res ^= i ^ nums[i];
  }
  return res ^ nums.length;
};

Python

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

C++

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

---

Time/Space Complexity:

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

---

Explanation:

First note that brute-force solution is trivial, you could for example create a set (also note that from the problem statement all numbers in nums are unique) from the input array and then loop over 0..n and for every number check if it exists in set. The first number that doesn't exist in the set is the missing number. However you will probably be asked if you could optimize the space complexity. If you are asked a question like this take a step back and think about (also ask the interviewer) input array properties. From the problem constraints we know that

• all numbers are unique in the input array
• all numbers are between 0 and n, where n is the length of array.

So to solve this problem we have to find a way to get the difference between two groups, the first group are the numbers in the input array and for the second group we have all numbers from 0 to n. So in other words group 2 contains all elements (0..n) including our missing number, so we have to test our first group (elements in input array) against the second group to find the missing number. In order to do that let's investigate XOR operator. XOR operator performs a logical exclusion on two Boolean expressions, or a bitwise exclusion on two numeric expressions.

If bit in expression1 is	And bit in expression2 is	The bit in result is
1	1	0
1	0	1
0	1	1
0	0	0

So if we have two numbers 3 and 5, their XOR would be 011 (3 presented in binary) XOR 101 (5 presented in binary) = 110 (6 in binary), since from left to right (0^1=1, 1^0=1, 1^1=0) where ^ is XOR operator. How does this help us find the missing number? Well first the XOR is interesting since it has some nice properties we can use:

• x^0 = x (0 is neutral) that's why we set it as initial value of res
• x^x = 0 when you xor number with itself the result is 0
• a^b = b^a commutative, we can change the order of operands
• (a^b)^c = (a^c)^b associative

So we use these 4 properties to solve our problem. We xor all the elements from both groups (note that order is you use XOR is not important, in other words you could XOR all number from second group and then all numbers from input array or do it simultaneously), since the mathing number will cross each other out (result will be 0, rule x^x=0), the res value will be equal to the only number is second group that's missing in the first group.