We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Beautiful Numbers

Number: 3801

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given two positive integers l and r, count how many numbers in the inclusive range [l, r] are “beautiful”. A number is beautiful if the product of its digits is divisible by the sum of its digits. For example, 10 is beautiful because 1×0 = 0 and 0 is divisible by 1+0 = 1.

Key Insights

  • Digits that include zero automatically yield a product of 0 (and as long as the sum is positive, 0 mod (sum) equals 0).
  • Every one‐digit number is beautiful since d % d = 0.
  • The direct brute force solution is infeasible for r up to 10^9.
  • A digit DP approach is viable by iterating over the digits of the number while accumulating both the sum and product of digits.
  • To avoid an explosion of state when accumulating the product, a key optimization is to use a flag (“zeroFound”) when a zero is encountered, as then the product becomes 0 and the condition is automatically met.
  • The overall answer is computed as countBeautiful(r) – countBeautiful(l – 1).

Space and Time Complexity

Time Complexity: O(digit_count × state_space) where state_space is determined by parameters (current position, tight flag, started flag, zeroFound flag, accumulated sum, and accumulated product). With maximum 10 digits and memoization, the number of unique states remains manageable. Space Complexity: O(number of states) due to memoization, which is feasible given the reduced state space from using flags and the limited number of digits.

Solution

We use a digit dynamic programming (DP) approach to count numbers up to a given limit which satisfy the “beautiful” property. The state in our recursive DP includes: • pos: current digit index in the number’s digit list. • tight: indicates whether the current prefix exactly matches the prefix of the limit (controls whether we can choose any digit or only up to a limit). • started: indicates whether we have begun the number (to handle leading zeros). • zeroFound: a flag to mark if we have already encountered a digit ‘0’ (in which case the product becomes 0). • s: the accumulated sum of digits. • p: the accumulated product of digits (if no zero has been encountered).

When we reach the end of the digits, if a number has been started then: • If zeroFound is true, the product is 0 and the condition holds. • Otherwise, we check if p % s == 0.

We then compute the answer for r and subtract the answer for (l – 1) so that only the numbers in [l, r] are counted.

The implementations in Python, JavaScript, C++ and Java all use this recursive DP (with memoization) approach along with standard digit DP techniques.

Code Solutions

# Python solution using recursion with memoization

def count_beautiful(n):
    # Convert integer n to a list of its digits
    digits = list(map(int, str(n)))
    N = len(digits)
    
    from functools import lru_cache
    @lru_cache(maxsize=None)
    def dp(pos, tight, started, zeroFound, s, p):
        # When we processed all digits
        if pos == N:
            # If no digits have been chosen, skip (number "0" is not counted)
            if not started:
                return 0
            # If a zero was encountered (or product is 0) then condition holds automatically
            if zeroFound:
                return 1
            # Otherwise check the divisibility condition: product % sum == 0
            return 1 if (s > 0 and p % s == 0) else 0
        
        res = 0
        limit = digits[pos] if tight else 9
        # Loop through all possible next digits
        for d in range(0, limit + 1):
            new_tight = tight and (d == limit)
            # If number has not started, we can choose to continue skipping leading zeros
            if not started:
                if d == 0:
                    # Still not starting the number
                    res += dp(pos + 1, new_tight, False, False, 0, 1)
                else:
                    # Start the number with digit d
                    # Since d != 0, zeroFound remains False.
                    res += dp(pos + 1, new_tight, True, False, d, d)
            else:
                # Already started the number
                new_s = s + d
                if zeroFound:
                    # Once we have a zero, product remains 0 irrespective of future digits
                    res += dp(pos + 1, new_tight, True, True, new_s, 0)
                else:
                    if d == 0:
                        # Encounter a zero; product becomes 0 and we mark zeroFound flag
                        res += dp(pos + 1, new_tight, True, True, new_s, 0)
                    else:
                        new_p = p * d
                        res += dp(pos + 1, new_tight, True, False, new_s, new_p)
        return res

    return dp(0, True, False, False, 0, 1)

def count_beautiful_in_range(l, r):
    return count_beautiful(r) - count_beautiful(l - 1)

# Example usage:
if __name__ == "__main__":
    l = 10
    r = 20
    print(count_beautiful_in_range(l, r))  # Expected output: 2
← Back to All Questions