시퀀스에서 누락 된 번호 찾기

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의 XOR 인 방법 및 R2는 전술 한 경우에 누락 정수 발견 ? 모든

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의 결과가 O를 참 거짓 그런데. 관련이없는 노트에

는 XOR의이 속성은 암호화의 간단한 (하지만 사소한되지 않음) 형태에 대한 좋은 후보합니다.

Answer 2

첫째, 당신은 (한 n가 int에 맞는로)도 정수 오버 플로우의 존재에 원래의 방법 일 수 있습니다.

XOR 방법에 대해서는 R1 xor M == R2 (여기서 M은 누락 된 숫자 임)을 준수하십시오. 이로부터 R1 xor M xor R2 == 0이고 따라서 M == R1 xor R2이됩니다.

Answer 3

XOR 작품마다 있기 때문에 당신은 XOR1와 비트 당신은 그것을 뒤집은 때마다 당신은이 같은 0와 비트를 유지 XOR. 따라서 XOR의 결과로 누락 된 숫자를 저장하면 모든 데이터가 XOR이라는 '부정적'인상을줍니다. XOR이 두 항목을 함께 사용하면 손실 된 번호가 복원됩니다.

Answer 4

간단히하기 위해 하위 비트 (LOB)의 XOR을 살펴 보겠습니다. x를 누락 된 정수라고합시다.

목록의 각 정수 1 또는 0 R1 (LOB (R1))의 LOB를 기여한다.

범위에서 각각 정수 1 또는 LOB (R2)을 제로에 기여한다.

이제 LOB (R1) == LOB (R2)라고 가정하십시오. R2 == R2 XOR x이므로 LOB (x) == 0 == LOB (R1) XOR LOB (R2) 인 경우에만 발생합니다. (1 XOR 1 = 0, 0 XOR 0 = 0)

또는 가정 ((R1) == LOB (R2)이.이 만 일어날 수 LOB LOB (X) == 1 == 로브 (R1) XOR 경우

그러나 XOR은 비트 단위로 독립적으로 계산되기 때문에 하위 비트는 모두 작동합니다.