Count Beautiful Numbers

Problem

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.

Examples

Example 1

1
2
3
4


Input: l = 10, r = 20
Output: 2
Explanation:
The beautiful numbers in the range are 10 and 20.

Example 2

1
2
3
4


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

Method 1 – Digit DP (Dynamic Programming) 1

Intuition

A number is beautiful if the product of its digits is divisible by the sum of its digits. Since the range can be large, we use digit dynamic programming (digit DP) to count such numbers efficiently. We enumerate all possible digit combinations, keeping track of the sum and product of digits, and use memoization to avoid recomputation.

Approach

Define a DP function: dp(pos, tight, sum, prod, leading_zero), where:
- pos: current digit position (from left to right)
- tight: whether the current prefix is equal to the upper bound
- sum: sum of digits so far
- prod: product of digits so far
- leading_zero: whether we are still placing leading zeros
For each digit, try all possible values (0 to upper bound at this position if tight, else 9).
For each complete number (when pos == len), if sum > 0 and prod % sum == 0, count it.
Use memoization to cache results.
To count numbers in [l, r], compute f(r) - f(l-1).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


class Solution {
public:
    int countBeautifulNumbers(int l, int r) {
        return count(r) - count(l - 1);
    }
    int count(int n) {
        string s = to_string(n);
        memo.clear();
        return dp(0, 1, 0, 1, 1, s);
    }
    unordered_map<string, int> memo;
    int dp(int pos, int tight, int sum, int prod, int leading_zero, const string& s) {
        if (pos == s.size()) return sum > 0 && prod % sum == 0;
        string key = to_string(pos) + "," + to_string(tight) + "," + to_string(sum) + "," + to_string(prod) + "," + to_string(leading_zero);
        if (!tight && !leading_zero && memo.count(key)) return memo[key];
        int res = 0, up = tight ? s[pos] - '0' : 9;
        for (int d = 0; d <= up; ++d) {
            int nsum = sum + (leading_zero && d == 0 ? 0 : d);
            int nprod = (leading_zero && d == 0 ? 1 : prod * (d == 0 ? 1 : d));
            res += dp(pos + 1, tight && d == up, nsum, nprod, leading_zero && d == 0, s);
        }
        if (!tight && !leading_zero) memo[key] = res;
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51


func countBeautifulNumbers(l, r int) int {
    return count(r) - count(l-1)
}
func count(n int) int {
    s := strconv.Itoa(n)
    memo := map[string]int{}
    var dp func(pos, tight, sum, prod, leadingZero int) int
    dp = func(pos, tight, sum, prod, leadingZero int) int {
        if pos == len(s) {
            if sum > 0 && prod%sum == 0 {
                return 1
            }
            return 0
        }
        key := fmt.Sprintf("%d,%d,%d,%d,%d", pos, tight, sum, prod, leadingZero)
        if tight == 0 && leadingZero == 0 {
            if v, ok := memo[key]; ok {
                return v
            }
        }
        res := 0
        up := 9
        if tight == 1 {
            up = int(s[pos] - '0')
        }
        for d := 0; d <= up; d++ {
            nsum := sum
            nprod := prod
            if !(leadingZero == 1 && d == 0) {
                nsum += d
                if d != 0 {
                    nprod *= d
                }
            }
            nleadingZero := 0
            if leadingZero == 1 && d == 0 {
                nleadingZero = 1
            }
            ntight := 0
            if tight == 1 && d == up {
                ntight = 1
            }
            res += dp(pos+1, ntight, nsum, nprod, nleadingZero)
        }
        if tight == 0 && leadingZero == 0 {
            memo[key] = res
        }
        return res
    }
    return dp(0, 1, 0, 1, 1)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


class Solution {
    public int countBeautifulNumbers(int l, int r) {
        return count(r) - count(l - 1);
    }
    int count(int n) {
        String s = String.valueOf(n);
        memo.clear();
        return dp(0, 1, 0, 1, 1, s);
    }
    Map<String, Integer> memo = new HashMap<>();
    int dp(int pos, int tight, int sum, int prod, int leadingZero, String s) {
        if (pos == s.length()) return sum > 0 && prod % sum == 0 ? 1 : 0;
        String key = pos+","+tight+","+sum+","+prod+","+leadingZero;
        if (tight == 0 && leadingZero == 0 && memo.containsKey(key)) return memo.get(key);
        int res = 0, up = tight == 1 ? s.charAt(pos) - '0' : 9;
        for (int d = 0; d <= up; ++d) {
            int nsum = sum, nprod = prod;
            if (!(leadingZero == 1 && d == 0)) {
                nsum += d;
                if (d != 0) nprod *= d;
            }
            int nleadingZero = (leadingZero == 1 && d == 0) ? 1 : 0;
            int ntight = (tight == 1 && d == up) ? 1 : 0;
            res += dp(pos+1, ntight, nsum, nprod, nleadingZero, s);
        }
        if (tight == 0 && leadingZero == 0) memo.put(key, res);
        return res;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


class Solution {
    fun countBeautifulNumbers(l: Int, r: Int): Int {
        return count(r) - count(l - 1)
    }
    fun count(n: Int): Int {
        val s = n.toString()
        val memo = mutableMapOf<String, Int>()
        fun dp(pos: Int, tight: Int, sum: Int, prod: Int, leadingZero: Int): Int {
            if (pos == s.length) return if (sum > 0 && prod % sum == 0) 1 else 0
            val key = "$pos,$tight,$sum,$prod,$leadingZero"
            if (tight == 0 && leadingZero == 0 && key in memo) return memo[key]!!
            var res = 0
            val up = if (tight == 1) s[pos] - '0' else 9
            for (d in 0..up) {
                var nsum = sum
                var nprod = prod
                if (!(leadingZero == 1 && d == 0)) {
                    nsum += d
                    if (d != 0) nprod *= d
                }
                val nleadingZero = if (leadingZero == 1 && d == 0) 1 else 0
                val ntight = if (tight == 1 && d == up) 1 else 0
                res += dp(pos+1, ntight, nsum, nprod, nleadingZero)
            }
            if (tight == 0 && leadingZero == 0) memo[key] = res
            return res
        }
        return dp(0, 1, 0, 1, 1)
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


class Solution:
    def countBeautifulNumbers(self, l: int, r: int) -> int:
        def count(n: int) -> int:
            from functools import lru_cache
            s = str(n)
            @lru_cache(maxsize=None)
            def dp(pos: int, tight: int, ssum: int, prod: int, leading_zero: int) -> int:
                if pos == len(s):
                    return int(ssum > 0 and prod % ssum == 0)
                res = 0
                up = int(s[pos]) if tight else 9
                for d in range(0, up+1):
                    nsum = ssum
                    nprod = prod
                    if not (leading_zero and d == 0):
                        nsum += d
                        if d != 0:
                            nprod *= d
                    nleading_zero = leading_zero and d == 0
                    ntight = tight and d == up
                    res += dp(pos+1, ntight, nsum, nprod, nleading_zero)
                return res
            return dp(0, 1, 0, 1, 1)
        return count(r) - count(l-1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


impl Solution {
    pub fn count_beautiful_numbers(l: i32, r: i32) -> i32 {
        fn count(n: i32) -> i32 {
            let s = n.to_string().chars().collect::<Vec<_>>();
            use std::collections::HashMap;
            fn dp(pos: usize, tight: bool, sum: i32, prod: i32, leading_zero: bool, s: &Vec<char>, memo: &mut HashMap<(usize, bool, i32, i32, bool), i32>) -> i32 {
                if pos == s.len() {
                    return if sum > 0 && prod % sum == 0 { 1 } else { 0 };
                }
                let key = (pos, tight, sum, prod, leading_zero);
                if !tight && !leading_zero {
                    if let Some(&v) = memo.get(&key) { return v; }
                }
                let up = if tight { s[pos].to_digit(10).unwrap() as i32 } else { 9 };
                let mut res = 0;
                for d in 0..=up {
                    let nsum = if leading_zero && d == 0 { sum } else { sum + d };
                    let nprod = if leading_zero && d == 0 { prod } else { if d == 0 { prod } else { prod * d } };
                    let nleading_zero = leading_zero && d == 0;
                    let ntight = tight && d == up;
                    res += dp(pos+1, ntight, nsum, nprod, nleading_zero, s, memo);
                }
                if !tight && !leading_zero { memo.insert(key, res); }
                res
            }
            let mut memo = HashMap::new();
            dp(0, true, 0, 1, true, &s, &mut memo)
        }
        count(r) - count(l-1)
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


class Solution {
    countBeautifulNumbers(l: number, r: number): number {
        return this.count(r) - this.count(l - 1);
    }
    count(n: number): number {
        const s = n.toString();
        const memo = new Map<string, number>();
        const dp = (pos: number, tight: boolean, sum: number, prod: number, leadingZero: boolean): number => {
            if (pos === s.length) return sum > 0 && prod % sum === 0 ? 1 : 0;
            const key = `${pos},${tight},${sum},${prod},${leadingZero}`;
            if (!tight && !leadingZero && memo.has(key)) return memo.get(key)!;
            let res = 0;
            const up = tight ? Number(s[pos]) : 9;
            for (let d = 0; d <= up; ++d) {
                let nsum = sum, nprod = prod;
                if (!(leadingZero && d === 0)) {
                    nsum += d;
                    if (d !== 0) nprod *= d;
                }
                const nleadingZero = leadingZero && d === 0;
                const ntight = tight && d === up;
                res += dp(pos+1, ntight, nsum, nprod, nleadingZero);
            }
            if (!tight && !leadingZero) memo.set(key, res);
            return res;
        };
        return dp(0, true, 0, 1, true);
    }
}

Complexity

⏰ Time complexity: O(D^3 * log N), where D is the number of digits (up to 9) and N is the upper bound, due to digit DP and state space.
🧺 Space complexity: O(D^3 * log N), for the DP memoization table.

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – Digit DP (Dynamic Programming) 1#

Intuition#

Approach#

Code#

Complexity#