缺少在C++中输入的值中的元素

Question

代码采用整数n并接受n-1元素.输入的元素都是从数字1到n,除非他们中的一个.我们应该找到缺失的元素.

这个解决方案是最快的.但是,我不明白.
有人能解释一下吗？

#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);
}

输入:

10
3 8 10 1 7 9 6 5 2

输出:

4

Answer 1

这使用了XOR是可交换和关联的事实(所以顺序无关紧要),以及x^x == 0所有这些x.

它取所有数字在1和n之间的XOR,并且还与所有输入数字相关.输入的任何数字将在最终结果中进行两次异或,因此将被取消.剩下的唯一数字是未输入的数字.这个数字只被XOR一次,因此这将是所有XOR的结果值.

对于您给出的示例:输入数字为: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

请注意,代码编写有些令人困惑,因为XOR的顺序并不简单:它在对输入进行异或运算和对1和n之间的下一个数字进行异或运算之间进行交替.这样做只是为了保持代码简短.它会更清楚:

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;