Tejav
#3490

Count Beautiful Numbers

Hard
Dynamic ProgrammingDigit Dynamic ProgrammingRecursive Backtracking
LeetCode ↗

Approaches

Brute ForceOptimal
Complexity Comparison
Brute ForceOptimal Solution★
Time
O(n²)
O(n)
Space
O(1)
O(n)
💡

Intuition

Time O(n)Space O(n)

Use digit dynamic programming to efficiently count beautiful numbers without checking each one individually. This leverages the properties of digits and their combinations.

⚙️

Algorithm

3 steps
  1. 1Step 1: Define a recursive function with memoization to count beautiful numbers up to a given limit.
  2. 2Step 2: For each digit position, decide whether to include the current digit or not, while maintaining the sum and product.
  3. 3Step 3: Use the results from the recursive calls to build the count of beautiful numbers.
solution.py10 lines
1def countBeautifulNumbers(l, r):
2    def dp(pos, sum_digits, product_digits, tight):
3        if pos == len(str(r)):
4            return 1 if product_digits % sum_digits == 0 else 0
5        limit = int(str(r)[pos]) if tight else 9
6        count = 0
7        for digit in range(0, limit + 1):
8            count += dp(pos + 1, sum_digits + digit, product_digits * digit if digit > 0 else product_digits, tight and (digit == limit))
9        return count
10    return dp(0, 0, 1, True) - dp(0, 0, 1, True) + 1
ℹ

Complexity note: The complexity is reduced by using digit dynamic programming, allowing us to count valid numbers without iterating through each one explicitly.

  • 1The product of digits must be divisible by the sum of digits.
  • 2Dynamic programming can optimize counting by avoiding redundant calculations.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.