PageNumbers

TCO09 Qual 2 · 2009-02-24 · by misof

TCO09 Qual 2 · 2009-02-24 · by misof · Brute Force, Recursion, Simple Math, Simple Search, Iteration

Show categories

Class Name: PageNumbers

Return Type: int[]

Method Name: getCounts

Arg Types: (int)

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.

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.

1
Returns: {0, 1, 0, 0, 0, 0, 0, 0, 0, 0 }

88)

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

Watch out for the time limit.

Submissions are judged against all 118 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class PageNumbers with a public method vector<int> getCounts(int N) · 118 test cases · 2 s / 256 MB per case