Missing Number [LeetCode]

Problem Description

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

For example,
Given nums = [0, 1, 3] return 2.

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

Solution
Again, similar to other bit manipulation problems, we can use XOR operator. One NOTE about XOR:
1. if A ^ B = C then A = B ^ C, and B = A ^ C,
2. and A^A = 0, 0 ^ A = A,
where ^ is XOR bit operator.
Since nums contains numbers from 0 to n with one number is missing, then if we xor all the numbers in nums with 0 ^ 1 ^ 2 ... ^ n, we will get the number we need to find.
Below is the codes.

I. Java Code

view plainprint?

1. public class Solution {  
2.     public int missingNumber(int[] nums) {  
3.         int r = 0;  
4.         for (int i = 0; i<nums.length; i++){  
5.             r ^=  i ^ nums[i];  
6.         }  
7.         return r ^ nums.length;  
8.     }  
9. }  

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

II. Python Code

view plainprint?

1. class Solution(object):  
2.     def missingNumber(self, nums):  
3.         """ 
4.         :type nums: List[int] 
5.         :rtype: int 
6.         """  
7.         r = 0  
8.         for i in range(len(nums)):  
9.             r ^= i ^ nums[i]  
10.         return r ^ len(nums)  

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

III. C++ Code

view plainprint?

1. class Solution {  
2. public:  
3.     int missingNumber(vector<int>& nums) {  
4.         int r = 0;   
5.         for (int i = 0; i<nums.size(); i++){  
6.             r ^= i ^ nums[i];  
7.         }  
8.         return r ^ nums.size();  
9.     }  
10. };  

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

IV. Javascript Code

view plainprint?

1. /**  
2.  * @param {number[]} nums  
3.  * @return {number}  
4.  */  
5. var missingNumber = function(nums) {  
6.     var r = 0;  
7.     for(var i = 0; i<nums.length; i++){  
8.         r ^= i ^ nums[i];  
9.     }  
10.     return r ^ nums.length;  
11. };  

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

Appendix A: Other methods
We can use other methods such as Hash Table with O(n) space complexity. We also can get the number by summing up all the elements in the array, the take the difference of n(n+1)/2 and that sum. (NOTE: n(n+1)/2 is the sum of numbers from 0 to n).