Мне предоставлен список из 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.
Как этот метод работает?.. Как XOR R1 и R2 находит недостающее целое в приведенном выше случае?