PageNumbers | Topcoder Archive

Problem Statement

We have a book with N pages, numbered 1 to N. How many times does each digit occur in the page numbers?

You are given an int N. Return a int[] with 10 elements, where for all i between 0 and 9, inclusive, the element i will be the number of times digit i occurs when we write down all the numbers between 1 and N, inclusive.

Definition

Class:: PageNumbers
Method:: getCounts
Parameters:: int
Returns:: int[]
Method signature:: int[] getCounts(int N)
(be sure your method is public)

Notes

You may assume that for any valid input each of the output values fits into an int.

Constraints

N will be between 1 and 1,000,000,000, inclusive.

Examples

```
7
```
```
Returns: {0, 1, 1, 1, 1, 1, 1, 1, 0, 0 }
```
The page numbers in this case are simply 1, 2, 3, 4, 5, 6, and 7.
```
11
```
```
Returns: {1, 4, 1, 1, 1, 1, 1, 1, 1, 1 }
```
In comparison to the previous case, we added the pages 8, 9, 10, and 11. Now we have each digit exactly once, except for the digit 1 that occurs four times: once in 1 and 10, and twice in 11.
```
19
```
```
Returns: {1, 12, 2, 2, 2, 2, 2, 2, 2, 2 }
```
Digits 2 to 9 now occur twice each, and we have plenty of occurrences of the digit 1.
```
999
```
```
Returns: {189, 300, 300, 300, 300, 300, 300, 300, 300, 300 }
```
Due to symmetry, each of the digits 1 to 9 occurs equally many times in the sequence 1,2,...,999.

543212345

Returns: {429904664, 541008121, 540917467, 540117067, 533117017, 473117011, 429904664, 429904664, 429904664, 429904664 }

Watch out for the time limit.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.