Day 1: Lens Stacking

easyGreedytwo pointersBinary Search

An optical technician has a collection of lenses, each with an integer magnification factor. The magnification factors of the lenses are given in a sorted array

L

of length

N

.

By stacking two distinct lenses together, their magnifications multiply. That is, using lens

i

and lens

j

(

i

not equal to

j

), the total magnification becomes

L_i \times L_j

.

You are given a target magnification

M

. Determine whether there exists any pair of distinct lenses whose combined magnification is exactly

M

Input Format:

The first line contains two integers

N

and

M

(

2 \le N \le 2 \cdot 10^5

1 \le M \le 10^{12}

) --- the number of lenses and the target magnification.
The second line contains

N

integers

L_1, L_2, \ldots, L_N

(

1 \le L_i \le 10^6

), representing the magnification factors of the lenses. The array is sorted in non-decreasing order.

Output Format:

Output YES if there exists a pair of lenses with magnifications that multiply to

M

. Otherwise, output NO.

Examples:

Example 1:

Input:

2 50
5 10

Output:

YES

Example 2:

Input:

4 5000000
10 100 2000 500000

Output:

YES

Example 3:

Input:

2 90
1 2

Output:

NO

Day 1: Lens Stacking

Input Format:

Output Format:

Examples:

Example 1:

Example 2:

Example 3:

Code