3490. Count Beautiful Numbers
SourceWeekly Contest 441 Q4DifficultyHardRating2502
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
Solutions
Solution 1
Thinking
A beautiful number has digit-product divisible by digit-sum. The range is large, so we count with digit DP.
The product’s primes are only \(2,3,5,7\); the sum is at most \(9\) times the length. A state stores position, tight flag, leading-zero flag, current sum, and product (or prime exponents).
Subtract the count on \([1,l-1]\) from \([1,r]\). Leading zeros keep product \(1\) and add nothing to the sum, so a \(0\) is not multiplied in too early.
1 | |
1 | |
1 | |
1 | |