查找序列中缺少的数字 [英] Finding the number missing in the sequence

问题描述

已为我提供了n个整数的列表，这些整数在1到n的范围内。列表中没有重复项。但是列表中缺少整数之一。我必须找到丢失的整数。

I have been given a list of n integers and these integers are in the range of 1 to n. There are no duplicates in list.But one of the integers is missing in the list.I have to find the missing integer.

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.

但是，如果数字的总和超过最大允许整数，则上述方法将失败。

But the above method will fail if the sum of the numbers goes beyond maximum allowed integer.

所以我搜索了第二个解决方案，发现了如下方法：

So i searched for a second solution and i found a method as follows:

 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如何在中找到丢失的整数

How is this method working?..How is the XOR of R1 and R2 finds the missing integer in the above case?

推荐答案

要回答您的问题，您只需记住

To answer your question , you just have to remember that

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

，并且紧随其后的是

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

证明第一个属性，只需写下XOR真值表：

To prove the first property, just write down the XOR truth table:

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

真值表简述：如果两个位相同，则XOR的结果为false，否则为true

Truth table in short : if both the bits are same, result of XOR is false, true otherwise.

不相干的是，XOR的此属性使其成为简单（但不平凡）加密形式的不错选择。

On an unrelated note, this property of XOR makes it a nice candidate for simple ( but not trivial ) forms of encryption.

这篇关于查找序列中缺少的数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！