# HackerEarth Sherlock and Numbers problem solution

In this HackerEarth Sherlock and Numbers problem solution Watson gives to Sherlock a bag of numbers [1, 2, 3 ... N] and then he removes K numbers A1, A2 ... AK from the bag. He now asks Sherlock to find the P'th smallest number in the bag.

## HackerEarth Sherlock and Numbers problem solution.

`#include<bits/stdc++.h>#define assn(n,a,b) assert(n<=b && n>=a)using namespace std;#define pb push_back#define mp make_pair#define clr(x) x.clear()#define sz(x) ((int)(x).size())#define F first#define S second#define REP(i,a,b) for(i=a;i<b;i++)#define rep(i,b) for(i=0;i<b;i++)#define rep1(i,b) for(i=1;i<=b;i++)#define pdn(n) printf("%d\n",n)#define sl(n) scanf("%lld",&n)#define sd(n) scanf("%d",&n)#define pn printf("\n")typedef pair<int,int> PII;typedef vector<PII> VPII;typedef vector<int> VI;typedef vector<VI> VVI;typedef long long LL;#define MOD 1000000007LL mpow(LL a, LL n) {LL ret=1;LL b=a;while(n) {if(n&1)     ret=(ret*b)%MOD;b=(b*b)%MOD;n>>=1;}return (LL)ret;}#define MAXK 100000#define MAXN 1000000000int ar[MAXK];int get(int n, int k){    int i=0;    while(i<k and ar[i]<=n)i++;    return n-i;}int main(){    int t;    sd(t);    assn(t,1,10);    while(t--){        int n,k,p,s=0;        sd(n),sd(k),sd(p);        assn(n,1,MAXN);        assn(k,0,MAXK);        assn(p,1,n);        for(int i=0; i<k; i++)            sd(ar[i]);        sort(ar,ar+k);        int l=0,r=n,mid;        if(get(r,k)<p){            pdn(-1);            continue;        }        while(r-l>1){            mid=(r+l)/2;            int q=get(mid,k);            if(q<p)l=mid;            else r=mid;        }        pdn(l+1);    }    return 0;}`

### Second solution

`#include <cstdio>#include <cmath>#include <iostream>#include <set>#include <algorithm>#include <vector>#include <map>#include <cassert>#include <string>#include <cstring>#include <queue>using namespace std;#define rep(i,a,b) for(int i = a; i < b; i++)#define S(x) scanf("%d",&x)#define S2(x,y) scanf("%d%d",&x,&y)#define P(x) printf("%d\n",x)#define all(v) v.begin(),v.end()#define sz size()typedef long long int LL;typedef pair<int, int > pii;typedef vector<int > vi;set<int > s;vi v;int lessThan(int x) {  int lo = 0, hi = (int)v.size() - 1;  int res = -1;  while(lo <= hi) {    int mi = (lo + hi) >> 1;    if(v[mi] <= x) {      res = mi;      lo = mi + 1;    } else {      hi = mi - 1;    }  }  return res + 1;}int main() {  int t;  S(t);  assert(t >= 1 && t <= 10);  while(t--) {    int n,k,p;    scanf("%d%d%d",&n,&k,&p);    assert(n >= 1 && n <= 1000000000);    assert(k >= 1 && k <= min(n, 100000));    assert(p >= 1 && p <= 1000000000);    s.clear();    v.clear();    rep(i,0,k) {      int x;      S(x);      assert(x >= 1 && x <= n);      if(s.find(x) == s.end()) {        v.push_back(x);        s.insert(x);      }    }    sort(all(v));    int lo = 1, hi = 2*n;    int ans = 0;    while(lo <= hi) {      int mi = (lo + hi * 1LL) / 2;      int x = lessThan(mi);      int tot = mi - x;      if(tot >= p) {        ans = mi;        hi = mi - 1;      } else {        lo = mi + 1;      }    }    if(ans > n) ans = -1;    P(ans);  }  return 0;}`