Find the Missing Number

Question

Given an array contains N numbers of 0 .. N, find which number doesn't exist in the array.

Example Given N = 3 and the array [0, 1, 3], return 2.

Challenge Do it in-place with O(1) extra memory and O(n) time.

Thoughts

因为array不是sorted的，所以也不能sort再去搜索，因为sort就要O(Nlogn)

可以想到用bit manipulation, 因为已经知道N, 可以从1-N做xor, 再对array里的number做一遍xor,得到的那个数就是missing number

Solution

class Solution:
    # @param nums: a list of integers
    # @return: an integer
    def findMissing(self, nums):
        # write your code here
        length = len(nums)
        completeX = 0
        for i in range(length + 1):
            completeX ^= i
        for num in nums:
            completeX ^= num
        return completeX