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.

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?

Tags

• Maths
• Bit Manipulation
• Hash Table

Thought

There are many different solutions: maths, bit manipulation or hash. Here I will introduce the later two methods.

Hash Table:

1. Define a variable named bucket to store the missing number. The initial value should be the length of the array.
2. Modify the array to build the self-defined hash table such that A[i] = i or A[i] = i + 1.
3. Run the whole array to build the hash table. When the value of position in the original array is equal to the bucket, decrease the bucket and the index value by 1 and continue.
4. The final bucket number will be the result.

Bit Manipulation:

Considering the Single number, if we use the xor for the whole list and a self-defined list without missing value, the final result will be the answer.

Code

class Solution(object):
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # Hash table
        bucket = len(nums)
        for i in xrange(len(nums)):
            idx = nums[i]
            while idx != i:
                if i >= bucket and idx == i + 1:
                    break
                if idx == bucket:
                    idx -= 1
                    bucket -= 1
                tmp = nums[idx]
                nums[idx] = nums[i]
                nums[i] = tmp
                idx = nums[i]
        return bucket

        # use bit manipulation
        result = 0
        for i in xrange(len(nums) + 1):
            result ^= i
        for num in nums:
            result ^= num
        return result