# Multiple of 3 CodeChef Solution – DSA LEARNING SERIES

Today we will be Solving Multiple of 3 CodeChef Problem which is a part of CodeChef DSA Learning Series.

Contents

Consider a very long K-digit number N with digits d0, d1, …, dK-1 (in decimal notation; d0 is the most significant and dK-1 the least significant digit). This number is so large that we can’t give it to you on the input explicitly; instead, you are only given its starting digits and a way to construct the remainder of the number.

Specifically, you are given d0 and d1; for each i ≥ 2, di is the sum of all preceding (more significant) digits, modulo 10 — more formally, the following formula must hold:

Determine if N is a multiple of 3.

## Input

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.

The first and only line of each test case contains three space-separated integers K, d0 and d1.

## Output

For each test case, print a single line containing the string “YES” (without quotes) if the number N is a multiple of 3 or “NO” (without quotes) otherwise.

• 1 ≤ T ≤ 1000
• 2 ≤ K ≤ 1012
• 1 ≤ d0 ≤ 9
• 0 ≤ d1 ≤ 9

## Example

Input

``````3
5 3 4
13 8 1
760399384224 5 1``````

Output

``````NO
YES
YES
``````

## Explanation

Example case 1: The whole number N is 34748, which is not divisible by 3, so the answer is NO.

Example case 2: The whole number N is 8198624862486, which is divisible by 3, so the answer is YES.

## Solutions – Multiple of 3 CodeChef Solution

``````import java.util.Scanner;

class MULTHREE {
public static void solve(long k,int d0,int d1){
StringBuffer sb=new StringBuffer(""+d0+d1);
long sum=d1+d0;

if(k>=3){
if(sum%5!=0){
sum=sum+(sum%10);
for(long i=(k-3)%4;i>0;i--){
sum=sum+(sum%10);
}
sum=sum+((k-3)/4)*20;
}else {
System.out.println("NO");
return;
}
}

if(sum%3==0){
System.out.println("YES");
}else {
System.out.println("NO");
}

}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int T=sc.nextInt();
while (T-->0){
int d0,d1;
long k;
k=sc.nextLong();
d0=sc.nextInt();
d1=sc.nextInt();
solve(k,d0,d1);
}
}
}
``````

### C++

``````#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int main() {

ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

int t ;

cin >> t;

while(t--){

ll k;int d0,d1;
cin >> k >> d0 >> d1;
int s = d0+d1;

int c = (2*s)%10 + (4*s)%10 +(6*s)%10 +(8*s)%10;
ll cycles = (k-3)/4;
ll ans = 0;
if(k==2){
ans = s;
}
else{
ans = s+(s%10) + (c *1LL *cycles);

int left = (k-3)-(cycles*4);
int p=2;
for(int i=1;i<=left;i++){
ans += (p*s)%10;
p=(p*2)%10;
}
}

if(ans%3==0) cout << "YES\n";

else      cout << "NO\n";
}
return 0;
}``````

Disclaimer: The above Problem (Multiple of 3) is generated by CodeChef but the Solution is provided by CodingBroz.

Broz Who Code

CodingBroz