In this post, we will be solving the Factor of 3 which was one of the question in TCS Codevita Season 9. The program is accompanied by the explanation of code and algorithm. This problem is solved using Python.

**Problem Description**

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.

**Constraints**

1 <= T <= 10

2 <= N <= 10^5

1 <= 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

1

4

1 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

1

4

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

**Also Read: **Railway Station CodeVita Solution in Python

## Algorithm for Factor of 3

The algorithm to solve Factor of 3 problem is given below.

Step 1: Start. Step 2: Take number of test cases as input in T. Step 3: Repeat from step 4 to step 10 T times. Step 4: Take size of array as input in N. Step 5: Take N space separated integers as input in arr. Step 6: Declare a list remainder for storing the remainder of integers in N when divided by 3. Step 7: Repeat from step 8 for N times. Step 8: Calculate the remainder of the integer when divided by 3 and append it in remainder list. Step 9: Count the number of remainder and assign it to variable c0, c1 and c2 for remainders 0, 1 and 2 respectively. Step 10: If (c0 == 0 and c1 != 0 and c2 != 0) or (c0 > (c1 + c2 + 1)) then the array cannot be rearranged and print "No" else it can be rearranged and print "yes" Step 11: End.

In short,

Start, T = input() # test case Repeat T times: N = input() # size of array arr = input() # array of N elements remainder = [] Repeat N times: remainder.append(arr[i] % 3) c0 = remainder.count(0) c1 = remainder.count(1) c2 = remainder.count(2) If (c0 == 0 and c1 != 0 and c2 != 0) or (c0 > (c1 + c2 + 1)): print("No") else: print("Yes")

## Program for Factor of 3 Codevita in Python

# Take test case as input in T T = int(input()) for i in range(T): # Take size of array as input in N N = int(input()) # Take N space separated integers in arr arr = list(map(int, input().split())) remainder = [] # calculate remainder of elements of arr for i in range(N): remainder.append(arr[i] % 3) c0 = remainder.count(0) c1 = remainder.count(1) c2 = remainder.count(2) # Check whether the condition is true or false if (c0 == 0 and c1 != 0 and c2 != 0) or (c0 > (c1 + c2 + 1)): print("No") else: print("Yes")

**Output**

1 4 1 2 3 3 Yes

1 4 3 6 1 9 No

**Explanation**

- At first, test case is taken as input in variable
`T`

. The input should be a integer.

T = int(input())

- Since we need to execute for T test cases we will be using loop. Here
`for`

loop is used for T test cases.

foriinrange(T): . . .

- Then, size of array is taken as input in variable
`N`

.

N = int(input())

- We will take integers as input in variable
`arr`

. We are taking input in same line and splitting it when “space” is encountered. For splitting the input we are using`split()`

with the`input()`

. The input should be a integer.

arr = list(map(int, input().split()))

- After that, we loop for N integers. This loop is used to find remainder of every integers stored in elements variable and append it in
`remainder`

variable.

foriinrange(N): remainder.append(arr[i] % 3)

Then, the count of remainder 0, 1 and 2 are counted and assigned to c0, c1 and c2 respectively. This can be done using `count()`

method. Since, we are dividing by 3 at most there will be 3 remainders i.e. 0, 1 and 2.

This can also be done using other method. You can use any method, at last result will be same.

for ele in arr: if ele %3==0: c0+=1 elif ele%3==1: c1+=1 else: c2+=1

- Finally, we check if the given array can be rearranged or not. We can check it just by checking the count of remainders of each type.

if (c0 == 0 and c1 != 0 and c2 != 0) or (c0 > (c1 + c2 + 1)): print("No") else: print("Yes")

**More Examples**

Explore more TCS CodeVita Solution in Python and C Programming