Factor of 3 Codevita 9 Solution in Python

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.

for i in range(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.

for i in range(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