Numbers With a Fixed Ending and Small Digits

Hard

You are given integers low, high, max_digit and a string ending: a positive number written without leading zeros. A positive integer x **qualifies** if its decimal form ends with ending (the whole of x may equal ending) and every digit of x is at most max_digit. Return how many qualifying integers lie in the range [low, high], both ends included.

Example 1

low=10, high=500, max_digit=3, ending="21" → 4

21, 121, 221 and 321 qualify: each ends in 21 and uses only digits up to 3. 421 is out because of its 4.

Example 2

low=1, high=99, max_digit=9, ending="7" → 10

These are 7, 17, 27, ..., 97: ten numbers.

Example 3

low=100, high=450, max_digit=5, ending="500" → 0

Any number ending in 500 is at least 500, but the range stops at 450.

Constraints

1 ≤ low ≤ high ≤ 10¹⁵
1 ≤ max_digit ≤ 9
1 ≤ len(ending) ≤ number of digits in high
ending uses only digits up to max_digit and does not start with zero

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Math String Dynamic Programming

Similar problems

Numbers From Working Keys Hard Flip the Circuit Output Hard Grading the Arithmetic Quiz Hard Sections of Two Seats Hard Numbers With a Digit Sum in Bounds Hard

Input

low=10, high=500, max_digit=3, ending="21"

Expected

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