Half Sequence solution codechef

Half Sequence solution codechef

hef 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.

Half Sequence solution codechef

  • 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.

Half Sequence solution codechef

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

Constraints

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

Half Sequence solution codechef

 

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

Sample Output 1 

NO
YES
NO

Explanation

  • 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.

  • For Solution

    Click Here!

Leave a Comment

Your email address will not be published.