×

# NUM239 - Editorial

Practice

Contest

Author: Ivan Safonov

Editorialist: Bhuvnesh Jain

CAKEWALK

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:

View Content

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

# Time Complexity

$O(N + T)$

# Space Complexity

$O(N)$

Setter's solution

Tester's solution

Editorialist solution

This question is marked "community wiki".

6★likecs
3.7k2481
accept rate: 9%

19.8k350498541

 2 Its a simple Brute Force application. Amazed to see such a simple problem in LTIME61B. My code goes here...(in cpp).## Heading ##  #include 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<
 0 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) answered 30 Jun '18, 23:29 72●7 accept rate: 13% 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... (01 Jul '18, 00:20) I did O(1) space approach (01 Jul '18, 00:22) @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. (01 Jul '18, 01:02)

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 /

# 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;


}

1
accept rate: 0%

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×1,688
×593
×218
×67
×43

question asked: 25 Jun '18, 23:40

question was seen: 643 times

last updated: 03 Jul '18, 08:41