SOD3 - Editorial

editorial
, ,
1

PROBLEM LINK:

Contest - Division 3
Contest - Division 2
Contest - Division 1

DIFFICULTY:

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.

TIME COMPLEXITY:

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

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

int main() {
	// your code goes here
	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.

3

Submission Link : CodeChef: Practical coding for everyone
plz tell any testcase where this is failing, It is passing only first task.
Thanks

Edit: @ssjgz @cubefreak777 @anshu23_1999 Plz help

4

1
13 14
correct answer - 0

5

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

6 
1
2 4
1 Like
7

Thanks :raised_hands:

1 Like
9

1
2 4
correct answer-1

1 Like
10 
1
3 4
11

Thanks :raised_hands:

12

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

13

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

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

14

Help me …
Submission Link : CodeChef: Practical coding for everyone
Plz tell any testcase where this is failing, Only one task fails to pass .

15

Please, people, read the thread and try the testcases that other people have posted!

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

Why is this wrong?

18

Please post your full, formatted code :slight_smile:

1 Like
19

here

20

That solution is AC.

21

Sorry my bad. here

1 Like