Problem Statement |
| | It is a known fact that of all numbers, 4 is the one that brings the worst luck. It is for this reason that when generating number sequences, we need to avoid patterns related to the number 4 as much as possible.
You are given a long n. Count the number of positive integers that satisfy all of the following conditions:
- The number contains at most n digits.
- The number does not contain four consecutive '4' digits. For example, 43444124 is allowed, but 45444474 is not.
- The number of digits in the number is not a multiple of any of the integers greater than 10 that contain only '4' in their decimal representations (44, 444, 4444, 44444, ...).
Return the total count of these numbers modulo 1000000007. |
| |
Definition |
| | | Class: | AvoidFour | | Method: | count | | Parameters: | long | | Returns: | int | | Method signature: | int count(long n) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | n will be between 1 and 40000000000 (4e10), inclusive. |
| |
Examples |
| 0) | |
| | | Returns: 9998 | | Of all the 9999 positive integers containing 1, 2, 3 or 4 digits, 4444 is the only one that contains four consecutive '4' digits. |
|
|
| 1) | |
| | | Returns: 99980 | | The numbers to ignore are: 4444, 44440, 44441, 44442, ..., 44449, 14444, 24444, 34444, 54444, ... , 94444. |
|
|
| 2) | |
| | |
| 3) | |
| | | Returns: 576334228 | | 88 is a multiple of 44, so all numbers with 88 digits are ignored. |
|
|
| 4) | |
| | |