Editorial Series - LeetCode 268. Missing Number

Problem Description

In this problem, you are given an integer array nums which contains n distinct integers where 0 <= nums[i] <= n. Your task is to determine that one integer, in the range [0, n], which is missing in the array.

There is a follow-up question associated with the problem which is:

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

My solution attempts to answer this question. So, let’s get started!

Solution Description

Suppose you are given 3 integers a, b, and c. It is mentioned that two of the integers are equivalent. How will you determine the third, single-occurring integer?
Well, there are several solutions, however, I am going to discuss the xor-approach.

Let’s review the properties of xor.

0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

From the above properties, you can deduce that if an integer x is equivalent to an integer y then x ^ y is equivalent to 0. Also,

0 ^ x = x

So, if you just take the xor of the 3 integers a, b and c, you are going to get the single-occurring integer.

Now, let’s be more generic.

In a list of n integers, if all the distinct integers, except one, have an even number of occurrences then taking xor of all the integers will result in the integer which has an odd number of occurrence.

Okay, got it! But how is the xor-approach relevant to this problem’s solution?
Let’s say nums = [3, 0, 1]. So, n = 3, and the missing integer from the range [0, 3] is 2. If you think carefully, all the integers from the range [0, 3] appear once (odd occurrence) except 2, which has 0 occurrences (even occurrence).

So, if you can make 2 appear once and the rest of the integers appear twice then taking xor of all the integers will result in 2, the answer. For this, you can utilize the information that the expected array is [0, 1, 2, 3] from which 2 is missing. So, taking xor of the integers in the expected array and, xor of the integers of the input array will result in the missing integer.

xor of expected array integers: 0 ^ 1 ^ 3 ^ 2
   xor of input array integers: 0 ^ 1 ^ 3

Here, 0, 1, and 3 appear twice and 2 appears once.

This can be easily achieved using a single loop.

Solution Code

If you are stuck with the solution of this problem, check the codes below:

C++

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

Java

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

Python

class Solution(object):
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        missing = n
        
        for i in range(0, n):
            missing ^= i ^ nums[i]
        
        return missing
           

C#

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

Ruby

# @param {Integer[]} nums
# @return {Integer}
def missing_number(nums)
    n = nums.length()
    missing = n
    n.times { |i| missing ^= i ^ nums[i] }
    missing
end