题解：落单的编号

思路

异或有三个关键性质：

• x ^ x = 0；
• x ^ 0 = x；
• 异或满足交换律和结合律。

因此把所有编号依次异或，成对编号会互相抵消，最后只剩下落单编号。

复杂度

时间复杂度 $O(n)$，额外空间复杂度 $O(1)$。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    unsigned int ans = 0;
    for (int i = 0; i < n; i++) {
        unsigned int x;
        cin >> x;
        ans ^= x;
    }
    cout << ans << "\n";
    return 0;
}