Yes that’s correct.
I just ran an AC solution submitted by someone , which gives NO as output for this test case, and is accepted…
Which one can you provide the link please?
That solution is incorrect then. Sometimes wrong solutions get accepted due to weak test cases.
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.
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
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.
Glad for that!
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.
thnx for clarification
can anyone explain a little more why 9?
First 9 odd primes?
Shouldn’t they be 3,5,7,11, … so on?
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.
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
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