Count Fancy Numbers in a Range solution and explanation
3 more videos on this problem
Q4. Count Fancy Numbers in a Range || Digit Dynamic Programming || Leetcode Biweekly 178 || Watch2X🚀Rajan Keshari ( CSE - IIT Dhanbad ) · 22:37 · 969 views
Leetcode 3869 | Count Fancy Numbers in a Range | Very easy Explanation | Digit DPCodeWithMeGuys · 31:49 · 390 views
LeetCode Problem 3869 | Count Fancy Numbers in a RangeRepovive TV · 41:04 · 207 views
3869. Count Fancy Numbers in a Range (Leetcode Hard)Programming Live with Larry · 1:26:51 · 180 views
The problem
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.
Solution
We first define a function check(s) to determine whether an integer s is a good number. For s < 100, we only need to check whether s is a multiple of 11; if so, s is not a good number. For s geq 100, we need to check whether the digits of s form a strictly monotonic sequence, i.e., strictly increasing or strictly decreasing. Since the range of digit sums is small, when the digit sum exceeds 100, we only need to check the relationship between the tens digit and the units digit of the digit sum.
Next, we use digit DP to count the number of fancy numbers in the interval [l, r]. We define a recursive function dfs(pos, s, prev, st, lim), where:
- Integer
posrepresents the current digit position being processed, from high to low. - Integer
srepresents the current digit sum. - Integer
prevrepresents the value of the previous digit. - Integer
strepresents the state of the current digit sequence, where state0means there is at most one digit so far, state1means strictly increasing, state2means strictly decreasing, and state3means not strictly monotonic. - Boolean
limindicates whether the current digit is constrained by the upper bound.
In the recursive function, if pos exceeds the length of the number, we have finished processing a number. If the state st is not equal to 3, the number is a good number and we return 1; otherwise, we call check(s) to determine whether the digit sum is a good number, returning 1 if it is, and 0 otherwise.
During the recursion, we enumerate the range of the current digit: if lim is true, the range is [0, num[pos]]; otherwise, it is [0, 9]. For each value, we update the state st and recursively call dfs to process the next digit.
Finally, we compute the count of fancy numbers in [0, r] and [0, l-1] separately, and the answer is their difference.
The time complexity is O(D^3 times log^2 r) and the space complexity is O(D^2 times log^2 r), where D = 10.
class Solution:
def countFancy(self, l: int, r: int) -> int:
def check(s: int) -> bool:
if s < 100:
return s % 11 != 0
return 1 < s // 10 % 10 < s % 10
@cache
def dfs(pos: int, s: int, prev: int, st: int, lim: bool) -> int:
if pos >= len(num):
if st != 3:
return 1
return int(check(s))
up = int(num[pos]) if lim else 9
res = 0
for i in range(up + 1):
nxt_st = st
if st == 0:
if prev == 0:
nxt_st = 0
elif i > prev:
nxt_st = 1
elif i < prev:
nxt_st = 2
else:
nxt_st = 3
elif st == 1:
if i > prev:
nxt_st = 1
else:
nxt_st = 3
elif st == 2:
if i < prev:
nxt_st = 2
else:
nxt_st = 3
else:
nxt_st = 3
res += dfs(pos + 1, s + i, i, nxt_st, lim and i == up)
return res
num = str(l - 1)
a = dfs(0, 0, 0, 0, True)
dfs.cache_clear()
num = str(r)
b = dfs(0, 0, 0, 0, True)
return b - aclass Solution {
private String num;
private Long[][][][] f;
public long countFancy(long l, long r) {
num = String.valueOf(l - 1);
init();
long a = dfs(0, 0, 0, 0, true);
num = String.valueOf(r);
init();
long b = dfs(0, 0, 0, 0, true);
return b - a;
}
private void init() {
int n = num.length();
f = new Long[n][9 * n + 1][10][4];
}
private boolean check(int s) {
if (s < 100) {
return s % 11 != 0;
}
int mid = (s / 10) % 10;
int last = s % 10;
return mid > 1 && mid < last;
}
private long dfs(int pos, int s, int prev, int st, boolean lim) {
if (pos >= num.length()) {
if (st != 3) {
return 1;
}
return check(s) ? 1 : 0;
}
if (!lim && f[pos][s][prev][st] != null) {
return f[pos][s][prev][st];
}
int up = lim ? num.charAt(pos) - '0' : 9;
long res = 0;
for (int i = 0; i <= up; i++) {
int nxtSt = st;
if (st == 0) {
if (prev == 0) {
nxtSt = 0;
} else if (i > prev) {
nxtSt = 1;
} else if (i < prev) {
nxtSt = 2;
} else {
nxtSt = 3;
}
} else if (st == 1) {
if (i > prev) {
nxtSt = 1;
} else {
nxtSt = 3;
}
} else if (st == 2) {
if (i < prev) {
nxtSt = 2;
} else {
nxtSt = 3;
}
} else {
nxtSt = 3;
}
res += dfs(pos + 1, s + i, i, nxtSt, lim && i == up);
}
if (!lim) {
f[pos][s][prev][st] = res;
}
return res;
}
}class Solution {
public:
long long countFancy(long long l, long long r) {
auto check = [&](int s) -> bool {
if (s < 100) {
return s % 11 != 0;
}
int mid = (s / 10) % 10;
int last = s % 10;
return mid > 1 && mid < last;
};
string num = to_string(l - 1);
int n = num.size();
vector f(n, vector(9 * n + 1, vector(10, vector<long long>(4, -1))));
auto dfs = [&](this auto&& dfs, int pos, int s, int prev, int st, bool lim) -> long long {
if (pos >= n) {
if (st != 3) return 1;
return check(s) ? 1LL : 0LL;
}
if (!lim && f[pos][s][prev][st] != -1) {
return f[pos][s][prev][st];
}
int up = lim ? num[pos] - '0' : 9;
long long res = 0;
for (int i = 0; i <= up; i++) {
int nxtSt = st;
if (st == 0) {
if (prev == 0)
nxtSt = 0;
else if (i > prev)
nxtSt = 1;
else if (i < prev)
nxtSt = 2;
else
nxtSt = 3;
} else if (st == 1) {
if (i > prev)
nxtSt = 1;
else
nxtSt = 3;
} else if (st == 2) {
if (i < prev)
nxtSt = 2;
else
nxtSt = 3;
} else {
nxtSt = 3;
}
res += dfs(pos + 1, s + i, i, nxtSt, lim && i == up);
}
if (!lim) {
f[pos][s][prev][st] = res;
}
return res;
};
long long a = dfs(0, 0, 0, 0, true);
num = to_string(r);
n = num.size();
f.assign(n, vector(9 * n + 1, vector(10, vector<long long>(4, -1))));
long long b = dfs(0, 0, 0, 0, true);
return b - a;
}
};function countFancy(l: number, r: number): number {
const check = (s: number): boolean => {
if (s < 100) {
return s % 11 !== 0;
}
const mid = Math.floor(s / 10) % 10;
const last = s % 10;
return mid > 1 && mid < last;
};
let num: string;
let n: number;
let f: number[][][][];
const dfs = (pos: number, s: number, prev: number, st: number, lim: boolean): number => {
if (pos >= n) {
if (st !== 3) return 1;
return check(s) ? 1 : 0;
}
if (!lim && f[pos][s][prev][st] !== -1) {
return f[pos][s][prev][st];
}
const up = lim ? Number(num[pos]) : 9;
let res = 0;
for (let i = 0; i <= up; i++) {
let nxtSt = st;
if (st === 0) {
if (prev === 0) nxtSt = 0;
else if (i > prev) nxtSt = 1;
else if (i < prev) nxtSt = 2;
else nxtSt = 3;
} else if (st === 1) {
if (i > prev) nxtSt = 1;
else nxtSt = 3;
} else if (st === 2) {
if (i < prev) nxtSt = 2;
else nxtSt = 3;
} else {
nxtSt = 3;
}
res += dfs(pos + 1, s + i, i, nxtSt, lim && i === up);
}
if (!lim) {
f[pos][s][prev][st] = res;
}
return res;
};
const calc = (x: number): number => {
num = x.toString();
n = num.length;
f = Array.from({ length: n }, () =>
Array.from({ length: 9 * n + 1 }, () =>
Array.from({ length: 10 }, () => Array(4).fill(-1)),
),
);
return dfs(0, 0, 0, 0, true);
};
return calc(r) - calc(l - 1);
}func countFancy(l int64, r int64) int64 {
check := func(s int) bool {
if s < 100 {
return s%11 != 0
}
mid := (s / 10) % 10
last := s % 10
return mid > 1 && mid < last
}
var num string
var n int
var f [][][][]int64
var dfs func(pos, s, prev, st int, lim bool) int64
dfs = func(pos, s, prev, st int, lim bool) int64 {
if pos >= n {
if st != 3 {
return 1
}
if check(s) {
return 1
}
return 0
}
if !lim && f[pos][s][prev][st] != -1 {
return f[pos][s][prev][st]
}
up := 9
if lim {
up = int(num[pos] - '0')
}
var res int64 = 0
for i := 0; i <= up; i++ {
nxtSt := st
if st == 0 {
if prev == 0 {
nxtSt = 0
} else if i > prev {
nxtSt = 1
} else if i < prev {
nxtSt = 2
} else {
nxtSt = 3
}
} else if st == 1 {
if i > prev {
nxtSt = 1
} else {
nxtSt = 3
}
} else if st == 2 {
if i < prev {
nxtSt = 2
} else {
nxtSt = 3
}
} else {
nxtSt = 3
}
res += dfs(pos+1, s+i, i, nxtSt, lim && i == up)
}
if !lim {
f[pos][s][prev][st] = res
}
return res
}
calc := func(x int64) int64 {
num = strconv.FormatInt(x, 10)
n = len(num)
f = make([][][][]int64, n)
for i := 0; i < n; i++ {
f[i] = make([][][]int64, 9*n+1)
for j := 0; j <= 9*n; j++ {
f[i][j] = make([][]int64, 10)
for k := 0; k < 10; k++ {
f[i][j][k] = make([]int64, 4)
for t := 0; t < 4; t++ {
f[i][j][k][t] = -1
}
}
}
}
return dfs(0, 0, 0, 0, true)
}
return calc(r) - calc(l-1)
}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 |
Frequently asked questions
Is Count Fancy Numbers in a Range easy or hard?
Count Fancy Numbers in a Range is categorized as a Hard problem because it requires recognizing the Digit DP pattern. Understanding how to model the digit states and manage the tight bound is the main challenge.
Count Fancy Numbers in a Range Python/Java solution
Most implementations define a recursive digit DP function with parameters such as position, tight flag, and rule-specific state. Memoization stores intermediate results. The same logic translates directly across Python, Java, C++, Go, and TypeScript.
What is the best approach for Count Fancy Numbers in a Range?
Digit Dynamic Programming is the most efficient approach. Instead of iterating through every number, it builds valid numbers digit by digit while respecting the upper bound and the fancy-number constraints. This reduces the complexity to roughly O(d * states * 10), where d is the number of digits.
Is Count Fancy Numbers in a Range asked at Google/Amazon/Meta?
Digit DP problems that count numbers with digit constraints are common in interviews at companies like Google, Amazon, and Meta. Variants often involve counting numbers without repeated digits, limiting digit sums, or enforcing adjacency rules.
What data structure is used in Count Fancy Numbers in a Range?
The solution primarily uses recursion with memoization (a DP table or hash map) to store computed states. The digits of the bound are typically stored in an array or string to process them sequentially during the DP transitions.
What is the time complexity of Count Fancy Numbers in a Range?
The optimal Digit DP solution runs in O(d * states * 10) time, where d is the number of digits in the bound. Each DP state explores digits 0–9 while memoization avoids recomputation. Space complexity is O(d * states) for the DP cache.
How to solve Count Fancy Numbers in a Range in O(d * states * 10)?
Use a digit DP function that processes the number from the most significant digit to the least. Maintain state variables such as the current index, whether the prefix is tight with the bound, and any rule-specific properties required for a fancy number. Compute count(high) and subtract count(low − 1) to get the final answer.