Missing Number

Question: Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

You may view the full question here.

Approach: Let’s steer away from the usual approaches and try something less obvious. Here are two approaches inspired from the Leetcode solution section.

Approach 1: This solution uses XOR operation. Let’s have a quick recap of XOR operation —

XOR Table

The wiki definition states that this operator return 1 only when one of its inputs is 1. That’s one way of putting it. If you look closely, whenever the operands are similar say (0,0) or (1,1) the result is 0. Now, let’s try leveraging this property.

Coming back to our problem — if all the values in the list existed and none were missing, and all the values were sorted, we would have a list that looks like this —

In the above list, if we XOR-ed all the values and the indices, the cumulative result will be zero.

But, the actual list at hand has a missing value, therefore, the corresponding index will not have a valid match to be XOR-ed with. As a result, the cumulative XOR of our input list will have all the values XOR-ed to 0, except the one value that is missing. That missing value will be our result that needs to be returned.

//Approach 1:
//Runtime: 0ms
//Memory usage: 39.4MB
class Solution {
    public int missingNumber(int[] nums) {
        int result = nums.length;
        for(int i = 0; i<nums.length; i++){
            result ^= i ^ nums[i];
        }
        return result;
    }
}

Approach 2: Hopefully the previous approach has the set the stage for the kind of solutions we are trying to discuss here. We are trying to understand how a given set behaves as a group and see the deviation when one value is missing.

Gauss’ Formula is yet another way to estimate which value is missing. Here, we understand that the values from 0 to n always add to a definite number that can be computed with the formula (Gauss’ Formula)=n*(n+1)/2

Now, if we add our input list, this sum will be exactly short by the missing value. So, we simply return the difference as the result.

//Approach 2:
//Runtime: 0ms
//Memory usage: 39.8MB
class Solution {
    public int missingNumber(int[] nums) {
        int sum = 0;
        for(int i = 0; i<nums.length; i++){
            sum+=nums[i];
        }
        return ((nums.length)*(nums.length + 1)/2) - sum;
    }
}

Find more posts here.

Cheers & Chao!