Count Fancy Numbers in a Range - Video Solutions
Q4. Count Fancy Numbers in a Range || Digit Dynamic Programming || Leetcode Biweekly 178 || Watch2X🚀
Count Fancy Numbers in a Range - Video Solution
Watch 4 video solutions for Count Fancy Numbers in a Range, a hard level problem involving Math, Dynamic Programming. This walkthrough by Rajan Keshari ( CSE - IIT Dhanbad ) has 969 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given two integers l and r.
An integer is called good if its digits form a strictly monotone sequence, meaning the digits are strictly increasing or strictly decreasing. All single-digit integers are considered good.
An integer is called fancy if it is good, or if the sum of its digits is good.
Return an integer representing the number of fancy integers in the range [l, r] (inclusive).
A sequence is said to be strictly increasing if each element is strictly greater than its previous one (if exists).
A sequence is said to be strictly decreasing if each element is strictly less than its previous one (if exists).
Example 1:
Input: l = 8, r = 10
Output: 3
Explanation:
- 8 and 9 are single-digit integers, so they are good and therefore fancy.
- 10 has digits
[1, 0], which form a strictly decreasing sequence, so 10 is good and thus fancy.
Therefore, the answer is 3.
Example 2:
Input: l = 12340, r = 12341
Output: 1
Explanation:
- 12340
- 12340 is not good because
[1, 2, 3, 4, 0]is not strictly monotone. - The digit sum is
1 + 2 + 3 + 4 + 0 = 10. - 10 is good as it has digits
[1, 0], which is strictly decreasing. Therefore, 12340 is fancy.
- 12340 is not good because
- 12341
- 12341 is not good because
[1, 2, 3, 4, 1]is not strictly monotone. - The digit sum is
1 + 2 + 3 + 4 + 1 = 11. - 11 is not good as it has digits
[1, 1], which is not strictly monotone. Therefore, 12341 is not fancy.
- 12341 is not good because
Therefore, the answer is 1.
Example 3:
Input: l = 123456788, r = 123456788
Output: 0
Explanation:
- 123456788 is not good because its digits are not strictly monotone.
- The digit sum is
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 8 = 44. - 44 is not good as it has digits
[4, 4], which is not strictly monotone. Therefore, 123456788 is not fancy.
Therefore, the answer is 0.
Constraints:
1 <= l <= r <= 1015
Approach Overview
Problem Overview: Given two integers representing a range [low, high], count how many numbers inside the range satisfy the definition of a fancy number. The constraint is defined by rules on the digits of the number, which makes brute force checking impractical for large ranges.
Approach 1: Brute Force Enumeration (O(n * d) time, O(1) space)
The most direct method iterates through every number from low to high. For each value, extract its digits and verify whether it satisfies the fancy number conditions. This typically involves repeated division/modulo operations to inspect digits and apply the rule. The approach is easy to implement but quickly becomes infeasible when the range spans millions or billions of numbers.
Approach 2: Digit Dynamic Programming (O(d * states * 10) time, O(d * states) space)
A much more scalable method uses Digit DP. Instead of checking each number individually, treat the number as a sequence of digits and build valid numbers digit by digit. Convert the upper bound into a digit array and recursively construct numbers while tracking states such as current position, whether the prefix is still constrained by the bound (tight flag), and other rule-specific states related to the fancy condition. Memoization stores results for repeated states, avoiding recomputation.
To count numbers in a range, compute count(high) and subtract count(low - 1). Each DP state explores digits 0–9 and transitions based on the rule that defines a fancy number. Because the number of digits d is small (usually ≤ 19 for 64-bit integers), the state space remains manageable.
This pattern appears frequently in problems involving digit constraints such as limiting digit frequency, preventing adjacent matches, or enforcing divisibility properties. If you want to get comfortable with this technique, review problems under dynamic programming and math. Digit-based counting problems often combine both concepts.
Recommended for interviews: Interviewers expect the Digit DP approach. Starting with brute force shows you understand the property being checked, but recognizing that the range can be huge and switching to a digit-level dynamic programming solution demonstrates stronger algorithmic thinking.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n * d) | O(1) | Very small ranges where direct checking is acceptable |
| Digit Dynamic Programming | O(d * states * 10) | O(d * states) | Large ranges with digit-based constraints |