In this HackerEarth Discover the Monk problem solution You are given an array A of size N, and Q queries to deal with. For each query, you are given an integer X, and you're supposed to find out if X is present in the array A or not.


HackerEarth Discover the Monk problem solution


HackerEarth Discover the Monk problem solution.

#include <iostream>
#include <cassert>
#include <algorithm>
#include <vector>

using namespace std;
vector <long long > v;

int main()
{
int n, q;
long long x;
cin >> n >> q;
assert(1 <= n and n <= 100000);
assert(1 <= q and q <= 100000);
for(int i = 0;i < n;++i)
{
cin >> x;
v.push_back(x);
}
sort(v.begin(), v.end());
string s;
for(int i = 0;i < q;++i)
{
cin >> x;
assert(1 <= x and x <= 1000000000LL);
if(binary_search(v.begin(), v.end(), x))
s = "YES";
else
s = "NO";
cout << s << endl;
}
}

Second solution

#include <bits/stdc++.h>
using namespace std;
int main()
{
int N,Q;
cin>>N>>Q;
int a[N];
for(int i=0;i<N;i++)
cin>>a[i];
sort(A,A+N);
for(int i=0;i<Q;i++)
{
int X;
cin>>X;
bool flag=false;
int lb=0,ub=N-1;
while(lb<=ub)
{
int mid=(lb+ub)/2;
if(a[mid]>X)
ub=mid-1;
else if(a[mid]<X)
lb=mid+1;
else
{
flag=true;
break;
}
}
if(flag)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}