MissingNumber.cpp

#include <bits/stdc++.h>
using namespace std;

void swap(int*a,int*b){
    int temp = *a;
    *a = *b;
    *b = temp;
}

int gcd(int a,int b){
    if(a > b)return gcd(b,a);
   
    while(b%a){
        a = b%a;   
    }
    return a;
}

void solve(vector<int>array,int n){
    sort(array.begin(),array.end());

    int l = 0;
    int r = n-1;

    if(array[0] != 1){cout << 1;return;}
    if(array[n-2] != n){cout << n ;return;}

    while(l < r){
        int mid = (l + r + 1)/2;

        if(array[mid] - array[mid-1] >= 2){
            l = mid+1;
            break;
        }else if(array[mid+1] - array[mid] >= 2){
            l = mid+2;break;
        }

        if(array[mid] > mid + 1){
            r = mid;
        }else{
            l = mid;
        }
    }

    cout << l;
    return;

}

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

    vector<int>array(n-1);
    for(int i = 0 ;  i < n-1 ; i ++)cin >> array[i];

    solve(array,n);
    return 0;
}