/*
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?

Credits:
 */

/*
 * 本题要找出 0...n 中缺少的数，使用位运算的效率最高
 * 使 res 异或 0...n 中的每个数，再异或 nums 向量中的每个数
 * 异或两次不修改原值，仅异或一次的数被留在 res 中
 */

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