Half Sequence Solution Codechef september cook off 2021
Chef has an arrayof size . Chef wants to choose any subsequence of size exactly from the array such that GCD of all the elements in that sequence must be . Chef names such a kind of sequence as a half-sequence.
Help Chef to find whether he would be able to select any half-sequence in the given array.
As a reminder,
- A subsequence of an array is a sequence that can be derived from the given array by deleting zero or more elements without changing the order of the remaining elements.
- GCD stands for Greatest Common Divisor. The greatest common divisor of a subsequence is the largest integer here. such that all the numbers in sequence are divisible by . For more information, refer to
- is the ceiling (round up) operation: .
- The first line contains an integer denoting the number of test cases. The test cases then follow.
- The first line of each test case contains a single integer denoting the size of the array.
- The second line of each test case contains space-separated integers denoting the given array.
For each test case, output on one line
YES if Chef can find a half-sequence, else print
NO. Output is case insensitive.
- Sum of over all test cases does not exceed
Sample Input 1
3 5 1 2 3 4 5 4 1 2 3 4 3 30 42 70
Sample Output 1
NO YES NO
For the first test case, Chef wants to selectnumbers. But for any numbers, GCD would not be . Therefore the answer is
For the second test case, Chef wants to selectnumbers. Chef can select the subsequence with GCD of . Therefore the answer is
For the third test case, Chef wants to selectnumbers. But for any numbers, GCD would be bigger than . Therefore the answer is