Balanced Multiples

Hard

Call a number balanced if its decimal notation has as many even digits as odd ones (zero counts as even). You are given bounds lo and hi and a number divisor. Count the numbers in the range [lo, hi] that are balanced and also divisible by divisor. The bounds reach 10⁹, so checking every number in the range is not an option.

Example 1

lo=30, hi=50, divisor=7 → 1

The multiples of 7 in range are 35, 42 and 49. Both digits of 35 are odd, both of 42 are even, while 49 has one even and one odd digit. The answer is 1.

Example 2

lo=100, hi=999, divisor=1 → 0

A three-digit number has an odd number of digits, so they cannot split evenly.

Example 3

lo=1000, hi=1100, divisor=5 → 11

Constraints

1 ≤ lo ≤ hi ≤ 10⁹
1 ≤ divisor ≤ 20

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Math Dynamic Programming

Similar problems

How Many Ones Are Written Hard Tasters and the Spoiled Cask Hard Two Groups With the Same Average Hard Prototype Drop Tests Hard Numbers From Working Keys Hard

Input

lo=30, hi=50, divisor=7

Expected

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