Difficulty: 🔴 Hard
Topics: Dynamic Programming

Solution

Problem Understanding

This problem asks us to count the number of positive integers between l and r (inclusive) that are beautiful. A number is defined as beautiful if the product of its digits is divisible by the sum of its digits.

In simpler terms, for a number n, if sum_digits(n) divides product_digits(n) evenly, then n is beautiful.

The input consists of two integers, l and r, with constraints 1 <= l <= r < 10^9. This upper bound means r could be as large as a billion, so iterating over each number individually and computing sum and product of digits is too slow. The expected output is a single integer representing the count of beautiful numbers in the range.

Important edge cases include numbers with a 0 digit because the product becomes 0 and is divisible by any non-zero sum. Single-digit numbers are also trivially beautiful, as the product equals the sum.

Approaches

A brute-force approach would iterate from l to r, compute the sum and product of digits for each number, and check the divisibility condition. While correct, this approach is impractical because iterating up to 10^9 numbers would be far too slow.

The key observation for an optimal solution is to use digit dynamic programming (digit DP). Digit DP allows us to count numbers with certain properties without enumerating all of them explicitly. The idea is to define a DP state that captures the current position in the number, the current sum of digits, the current product modulo sum, and whether the number prefix is tight to the upper bound. Using memoization avoids recalculating the same state multiple times.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(r - l + 1 * d)	O(1)	d = number of digits, calculates sum/product for each number
Digit DP	O(d * s * p)	O(d * s * p)	Efficiently counts beautiful numbers using DP and memoization

Algorithm Walkthrough

Convert the upper bound r to a string for easy digit access and define a recursive function dp(pos, tight, sum, product) where pos is the current digit index, tight indicates if we are still bounded by r, sum is the sum of digits so far, and product is the product of digits so far.
At each digit, iterate through all possible digits (0 to 9 if not tight, or 0 to current digit if tight) and recursively call dp for the next position.
Update the sum and product at each step and carry forward the tight constraint.
When all digits are processed (pos == len(number)), check if the current product is divisible by sum. If so, count this number.
Use memoization keyed by (pos, tight, sum, product) to store results of subproblems and avoid recomputation.
To handle a range [l, r], compute count(1, r) and count(1, l - 1) and subtract to get the count in [l, r].

This works because the DP state effectively enumerates all numbers by their digit positions while reusing computations for numbers sharing common prefixes.

LeetCode 3490 - Count Beautiful Numbers

Problem Understanding

We are given two integers l and r, and we must count how many integers in the inclusive range [l, r] are beautiful.

A number is considered beautiful when:

Compute the sum of its digits.
Compute the product of its digits.
The product must be divisible by the sum.

Formally, for a number with digit sum S and digit product P, the number is beautiful if:

$$P \bmod S = 0$$

The input consists of two positive integers defining a range. The output is the number of beautiful integers that lie inside that range.

The constraint r < 10^9 means every number has at most 9 digits. Although this is small in terms of digit count, the range itself can contain nearly one billion numbers. Iterating through every number individually is therefore impossible.

A few important observations immediately stand out.

If a number contains a digit 0, then its digit product becomes 0. Since the digit sum of a positive integer is always positive, 0 % sum == 0, so every positive number containing at least one non-leading zero digit is automatically beautiful.

Single digit numbers are also always beautiful because for any digit d from 1 to 9:

$$d \bmod d = 0$$

The challenging part of the problem is efficiently counting numbers whose digits are all non-zero and whose digit product is divisible by the digit sum.

Approaches

Brute Force

The most direct solution is to iterate through every number from l to r.

For each number:

Extract its digits.
Compute the digit sum.
Compute the digit product.
Check whether the product is divisible by the sum.

This approach is correct because it directly implements the definition of a beautiful number.

Unfortunately, it is far too slow. In the worst case the range size can approach 10^9, making even a constant-time check per number infeasible.

Key Insight

The constraint on the value of the number is large, but the number of digits is small, at most 9.

This strongly suggests a digit DP solution.

The difficult part is the divisibility condition. Storing the full digit product in DP state is impossible because products grow very quickly.

The crucial observation is that the maximum digit sum is:

$$9 \times 9 = 81$$

Every possible digit sum is therefore between 1 and 81.

Any number up to 81 has prime factors only among:

$$2,3,5,7$$

If the digit product is divisible by the digit sum, then the product must contain at least the prime factor exponents required by that sum.

Instead of storing the product itself, we store the exponents of primes (2,3,5,7) appearing in the digit product.

At the end of the digit DP, once the digit sum is known, we compare the accumulated prime exponents against the factorization of the sum.

Numbers containing a zero digit are handled separately because their product instantly becomes zero and they are automatically beautiful.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O((r - l + 1) · D)	O(1)	Check every number individually
Optimal Digit DP	O(D · S · P)	O(D · S · P)	Tracks digit sum and prime-factor exponents instead of full products

Here:

D ≤ 9 is the digit count.
S ≤ 81 is the digit sum.
P represents the bounded prime-exponent state space.

Algorithm Walkthrough

We define a function count(n) that returns the number of beautiful integers in [1, n].

The final answer is:

$$count(r) - count(l-1)$$

Step 1: Precompute digit prime factorizations

For every digit from 1 to 9, precompute how many factors of 2, 3, 5, and 7 it contributes.

For example:

8 = 2³
6 = 2 × 3
9 = 3²

These contributions will be accumulated during digit DP.

Step 2: Precompute sum factorizations

Every digit sum lies between 1 and 81.

For each possible sum:

Factor it using only primes (2,3,5,7).
If anything remains after removing these primes, mark the sum as impossible.

At DP termination we only need to compare stored exponents against the required exponents of the sum.

Step 3: Count numbers containing a zero digit

Any positive integer containing a non-leading zero digit has digit product 0.

Since:

$$0 \bmod (\text{positive sum}) = 0$$

all such numbers are beautiful.

A separate digit DP counts positive integers whose digits are all non-zero.

Then:

$$\text{numbers with zero digit} = \text{all positive numbers} - \text{numbers with no zero digit}$$

Step 4: Build the main digit DP

The state consists of:

Current position.
Current digit sum.
Exponents of (2,3,5,7) accumulated from the product.
Tight flag.
Started flag.

The started flag distinguishes leading zeros from actual digits.

Step 5: Transition

For every possible digit:

If we have not started and choose another leading zero, nothing changes.
Otherwise:
Add digit to the sum.
Add its prime-factor exponents to the state.

The DP recursively processes the next position.

Step 6: Evaluate terminal states

When all positions are processed:

Ignore states that never started.
Let the final digit sum be sum.

Look up the prime-factor requirements of sum.

The number is beautiful if every stored exponent is at least the required exponent of the sum.

Step 7: Combine results

The main DP counts beautiful numbers with no zero digit.

The separate count of numbers containing a zero digit is added.

This produces count(n).

Finally compute:

$$count(r)-count(l-1)$$

Why it works

The DP enumerates every valid number exactly once through digit construction. For numbers with no zero digit, the product is represented by its prime-factor exponents. A product is divisible by the digit sum exactly when its exponent vector dominates the exponent vector of the sum. Numbers containing a zero digit are counted separately and are automatically beautiful because their product equals zero. Since every positive integer belongs to exactly one of these categories, the algorithm counts precisely all beautiful numbers.

Python Solution

from functools import lru_cache

class Solution:
    def beautifulNumbers(self, l: int, r: int) -> int:
        def count_beautiful(n: int) -> int:
            s = str(n)
            
            @lru_cache(None)
            def dp(pos: int, tight: bool, sum_digits: int, product_digits: int) -> int:
                if pos == len(s):
                    return int(product_digits % sum_digits == 0) if sum_digits != 0 else 0
                
                limit = int(s[pos]) if tight else 9
                total = 0
                for digit in range(0, limit + 1):
                    new_tight = tight and (digit == limit)
                    new_sum = sum_digits + digit
                    new_product = product_digits * digit if digit != 0 else product_digits
                    if digit == 0 and sum_digits == 0:
                        new_product = 1  # edge case for leading zeros
                    total += dp(pos + 1, new_tight, new_sum, new_product)
                return total
            
            return dp(0, True, 0, 1)
        
        return count_beautiful(r) - count_beautiful(l - 1)

In this implementation, count_beautiful(n) counts all beautiful numbers from 1 to n using digit DP with memoization. Leading zeros are handled carefully to ensure products start correctly. from typing import List, Tuple

class Solution: def beautifulNumbers(self, l: int, r: int) -> int: digit_factors = [(0, 0, 0, 0)] * 10

    def factor_digit(x: int) -> Tuple[int, int, int, int]:
        c2 = c3 = c5 = c7 = 0
        while x % 2 == 0 and x > 0:
            c2 += 1
            x //= 2
        while x % 3 == 0 and x > 0:
            c3 += 1
            x //= 3
        while x % 5 == 0 and x > 0:
            c5 += 1
            x //= 5
        while x % 7 == 0 and x > 0:
            c7 += 1
            x //= 7
        return (c2, c3, c5, c7)

    for d in range(1, 10):
        digit_factors[d] = factor_digit(d)

    sum_factors = [None] * 82
    for s in range(1, 82):
        x = s
        c2 = c3 = c5 = c7 = 0

        while x % 2 == 0:
            c2 += 1
            x //= 2

        while x % 3 == 0:
            c3 += 1
            x //= 3

        while x % 5 == 0:
            c5 += 1
            x //= 5

        while x % 7 == 0:
            c7 += 1
            x //= 7

        if x == 1:
            sum_factors[s] = (c2, c3, c5, c7)

    def count_up_to(n: int) -> int:
        if n <= 0:
            return 0

        digits = list(map(int, str(n)))
        m = len(digits)

        @lru_cache(None)
        def count_no_zero(
            pos: int,
            tight: bool,
            started: bool,
        ) -> int:
            if pos == m:
                return int(started)

            limit = digits[pos] if tight else 9
            ans = 0

            for d in range(limit + 1):
                nt = tight and d == limit

                if not started and d == 0:
                    ans += count_no_zero(pos + 1, nt, False)
                elif d != 0:
                    ans += count_no_zero(pos + 1, nt, True)

            return ans

        @lru_cache(None)
        def beautiful_no_zero(
            pos: int,
            digit_sum: int,
            p2: int,
            p3: int,
            p5: int,
            p7: int,
            tight: bool,
            started: bool,
        ) -> int:
            if pos == m:
                if not started:
                    return 0

                req = sum_factors[digit_sum]
                if req is None:
                    return 0

                return int(
                    p2 >= req[0]
                    and p3 >= req[1]
                    and p5 >= req[2]
                    and p7 >= req[3]
                )

            limit = digits[pos] if tight else 9
            ans = 0

            for d in range(limit + 1):
                nt = tight and d == limit

                if not started and d == 0:
                    ans += beautiful_no_zero(
                        pos + 1,
                        digit_sum,
                        p2,
                        p3,
                        p5,
                        p7,
                        nt,
                        False,
                    )
                elif d != 0:
                    f2, f3, f5, f7 = digit_factors[d]
                    ans += beautiful_no_zero(
                        pos + 1,
                        digit_sum + d,
                        p2 + f2,
                        p3 + f3,
                        p5 + f5,
                        p7 + f7,
                        nt,
                        True,
                    )

            return ans

        total_positive = n
        no_zero_count = count_no_zero(0, True, False)
        with_zero = total_positive - no_zero_count

        no_zero_beautiful = beautiful_no_zero(
            0,
            0,
            0,
            0,
            0,
            0,
            True,
            False,
        )

        return with_zero + no_zero_beautiful

    return count_up_to(r) - count_up_to(l - 1)


The implementation begins by precomputing prime-factor contributions for digits `1` through `9`. This allows the digit DP to update prime exponents in constant time.

Next, it precomputes the factorization of every possible digit sum from `1` through `81`. These factorizations are used at terminal states to verify divisibility.

The helper `count_no_zero` counts all positive integers up to `n` whose digits are entirely non-zero. Subtracting this from `n` gives the count of numbers containing at least one zero digit.

The main DP, `beautiful_no_zero`, tracks the digit sum and accumulated prime exponents. When the number is fully constructed, it checks whether the product contains enough prime factors to be divisible by the digit sum.

Finally, the beautiful non-zero-digit numbers and the automatically beautiful zero-containing numbers are combined.

## Go Solution

```go
func beautifulNumbers(l int, r int) int {
    var dp func(pos int, tight bool, sum int, product int) int
    memo := map[[4]int]int{}
    s := func(n int) []int {
        res := []int{}
        for n > 0 {
            res = append([]int{n % 10}, res...)
            n /= 10
        }
        return res
    }
    
    countBeautiful := func(n int) int {
        digits := s(n)
        var dfs func(pos int, tight int, sum int, product int) int
        dfs = func(pos int, tight int, sum int, product int) int {
            if pos == len(digits) {
                if sum != 0 && product%sum == 0 {
                    return 1
                }
                return 0
            }
            key := [4]int{pos, tight, sum, product}
            if val, ok := memo[key]; ok {
                return val
            }
            limit := 9
            if tight == 1 {
                limit = digits[pos]
            }
            total := 0
            for d := 0; d <= limit; d++ {
                newTight := 0
                if tight == 1 && d == limit {
                    newTight = 1
                }
                newSum := sum + d
                newProduct := product
                if d != 0 {
                    newProduct *= d
                } else if sum == 0 {
                    newProduct = 1
                }
                total += dfs(pos+1, newTight, newSum, newProduct)
            }
            memo[key] = total
            return total
        }
        return dfs(0, 1, 0, 1)
    }
    
    return countBeautiful(r) - countBeautiful(l-1)
}

In Go, memoization is implemented via a map with array keys. Leading zeros are handled similarly, ensuring the product starts as 1.

Worked Examples

Example 1: l = 10, r = 20

We compute count_beautiful(20) and count_beautiful(9). Numbers 10 and 20 satisfy the beautiful condition. DP recursively enumerates all possibilities and counts only these two.

Example 2: l = 1, r = 15

Single-digit numbers 1 to 9 are all beautiful. Number 10 is also beautiful. The count is 10.

import "strconv"

func beautifulNumbers(l int, r int) int { digitFactors := [10][4]int{}

for d := 1; d <= 9; d++ {
	x := d
	var c [4]int

	for x%2 == 0 {
		c[0]++
		x /= 2
	}
	for x%3 == 0 {
		c[1]++
		x /= 3
	}
	for x%5 == 0 {
		c[2]++
		x /= 5
	}
	for x%7 == 0 {
		c[3]++
		x /= 7
	}

	digitFactors[d] = c
}

sumFactors := [82][5]int{}

for s := 1; s <= 81; s++ {
	x := s
	c2, c3, c5, c7 := 0, 0, 0, 0

	for x%2 == 0 {
		c2++
		x /= 2
	}
	for x%3 == 0 {
		c3++
		x /= 3
	}
	for x%5 == 0 {
		c5++
		x /= 5
	}
	for x%7 == 0 {
		c7++
		x /= 7
	}

	if x == 1 {
		sumFactors[s] = [5]int{1, c2, c3, c5, c7}
	}
}

countUpTo := func(n int) int {
	if n <= 0 {
		return 0
	}

	str := strconv.Itoa(n)
	digits := make([]int, len(str))

	for i := range str {
		digits[i] = int(str[i] - '0')
	}

	type Key1 struct {
		Pos     int
		Tight   bool
		Started bool
	}

	memo1 := map[Key1]int{}

	var dfsNoZero func(int, bool, bool) int

	dfsNoZero = func(pos int, tight bool, started bool) int {
		if pos == len(digits) {
			if started {
				return 1
			}
			return 0
		}

		key := Key1{pos, tight, started}
		if !tight {
			if v, ok := memo1[key]; ok {
				return v
			}
		}

		limit := 9
		if tight {
			limit = digits[pos]
		}

		ans := 0

		for d := 0; d <= limit; d++ {
			nt := tight && d == limit

			if !started && d == 0 {
				ans += dfsNoZero(pos+1, nt, false)
			} else if d != 0 {
				ans += dfsNoZero(pos+1, nt, true)
			}
		}

		if !tight {
			memo1[key] = ans
		}

		return ans
	}

	type Key2 struct {
		Pos     int
		Sum     int
		P2      int
		P3      int
		P5      int
		P7      int
		Tight   bool
		Started bool
	}

	memo2 := map[Key2]int{}

	var dfsBeautiful func(int, int, int, int, int, int, bool, bool) int

	dfsBeautiful = func(
		pos int,
		sum int,
		p2 int,
		p3 int,
		p5 int,
		p7 int,
		tight bool,
		started bool,
	) int {
		if pos == len(digits) {
			if !started {
				return 0
			}

			info := sumFactors[sum]
			if info[0] == 0 {
				return 0
			}

			if p2 >= info[1] &&
				p3 >= info[2] &&
				p5 >= info[3] &&
				p7 >= info[4] {
				return 1
			}

			return 0
		}

		key := Key2{
			pos, sum, p2, p3, p5, p7,
			tight, started,
		}

		if !tight {
			if v, ok := memo2[key]; ok {
				return v
			}
		}

		limit := 9
		if tight {
			limit = digits[pos]
		}

		ans := 0

		for d := 0; d <= limit; d++ {
			nt := tight && d == limit

			if !started && d == 0 {
				ans += dfsBeautiful(
					pos+1,
					sum,
					p2,
					p3,
					p5,
					p7,
					nt,
					false,
				)
			} else if d != 0 {
				f := digitFactors[d]

				ans += dfsBeautiful(
					pos+1,
					sum+d,
					p2+f[0],
					p3+f[1],
					p5+f[2],
					p7+f[3],
					nt,
					true,
				)
			}
		}

		if !tight {
			memo2[key] = ans
		}

		return ans
	}

	noZero := dfsNoZero(0, true, false)
	withZero := n - noZero

	noZeroBeautiful := dfsBeautiful(
		0, 0, 0, 0, 0, 0,
		true, false,
	)

	return withZero + noZeroBeautiful
}

return countUpTo(r) - countUpTo(l-1)

}


The Go version follows the same logic as the Python implementation. Because Go does not provide built-in memoization decorators, explicit map-based caches are used. Structs serve as memoization keys. Integer overflow is not a concern because the answer never exceeds `10^9`, which comfortably fits within Go's `int`.

## Worked Examples

### Example 1

Input:

l = 10 r = 20


We compute:

count(20) - count(9)


Numbers from 10 to 20:

| Number | Digit Sum | Digit Product | Beautiful |
| --- | --- | --- | --- |
| 10 | 1 | 0 | Yes |
| 11 | 2 | 1 | No |
| 12 | 3 | 2 | No |
| 13 | 4 | 3 | No |
| 14 | 5 | 4 | No |
| 15 | 6 | 5 | No |
| 16 | 7 | 6 | No |
| 17 | 8 | 7 | No |
| 18 | 9 | 8 | No |
| 19 | 10 | 9 | No |
| 20 | 2 | 0 | Yes |

Total beautiful numbers:


### Example 2

Input:

l = 1 r = 15


Single-digit numbers:

| Number | Sum | Product | Beautiful |
| --- | --- | --- | --- |
| 1 | 1 | 1 | Yes |
| 2 | 2 | 2 | Yes |
| 3 | 3 | 3 | Yes |
| 4 | 4 | 4 | Yes |
| 5 | 5 | 5 | Yes |
| 6 | 6 | 6 | Yes |
| 7 | 7 | 7 | Yes |
| 8 | 8 | 8 | Yes |
| 9 | 9 | 9 | Yes |
| 10 | 1 | 0 | Yes |
| 11 | 2 | 1 | No |
| 12 | 3 | 2 | No |
| 13 | 4 | 3 | No |
| 14 | 5 | 4 | No |
| 15 | 6 | 5 | No |

The number `10` contains a zero digit and is automatically beautiful.

Numbers `11` through `15` are not beautiful.

Total:


## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(d * s * p) | d = number of digits (<=9), s = max possible sum of digits, p = max possible product; memoization avoids repeated computation |
| Space | O(d * s * p) | Storage for memoization of DP states |

The exponential state space is manageable because the sum and product are bounded by the maximum number of digits, and memoization ensures we compute each state once.
| Time | O(D × S × P) | Digit DP visits all reachable digit-sum and exponent states |
| Space | O(D × S × P) | Memoization table stores DP states |

Here:

- `D ≤ 9`
- `S ≤ 81`
- `P` is the bounded exponent-state space for primes `(2,3,5,7)`

Because the maximum digit count is only 9, the state space remains small enough for an efficient digit-DP solution. The algorithm runs comfortably within contest limits.

## Test Cases

test cases

sol = Solution() assert sol.beautifulNumbers(10, 20) == 2 # example 1 assert sol.beautifulNumbers(1, 15) == 10 # example 2 assert sol.beautifulNumbers(1, 9) == 9 # single digits assert sol.beautifulNumbers(100, 1000) > 0 # larger range assert sol.beautifulNumbers(1, 1) == 1 # smallest range assert sol.beautifulNumbers(999999990, 1000000000) >= 0 # near upper bound


| Test | Why |
| --- | --- |
| 10 to 20 | Validates small range with 2 beautiful numbers |
| 1 to |  |
sol = Solution()

assert sol.beautifulNumbers(10, 20) == 2      # provided example
assert sol.beautifulNumbers(1, 15) == 10      # provided example

assert sol.beautifulNumbers(1, 1) == 1        # smallest possible input
assert sol.beautifulNumbers(9, 9) == 1        # largest single digit
assert sol.beautifulNumbers(10, 10) == 1      # contains zero

assert sol.beautifulNumbers(11, 11) == 0      # non-beautiful two digit
assert sol.beautifulNumbers(20, 20) == 1      # product zero

assert sol.beautifulNumbers(100, 100) == 1    # multiple zeros
assert sol.beautifulNumbers(101, 101) == 1    # internal zero

assert sol.beautifulNumbers(1, 10) == 10      # all single digits plus 10
assert sol.beautifulNumbers(1, 20) == 11      # example range extension

assert sol.beautifulNumbers(999999999, 999999999) >= 0  # upper bound stress

Test Summary

Test	Why
`(10,20)`	Official example
`(1,15)`	Official example
`(1,1)`	Smallest valid range
`(9,9)`	Single digit boundary
`(10,10)`	Product becomes zero
`(11,11)`	Simple non-beautiful case
`(20,20)`	Zero digit handling
`(100,100)`	Multiple zero digits
`(101,101)`	Internal zero digit
`(1,10)`	Transition from one digit to two digits
`(1,20)`	Mixed range
`(999999999,999999999)`	Maximum constraint

Edge Cases

Numbers Containing Zero Digits

A common mistake is trying to factorize a product that becomes zero. Once a non-leading zero digit appears, the entire digit product becomes zero and the number is automatically beautiful because the digit sum remains positive. The implementation handles these numbers separately by counting all numbers containing at least one zero digit and adding them directly to the answer.

Leading Zeros During Digit DP

Digit DP frequently constructs numbers using leading zeros. These zeros are not actual digits of the number and must not contribute to the digit sum or product. The started flag ensures that leading zeros are ignored until the first non-zero digit is chosen.

Digit Sums With Unsupported Prime Factors

The digit product of a non-zero-digit number can only contain prime factors 2, 3, 5, and 7, because every digit from 1 to 9 factors into those primes. If the digit sum contains some other prime factor after factorization, divisibility is impossible. The implementation detects this during preprocessing and immediately rejects such terminal states. This avoids unnecessary computation and guarantees correctness.