Check if a number whose digits follow a sum rule is divisible by 3

Updated

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.

Comment
Mithlesh Upadhyay Published 19 Nov 2026 · 3 min read

Mithlesh Upadhyay is a Computer Science and AI expert from Madhya Pradesh with strong academic background (BE in CSE and M.Tech in AI) and over six years of experience in technical content development. He has contributed tech articles, led teams, and worked in Full Stack Development and Data Science. He founded the w3colleges.org portal for learning resources.

Related tutorials