Given first two digits d1 and d2 and a relation to find the other digits till dk. Find if the number formed is divisible by 3. digit di is the sum of all preceding digits modulo 10. Note :
K<=10^18
Examples :
Input : k=6 d1=2 d2=4 Output : NO Explanation : the number formed is 246248 which is not divisible by 3 d3 = (2+4)%10 = 6 d4 = (2+4+6)%10 = 2 d5 = (2+4+6+2)%10 = 4 d6 = (2+4+6+2+4)%10 = 8 Input : k=3 d1=3 d2=3 Output : YES Explanation : the number formed is 336 which is divisible by 3
A normal approach will be to run a loop from 3 to k and find out all the digits and sum it up , and check if the sum is divisible by 3. If the sum is divisible by 3, then print a “YES” else print a “NO”. An efficient solution can be formed by making some key observations. When we add up numbers and do a mod of 10, a constant pattern is formed of the form 6248 or 2486 or 4862 or 8624 . So we can take any of the patterns and find out the rest of the numbers. In the illustration we have taken the pattern 6248 into account and solved the problem, we store the sum till we get the dc+1 to be 6 where c is the last digit before the pattern appears. And then all the patterns will be of the form 62486248…..6248… Since the pattern is of length 4. So the rest k-c digits will have (k-c)/4 “6248” patterns in it. Hence we add sum of “6248” i.e., 20*((k-c)/4) in the final sum. And if (k-c)%4==1, then we add 6 to the sum , if (k-c)%4==2 then add 8, (k-c)%4==3 then add 12. Hence we get the final sum, divide the final sum by 3 to check if the number is divisible by 3 or not according to the sum property of divisibility of 3.. Any of the above mentioned patterns can be taken into consideration while solving the problem. Below is the c++ illustration of the above approach.
Implementation :
#include <bits/stdc++.h>
using namespace std;
// function call to check if the number is divisible by 3
bool check(int d1,int d2,long long k)
{
long long sumf = d1+d2;
int next = 0;
int c = 2;
while(true)
{
// at first time
if(c==2)
next = (d1+d2)%10 ;
else // at second time
next = (next+next)%10 ;
// break conditions
// 1 when k digits are formed
// 2 when the pattern appears
if(c==k or next==6)
break;
// add up the sumf
sumf+=next;
// increase the digit counter
c+=1;
// if 000..000 pattern appears
if(next==0)
{
// if totalsum is divisible by 3
if((sumf)%3==0)
return true;
else
return false;
}
}
// pattern sum added
sumf += ((k-c)/4)*20;
// remaining of the pattern is added
if(((k-c)%4)==1)
sumf += 6;
else if(((k-c)%4)==2)
sumf += 8;
else if(((k-c)%4)==3)
sumf += 12;
if(sumf%3==0)
return true;
else
return false;
}
// driver code to check the above function
int main() {
long long k = 3;
int d1 = 3, d2 = 3;
// function call
if(check(d1,d2,k))
cout << "YES\n";
else
cout << "NO\n";
return 0;
}
Output :
YES
Time Complexity : O(1) It is almost constant as the pattern appears after a maximum of 6 calculations at worst.