21｜缺少的數字
相關主題： 控制記憶體的必備指令、資料型態與範圍
C 或 C++ 皆可｜CPU 時間上限 2 秒｜記憶體預算 2048 bytes（2 KB，heap + 全域/靜態資料 + stack 合計）
1 到 n 這 n 個整數，有人把其中 n - 1 個打亂順序送過來，剛好漏掉了一個。請找出漏掉的是哪一個數字。
最直覺的做法是開一個陣列記錄「哪些數字出現過」，最後看哪一格沒被標記到。可是 n 最多 200000，這個陣列用 bool 也要 200000 bytes，而記憶體預算只有 2048 bytes。
這一題要用一點數學：不必記住任何一個讀過的數字，只靠一兩個變數就能找出答案。
- 第一行是一個整數 n（2 ≤ n ≤ 200000）。
- 第二行有 n - 1 個整數，數字之間用一個空格隔開。它們是 1 到 n 之中 n - 1 個不同的數字，順序是打亂的。
一行一個整數：1 到 n 之中，沒有出現在輸入裡的那個數字。
輸入：
52 5 1 4輸出：
31 到 5 之中，2、5、1、4 都出現了，只有 3 沒有出現。
記憶體預算怎麼算
Section titled “記憶體預算怎麼算”檢查時會把下面三項加起來，合計不能超過 2048 bytes：
| 項目 | 包含什麼 |
|---|---|
| heap 最高用量 | 執行期間「同一時間還沒釋放」的 malloc / calloc / realloc / new 的最大總量，包含 std::vector 等標準函式庫容器在內部配置的記憶體 |
| 全域 / 靜態資料 | 全域變數、static 變數，加上常數和字串常值（例如格式字串 "%d\n"） |
| stack 最深用量（約） | 區域變數、函式呼叫，以及 scanf / printf 等函式內部用到的 stack。程式啟動和最基本的輸入輸出本身用掉的部分（約 5 KB）會自動扣掉 |
C 執行環境內部的輸入輸出緩衝區不計算，所以正常使用 scanf / printf 或 std::cin / std::cout 不必擔心。檢查結果最後的「記憶體預算」會列出這三項各用了多少。
幾個常見的陷阱：
bool seen[200001]要 200001 bytes；就算用第 22 題的位元技巧壓縮成每個數字 1 個位元，也還要 25000 bytes。都超過預算。- 把數字存進陣列再排序：200000 個
int要 800000 bytes。 - C++20 的
std::format會把約 12.5 KB 的表格放進你的程式（算在「常數與字串」），這一題用不起。 - 1 加到 200000 的總和約 2 × 10^10，
int裝不下（最大約 2.1 × 10^9）。int溢位時第一階段的 Sanitizer 會抓到signed integer overflow。
C：
- 等差級數：1 + 2 + … + n = n × (n + 1) / 2
long long和%lld；轉型要在乘法之前：(long long)n * (n + 1)- XOR 運算子
^：a ^ a == 0、a ^ 0 == a
C++：
- 同上的公式和
long long ^=運算子- 在迴圈裡用
std::cin >> x一次讀一個數字，不需要std::vector
提示 1：如果什麼都沒漏掉…
如果 1 到 n 全部都在，加起來會是多少？（高中學過的等差級數公式。）
現在少了一個數字，實際讀到的總和就會比「應該有的總和」少一點。少了多少？
讀數字的時候只需要把它加進總和，加完就不用再記得它了。
提示 2：小心溢位
n = 200000 時，1 加到 n 的總和約 2 × 10^10，超過 int 的上限 2147483647，所以總和要用 long long。
還要注意轉型的時機：
(long long)n * (n + 1) / 2：n 先變成long long，乘法用long long計算，正確。(long long)(n * (n + 1) / 2)：括號裡的乘法已經用int算完（已經溢位）才轉型，來不及了。
提示 3：另一種完全不會溢位的做法：XOR
XOR（^）是逐位元運算，有這些性質：
a ^ a == 0：同一個數字 XOR 兩次會互相抵消a ^ 0 == a- 順序不影響結果：
a ^ b ^ c == c ^ a ^ b
如果把 1、2、…、n 和讀到的 n - 1 個數字全部 XOR 在一起，出現兩次的數字都會抵消掉，最後剩下的是什麼？
XOR 沒有進位：參與運算的數字都小於 2^18（262144）時，XOR 的結果也一定小於 2^18，所以用 int 就不會溢位。