Count Beautiful Numbers

• 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.

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.

1class Solution {2    private boolean isBeautiful(int n) {3        long sum = 0;4        long prod = 1;5        int temp = n;6        boolean hasZero = false;7 8        while (temp > 0) {9            int digit = temp % 10;10            if (digit == 0) {11                hasZero = true;12            }13            sum += digit;14            // We can't just multiply by non-zero digits15            // as the product would be wrong if a zero exists.16            // It's better to handle the hasZero case after the loop.17            prod *= digit;18            temp /= 10;19        }20 21        if (hasZero) {22            return true; // Product is 0, sum > 0, so 0 % sum == 0.23        }24 25        if (sum == 0) { // Should not happen for n > 026            return false;27        }28 29        return prod % sum == 0;30    }31 32    public int countBeautifulNumbers(int l, int r) {33        int count = 0;34        for (int i = l; i <= r; i++) {35            if (isBeautiful(i)) {36                count++;37            }38        }39        return count;40    }41}

• 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.

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.

1// Note: This is a conceptual sketch. A full implementation is lengthy.2class Solution {3    String s;4    Long[][][][][][][] memo;5    int[][] digitPrimeFactors; // Precomputed prime factors for digits 1-96    int[][] sumPrimeFactors;   // Precomputed prime factors for sums 1-817 8    public int countBeautifulNumbers(int l, int r) {9        return count(r) - count(l - 1);10    }11 12    private int count(int n) {13        if (n == 0) return 0;14        s = String.valueOf(n);15        // Precomputation would be done here or in a constructor.16 17        // Part 1: Count numbers with a '0'.18        // This is n - countNoZeros(n).19        // countNoZeros can be implemented with its own simple Digit DP.20        int countWithZero = n - countNoZeros(n);21 22        // Part 2: Count beautiful numbers with no '0's.23        memo = new Long[s.length()][82][7][5][3][3][2]; // is_less, is_started combined24        int countBeautifulNoZero = (int) dfs(0, 0, 0, 0, 0, 0, true, true);25 26        return countWithZero + countBeautifulNoZero;27    }28 29    // Simplified signature for the main DP30    private long dfs(int index, int sum, int p2, int p3, int p5, int p7, boolean isLess, boolean isStarted) {31        if (index == s.length()) {32            if (isStarted) return 0; // Empty number33            if (sum == 0) return 0;34            // Check if product is divisible by sum using prime exponents35            // ... check logic ...36            return 1; // if beautiful37        }38        // ... memoization check ...39 40        long ans = 0;41        // if isStarted, we can form a number with fewer digits42        if (!isStarted) {43            ans += dfs(index + 1, 0, 0, 0, 0, 0, true, false);44        }45 46        int limit = isLess ? 9 : s.charAt(index) - '0';47        for (int d = 1; d <= limit; d++) {48            // update sum, p2, p3, p5, p7 based on digit d49            // new_p2 = Math.min(6, p2 + digitPrimeFactors[d][0]);50            // ... recursive call ...51        }52        // ... memoize and return ans ...53        return ans;54    }55 56    private int countNoZeros(int n) {57        // Implementation of a simpler Digit DP to count numbers with digits 1-9 up to n.58        return 0; // Placeholder59    }60}