CODEWITHSUNDEEP
c++bitlogical-operatorsxor
MathGeek
MathGeek

Reputation: 531

Find the missing number using XOR logic

Given an array C of size N-1 and given that there are numbers from 1 to N with one element missing, the missing number is to be found.

I have seen that it can be solved using some interesting property of XOR.

The interesting property is 

Assume a1 ^ a2 ^ a3 ^ …^ an = x and a1 ^ a2 ^ a3 ^ …^ an-1 = y

Then x ^ y = an

I tried to understand the logic but I failed.

Can someone explain the logic involved there?

Upvotes: 0

Views: 214

Answers (1)

Blindy
Blindy

Reputation: 67382

a ^ a is by definition 0, and in your case you're calculating:

x: a[0] ^ a[1] ^ a[2] ^ .. ^ a[n-1] ^ a[n] ^
y: a[0] ^ a[1] ^ a[2] ^ .. ^ a[n-1]        
   =======================================
      0 ^    0 ^    0 ^ .. ^      0 ^ a[n] = a[n]

Upvotes: 4

Related Questions