---
title: 1A 遺失的數字
tags: solution
---

# A. 遺失的數字

### 1. Summation Version : $\frac{N(N+1)}{2}-\sum x$

最簡單的直覺方式是將數字總合起來，並檢查與原本1~N的級數和差多少，
便可以找出其缺失的數字為多少。

但要注意總和後數字會在int範圍溢位的情形 :
$2\times10^5\times(2\times10^5+1) = 40000200000 > 2147483647$。

可以使用 **unsigned int** 或 **long** 以上的資料型態進行實作。

> Time Complexity : $O(N)$

# include <iostream>
using namespace std;

int main(){
    long long N,num,sum;
    cin>>N;
    sum = N*(N+1)/2;
    
    while(N--){
        cin >> num;
        sum -= num;
    }
    cout<<sum;
}

---

### 2. XOR Version :
利用XOR自反律的特性，也就是 (p\^q)\^p = q 之算術特性，並可以利用「位元運算」些微的加速。
且因其數字範圍必定會 $\leq N$，不需要考慮會溢位的問題。
> Time Complexity : $O(N)$

# include <iostream>
using namespace std;

int main(){
    int N,n,ans = 0;
    cin>>N;

    for(n = 1 ; n<=N ; n++)
        ans ^= n;

    while(--N){
        cin>>n;
        ans ^= n;
    }
    cout<<ans;
}