HDU 2095 找你的禮物：異或運算的經典應用

問題描述

新年派對上有 n 個禮物（n 為奇數），每個禮物有一個卡片號碼。只有一個號碼出現奇數次，其餘均出現偶數次。輸入多組測試數據，每組先給 n，再給 n 個正整數（< 2^31），輸出那個出現奇數次的號碼。n = 0 結束輸入。

核心洞察：異或運算性質

• x ^ x = 0（相同數異或為 0）
• x ^ 0 = x（任何數與 0 異或不變）
• 異或滿足交換律與結合律

因此，將所有號碼異或起來，成對出現的數字會抵消為 0，最終結果即為那個出現奇數次的數字。

算法複雜度

• 時間：O(n) 每測試用例，單次掃描。
• 空間：O(1)，只需一個變量累積異或值。

完整 C++ 代碼

#include <cstdio>

int main() {
    int n;
    while (scanf("%d", &n) == 1 && n) {
        int ans = 0, x;
        for (int i = 0; i < n; ++i) {
            scanf("%d", &x);
            ans ^= x;
        }
        printf("%d\n", ans);
    }
    return 0;
}

樣例演示

輸入：
5
1 1 3 2 2
3
1 2 1
0

輸出：
3
2

第一組：1^1^3^2^2 = 0^3^0 = 3；第二組：1^2^1 = 2。

避坑指南

• 輸入規模大（n < 1,000,000），必須使用 scanf/printf 或關閉同步流，否則會 TLE。
• 題目保證只有一個數出現奇數次，無需驗證輸入合法性。

舉一反三

此技巧廣泛應用於「找出唯一出現一次/奇數次的元素」類問題，如 LeetCode 136「只出現一次的數字」、LeetCode 260「只出現一次的數字 III」（需結合位運算分組）。