題意#
題目給定一個包含 \( n - 1 \) 個數字的數列。
這些數字原先範圍為 \( 1 \) 到 \( n \)，其中少了一個數。
要求找出缺少的數字。
思路#
除了開陣列紀錄數字，我們也可以利用 XOR（互斥或）的特性。
兩個相同的數字進行 XOR 運算會變成 0。
我們準備一個變數，與 \( 1 \) 到 \( n \) 的所有數字作 XOR，
再與輸入的 \( n - 1 \) 個數字作 XOR。
有出現的數字會被 XOR 兩次而抵銷歸零。
缺少的數字只會被作 XOR 一次，
最後變數留下的值就是答案。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define WA() cin.tie(0)->sync_with_stdio(0)
#define int long long
signed main() { WA();
int n, xr = 0; // xr 用來做位元 XOR 運算，初始值為 0
cin >> n; // 讀取數列預期長度 n
vector<int> v(n-1);
for (auto &i : v) cin >> i; // 讀取缺了一個數字的數列
// 同時與陣列元素以及 1~n-1 進行 XOR 運算
for (int i = 0; i < n-1; i++) {
xr ^= v[i]; // XOR 原有陣列內的數字
xr ^= i+1; // XOR 1 到 n-1 之間的數字
}
xr ^= n; // 最後補上數字 n 進行 XOR
cout << xr; // 經過成對抵銷後，殘留下來的 xr 就是不見的數字
}
