LeetCode 3869 - Count Fancy Numbers in a Range

We are given two integers l and r, and we must count how many integers in the inclusive range [l, r] are fancy. The definition of a fancy number is based on the concept of a good number. A number is good if its digits form a strictly monotone sequence.

leetcodehardmathdynamic-programming

LeetCode Problem 3869

Difficulty: 🔴 Hard
Topics: Math, Dynamic Programming

Solution

LeetCode 3869 - Count Fancy Numbers in a Range

Problem Understanding

We are given two integers l and r, and we must count how many integers in the inclusive range [l, r] are fancy.

The definition of a fancy number is based on the concept of a good number.

A number is good if its digits form a strictly monotone sequence. This means that the digits are either:

  • Strictly increasing, where every digit is larger than the previous digit.
  • Strictly decreasing, where every digit is smaller than the previous digit.

Additionally, every single digit number is automatically considered good.

A number is fancy if either:

  1. The number itself is good.
  2. The sum of its digits is good.

For example:

  • 1234 is good because digits are strictly increasing.
  • 4321 is good because digits are strictly decreasing.
  • 1223 is not good because the sequence is not strictly monotone.
  • 12340 is not good, but its digit sum is 10, and 10 has digits [1,0], which are strictly decreasing. Therefore 12340 is fancy.

The constraint

1 <= l <= r <= 10^15

is extremely important.

The range can contain up to one quadrillion numbers, making any approach that iterates through every value impossible. We must count valid numbers mathematically rather than enumerate them.

Since 10^15 contains at most 16 decimal digits, this strongly suggests a digit DP solution. Digit DP allows us to count numbers satisfying digit-based properties up to a bound in roughly O(number_of_digits × state_space) time.

Important edge cases include:

  • Single digit numbers, which are always good.
  • Numbers containing repeated adjacent digits, which immediately break strict monotonicity.
  • Numbers whose digit sum is good even though the number itself is not.
  • Very large values close to 10^15.
  • Avoiding double counting numbers that are both good and whose digit sum is also good.

Approaches

Brute Force

The most direct solution is to iterate through every integer in [l, r].

For each number:

  1. Check whether its digits are strictly increasing.
  2. Check whether its digits are strictly decreasing.
  3. If neither is true, compute its digit sum.
  4. Check whether the digit sum is good.
  5. Count the number if either condition holds.

This approach is obviously correct because it directly implements the definition.

Unfortunately, it is completely infeasible.

The range may contain up to:

10^15 numbers

and even a constant amount of work per number would take far beyond practical limits.

Key Insight

The crucial observation is that the property depends only on digits.

Instead of examining every number individually, we count:

fancy numbers ≤ X

and then compute:

answer = F(r) - F(l - 1)

This is a standard digit-DP range counting pattern.

A number is fancy when:

(number is good)
OR
(digit_sum(number) is good)

Using inclusion-exclusion:

fancy
=
good_numbers
+
numbers_with_good_digit_sum
-
numbers_satisfying_both

Therefore we need three counting functions:

A(X) = count(good numbers ≤ X)

B(X) = count(numbers ≤ X whose digit sum is good)

C(X) = count(numbers ≤ X that are good and whose digit sum is good)

Then:

F(X) = A(X) + B(X) - C(X)

The key observation that makes this tractable is that:

  • Maximum digit count is only 16.
  • Maximum digit sum is only:
16 × 9 = 144

Therefore digit-sum states are tiny.

The monotonicity state can also be represented compactly with digit DP.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O((r-l+1) · 16) O(1) Checks every number individually
Optimal Digit DP O(16 × state space) O(state space) Counts valid numbers without enumeration

Algorithm Walkthrough

Precomputation

Before running digit DP, precompute all good digit sums.

Since every number up to 10^15 has at most 16 digits:

maximum digit sum = 144

For every value 0...144, determine whether its decimal representation is good.

Store the result in:

good_sum[s]

Counting Good Numbers

We build a digit DP that processes digits from left to right.

The state stores:

  1. Current position.
  2. Whether we are still tight to the upper bound.
  3. Whether a non-leading digit has started.
  4. Previous digit.
  5. Current trend:
  • unknown
  • increasing
  • decreasing

Whenever a new digit is chosen:

  • If no previous digit exists, simply record it.
  • Otherwise compare against the previous digit.
  • Equal digits are forbidden.
  • Once a trend is established, future digits must continue following it.

At the end of the number, every formed number is good.

Counting Numbers With Good Digit Sum

Another digit DP tracks:

  1. Position.
  2. Current digit sum.
  3. Tight flag.

At the end:

good_sum[current_sum]

determines whether the constructed number contributes.

Counting Numbers Satisfying Both Conditions

Combine both ideas into a single DP.

Track:

  1. Position.
  2. Digit sum.
  3. Previous digit.
  4. Monotonic trend.
  5. Started flag.
  6. Tight flag.

At the terminal state:

good_sum[digit_sum]

must be true, and the digit sequence must also satisfy the monotonic condition.

Inclusion-Exclusion

For any upper bound X:

  1. Compute A(X).
  2. Compute B(X).
  3. Compute C(X).
  4. Return:
A(X) + B(X) - C(X)

Finally:

answer = F(r) - F(l-1)

Why it Works

Digit DP enumerates every valid number up to a bound exactly once. The monotonicity state precisely captures whether the currently constructed prefix can still become a strictly increasing or strictly decreasing sequence. The digit-sum state captures the exact sum of digits. Since inclusion-exclusion counts the union of two sets by adding both counts and subtracting their intersection, the final result counts every fancy number exactly once.

Python Solution

from functools import lru_cache
from typing import List

class Solution:
    def countFancy(self, l: int, r: int) -> int:
        MAX_SUM = 16 * 9

        def is_good_value(x: int) -> bool:
            s = str(x)
            if len(s) == 1:
                return True

            inc = True
            dec = True

            for i in range(1, len(s)):
                if s[i] <= s[i - 1]:
                    inc = False
                if s[i] >= s[i - 1]:
                    dec = False

            return inc or dec

        good_sum = [False] * (MAX_SUM + 1)
        for s in range(MAX_SUM + 1):
            good_sum[s] = is_good_value(s)

        def count_up_to(n: int) -> int:
            if n <= 0:
                return 0

            digits = list(map(int, str(n)))
            m = len(digits)

            @lru_cache(None)
            def count_good(
                pos: int,
                tight: int,
                started: int,
                prev: int,
                trend: int,
            ) -> int:
                if pos == m:
                    return int(started)

                limit = digits[pos] if tight else 9
                ans = 0

                for d in range(limit + 1):
                    ntight = tight and d == limit

                    if not started and d == 0:
                        ans += count_good(
                            pos + 1,
                            ntight,
                            0,
                            10,
                            0,
                        )
                        continue

                    if not started:
                        ans += count_good(
                            pos + 1,
                            ntight,
                            1,
                            d,
                            0,
                        )
                        continue

                    if d == prev:
                        continue

                    if trend == 0:
                        ntrend = 1 if d > prev else 2
                        ans += count_good(
                            pos + 1,
                            ntight,
                            1,
                            d,
                            ntrend,
                        )
                    elif trend == 1:
                        if d > prev:
                            ans += count_good(
                                pos + 1,
                                ntight,
                                1,
                                d,
                                1,
                            )
                    else:
                        if d < prev:
                            ans += count_good(
                                pos + 1,
                                ntight,
                                1,
                                d,
                                2,
                            )

                return ans

            @lru_cache(None)
            def count_sum(
                pos: int,
                tight: int,
                digit_sum: int,
            ) -> int:
                if pos == m:
                    return int(good_sum[digit_sum])

                limit = digits[pos] if tight else 9
                ans = 0

                for d in range(limit + 1):
                    ans += count_sum(
                        pos + 1,
                        tight and d == limit,
                        digit_sum + d,
                    )

                return ans

            @lru_cache(None)
            def count_both(
                pos: int,
                tight: int,
                started: int,
                prev: int,
                trend: int,
                digit_sum: int,
            ) -> int:
                if pos == m:
                    return int(started and good_sum[digit_sum])

                limit = digits[pos] if tight else 9
                ans = 0

                for d in range(limit + 1):
                    ntight = tight and d == limit

                    if not started and d == 0:
                        ans += count_both(
                            pos + 1,
                            ntight,
                            0,
                            10,
                            0,
                            digit_sum,
                        )
                        continue

                    if not started:
                        ans += count_both(
                            pos + 1,
                            ntight,
                            1,
                            d,
                            0,
                            digit_sum + d,
                        )
                        continue

                    if d == prev:
                        continue

                    if trend == 0:
                        ntrend = 1 if d > prev else 2
                        ans += count_both(
                            pos + 1,
                            ntight,
                            1,
                            d,
                            ntrend,
                            digit_sum + d,
                        )
                    elif trend == 1:
                        if d > prev:
                            ans += count_both(
                                pos + 1,
                                ntight,
                                1,
                                d,
                                1,
                                digit_sum + d,
                            )
                    else:
                        if d < prev:
                            ans += count_both(
                                pos + 1,
                                ntight,
                                1,
                                d,
                                2,
                                digit_sum + d,
                            )

                return ans

            a = count_good(0, 1, 0, 10, 0)
            b = count_sum(0, 1, 0)
            c = count_both(0, 1, 0, 10, 0, 0)

            return a + b - c

        return count_up_to(r) - count_up_to(l - 1)

The implementation follows the inclusion-exclusion formula directly.

The helper is_good_value determines whether a digit sequence is strictly increasing or strictly decreasing. Since digit sums never exceed 144, all good digit sums are precomputed once.

count_good performs a digit DP that counts numbers whose digits are strictly monotone.

count_sum performs a digit DP that only tracks digit sums and checks whether the final sum belongs to the precomputed good set.

count_both merges both state spaces and counts numbers satisfying both properties simultaneously.

The final result for a bound n is:

good + good_digit_sum - intersection

and the requested range answer is obtained using:

F(r) - F(l-1)

Go Solution

package main

func countFancy(l int64, r int64) int64 {
	const maxSum = 16 * 9

	goodSum := make([]bool, maxSum+1)

	isGoodValue := func(x int) bool {
		s := []byte{}
		if x == 0 {
			s = append(s, '0')
		} else {
			tmp := x
			digits := []byte{}
			for tmp > 0 {
				digits = append(digits, byte(tmp%10)+'0')
				tmp /= 10
			}
			for i := len(digits) - 1; i >= 0; i-- {
				s = append(s, digits[i])
			}
		}

		if len(s) == 1 {
			return true
		}

		inc := true
		dec := true

		for i := 1; i < len(s); i++ {
			if s[i] <= s[i-1] {
				inc = false
			}
			if s[i] >= s[i-1] {
				dec = false
			}
		}

		return inc || dec
	}

	for i := 0; i <= maxSum; i++ {
		goodSum[i] = isGoodValue(i)
	}

	var countUpTo func(int64) int64

	countUpTo = func(n int64) int64 {
		if n <= 0 {
			return 0
		}

		digits := []int{}
		tmp := n

		for tmp > 0 {
			digits = append(digits, int(tmp%10))
			tmp /= 10
		}

		for i, j := 0, len(digits)-1; i < j; i, j = i+1, j-1 {
			digits[i], digits[j] = digits[j], digits[i]
		}

		type State struct {
			pos, tight, started, prev, trend, sum int
		}

		memoGood := map[[5]int]int64{}
		var dfsGood func(int, int, int, int, int) int64

		dfsGood = func(pos, tight, started, prev, trend int) int64 {
			if pos == len(digits) {
				if started == 1 {
					return 1
				}
				return 0
			}

			key := [5]int{pos, tight, started, prev, trend}
			if v, ok := memoGood[key]; ok {
				return v
			}

			limit := 9
			if tight == 1 {
				limit = digits[pos]
			}

			var ans int64

			for d := 0; d <= limit; d++ {
				ntight := 0
				if tight == 1 && d == limit {
					ntight = 1
				}

				if started == 0 && d == 0 {
					ans += dfsGood(pos+1, ntight, 0, 10, 0)
					continue
				}

				if started == 0 {
					ans += dfsGood(pos+1, ntight, 1, d, 0)
					continue
				}

				if d == prev {
					continue
				}

				if trend == 0 {
					ntrend := 1
					if d < prev {
						ntrend = 2
					}
					ans += dfsGood(pos+1, ntight, 1, d, ntrend)
				} else if trend == 1 {
					if d > prev {
						ans += dfsGood(pos+1, ntight, 1, d, 1)
					}
				} else {
					if d < prev {
						ans += dfsGood(pos+1, ntight, 1, d, 2)
					}
				}
			}

			memoGood[key] = ans
			return ans
		}

		memoSum := map[[3]int]int64{}
		var dfsSum func(int, int, int) int64

		dfsSum = func(pos, tight, sum int) int64 {
			if pos == len(digits) {
				if goodSum[sum] {
					return 1
				}
				return 0
			}

			key := [3]int{pos, tight, sum}
			if v, ok := memoSum[key]; ok {
				return v
			}

			limit := 9
			if tight == 1 {
				limit = digits[pos]
			}

			var ans int64

			for d := 0; d <= limit; d++ {
				ntight := 0
				if tight == 1 && d == limit {
					ntight = 1
				}
				ans += dfsSum(pos+1, ntight, sum+d)
			}

			memoSum[key] = ans
			return ans
		}

		memoBoth := map[State]int64{}
		var dfsBoth func(int, int, int, int, int, int) int64

		dfsBoth = func(pos, tight, started, prev, trend, sum int) int64 {
			if pos == len(digits) {
				if started == 1 && goodSum[sum] {
					return 1
				}
				return 0
			}

			key := State{pos, tight, started, prev, trend, sum}
			if v, ok := memoBoth[key]; ok {
				return v
			}

			limit := 9
			if tight == 1 {
				limit = digits[pos]
			}

			var ans int64

			for d := 0; d <= limit; d++ {
				ntight := 0
				if tight == 1 && d == limit {
					ntight = 1
				}

				if started == 0 && d == 0 {
					ans += dfsBoth(pos+1, ntight, 0, 10, 0, sum)
					continue
				}

				if started == 0 {
					ans += dfsBoth(pos+1, ntight, 1, d, 0, sum+d)
					continue
				}

				if d == prev {
					continue
				}

				if trend == 0 {
					ntrend := 1
					if d < prev {
						ntrend = 2
					}
					ans += dfsBoth(pos+1, ntight, 1, d, ntrend, sum+d)
				} else if trend == 1 {
					if d > prev {
						ans += dfsBoth(pos+1, ntight, 1, d, 1, sum+d)
					}
				} else {
					if d < prev {
						ans += dfsBoth(pos+1, ntight, 1, d, 2, sum+d)
					}
				}
			}

			memoBoth[key] = ans
			return ans
		}

		a := dfsGood(0, 1, 0, 10, 0)
		b := dfsSum(0, 1, 0)
		c := dfsBoth(0, 1, 0, 10, 0, 0)

		return a + b - c
	}

	return countUpTo(r) - countUpTo(l-1)
}

The Go version mirrors the Python logic exactly. Maps are used instead of lru_cache, and all counts use int64 to safely accommodate values up to the size of the search space.

Worked Examples

Example 1

l = 8
r = 10

Numbers in range:

Number Good? Digit Sum Sum Good? Fancy?
8 Yes 8 Yes Yes
9 Yes 9 Yes Yes
10 Yes (1>0) 1 Yes Yes

Result:

3

Example 2

l = 12340
r = 12341

For 12340:

Property Value
Digits 1 2 3 4 0
Good? No
Digit Sum 10
Is 10 Good? Yes
Fancy? Yes

For 12341:

Property Value
Digits 1 2 3 4 1
Good? No
Digit Sum 11
Is 11 Good? No
Fancy? No

Answer:

1

Example 3

l = 123456788
r = 123456788
Property Value
Digits 1 2 3 4 5 6 7 8 8
Good? No
Digit Sum 44
Is 44 Good? No
Fancy? No

Answer:

0

Complexity Analysis

Measure Complexity Explanation
Time O(D × S) Digit DP visits each state once
Space O(D × S) Memoization tables store DP states

Where:

  • D ≤ 16 is the number of digits.
  • S is the combined state space involving digit sum, trend, previous digit, and tight status.

Since digit sum never exceeds 144, the total state space remains small, making the solution easily fast enough.

Test Cases

sol = Solution()

assert sol.countFancy(8, 10) == 3          # example 1
assert sol.countFancy(12340, 12341) == 1   # example 2
assert sol.countFancy(123456788, 123456788) == 0  # example 3

assert sol.countFancy(1, 9) == 9           # all single digits

assert sol.countFancy(10, 10) == 1         # strictly decreasing
assert sol.countFancy(12, 12) == 1         # strictly increasing
assert sol.countFancy(11, 11) == 0         # repeated digits

assert sol.countFancy(21, 21) == 1         # decreasing
assert sol.countFancy(123, 123) == 1       # increasing
assert sol.countFancy(321, 321) == 1       # decreasing

assert sol.countFancy(100, 100) == 1       # digit sum = 1

assert sol.countFancy(98, 102) >= 0        # range crossing digit length

assert sol.countFancy(999999999999999, 999999999999999) >= 0  # upper bound stress

assert sol.countFancy(1, 1000) >= sol.countFancy(1, 100)      # monotonic range growth

Test Summary

Test Why
(8,10) Official example 1
(12340,12341) Official example 2
(123456788,123456788) Official example 3
(1,9) Single digit numbers
(10,10) Strictly decreasing two-digit number
(12,12) Strictly increasing two-digit number
(11,11) Repeated digit rejection
(21,21) Basic decreasing sequence
(123,123) Basic increasing sequence
(321,321) Multi-digit decreasing sequence
(100,100) Not good itself, good digit sum
(98,102) Crosses power of ten boundary
Large upper bound Maximum constraint stress
Nested ranges Consistency check

Edge Cases

Single-Digit Numbers

Every single-digit number is automatically good. A common bug is treating monotonicity as requiring at least two digits and accidentally rejecting values from 1 to 9. The implementation explicitly treats all one-digit numbers as good, both in the precomputation and in the digit-DP construction.

Repeated Digits

Strict monotonicity does not allow equality. Numbers such as 11, 122, and 4331 are not good. During DP transitions, any choice where current_digit == previous_digit is immediately discarded, ensuring strictness is enforced.

Numbers That Are Not Good but Have Good Digit Sums

Values such as 12340 are the main reason the problem is interesting. The number itself is not monotone, but its digit sum is good. The inclusion-exclusion formulation correctly counts such numbers through the digit-sum DP even when they are excluded by the monotonic DP.

Large Values Near 10^15

A brute-force solution would be impossible near the upper bound. The digit DP only depends on the number of digits and the digit-sum state space, both of which remain tiny even at 10^15. This guarantees efficient performance across the entire input range.

Numbers Satisfying Both Conditions

A number such as 123 is good, and its digit sum 6 is also good. Without inclusion-exclusion it would be counted twice. The intersection DP computes exactly those numbers satisfying both properties, and subtracting that count removes all duplicates.