Answer many membership questions quickly.
What to build
A program that chooses the right structure for repeated lookups.
Requirements
- Read the numbers and store them in a set.
- For each query, print
YESif it is among the numbers, otherwiseNO.
Input
The first line has n. The second line has n whole numbers. The third line has q. The fourth line has q whole numbers.
Output
q lines.
Constraints
n and q are from 1 to 100000.
Example
Input:
3
1 2 3
2
2 5
Output:
YES
NO
Why it works
A list would be searched from the start for every query, up to n times q steps. A set finds each answer in about the same time, however large it is.
Examples
Example 1 · Input
3 1 2 3 2 2 5
Expected output
YES NO
Example 2 · Input
1 7 1 7
Expected output
YES
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Put the numbers in a set first.
Hint 2
x in my_set is very fast.
Solution
Show one correct solution (try it yourself first)
n = int(input())
nums = set(input().split())
q = int(input())
for x in input().split():
print("YES" if x in nums else "NO")