[C/C++] BOJ #1019 - Book Page

Han Ji-min loves books and works at a library.  One spring night, while reading a book, she suddenly became curious about how many digits were written on the pages of the book she was flipping through.  The book’s pages are numbered from page 1 to page N. Let’s calculate how many digits are written on the pages of the book she read.

 

Han, Jimin

 

---

Although it’s a bit different from the original problem, I was reminded of Han Ji-min, who appeared in Drama "One Spring Night", and the similarity between her name and “Ji-min” in the problem inspired me to modify the problem’s content. The original problem can be found at the link below. The difficulty level is Gold I.

 

---

This problem doesn’t seem to have major issues being solved using brute force.  However, considering  is as large as 1 billion, it might be a bit too large for brute force.

If we can exclude numbers starting with 0, counting the digits becomes a bit simpler.  For example, considering numbers from 0 to 999, they would look like 000, 001, 002, …, 998, 999, and each digit from 0 to 9 appears equally.

I used this principle to solve the problem.

Even though a number cannot start with 0, it can still have zeros in the middle if there is a digit at the beginning.

For instance:
• In numbers from 100 to 199, the digit 0 appears 20 times, and the digit 9 also appears 20 times.
• However, the digit 1 appears 120 times because the hundreds place always contains 1.

Using this, I constructed a mathematical formula to avoid calculating every single case.

Here are some example inputs for reference:

597
109 220 220 220 220 218 120 120 119 117 

7238
2143 3254 3193 3153 3144 3144 3144 2383 2144 2143 

987654321
780521262 891632373 891632364 891632284 891631584 891625584 891575584 891175584 888175584 868175584

 

Feel free to use the outputs for the given inputs as a reference to verify if your solution produces the correct results.

 

book pages

 

Below is the source code I wrote.

//----------------------------------------------------------
//    baekjoon #1019 - Book Page
//        - by Aubrey Choi
//        - created at 2019-07-05
//----------------------------------------------------------
#include <stdio.h>

int main()
{
    int n, s = 1, ans[10] = {0, };
    scanf("%d", &n);
    while(n > 0)
    {
        int t = n / (s * 10);
        int r = n % (s * 10);
        for(int i = 0; i < 10; i++) ans[i] += t*s;
        for(int i = 1; i <= r / s; i++) ans[i] += s;
        ans[(r/s+1)%10] += r % s;
        n -= 9 * s;
        s *= 10;
    }
    for(int i = 0; i < 10; i++) printf("%d ", ans[i]);
    putchar('\n');
    return 0;
}