Count Digit Strings Divisible by K

Problem

Count the digit strings of length n, allowing leading zeros, whose numeric value is divisible by k.

Track the number of strings for every remainder modulo k and extend each state by appending each of the ten digits. Assume n >= 1 and k >= 1.

Hint

Appending a digit transforms remainder r into (r * 10 + d) modulo k.

case 1

in: [1,2]

expected: 5

case 2

in: [1,10]

expected: 1

case 3

in: [2,7]

expected: 15

case 4

in: [3,3]

expected: 334

case 5

in: [4,5]

expected: 2000

Starter codePython

def count_divisible_digit_strings(n, k):
    # Your code here
    pass

5 test cases · run your code against them in the editor