Yes that’s correct.
1 Like
I just ran an AC solution submitted by someone , which gives NO as output for this test case, and is accepted…
1 Like
Which one can you provide the link please?
1 Like
That solution is incorrect then. Sometimes wrong solutions get accepted due to weak test cases.
1 Like
There are many solutions giving NO as answer for the following test:
1
4
4 8 18 20
'Cause they are sorting the sequence and just checking the first (n+1)/2 even elements.
2 Likes
hmmmm, if that’s the case i get your frustration , we always make sure to make things right , apology for weak cases , though hope you can learn something out of the problem 
6 Likes
Actually I leaned a lot , one of the things look for simple solution , I oversolved the problem ( I used randomisation to check for random 50 numbers ) luckily got AC within Time.
2 Likes
Glad for that!
2 Likes
Observe that any single number <=10^9 can be made up of at most 9 distinct prime numbers. Can anyone please give the proof of that? Why is it so?
Observe that the product of the first 9 odd primes is 3,23,48,46,615 already greater than 1e9.
3 Likes
thnx for clarification
can anyone explain a little more why 9?
1 Like
First 9 odd primes?
Shouldn’t they be 3,5,7,11, … so on?
1 Like
let’s see this example: N=4, A=[ 210,462,330,770]. Here K=2. GCD of all 4 numbers is 2, but for any 2 number GCD is not 2. similarly, when k \le9 we cannot simply guess the answer by finding GCD of the whole array and we need brute force.
If N=20, K would be 10. suppose if the gcd of 20 elements is 2, we can choose at least one subsequence of size 10 with gcd 2. Because every number( \le10^9) can be made up atmost 9 distinct primes.
1 Like
There is no need to see the number of digits a number has. A simple solution is that I had done is that we know that you cannot take odd numbers for getting gcd = 2 thus you can straightaway reject them. Next store all the even numbers. Since subsequence has to be of length of ceil of N/2 thus we can check if length of even numbers array is less than ceil of N/2.If it is true then we cannot make a subsequence of length ceil(N/2). If the size of even numbers array is greater than or equal to ceil(N/2) then sort the array. If the first number is 2 then no further checking 2 is itself the smallest even number (natural).You can always make a subsequence of the above requirement if 2 is present. If 2 is not present then thinking part comes in. Take the gcd of first ceil(N/2)-1 numbers from this array. If its gcd is 2 then answer is yes else now you can take the gcd and start for rest of element taking one at a time if the gcd of first ceil(N/2)-1 numbers and the present number is 2. If at any point its possible then answer is yes else the answer is a BIG NO
5 Likes
I don’t know what happens but my wrong solution passed all test cases, What I did was first I taken all the even elements and then created 2 arrays, I included an element in first array if overall gcd of first array will be less after including this, otherwise it was in second array then I just checked if I get gcd of first array as 1 then answer is YES otherwise NO, but there are many tcs where my solution will fail, for example:
8 4 6
16 8 4 6
mu submission link: Bawal ho gaya ye to
2 Likes