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 usingsplit()
with theinput()
. 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