KJCP02 - Editorial

general
, , , , ,
1

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.