17

n 個の整数のリストが与えられましたが、これらの整数の範囲は 1 から n です。リストに重複はありませんが、整数の 1 つがリストにありません。欠落している整数を見つけなければなりません。 

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.

ただし、数値の合計が最大許容整数を超えると、上記の方法は失敗します。

だから私は2番目の解決策を探し、次のような方法を見つけました:

 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 はどのようにして不足している整数を見つけますか?

4

4 に答える 4

31

あなたの質問に答えるには、それを覚えておく必要があります

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 のこの特性により、単純な (ただし自明ではない) 形式の暗号化に適しています。

于 2013-08-20T13:05:53.280 に答える