Is Count Beautiful Numbers easy or hard?

Count Beautiful Numbers is categorized as a Hard problem. The difficulty comes from modeling the digit constraints correctly in a DP state and implementing a memoized digit DP that handles large numeric ranges efficiently.

Count Beautiful Numbers Python/Java solution

Python, Java, C++, and Go implementations follow the same idea: implement a recursive digit DP with memoization. The function tracks the current digit index, tight constraint, and digit-related state values, then iterates through valid digits and accumulates counts.

How to solve Count Beautiful Numbers in O(d * state)?

Model the number construction as a digit DP problem. Process digits from most significant to least significant, maintain a state containing the current index, a tight flag for the bound, and the required digit metrics. Use memoization when the prefix is not tight to reuse previously computed states.

What is the best approach for Count Beautiful Numbers?

The optimal approach is Digit Dynamic Programming (Digit DP). It constructs numbers digit by digit while tracking constraints in a DP state such as index, tight bound, and accumulated digit properties. This avoids iterating through every number in the range and reduces the complexity to roughly O(d * state * 10).

Is Count Beautiful Numbers asked at Google/Amazon/Meta?

Digit DP problems similar to Count Beautiful Numbers appear in interviews at companies like Google, Amazon, and Meta. These companies frequently test range counting problems with digit constraints because they evaluate dynamic programming and state modeling skills.

What data structure is used in Count Beautiful Numbers?

The solution primarily uses dynamic programming with memoization, typically implemented with arrays or hash maps to cache states. Recursion or iterative DP is used to explore digit transitions while respecting the upper bound constraint.

What is the time complexity of Count Beautiful Numbers?

The optimized solution using Digit DP runs in O(d * state * 10) time, where d is the number of digits in the upper bound and state represents tracked digit properties in the DP. Space complexity is O(d * state) due to memoization of DP states.

Description Hints 1 Video 1:11:57

3490. Count Beautiful Numbers

Hard24.5% acceptance1 company

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 < 10⁹

Asked at 1 company

Google

Topics

Dynamic Programming

Hints open one at a time

Hint 1

Use digit dynamic programming.

LanguageLoading editor…

1class Solution:
2    def beautifulNumbers(self, l: int, r: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

10
20

Input

1
15

Your code is saved on this device.