Problem Idea

The problem basically gives an array of positive integers (each value is between 1 and 67). For every test case, we need to decide if it’s possible to choose at least one element (a non-empty subset) such that the product of the chosen numbers becomes exactly 67. If it’s possible, print “YES”; otherwise, print “NO”.

Key Observation

The whole problem becomes very easy once you notice one thing: 67 is a prime number. A prime number has only two factors: 1 and itself. So the only way to make the product 67 is: Take the number 67 alone, or Take 67 with some 1’s (because multiplying by 1 doesn’t change the product)

That means: If the array contains 67, we can just pick that single element, and the product will be 67. If the array does not contain 67, then no combination of other numbers can multiply to 67 (because 67 can’t be formed by multiplying smaller numbers except using 1 and 67).

Final Approach

For each test case: Read n and the array Check if 67 exists in the array If yes → print “YES” Otherwise → print “NO”

Why This Works (Short Proof)

If 67 is present: choose {67} → product is 67 → valid If 67 is not present: since 67 is prime, you cannot create it by multiplying other numbers → impossible

Complexity

The check is very small and fast: we only scan the array once. So the time complexity is O(n) per test case (and here n is tiny anyway).

That’s it, no sieve, no heavy math, just a simple prime observation.

Author: ahmedmshakil