找到序列中缺少的数字

Question

我得到了一个n个整数的列表,这些整数在1到n的范围内.列表中没有重复项.但是列表中缺少其中一个整数.我必须找到缺少的整数.

Example: If n=8
I/P    [7,2,6,5,3,1,8]
O/P    4

I am using a simple concept to find the missing number which is to get the 
sum of numbers 
       total = n*(n+1)/2
And then Subtract all the numbers from sum.

但是如果数字的总和超出允许的最大整数,则上述方法将失败.

所以我搜索了第二个解决方案,我找到了一个方法如下:

 1) XOR all the elements present in arr[], let the result of XOR be R1.
 2) XOR all numbers from 1 to n, let XOR be R2.
 3) XOR of R1 and R2 gives the missing number.

这个方法是如何工作的？在上述情况下,R1和R2的XOR如何找到缺失的整数？

Answer 1

要回答你的问题,你必须记住这一点

A XOR B = C => C XOR A = B

紧接着就是这样

(PARTIAL SUM) XOR (MISSING ELEMENT) = (TOTAL) => 
(TOTAL) XOR ( PATIAL SUM) = (MISSING ELEMNT)

要证明第一个属性,只需写下XOR真值表:

A B | A XOR B
0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 0

简而言之:如果两个位都相同,则XOR的结果为false,否则为true.

在一个不相关的说明中,XOR的这个属性使它成为简单(但不是微不足道)加密形式的一个很好的候选者.