Numbers From Working Keys

Hard

Not every button works on an old keypad lock: only the digits in the list keys do (each one is a single-character string, and the list is sorted in increasing order). Every working button can be pressed any number of times. How many positive integers no greater than limit can be typed on this lock? For example, with keys = ["1", "4"] you can type 1, 4, 11, 14, 41, 44, 111 and so on.

Example 1

keys=["2", "8"], limit=30 → 4

2, 8, 22 and 28 fit. 82 and 88 are already above 30.

Example 2

keys=["3", "6", "9"], limit=500 → 21

3 one-digit numbers, 9 two-digit ones and 9 three-digit ones starting with 3: 21 in total.

Example 3

keys=["5"], limit=4 → 0

The smallest number you can type is 5, which is already above 4.

Constraints

1 ≤ len(keys) ≤ 9
Each element of keys is a single digit from 1 to 9
The digits in keys are distinct and in increasing order
1 ≤ limit ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Math String Binary Search Dynamic Programming

Similar problems

Grading the Arithmetic Quiz Hard Phrase From Word Beginnings, Long Edition Hard Words Hidden in a Text Medium Target From Word Beginnings Medium Every Way to Space the Words Hard

Input

keys=["2", "8"], limit=30

Expected

Run checks the first 3 tests in your browser. Submit checks all 116 tests on the server, hidden ones included.