Найдите недостающий номер с помощью логики XOR

Question

Учитывая массив C размера N-1 и учитывая, что есть числа от 1 до N с отсутствующим одним элементом, недостающий номер должен быть найден.

Я видел, что это может быть решено с использованием некоторого интересного свойства XOR.

Интересное свойство:

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

Then x ^ y = an

Я пытался понять лог c, но мне это не удалось.

Может кто-нибудь объяснить logi c там участвует?

Answer 1

a ^ a по определению 0, и в вашем случае вы вычисляете:

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]