HackerRank Sherlock and GCD challenge
There is a simple efficient solution for this problem which uses the following observation: if \$ A ⊆ B \$, then \$ \gcd(A) ≥ \gcd(B) \$. Proof: if \$ g = \gcd(B) \$ then \$ g \$ divides all elements of \$ B \$. But all elements from \$ A \$ are in \$ B \$, thus \$ g \$ divides all elements in \$ A \$. Hence, \$ \gcd(A) ≥ g \$.

This means that we can simply check that the GCD of all elements of the given array is \$ 1 \$.

What about duplicates? They don't matter because they do not affect the value of the greatest common divisor.

How to compute the GCD of an array? We can use the following property: $$ \gcd(a_0, a_1, a_2, \dotsc, a_{n - 1}) = \gcd(\gcd(a_0, a_1), a_2, \dotsc, a_{n - 1}). $$ To compute the GCD of two numbers one can use Euclid's algorithm.

The time complexity is \$ O(n + \log \max A) \$, where \$ \max A \$ is the maximum element of the array \$A\$.