Count Beautiful Numbers - Practice Coding Problems

Count Beautiful Numbers - Problem

Dynamic Programming Hard

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: For number 144, digit product = 1×4×4 = 16, digit sum = 1+4+4 = 9. Since 16 % 9 ≠ 0, 144 is not beautiful.

Input & Output

Example 1 — Small Range

$ Input: l = 1, r = 10

› Output: 1

💡 Note: Only number 1 is beautiful: digit product = 1, digit sum = 1, and 1 % 1 = 0. Numbers 2-10 don't satisfy the condition.

Example 2 — Including Zero Digits

$ Input: l = 10, r = 20

› Output: 1

💡 Note: Number 10: product = 1×0 = 0, sum = 1+0 = 1, and 0 % 1 = 0, so it's beautiful. Other numbers in range don't satisfy the condition.

Example 3 — Larger Range

$ Input: l = 1, r = 100

› Output: 4

💡 Note: Beautiful numbers are: 1 (1%1=0), 10 (0%1=0), 20 (0%2=0), 100 (0%1=0). All have zero in product making them divisible by their digit sum.

Constraints

1 ≤ l ≤ r ≤ 10¹²
Both l and r are positive integers

Visualization

Tap to expand

Understanding the Visualization

Input Range

Given range [l, r] to check for beautiful numbers

Check Beautiful

For each number: product of digits divisible by sum of digits

Count Result

Return total count of beautiful numbers in range

Key Takeaway

🎯 Key Insight: Numbers with zero digits are automatically beautiful since their product is 0, and 0 is divisible by any non-zero sum

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is recognizing that any number containing a zero digit will have a product of zero, making it automatically beautiful since 0 % sum = 0. For numbers without zeros, we need to check if the product of digits is divisible by their sum. The optimal approach uses digit DP with memoization to efficiently count beautiful numbers without checking each one individually. Time: O(log₁₀(r) × states), Space: O(states).

Common Approaches

Approach	Time	Space	Notes
✓ Digit DP with Memoization	O(log₁₀(r) × 9¹⁰ × sum_limit × product_limit)	O(log₁₀(r) × sum_limit × product_limit)	Use digit-based dynamic programming with memoization to avoid redundant calculations
Brute Force	O((r-l) × log₁₀(r))	O(1)	Check each number individually by calculating digit product and sum

Digit DP with Memoization — Algorithm Steps

Step 1: Use recursive function with position, tight constraint, product and sum
Step 2: Memoize states to avoid recalculating same digit patterns
Step 3: Build numbers digit by digit and count beautiful ones

Visualization

Tap to expand

Step-by-Step Walkthrough

Digit Position

Build number digit by digit from left to right

Track State

Maintain product, sum, and constraint flags

Memoize

Cache results for identical states

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_STATES 1000000
struct State {
    int pos, tight, started, prod, sum;
    int result;
    int used;
} states[MAX_STATES];

int stateCount = 0;

int findState(int pos, int tight, int started, int prod, int sum) {
    for (int i = 0; i < stateCount; i++) {
        if (states[i].pos == pos && states[i].tight == tight && 
            states[i].started == started && states[i].prod == prod && states[i].sum == sum) {
            return i;
        }
    }
    return -1;
}

int dp(const char* numStr, int pos, int tight, int started, int prod, int sum, int len) {
    if (pos == len) {
        return (started && sum > 0 && prod % sum == 0) ? 1 : 0;
    }
    
    int stateIdx = findState(pos, tight, started, prod, sum);
    if (stateIdx != -1 && states[stateIdx].used) {
        return states[stateIdx].result;
    }
    
    int limit = tight ? (numStr[pos] - '0') : 9;
    int result = 0;
    
    for (int digit = 0; digit <= limit; digit++) {
        int newTight = tight && (digit == limit);
        int newStarted = started || (digit > 0);
        int newProd = newStarted ? prod * digit : 1;
        int newSum = newStarted ? sum + digit : 0;
        
        if (newStarted && (newProd > 100000 || newSum > 100)) {
            continue;
        }
        
        result += dp(numStr, pos + 1, newTight, newStarted, newProd, newSum, len);
    }
    
    if (stateCount < MAX_STATES) {
        states[stateCount].pos = pos;
        states[stateCount].tight = tight;
        states[stateCount].started = started;
        states[stateCount].prod = prod;
        states[stateCount].sum = sum;
        states[stateCount].result = result;
        states[stateCount].used = 1;
        stateCount++;
    }
    
    return result;
}

int countBeautiful(int num) {
    char numStr[20];
    sprintf(numStr, "%d", num);
    stateCount = 0;
    return dp(numStr, 0, 1, 0, 1, 0, strlen(numStr));
}

int solution(int l, int r) {
    return countBeautiful(r) - countBeautiful(l - 1);
}

int main() {
    int l, r;
    scanf("%d", &l);
    scanf("%d", &r);
    
    int result = solution(l, r);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log₁₀(r) × 9¹⁰ × sum_limit × product_limit)

Each digit position with all possible product/sum combinations, but memoized

⚡ Linearithmic

Space Complexity

O(log₁₀(r) × sum_limit × product_limit)

Memoization table stores states for position, sum, and product combinations

✓ Linear Space

25.0K Views

Medium Frequency

~35 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Digit DP with Memoization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler