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 |
| 0) | |
| | | 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. |
|
|
| 1) | |
| | | 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. |
|
|
| 2) | |
| | | 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. |
|
|
| 3) | |
| | | 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. |
|
|
| 4) | |
| | | Returns:
{429904664, 541008121, 540917467, 540117067, 533117017, 473117011, 429904664, 429904664, 429904664, 429904664 } | | Watch out for the time limit. |
|
|