268. 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.

Example 1:

Input: [3,0,1]
Output: 2

Example 2:

Input: [9,6,4,2,3,5,7,0,1]
Output: 8

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

Problem Summary

Given a sequence containing n numbers from 0, 1, 2, ..., n, find the number in 0 .. n that does not appear in the sequence. The algorithm should have linear time complexity. Can you implement it using only constant extra space?

Solution Ideas

• The requirement is to find the missing number among 0, 1, 2, ..., n. Still use the property of XOR, X^X = 0. Here we need to construct an X, and we can use the array indices. The numeric indices are from [0, n-1], and the numbers are [0, n]. XOR the numbers in the array one by one, then XOR the result with n once more to cancel out the numbers that appear. The remaining number is the one that did not appear before, the missing number.

Code

package leetcode

func missingNumber(nums []int) int {
	xor, i := 0, 0
	for i = 0; i < len(nums); i++ {
		xor = xor ^ i ^ nums[i]
	}
	return xor ^ i
}