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 · March 28, 2019, 1:04am

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 · March 28, 2019, 1:04am

I did O(1) space approach

aryanc403 · March 28, 2019, 1:04am

@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:45pm

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:29pm

@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:44am

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 ! ‘’’