# Factor of 3 Codevita 9 Solutions

Page Contents

## Factor of 3 Codevita 9 Solutions

Given an array arr, of size N, find whether it is possible to rearrange the elements of array such that sum of no two adjacent elements is divisible by 3.

Also Read: TCS CodeVita Season 10

Constraints

`1 <= T <= 102 <= N <= 10^51 <= arr[i] <= 10^5`

Input

First line contains integer T denoting the number of testcases.
Each test cases consists of 2 lines as follows-
First line contains integer N denoting the size of the array.
Second line contains N space separated integers.

Output

For each test case print either “”Yes”” or “”No”” (without quotes) on new line.

Time Limit
1

Examples

Example 1

Input

`141 2 3 3`

Output

`Yes`

Explanation

Some of the rearrangements can be {2,1,3,3}, {3,3,1,2}, {2,3,3,1}, {1,3,3,2},…
We can see that there exist at least 1 combination {3,2,3,1} where sum of 2 adjacent number is not divisible by 3. Other combinations can be {1,3,2,3}, {2,3,1,3}.
Hence the output is Yes.

Example 2

Input

`143 6 1 9`

Output

`No`

Explanation

All possible combination of {3,6,1,9} are
{1,3,6,9}, {1,3,9,6}, {1,6,9,3}, {1,6,3,9}, {1,9,3,6}, {1,9,6,3},
{6,1,3,9}, {6,1, 9,3}, {6,3,1,9}, {6,3,9,1}, {6,9,1,3}, {6,9,3,1},
{3,1,6,9}, {3,1,9,6}, {3,9,1,6}, {3,9,6,1}, {3,6,1,9}, {3,6,9,1},
{9,1,3,6}, {9,1,6,3}, {9,3,1,6}, {9,3,6,1}, {9,6,1,3}, {9,6,3,1}.
Since none of these combinations satisfy the condition, the output is No.

## Solution

Program Python:

```for i in range (int(input("Enter Test Case"))):
N = int(input())

list1 = list(map(int,input().split()))
array = []
for i in range(N):
array.append(list1[i]%3)
x = array.count(0)
y = array.count(1)
z = array.count(2)
if x == 0 and y != 0 and z !=0:
print("NO")
elif x == 0 and y == 0 and z !=0:
print("YES")

elif x == 0 and y != 0 and z ==0:
print("YES")
elif x<=(z+y):
print("YES")
else:
print("No")```