Count Good Numbers
Real-world version: Shelf Label CodesThe statement here is our own: the same inputs, outputs and technique.
A warehouse prints shelf labels. A label is a row of exactly n digit slots, numbered from 0 on the left. The printer accepts a label only when
- every slot whose number is even carries a digit that is a multiple of two, that is one of
0,2,4,6,8, and - every slot whose number is odd carries a prime digit, that is one of
2,3,5,7.
Leading zeros are ordinary digits here; a label is just a row of slots, not a number.
Given n, count the labels the printer accepts. The count grows far beyond what a 64-bit integer holds, so return it modulo 1000000007.
Examples
Example 1
- Input
- n = 7
- Output
- 40000
Slots 0, 2, 4 and 6 each accept five digits and slots 1, 3 and 5 each accept four, so the printer accepts 625 * 64 = 40000 labels, which is already below the modulus.
Example 2
- Input
- n = 26
- Output
- 426560007
There are 13 even-numbered slots and 13 odd-numbered ones, and the resulting count reduced modulo 1000000007 is 426560007.
Example 3
- Input
- n = 900000000000000
- Output
- 676101114
The label has 450000000000000 slots of each kind, and the count reduced modulo 1000000007 is 676101114.
Constraints
- 1 <= n <= 10^15
- The answer is returned modulo 1000000007, so it is always below that modulus.
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def count_good_numbers(n: int) -> int:public int countGoodNumbers(long n)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 11 test cases: 11 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's