CODEWITHSUNDEEP
c++math
Supesu
Supesu

Reputation: 676

Count amount of 3s in a series of numbers

(This isn't homework)

I'm working on a practice question (https://train.nzoi.org.nz/problems/1207) - "count the number of 3's when printing the numbers from 1 to N". I haven't found any solution online and I was wondering what a more efficient way to answer this question is.

my solution is:

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int l;
    cin >> l;

    int c=0;
    for (int i = 0; i < (l + 1); i++)
    {   
        int j = i;
        while (j>0)
        {
            int tmp = j%10;
            if (tmp == 3) c++;
            j /= 10;
        }
    }

    cout << c << endl;
    return 0;
}

although this takes a long time on long numbers.
what is a more efficient way to solve this problem?

EDIT:
For clarification, This is trying to find all instances of 3 while counting from 0 => N
E.G: 13 => 2 occurances of 3

Upvotes: 1

Views: 510

Answers (1)

anatolyg
anatolyg

Reputation: 28278

Looks like a good use-case for recursion. Call your function f(n) (short name because I'm going to use math notation below). Then calculate f(n) by something like f(a) + f(b) + ... when all of the numbers a, b, ... are much smaller than n.

I am only going to give ideas by examples, not code. I hope this will be complete enough to write code, and not too much, so the task remains interesting.

First of all:

f(0) = 0
f(1) = 0
f(2) = 0
f(3) = 1
f(4) = 1
...
f(9) = 1
f(10) = 1

Now calculate f(n) for n which are powers of 10:

f(10) = 1
f(100) = 20
f(1000) = 300
...
f(10^(n+1)) = 10 * f(10^n) + 10^n  (or something like that)

I hope I did it right. The idea is, for e.g. n = 1000, consider e.g. all 3-digit numbers with first digit 6. There are f(100) 3's in this list. The same for all other first digits, except for 3, where there are 100 more 3's.

Now consider an arbitrary n. Check its first digit; call it d. The list of all numbers smaller than n contains all possible numbers whose first digit is smaller than d, and some numbers whose first digit is exactly d. Now consider all these lists separately, and count 3's in them.

General advice: keep your "slow" code accessible at all times while you are writing your "fast" code. This way, it will be easy to test your code, and find unhandled cases, off-by-one bugs and such.

Upvotes: 2

Related Questions