Half Sequence Solution Codechef september cook off 2021

Half Sequence Solution Codechef september cook off 2021

Chef has an array AA of size NN. Chef wants to choose any subsequence of size exactly N2⌈N2⌉ from the array such that GCD of all the elements in that sequence must be 22. 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 dd such that all the numbers in sequence are divisible by dd. For more information, refer to here.
  • x⌈x⌉ is the ceiling (round up) operation: 3.5=4,2=2⌈3.5⌉=4,⌈2⌉=2.

Input Format

  • The first line contains an integer TT denoting the number of test cases. The TT test cases then follow.
  • The first line of each test case contains a single integer NN denoting the size of the array.
  • The second line of each test case contains NN space-separated integers A1,A2....ANA1,A2….AN denoting the given array.

Output Format

For each test case, output on one line YES if Chef can find a half-sequence, else print NO. Output is case insensitive.


  • 1T201≤T≤20
  • 2N1052≤N≤105
  • 1Ai1091≤Ai≤109
  • Sum of NN over all test cases does not exceed 105105

Sample Input 1 

1 2 3 4 5
1 2 3 4
30 42 70

Sample Output 1 



  • For the first test case, Chef wants to select 52=3⌈52⌉=3 numbers. But for any 33 numbers, GCD would not be 22. Therefore the answer is NO.

  • For the second test case, Chef wants to select 42=2⌈42⌉=2 numbers. Chef can select the subsequence [2,4][2,4] with GCD of 22. Therefore the answer is YES.

  • For the third test case, Chef wants to select 32=2⌈32⌉=2 numbers. But for any 22 numbers, GCD would be bigger than 22. Therefore the answer is NO.

Solution: Click here

Leave a Comment