Explanation:
We need to output if a given query/number is present in the given list of numbers.
a brute force solution is to do a liner search for each query Time Complexity: O(Q*N)
another solution is to sort the numbers and then for each query do a binary search Time Complexity : O(nlogn + Qlogn)
An easier solution for this and optimal solution is to use a count array which stores frequency of each element or rather use a bool count array to check if a element is there Time Complexity : O(n+q)
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int a[n];
bool ck[1001];
memset(ck,false,sizeof(ck));
for(int i=0;i<n;i++)
{
cin>>a[i];
ck[a[i]]=true;
}
int q;
cin>>q;
while(q--)
{
int x;
cin>>x;
if(ck[x])
{
cout<<"1\n";
}
else
{
cout<<"0\n";
}
}
}
Code In C:
#include<stdio.h>
int main()
{
int n;
scanf("%d",&n);
int a[n];
int ck[1001]={0};
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
ck[a[i]]=1;
}
int q;
scanf("%d",&q);
while(q--)
{
int x;
scanf("%d",&x);
if(ck[x])
{
printf("1\n");
}
else
{
printf("0\n");
}
}
}