Count Beautiful Numbers

Start by defining a dynamic programming state based on the current digit index, the accumulated sum, and product of digits. Transition carefully while considering divisibility by the sum. Use memoization to handle overlapping subproblems and iterate through all digits efficiently for the range l to r.

Problem Statement

Given two positive integers l and r, a number is considered beautiful if the product of its digits is divisible by the sum of its digits. You need to find how many beautiful numbers exist in the inclusive range [l, r].

For example, given l = 10 and r = 20, the beautiful numbers are 10 and 20. Implement an algorithm that counts such numbers efficiently even for large ranges.

Examples

Example 1

Input: l = 10, r = 20

Output: 2

The beautiful numbers in the range are 10 and 20.

Example 2

Input: l = 1, r = 15

Output: 10

The beautiful numbers in the range are 1, 2, 3, 4, 5, 6, 7, 8, 9, and 10.

Constraints

• 1 <= l <= r < 109

Solution Approach

Define DP State

Use digit dynamic programming with a state representing the current index, the cumulative sum of digits, the cumulative product of digits, and a tight flag for bounds. This allows precise counting of valid numbers within l and r.

Transition Between States

For each digit, calculate new sum and product, check divisibility conditions at the end, and propagate counts using memoization. Handle the edge case when sum is zero to avoid division errors.

Compute Result Over Range

Apply the DP function from 0 to r and subtract the DP count from 0 to l-1 to get the exact count of beautiful numbers in [l, r]. Ensure all states are cached to avoid recomputation.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the number of digits, possible sums, and products tracked in DP. Space complexity is proportional to the DP state dimensions, which include index, sum, product, and tight flag.

What Interviewers Usually Probe

• Mentions need for counting numbers with a digit-based property.
• Hints at using a DP approach over digits for efficiency.
• Asks about handling large ranges without iterating every number.

Common Pitfalls or Variants

Common pitfalls

• Forgetting to handle the sum being zero when checking divisibility.
• Not caching DP states leading to TLE in large ranges.
• Mismanaging tight bounds causing incorrect counts at edges.

Follow-up variants

• Count numbers divisible by the sum of their digits without considering product.
• Find numbers where sum and product have a specific greatest common divisor.
• Count beautiful numbers only for even-length numbers within the range.

FAQ

What is a beautiful number in the Count Beautiful Numbers problem?

A beautiful number is a positive integer whose product of digits is divisible by the sum of its digits.

Which dynamic programming pattern fits this problem?

State transition dynamic programming, specifically digit DP, is used to track sums and products across digit positions.

How do I handle large ranges like 1 to 10^9?

Use memoized digit DP to avoid iterating each number individually, focusing only on digit positions, sum, and product.

What edge cases should I watch for?

Watch for sums equal to zero to prevent division errors and ensure tight bounds at l and r are respected.

Can this method be adapted for variants of beautiful numbers?

Yes, the digit DP approach can be modified for constraints like even-length numbers or alternative divisibility rules.