Scannable codes
HardOnline Assessment
Count the scannable locker codes in a range.
A warehouse labels lockers with positive whole numbers written in ordinary decimal, with no leading zeros. A locker code is scannable when both of these hold:
- the sum of its decimal digits is a multiple of
m, and - no two neighbouring digits are equal (so
1223is not scannable, but1232can be).
Input: lo, hi and m, all integers with lo <= hi. Every locker code from lo to hi inclusive is a candidate.
Output: an integer, how many codes c with lo <= c <= hi are scannable.
The range can span hundreds of trillions of codes, so checking them one at a time will be too slow.
Example 1
- Input:
- [1,30,5]
- Output:
- 5
- Explanation
- Between 1 and 30 the codes whose digit sum is a multiple of 5 are 5, 14, 19, 23 and 28 (digit sums 5, 5, 10, 5 and 10). None repeats a neighbouring digit, so the answer is 5.
Example 2
- Input:
- [100,130,3]
- Output:
- 7
- Explanation
- Between 100 and 130 the codes with digit sum divisible by 3 and no equal neighbours are 102, 105, 108, 120, 123, 126 and 129. Codes such as 111, 114 and 117 have digit sums divisible by 3 but repeat the digit 1 next to itself, so they are rejected. The answer is 7.
Example 3
- Input:
- [10,99,9]
- Output:
- 9
- Explanation
- Two-digit codes with digit sum 9 are 18, 27, 36, 45, 54, 63, 72, 81 and 90. The code 99 has digit sum 18, a multiple of 9, but repeats a digit, so it is rejected. The answer is 9.
Constraints
1 <= lo <= hi <= 1,000,000,000,000,000(1015)1 <= m <= 100