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:
Output: 2
Example 2
Input:
Output: 8
一个“简单”的问题，深思之后似乎并没有那么简单。
最开始的版本：
int missingNumber(int* nums, int numsSize)
{
int sum = 0;
sum = numsSize *(numsSize + 1) / 2;
for(int i = 0;i < numsSize;i++)
sum = sum - nums[i];
return sum;
}
程序很简单，1到n的和减去数组的每个元素，最后剩下的值就是缺失的元素。可是这里存在一个溢出的风险，numsSize *(numsSize + 1)可能超出int表示的最大范围，在不改变数据类型的前提下可以采用如下方法：
int missingNumber(int* nums, int numsSize)
{
int sum = 0;
if(0 == numsSize % 2)
sum = numsSize/2 *(numsSize + 1);
else
sum = (numsSize + 1)/2 *(numsSize);
for(int i = 0;i < numsSize;i++)
sum = sum - nums[i];
return sum;
}
另一种方法：
int missingNumber(int* nums, int numsSize)
{
int sum = 0;
int i = 0;
for(i = 0;i < numsSize;i++)
sum = sum + i - nums[i];
return sum + i;
}
以上代码均存在溢出风险，采用异或操作可以避免溢出，代码如下：
int missingNumber(int* nums, int numsSize)
{
int xor = 0;
int i = 0;
for(i = 0;i < numsSize;i++)
xor = xor ^ i ^ nums[i];
return xor ^ i;
}
异或操作可行性源于两个相同的数字异或为0，因此最后的结果就是缺失的数字，异或的顺序不重要。