I think the wording for this problem is very unclear. This was one of the more confusing "warmups" to solve, yet the solution was very straightforward.

I struggled with this problem until I discovered these properties of GCD:

• The gcd is an associative function: gcd(a, gcd(b, c)) = gcd(gcd(a, b), c).
• The gcd of three numbers can be computed as gcd(a, b, c) = gcd(gcd(a, b), c), or in some different way by applying commutativity and associativity. This can be extended to any number of numbers. (http://en.wikipedia.org/wiki/Greatest_common_divisor#Properties)

So, the gcd over this array [2,6,9,25] can be written as gcd(gcd(gcd(2,6),9),25) which is exactly equal to gcd(gcd(gcd(9,25),6),2) which is exactly equal to gcd(gcd(9,gcd(25,6)),2) which is exactly equal to gcd(gcd(9,2),gcd(25,6)) etc.

This means two things:
1. Each permutation of the array does not need to be checked because they all yield the same result. This should help reach an O(n) time complexity.
2. If any individual gcd calculation in the chain reaches 1, the entire evaluation will be 1. That means there must exist two numbers in the array which satisfy the conditions of B. Luckily, we don't need to print the contents of B itself.

Hope this helps!

I think the answer for testcase#16, case 3 is wrong. 27 15015 10010 6006 4290 2730 2310 20020 40040 80080 12012 24024 48048 96096 8580 17160 34320 68640 5460 10920 21840 43680 87360 4620 9240 18480 36960 73920 Since all the numbers except 15015 are even, they will have gcd>=2. Only possibility is 15015 paired with some other no. can be coprimes. But all numbers with 15015 have gcd>1, hence the answer should be "NO", but the answer given is YES. Am I wrong?

My solution runs fine for all test cases, except 16,17,18,19. I tried to run for 16th. The only test case where my solution differs from given output, is thsi test case:

27
15015 10010 6006 4290 2730 2310 20020 40040 80080 12012 24024 48048 96096 8580 17160 34320 68640 5460 10920 21840 43680 87360 4620 9240 18480 36960 73920

Can anyone point out the applicable subset i this?

Yeah, I agree with others who are saying that wording is confusing. However, it might seem trivial if the wording were straightforward.

Hint:

If for all subset, B, where there is an integer x where x divides all the numbers in the subset B and x is greater than 1, return NO.

Otherwise, return YES.