Description
You are given two positive integers, l and r. A positive integer is called beautiful if the product of its digits is divisible by the sum of its digits.
Return the count of beautiful numbers between l and r, inclusive.
Example 1:
Input: l = 10, r = 20
Output: 2
Explanation:
The beautiful numbers in the range are 10 and 20.
Example 2:
Input: l = 1, r = 15
Output: 10
Explanation:
The beautiful numbers in the range are 1, 2, 3, 4, 5, 6, 7, 8, 9, and 10.
Constraints:
1 <= l <= r < 109
Solution
Python3
class Solution:
def beautifulNumbers(self, l: int, r: int) -> int:
def f(num):
digits = list(map(int, str(num)))
N = len(digits)
@cache
def dp(index, tight, leading, product, sum):
if index == N:
return not leading and int(product % sum == 0)
limit = digits[index] if tight else 9
res = 0
for digit in range(limit + 1):
nxtTight = tight and digits[index] == digit
if leading:
if digit == 0:
res += dp(index + 1, nxtTight, True, 0, 0)
else:
res += dp(index + 1, nxtTight, False, digit, digit)
else:
res += dp(index + 1, nxtTight, False, product * digit, sum + digit)
return res
return dp(0, True, True, 0, 0)
return f(r) - f(l - 1)