# Count Beautiful Numbers
**Difficulty:** HARD
[External](https://leetcode.com/problems/count-beautiful-numbers)
Canonical: https://scaleengineer.com/dsa/problems/count-beautiful-numbers
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
---
## 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.

**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`

# Approaches
## Brute Force Iteration
The most straightforward approach is to simulate the process described in the problem statement. We can iterate through every number in the given range `[l, r]` and, for each number, check if it satisfies the "beautiful" condition. A counter will keep track of how many such numbers we find.
**Time:** O((r - l) * log<sub>10</sub>(r)) · **Space:** O(1)
**Pros:** Simple to understand and implement.; Correct for small ranges.
**Cons:** This approach is too slow for the given constraints. If `l` is 1 and `r` is 10<sup>9</sup>, the loop will run 10<sup>9</sup> times, which will lead to a 'Time Limit Exceeded' error.
### Explanation
This method involves a simple loop from `l` to `r`. Inside the loop, for each number, we define a helper function, `isBeautiful`, to determine if it meets the criteria. 

To implement `isBeautiful(n)`, we need to calculate the sum and the product of its digits. We can extract the digits by repeatedly taking the number modulo 10 (`n % 10`) and then dividing it by 10 (`n / 10`).

A crucial optimization comes from observing the effect of a zero digit. If any digit of a number is 0, the product of all its digits will be 0. For any positive number, the sum of its digits is always a positive integer. The condition `product % sum == 0` becomes `0 % sum == 0`, which is always true. Therefore, any positive integer containing the digit '0' is a beautiful number. This allows us to immediately classify such numbers without needing to compute the full product.

If a number does not contain any '0' digits, we compute the full sum and product and then check if the product is divisible by the sum.

```java
class Solution {
    private boolean isBeautiful(int n) {
        long sum = 0;
        long prod = 1;
        int temp = n;
        boolean hasZero = false;

        while (temp > 0) {
            int digit = temp % 10;
            if (digit == 0) {
                hasZero = true;
            }
            sum += digit;
            // We can't just multiply by non-zero digits
            // as the product would be wrong if a zero exists.
            // It's better to handle the hasZero case after the loop.
            prod *= digit;
            temp /= 10;
        }

        if (hasZero) {
            return true; // Product is 0, sum > 0, so 0 % sum == 0.
        }

        if (sum == 0) { // Should not happen for n > 0
            return false;
        }

        return prod % sum == 0;
    }

    public int countBeautifulNumbers(int l, int r) {
        int count = 0;
        for (int i = l; i <= r; i++) {
            if (isBeautiful(i)) {
                count++;
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter `beautiful_count` to 0.
- Iterate through each integer `num` from `l` to `r` (inclusive).
- For each `num`, check if it is a "beautiful" number using a helper function `isBeautiful(num)`.
- If `isBeautiful(num)` returns true, increment `beautiful_count`.
- After the loop finishes, return `beautiful_count`.

**Helper function `isBeautiful(n)`:**
- Initialize `sum = 0` and `product = 1`.
- Create a temporary variable `temp = n`.
- Loop while `temp > 0`:
  - Get the last digit: `digit = temp % 10`.
  - If `digit` is 0, the product of digits will be 0. Since the sum of digits for a positive number `n` is always positive, `0 % sum` will be 0. Therefore, the number is beautiful. We can stop and return `true` immediately after calculating the full sum.
  - Add the digit to `sum`: `sum += digit`.
  - Multiply the digit with `product`: `product *= digit`.
  - Update `temp`: `temp /= 10`.
- If the loop completes without finding a zero digit, check if `product % sum == 0`. Return `true` if it is, `false` otherwise.

## Digit DP with Prime Factorization State
For large ranges, a brute-force check is infeasible. A standard technique for such counting problems is Digit Dynamic Programming. The core idea is to count the number of beautiful integers up to `r` and subtract the count of beautiful integers up to `l-1`. This reduces the problem to creating an efficient `count(N)` function.
**Time:** O(log<sub>10</sub>(r)) · **Space:** O(log<sub>10</sub>(r))
**Pros:** Highly efficient, capable of solving the problem within the time limits for large constraints.; It is a generalizable technique for a wide class of digit-based counting problems.
**Cons:** The logic is highly complex and difficult to implement without errors.; The DP state is large, requiring careful management of memory and indices.
### Explanation
The `count(N)` function is implemented by splitting the problem into two disjoint cases: counting beautiful numbers that contain at least one '0', and counting beautiful numbers that do not.

1.  **Numbers with a '0':** Any number with a '0' digit is beautiful. The count of such numbers up to `N` is simply `N` minus the count of numbers up to `N` that are composed only of non-zero digits (1-9). This subproblem (`countNoZeros(N)`) can be solved with a straightforward Digit DP.

2.  **Beautiful numbers without a '0':** This requires a more sophisticated Digit DP. The key insight is that if the product of digits `P` is divisible by the sum of digits `S`, then the prime factors of `S` must be a subset of the prime factors of `P`. Since the digits are from {1..9}, the only primes that can appear in the factorization of `P` are {2, 3, 5, 7}. Consequently, `S` must also only be composed of these prime factors.

    We can build a recursive DP function `dfs(index, sum, p2, p3, p5, p7, is_less, is_started)` that constructs numbers digit by digit. The state variables track the current `sum` and the exponents of the primes {2,3,5,7} in the `product`. These exponents can be capped because we only need to know if they are greater than or equal to the exponents in the sum's factorization. For example, the highest power of 2 that can appear in a sum less than 82 is `64 = 2^6`, so we only need to track the exponent of 2 up to 6.

    At the base case of the recursion (when a full number is formed), we check if the final `sum` is valid (has only prime factors {2,3,5,7}) and if the accumulated prime exponents for the product are sufficient to make it divisible by the sum. The results are memoized to ensure efficiency.

```java
// Note: This is a conceptual sketch. A full implementation is lengthy.
class Solution {
    String s;
    Long[][][][][][][] memo;
    int[][] digitPrimeFactors; // Precomputed prime factors for digits 1-9
    int[][] sumPrimeFactors;   // Precomputed prime factors for sums 1-81

    public int countBeautifulNumbers(int l, int r) {
        return count(r) - count(l - 1);
    }

    private int count(int n) {
        if (n == 0) return 0;
        s = String.valueOf(n);
        // Precomputation would be done here or in a constructor.

        // Part 1: Count numbers with a '0'.
        // This is n - countNoZeros(n).
        // countNoZeros can be implemented with its own simple Digit DP.
        int countWithZero = n - countNoZeros(n);

        // Part 2: Count beautiful numbers with no '0's.
        memo = new Long[s.length()][82][7][5][3][3][2]; // is_less, is_started combined
        int countBeautifulNoZero = (int) dfs(0, 0, 0, 0, 0, 0, true, true);

        return countWithZero + countBeautifulNoZero;
    }

    // Simplified signature for the main DP
    private long dfs(int index, int sum, int p2, int p3, int p5, int p7, boolean isLess, boolean isStarted) {
        if (index == s.length()) {
            if (isStarted) return 0; // Empty number
            if (sum == 0) return 0;
            // Check if product is divisible by sum using prime exponents
            // ... check logic ...
            return 1; // if beautiful
        }
        // ... memoization check ...

        long ans = 0;
        // if isStarted, we can form a number with fewer digits
        if (!isStarted) {
            ans += dfs(index + 1, 0, 0, 0, 0, 0, true, false);
        }

        int limit = isLess ? 9 : s.charAt(index) - '0';
        for (int d = 1; d <= limit; d++) {
            // update sum, p2, p3, p5, p7 based on digit d
            // new_p2 = Math.min(6, p2 + digitPrimeFactors[d][0]);
            // ... recursive call ...
        }
        // ... memoize and return ans ...
        return ans;
    }

    private int countNoZeros(int n) {
        // Implementation of a simpler Digit DP to count numbers with digits 1-9 up to n.
        return 0; // Placeholder
    }
}
```
### Algorithm
- The problem of counting in a range `[l, r]` is converted to `count(r) - count(l-1)`, where `count(N)` finds all beautiful numbers from 1 to `N`.
- A number is beautiful if: (A) it contains at least one '0' digit, or (B) it has no '0' digits and its product of digits is divisible by its sum of digits. These two sets are disjoint.
- We calculate the counts for (A) and (B) up to `N` separately.
- **Count for (A):** The number of integers `<= N` with at least one '0' is `N - (count of numbers <= N with no '0's)`. The latter part can be solved with a simple Digit DP.
- **Count for (B):** This is the main challenge. We use a more complex Digit DP.
  - **Insight:** If `product % sum == 0`, then all prime factors of `sum` must also be prime factors of `product`. Since digits are from {1-9}, the prime factors of `product` can only be {2, 3, 5, 7}. Thus, `sum` must also only have these prime factors.
  - **DP State:** We design a state to build numbers digit by digit while tracking necessary information: `dp(index, sum, p2, p3, p5, p7, is_less, is_started)`.
    - `index`: Current digit position.
    - `sum`: Sum of digits so far.
    - `p2, p3, p5, p7`: Exponents of primes in the product. We can cap these exponents at the maximum required by any possible sum (e.g., max power of 2 in a sum <= 81 is `2^6=64`, so `p2` is capped at 6).
    - `is_less`: Flag indicating if our number is already smaller than `N`'s prefix.
    - `is_started`: Flag to handle numbers with fewer digits than `N`.
  - **Base Case:** When `index` reaches the end, we have a final `sum` and final prime exponents for the `product`. We check if `sum` is valid (has only prime factors {2,3,5,7}) and if the product's prime exponents are sufficient to divide the sum's prime exponents. If so, we've found one beautiful number.
  - **Transitions:** The function explores placing digits {1-9} at the current `index`, updating the state variables, and calling itself recursively. Results are memoized to avoid re-computation.