Đề bài
Cho dãy gồm $N-1$ số nguyên dương chứa các giá trị trong khoảng từ $1\to N$. Bạn được biết thông thêm thông tin là dãy này thiếu đúng một số. Nhiệm vụ của bạn là phải tìm được chính xác số còn thiếu đó.
Dữ liệu:
- Dòng đầu tiên chứa số nguyên $N$ $(2 \le N \le 2*10^5)$.
- Dòng thứ hai chứa $N-1$ số $a_i$ phân biệt với $a_i \in [1,N]$.
Kết quả:
- Một dòng duy nhất ghi ra giá trị còn thiếu.
Ví dụ:
Input
6
1 2 3 5 6
Output
4
Hướng dẫn
- Do có duy nhất một số bị thiếu nên ta có thể dùng công thức sau: $$Answer=Sum-CurrentSum$$
- Trong đó:
- Tổng từ $1\to N$ như sau: $Sum = \dfrac{N*(N+1)}{2}$.
- Tổng tất cả các số trong dãy sẽ là $CurrentSum = \sum a_i ; \forall i \in [1,N)$.
Mã nguồn tham khảo
[Đăng ký tài khoản để xem mã nguồn]
#include <bits/stdc++.h>
using namespace std;
#define task "test"
int n;
void solve(){
cin >> n;
long long currentsum = 0;
for(int i=1;i<n;i++){
int a;
cin >> a;
currentsum+=a;
}
cout << (1LL*(n+1)*n/2) - currentsum;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if(freopen(task".inp","r",stdin)){
freopen(task".out","w",stdout);
}
int t;
t=1;
while(t-->0){
solve();
}
}