The code takes an integer n and takes in n-1 elements. The elements entered are all the numbers from 1 to n, except one of them. We are supposed to find the missing element.
This solution is the fastest. However, I don't understand it.
Can anyone explain it ?
#include <iostream>
int main(){
int g,n,i,k;
std::cin>>n;
for(i=1; i<n; i++){
std::cin>>g;
k^=i^g;
}
std::cout<<(k^n);
}
Input:
10
3 8 10 1 7 9 6 5 2
Output:
4
This uses the fact that XOR is commutative and associative (so order doesn't matter), and that x^x == 0 for all x.
It takes the XOR of all numbers between 1 and n, and also xors it with all the input numbers. Any number that was input will be XORed twice into the final result, and therefore will be cancelled out. The only number remaining will be the number that wasn't input. This number was only XORed once, and therefore this will be the value of the result of all the XORs.
For the example you gave: The input numbers are: 3 8 10 1 7 9 6 5 2
1^2^3^4^5^6^7^8^9^10 ^ 3^8^10^1^7^9^6^5^2 =
(1^1)^(2^2)^(3^3)^4^(5^5)^(6^6)^(7^7)^(8^8)^(9^9)^(10^10) =
4
Note that the code is written somewhat confusingly, because the order of XORs is not straightforward: it alternates between XORing an input and XORing the next number between 1 and n. This is only done to keep the code short. It would be clearer as:
k = 0;
for (i=1; i<=n; i++)
k ^= i;
for (i=0; i<n-1; i++) {
std::cin >> g;
k ^= g;
}
std::cout << k;