Missing Number

• LeetCode: Missing Number

• Problem:

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

• Note:

Your algorithm should run in linear runtime complexity. 

Could you implement it using only constant extra space complexity?

• Examples:

For example,

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

• Analysis:

Use XOR notation to find the missing number.

• Code - Java:

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

• Code - C++:

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

• Code - Python:

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

• Code - C:

int missingNumber(int* nums, int numsSize) {
    int len = numsSize;
    int result = len;
    for (int i = 0; i < len; i++) {
        result ^= nums[i];
        result ^= i;
    }
    return result;
}

• Time Complexity: O(N), N is the length of nums.

• Space Complexity: O(1)