NUM239 - Editorial

likecs · June 25, 2018, 11:40pm

Problem Link

Practice

Contest

Author: Ivan Safonov

Tester: Hasan Jaddouh

Editorialist: Bhuvnesh Jain

Difficulty

CAKEWALK

Prerequisites

Prefix sums

Problem

You are given to integers L and R. Find the number of integers which have the last digit as 2, 3 or 9 and lie in the range [L, R].

Explanation

As the constrainsts are small on L and R, we can pre-calculate all good numbers. Then each test case just asks to find out how many good numbers lie within the given range. This can be easily answered using prefix-sums. If you don’t know about prefix-sums, you can read it here. Basically the idea is the following:

\sum_{i=l}^{i=r} A_i = \sum_{i=1}^{i=r} A_i - \sum_{i=1}^{i=l-1} A_i

\sum_{i=l}^{i=r} A_i = \text{(Prefix-sum at i=r)} - \text{(Prefix-sum at i=l-1)}

Below is a pseudo-code for it:


	def init():
		for i in [1, 1000000]:
			last_digit = i % 10
			if last_digit == 2 or last_digit == 3 or last_digit == 9:
				good[i] = 1
			else:
				good[i] = 0

		# Build prefix sum
		for i in [1, 1000000]:
			good[i] += good[i-1]

	def solve(l, r):
		ans = good[r] - good[l-1]
		return ans

The time complexity of the above approach will be O(N + T), where N = 100000 is for pre-computation and T is for answering every test case in O(1) using prefix-sums. The space complexity of the above approach will be O(N) for storing the prefix array of good elements.

Bonus Problem

Solve the problem without any pre-computation and in O(1) memory.

Idea:

Click to view

Note that every consecutive number from “x…0” to “x…9” has 3 good numbers.

Feel free to share your approach, if it was somewhat different.

Time Complexity

O(N + T)

Space Complexity

O(N)

Solution Links

Setter’s solution

Tester’s solution

Editorialist solution

shivam_g1470 · June 30, 2018, 11:29pm

Since constraints were easy there was no need to define an array to hold good/pretty numbers.

a simple brute force from l to r and checking the last digit would yield the same result.

See my submission: https://www.codechef.com/viewsolution/19019309

Time Complexity: O(N)

Space Complexity: O(1)

anishray042 · July 1, 2018, 12:18pm

My Solution:

Time Complexity : O(T)

Space Complexity : O(1)

It will be useful if no. of test case is quite large.

/* Written By : Anish Ray */

#include <bits/stdc++.h>

#define ll long long
#define v(k) vector
#define mod 1000000007
#define m(a,b) map <a,b>
#define ull unsigned long long
#define fi first
#define se second

using namespace std;

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

int t;
cin>>t;

while(t--)
{
	int l,r;
	cin>>l>>r;
	
	int c=0;
	int f=0;
	
	for(int i=0;i<10;i++)
	{
		if(l==r)
		{
			if(l%10==3||l%10==9||l%10==2)
				c+=1;
				
			f=1;
			break;
		}
	
		if(l%10==2)
		{
			break;
		}
		else if(l%10==3||l%10==9)
			c++;
		
		l++;
	}
	
	if(f!=1)
	{
		for(int i=0;i<10;i++)
		{
			if(r==l)
			{
				if(l%10==3||l%10==9||l%10==2)
					c+=1;
				
				f=1;
				break;
			}
	
			if(r%10==1)
			{
				break;
			}
			else if(r%10==9||r%10==3||r%10==2)
				c++;
		
			r--;
		}
	}
	
	if(f!=1)
	{
		c+=((r-l+1)/10)*3;
	}
	
	cout<<c<<endl;
}

return 0;

}

hunterr_196 · July 1, 2018, 5:18pm

Its a simple Brute Force application. Amazed to see such a simple problem in LTIME61B.
My code goes here…(in cpp).## Heading ##


#include <iostream>
using namespace std;

int main()
{
     int t,cnt,digit,l,r;
     cin>>t;
     while(t--)
    {
        cnt = 0;
        cin>>l>>r;
        for(int i=l;i<=r;i++)
        {
            digit = i % 10;
            if(digit == 2 || digit == 3 || digit == 9)
                cnt++;
        }
        cout<<cnt<<endl;
    }
    return 0;
}

l_returns · July 1, 2018, 12:20am

Wtf… I wasted a lot of time on this question due to some connection issue and due to some problem with codechef IDE…
Didn’t knew that 1st question is that low in div2 (as I was in div2 before contest and I was in div1 before previous contest)…
This is completely brute Force…

l_returns · July 1, 2018, 12:22am

I did O(1) space approach

aryanc403 · July 1, 2018, 1:02am

@l_returns Pro tip #1 (#nooffence) Never use codechef ide in short contest for testing soln. It will ~1 min to give verdict. And sometimes it also shows “Submission Limit Reached” . Alternative offline ide(Best Option), CodeForces Ide (A bit slower but can be used) both are relatively faster. I personally use these options for testing purpose.

sudhatks · September 16, 2019, 3:41pm

Time Complexity: O(T)
Space Complexity: O(1)
Java solution: https://www.codechef.com/viewsolution/26602770
Just check,

how many of (2,3,9) ending numbers are present between L and next round figure (multiple of 10)
how many of (2,3,9) ending numbers are present between R and previous round figure(multiple of 10)
find the difference between these two round figures and divide by 10 and multiply by 3 (because there are 3 possibilites for each 0-10, 10-20, 20-30 etc…)
sum of all the counts from above 3 steps gives the answer.

Eg: L=11 and R=33
1) count = 3, nextL = 20
2) count = 2, previousR = 30
3) count = (previousR-nextL)*3 = ((30-20)/10)*3 = 3
4) total count = 3+2+3 = 8

No need of any brute-force approach.

guruch2206 · December 5, 2019, 8:19am

Hi I am beginner. Why am I getting partially solved mark for this question? If my code is not right for all test cases where can I get those test cases to test on different IDE?
A little help please
Thanks in advance!

lightandl · April 29, 2020, 3:39pm

I did it in O(1) time complexity and O(1) space complexity
No Loops Bro…,I liked it

void solve(){
    int l,r;cin>>l>>r;l--;
    int a1=(r/10)*3;
    int a2=(l/10)*3;
    r=r%10;l=l%10;
    if(r>1)a1++;if(r>2)a1++;if(r==9)a1++;
    if(l>1)a2++;if(l>2)a2++;if(l==9)a2++;
    cout<<a1-a2<<endl;
 }

cybertron00 · June 4, 2020, 9:34am

yes, i too do it with the same approach

divyansh_833 · June 25, 2020, 5:24pm

Idk what is wrong with my solution.Can somebody help??

#include <bits/stdc++.h>
using namespace std;
int main()
{
int cases,i,n,a,b;
cin>>cases;
int temp1,temp,count;
while(cases–)
{
cin>>a>>b;
int temp=a%10;
if(temp<=2)
count=3;
else if(temp==3)
count=2;
else
if(temp<=9)
count=1;

	a=a+10-temp ;
while(a+10<b)
{
	a=a+10;
	count+=3;
}
while(b%10!=0)
{
	if(b%10==2 || b%10==3 || b%10==9)
		count++;
	b--;
}



	cout<<count<<endl;
}

}

d_may_tas · August 18, 2020, 2:28pm

@likecs @shivam_g1470 @anishray042 @hunterr_196 @l_returns @aryanc403

what is wrong with my code
https://www.codechef.com/viewsolution/36882644
my approach is for example l=12 and r =33
then l=l-1 mean l=11( because range is inclusive )
now lx =l%10 and rx =r%10
lx =1 and rx=3

now for get no of magical no l=( l/10*2 )and r =( r/10)*3
if lx>1 then add 1 if lx>2 and 1 and i lx>8 add 1
same for y
we get r=11 and l=3
finaly answer = r-l
11-3 =8 which is right
it is showing wa

yash19_pro · February 16, 2021, 5:14pm

Time Complexity : O(T)

Space Complexity : O(1)

Solution: 42856459 | CodeChef

rgada28 · June 13, 2021, 7:34am

I don’t know why this code is not getting accepted but it works fine in my PC

#include
using namespace std;

int main()
{

int t, rem, count = 0;
cin >> t;
while (t--)
{
    int l, r;
    cin >> l >> r;
    for (int i = l; i <= r; i++)
    {
        rem = i % 10;
        if (rem == 2 || rem == 3 || rem == 9)
        {
            count++;
        }
    }
    cout << count << "\n";
}
return 0;

}

ap_9000 · June 15, 2021, 7:11pm

#include<bits/stdc++.h>
#define lli long long int
using namespace std;

int main()
{

lli t;
cin>>t;
while(t–)
{
int l,r;
cin>>l>>r;

int k1=0;//for 2
int k2=0;//for 3
int k3=0;//for 9
int Ans = 0;

int x1 = l;
int x2 = l;
int x3 = l;
int temp = l%10;


if(temp >= 3)
    k1  = 12 - temp;
else
    k1 = 2 - temp;

if(x1+k1<=r)
{
    x1+=k1;
    Ans+=(r-x1)/10 + 1;
}


if(temp >= 4)
    k2 = 13 - temp;
else
    k2 = 3 - temp;

if(x2+k2<=r)
{
    x2+=k2;
    Ans+=(r-x2)/10 + 1;

}

k3 = 9 - temp;

if(x3+k3<=r)
{
    x3+=k3;
    Ans+=(r-x3)/10 + 1;

}

cout<<Ans<<"\n";
}

return 0;
}

sumit_9398 · June 29, 2021, 7:43am

I did it like this.

#include <stdio.h>
#include<stdlib.h>

long count_pretty(long, long);

int main(void) {
	long T;
	scanf("%ld", &T);
	for (long i = 1; i <= T; i++) {
	    // your code goes here
	    long L, R, count = 0L;
	    scanf("%ld %ld", &L, &R);
	    
	    long left = L - (L%10), right = R + (10 - (R%10));
	    count += 3 * ((right-left)/10);
	    
	    count -= (count_pretty(left, L) + count_pretty(R+1, right));
	    printf("%ld\n", count);
	}
	return 0;
}

long count_pretty(long left, long right){
long count = 0;
for (long i = left; i < right; i++) {
    if((i%10 == 2) || (i%10 == 3) || (i%10 == 9)) count++;
}
return count;
}

tannaom29 · July 26, 2021, 9:39am

PYTHON CODE

final = []
for _ in range(int(input())):
s,e = map(int,input().split())
count=0
for i in range(s,e+1):
if(i%10==2 or i%10==3 or i%10==9):
count+=1
final.append(count)
for times in final:
print(times)

‘’’ GOOD DAY ! ‘’’

joffan · July 27, 2021, 9:02pm

Well, if you have the spare time to do it that way… but better to just calculate how many whole tens (which each have three pretty numbers) and tidy up the edges:

fav = (2,3,9)
T = int(input())
for tx in range(T):
    L, R = map(int, input().split())
    Lten, Lunit = divmod(L,10)
    Rten, Runit = divmod(R,10)
    if Lten == Rten:
        ct = sum(i in fav for i in range(Lunit, Runit+1))
    else:
        ct = (3*(Rten-Lten-1) 
                + sum(i in fav for i in range(Lunit, 10)) 
                + sum(i in fav for i in range(0, Runit+1)))
    print(ct)

somildh · September 10, 2021, 3:23pm

#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{
int l,r;
cin>>l>>r;
int l0=l/10;
int r0=r/10;
int final=0;
final=(r0-l0)*3;
int lr=l%10;
int rr=r%10;
int count=0;
if(lr>1)
count–;
if(lr>2)
count–;
if(lr==9)
count–;
if(rr>1)
count++;
if(rr>2)
count++;
if(rr==9)
count++;
cout<<final+count<<endl;
}
}
not working please help