Thanks for replying, I corrected the error, but it is still giving WA which is obvious. I’m looking for any test case for N<16 for which it is failing. It would be great if you can help.
Let’s say n = 6 and you have to find the subset of size 5.
Let’s say all the numbers in set B are made of p1, p2… p6 prime numbers only (if there are more than the chances of getting gcd 1 increases).
So an example where gcd of whole array is 1, and still you cannot choose such a set
{
p1.p2.p3.p4.p5,
p2.p3.p4.p5.p6,
p3.p4.p5.p6.p1,
p4.p5.p6.p1.p2,
p5.p6.p1.p2.p3,
p6.p1.p2.p3.p4,
}
here, the gcd of this set is 1, but set of 5 numbers with gcd 1.
Usually when the size of this set is greater than 8, this type of set cannot be made such that every element can be <= 10^9.
Actually this is an example, which i used to contradict the logic that i can make a set of size, N < 8 where gcd is 1, so there would exist a proper subset with gcd 1.
2 Likes
Let, n = 5
5 4 6 24 48
Check these case there is 4 even number and I have to take 3 numbers for my required subsequence.
If We take the last 2 number (24,48) as u said, and then take another from the rest it will give me a NO.but if we take the first 2 number first then It gives me a YES.
1 Like
Actually this is just a counter case… There surely can be many cases where you can make a subset with gcd 1 when n is smaller than 9, but it’s not always true for that case… But it is always true for n greater than 9 if the gcd of the whole set is 1
N=6 and A=[30, 42 , 70 , 30 ,42 ,70], K=3.
Here for any two numbers, GCD is not 2. Your solution will give NO. But we can select [30,42,70] with gcd 2.
1 Like
Yes, got it. Thanks you, and it was a great problem. 
1 Like
this approach is wrong
1
5
30 30 30 42 70
correct output should be
YES
2x3x5x7x11x13x17x19x23 = 2.2 x 10^8 …
These are the first 9 primes. Including any other prime or even replacing with any other prime number will result in increase in 10^9 …
PS: In question number<=10^9 … if it is even number , we need to check for (5x10^8) for gcd==1.
1 Like
thnx but it was also clarified by someone else
If overall gcd is one, then ans almost all the time comes from 2 numbers.
if gcd == 1 must come from three numbers, then every two numbers must have at least one factor common
if gcd == 1 must come from four numbers, then every three numbers must have at least one factor common
if gcd == 1 must come from 9 numbers, then every eight numbers must have one factor common
in this case each number is a product of 8 distinct prime numbers
but max number is 10^9
In my submission, I checked all continuous ceil(N/2) length subsequences, but I think that storing the numbers and looping through ceil(N/2) of them (without repeat) would be a more correct answer.
For example:
1
5
6 12 12 40 40
would give me NO but the correct answer should be [6,12,40] which gives YES.