You are not logged in. Please login at www.codechef.com to post your questions!

×

NUM239 - Editorial

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:

View Content

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

This question is marked "community wiki".

asked 25 Jun '18, 23:40

likecs's gravatar image

6★likecs
3.7k2481
accept rate: 9%

edited 30 Jun '18, 22:38

admin's gravatar image

0★admin ♦♦
19.8k350498541


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;
}
link
This answer is marked "community wiki".

answered 01 Jul '18, 17:18

hunterr_196's gravatar image

2★hunterr_196
614
accept rate: 0%

edited 03 Jul '18, 08:41

aryanc403's gravatar image

5★aryanc403
2.7k1618

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)

link

answered 30 Jun '18, 23:29

shivam_g1470's gravatar image

4★shivam_g1470
727
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) l_returns5★

I did O(1) space approach

(01 Jul '18, 00:22) l_returns5★

@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) aryanc4035★

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 <k>

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;

}

link

answered 01 Jul '18, 12:18

anishray042's gravatar image

3★anishray042
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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