 SIMPLE

# PROBLEM:

Determine the number of integers in the range L to R (endpoints inclusive) whose sum of digits is divisible by 3.

# EXPLANATION:

A well known theorem from elementary number theory goes as follows:

A number is divisible by 3 if and only if the sum of its digits is divisible by 3.

Thus, the number of integers in the range [L, R] whose sum of digits is divisible by 3 is equal to the number of integers in the range divisible by 3.

Another well known theorem from elementary number theory says:

The number of integers in the range [1, N] divisible by d is equal to \lfloor\frac N d \rfloor, where \lfloor x \rfloor is the largest integer less than x.

Therefore, the number of integers in the range [L, R] divisible by 3 = number of integers in the range [1,R] divisible by 3 - number of integers in the range [1,L-1] divisible by 3 = \lfloor\frac R 3\rfloor -\lfloor\frac {L-1} 3\rfloor.

O(1)

per test case.

# SOLUTIONS:

Editorialist’s solution can be found here.

Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

• 1
• 2
• 3
• 4
• 5

0 voters

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

int main() {
ll t;
cin>>t;
while(t--)
{
ll l,r;
cin>>l>>r;
if(l==1&&r==2)
{
cout<<0<<endl;
}
else if(l==r)
{
if(l%3==0)
cout<<1<<endl;
else
cout<<0<<endl;
}
else
{
ll i=l;
ll j=r;
while(i%3!=0&&i<r)
i++;
while(j%3!=0&&j>l)
j--;
if(i==j)
{
if(i%3==0)
cout<<1<<endl;
}
else
{
ll diff=j-i;
ll ans;
ans=(diff/3)+1;
cout<<ans<<endl;
}
}

}

return 0;
}



can someone suggest me a failing test case. my code is passing every test case except the last one.
Thank You.

Submission Link : Solution: 51549163 | CodeChef
plz tell any testcase where this is failing, It is passing only first task.
Thanks

Edit: @ssjgz @cubefreak777 @anshu23_1999 Plz help

1
13 14

for i in range(int(input())):
l,r=map(int,input().split())
if l>r or r<3:
print(0)
continue
if(l==r and l%3==0):
print(1)
continue
if(l==r and l%3!=0):
print(0)
continue
if((r-l)<3 and r%3==0):
print(1)
continue
if((r-l)<3 and l%3==0):
print(1)
continue
if((r-l)<3):
print(0)
continue
for j in range(l,r+1):
print("j is ",j)
if(j%3==0):
break
for k in range(r,l,-1):
print(‘k is’,k)
if(k%3==0 and k!=0):
break
print((int(k//3)-int(j//3))+1)

my code is failing last test case can anyone please suggest the issue

1
2 4

1 Like

Thanks 1 Like

1
2 4

1 Like
1
3 4


Thanks How are you guys getting to know what test case is failing? How can I see the test cases?

https://www.codechef.com/viewsolution/51573871

I understood the soln but what is wrong with my approach… Can someone tell me?

Help me …
Submission Link : Solution: 51593788 | CodeChef
Plz tell any testcase where this is failing, Only one task fails to pass .

1
3 1000000000000000000

    l = ceil((1.0 * l) / 3) * 3;
r = floor((1.0 * r) / 3) * 3;
ans = (r - l) / 3 + 1;


Why is this wrong?

Please post your full, formatted code 1 Like

That solution is AC.