Digit Product Divisible by Digit Sum

Hard

Call a positive integer **balanced** if the product of its digits is divisible by the sum of its digits. For example, 36 is balanced: 3 · 6 = 18 is divisible by 3 + 6 = 9. A number with a zero digit is balanced too, since its digit product is 0. Given low and high, count the balanced numbers from low to high inclusive.

Example 1

low=20, high=40 → 5

20, 30 and 40 qualify (they contain a zero, so the digit product is 0), and so do 22 (4 is divisible by 4) and 36 (18 is divisible by 9). That makes 5.

Example 2

low=111, high=119 → 0

For 11d the digit sum is d + 2 and the product is d, which is always smaller than the sum and not divisible by it. None qualify.

Example 3

low=7, high=7 → 1

For a one-digit number the digit product and the digit sum are the same.

Constraints

1 ≤ low ≤ high < 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Dynamic Programming

Similar problems

Pattern With Dot and Star Hard Longest Balanced Bracket Stretch Hard Water Between Walls Hard Does the Text Fit the Pattern Hard Biggest Solid Panel Block Hard

Input

low=20, high=40

Expected

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