Problem Statement |
| | A positive integer is called Increasing Number if its digits are in non-descending order from left to right in decimal notation. For example, 1234, 111, 58 and 8899 are Increasing Numbers, while 314, 7654 and 2009 are not.
You are given a long digits and an int divisor. Calculate the number of Increasing Numbers that satisfy both of the following conditions and return this number modulo 1,000,000,007.
- The number contains exactly digits digits in the decimal notation with no leading zeroes.
- The number is divisible by divisor.
|
| |
Definition |
| | | Class: | IncreasingNumber | | Method: | countNumbers | | Parameters: | long, int | | Returns: | int | | Method signature: | int countNumbers(long digits, int divisor) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | digits will be between 1 and 1,000,000,000,000,000,000 (10^18), inclusive. |
| - | divisor will be between 1 and 500, inclusive. |
| |
Examples |
| 0) | |
| | | Returns: 4 | | 12, 24, 36, and 48 satisfy the conditions. |
|
|
| 1) | |
| | | Returns: 9 | | All 3-digits numbers divisible by 111 are Increasing Numbers. |
|
|
| 2) | |
| | | Returns: 0 | | There is no Increasing Number divisible by 10. |
|
|
| 3) | |
| | |