CSES 1. Missing Number (1083)

출처: https://cses.fi/problemset/task/1083

---

문제 설명

You are given all numbers between 1,2,…,n except one. Your task is to find the missing number.

입력 

The first input line contains an integer n.

The second line contains n−1 numbers. Each number is distinct and between 1 and n (inclusive).

출력 

Print the missing number.

입력 예

5
2 3 1 5

출력 예

4

---

문제 풀이

2 <= n <= 2⋅10^5,

1~N까지 합이 N*(N+1)/2 이므로, 입력들을 다 더해서 두 수의 차이를 비교하면 답을 찾을 수 있다.

 

프로그램 내용

#define MAX_N 2*100000

int main()
{
    int n;
    cin >> n;

    if (n > 2*100000) return 0;

    long sum=0;
    for(int i=0; i<n-1;i++)
        int temp;
        cin >> temp;
        sum += temp;

    long expected_sum = n*(n+1)/2;

    int missing = expected_sum - sum;

    cout << missing << endl;

 

Introductory problems ( link )