PROBLEM LINK:
Second Year Pains
Practice
Contest
Author: Vatsal Kanakiya
Tester: Dipen Ved
Editorialist: Chaitya Shah
DIFFICULTY:
EASY
PREREQUISITES:
Hashing and STL Maps.
PROBLEM:
Given an array of N integers find out whether the X is in the array or not.
QUICK EXPLANATION:
Take input using A normal array and hash the value using a map to 1.
Now just check if value at X is 1 or not to check if it is in the array or not.

Note: In ith iteration X will become
part of the array and we will have a
new array of length N+i
EXPLANATION:
Letâ€™s first consider solving the problem for a single test case. We will read N and M first than N integers. Now we want to hash the N integers so we will read each integer using a variable
Letâ€™s say temp and hash it.
So the code looks like:
for(int i=0;i<N;i++) {
int temp;
scanf("%d",&temp);
M[temp] = 1;
}
Now we will read M integers and check whether if the value in the map is 1 or not,
If it is 1 we print â€śYESâ€ť (without quotes) and else we print â€śNOâ€ť (without quotes) and hash the value of that integer to 1.
So the code looks like
for(int j = 0;j<M;j++){
int temp;
scanf(â€ś%dâ€ť,&temp);
if(M[temp] ) printf(â€śYES\nâ€ť);
else{
printf(â€śNO\nâ€ť);
M[temp] = 1;
}
}
ALTERNATIVE SOLUTION:
You can also do this using a set and check whether the element is in the set or not.
You can also use a huge array according to the constraints and hash the array without Maps.
AUTHORâ€™S AND TESTERâ€™S SOLUTIONS:
Authorâ€™s solution can be found here.