Count Beautiful Numbers - Solution & Explanation

Problem Overview: You need to count how many integers within a given range satisfy a specific set of digit-based conditions that define a beautiful number. The constraints depend on properties of the digits themselves, so checking each number independently quickly becomes too slow for large ranges.

Approach 1: Brute Force Enumeration (O(n * d) time, O(1) space)

The most direct idea is to iterate through every number in the range and check whether it satisfies the beauty condition. For each number, extract its digits and compute the required properties (such as digit sums, divisibility checks, or other digit relationships). This approach is easy to implement and helps validate the rules of the problem. However, when the range grows to large values (for example up to 10¹⁸), iterating through every candidate becomes infeasible. Time complexity is O(n * d), where d is the number of digits.

Approach 2: Digit Dynamic Programming (Digit DP) (O(d * state * 10) time, O(d * state) space)

The efficient solution treats the number as a sequence of digits and builds it from left to right using dynamic programming. Instead of iterating through every number, you count valid constructions digit by digit. The DP state typically includes the current digit index, whether the prefix is still tight with the upper bound, and additional values needed to verify the beauty condition (for example accumulated digit metrics or remainders). At each position, you try digits 0–9, update the state, and recursively continue.

Memoization stores results for states where the prefix is no longer restricted, which dramatically reduces repeated work. This converts an exponential search over numbers into a manageable state exploration proportional to the number of digits. Digit DP is a common pattern in range-counting problems that involve digit rules and is closely related to techniques in dynamic programming and combinatorial state transitions.

Recommended for interviews: Interviewers expect the Digit DP approach. Brute force demonstrates you understand the definition of a beautiful number, but it fails under large constraints. Digit DP shows you can model number construction as a state machine and cache overlapping subproblems—an essential technique for advanced dynamic programming problems involving digit constraints.