Count fancy numbers in a range

Math Dynamic Programming

25.4% acceptance

Mar 31, 2026

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).

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_fancy(l: i64, r: i64) -> i64 {
    Self::count_up_to(r) - Self::count_up_to(l - 1)
  }

  fn is_good(n: i64) -> bool {
    if n < 10 {
      return true;
    }
    let mut digits = Vec::new();
    let mut x = n;
    while x > 0 {
      digits.push(x % 10);
      x /= 10;
    }
    digits.reverse();
    let mut inc = true;
    let mut dec = true;
    for i in 1..digits.len() {
      if digits[i] <= digits[i - 1] {
        inc = false;
      }
      if digits[i] >= digits[i - 1] {
        dec = false;
      }
    }
    inc || dec
  }

  fn digit_sum(n: i64) -> i64 {
    let mut s = 0;
    let mut x = n;
    while x > 0 {
      s += x % 10;
      x /= 10;
    }
    s
  }

  fn is_fancy(n: i64) -> bool {
    Self::is_good(n) || Self::is_good(Self::digit_sum(n))
  }

  fn count_up_to(n: i64) -> i64 {
    if n <= 0 {
      return 0;
    }
    // Count numbers 1..=n that are fancy.
    // A number is fancy if it's good OR its digit sum is good.
    // Max digit sum for 10^15 is 9*15=135, so digit sum <=135.
    // A number whose digit sum is good: digit sum is single digit (always good) or
    // digit sum has strictly inc/dec digits.
    // Digit sums that are NOT good: two+ digit numbers that aren't strictly monotone.
    // Possible digit sums: 1..135. Not-good sums: e.g. 11,22,...,100,101,...
    // So we need: count of good numbers + count of non-good numbers whose digit sum is good.
    // 
    // For "good" numbers count, we can enumerate: strictly increasing subsequences of {0..9}
    // and strictly decreasing. Use digit DP or combinatorial.
    // For numbers whose digit sum is good but they aren't good: digit sum DP.
    //
    // Actually, let's think differently. Total fancy = good_count + (digit_sum_good_count - both_count).
    // But this is complex. Let me use digit DP.
    //
    // Approach: digit DP counting numbers in [1, n] where is_fancy.
    // is_fancy(x) = is_good(x) || is_good(digit_sum(x)).
    // Precompute which digit sums are "good". Max digit sum = 135.
    // Then digit DP tracking: position, tight constraint, digit_sum_so_far, 
    // is_still_increasing, is_still_decreasing, started.
    // If at any point is_still_increasing || is_still_decreasing => good => fancy.
    // Otherwise, check if digit_sum is good when we finish.
    
    let good_sums: Vec<bool> = (0..=135).map(|s| Self::is_good(s)).collect();
    
    let digits: Vec<u8> = {
      let mut d = Vec::new();
      let mut x = n;
      while x > 0 {
        d.push((x % 10) as u8);
        x /= 10;
      }
      d.reverse();
      d
    };
    let len = digits.len();
    
    // DP states: pos, tight, started, last_digit(0-9 or 10=none), still_inc, still_dec, digit_sum
    // This is too many states. Let's simplify.
    // Since we only care about is_good OR digit_sum is good:
    // Track: pos, tight, started, still_inc, still_dec, prev_digit, digit_sum
    // still_inc/still_dec only matter while started and tell us if number is "good".
    // If still_inc || still_dec at end => fancy.
    // Else check good_sums[digit_sum].
    // prev_digit: 0-9, digit_sum: 0-135. pos: up to 16.
    // States: 16 * 2 * 2 * 2 * 2 * 10 * 136 = ~139k per tight. Very feasible with memoization.
    
    // Use iterative DP or recursive with memo. Let's do recursive.
    use std::collections::HashMap;
    
    fn solve(
      pos: usize,
      tight: bool,
      started: bool,
      still_inc: bool,
      still_dec: bool,
      prev: i8, // -1 if not started
      dsum: u8,
      digits: &[u8],
      good_sums: &[bool],
      memo: &mut HashMap<(usize, bool, bool, bool, bool, i8, u8), i64>,
    ) -> i64 {
      if pos == digits.len() {
        if !started {
          return 0;
        }
        if still_inc || still_dec {
          return 1;
        }
        return if good_sums[dsum as usize] { 1 } else { 0 };
      }
      let key = (pos, tight, started, still_inc, still_dec, prev, dsum);
      if let Some(&v) = memo.get(&key) {
        return v;
      }
      let limit = if tight { digits[pos] } else { 9 };
      let mut count = 0i64;
      for d in 0..=limit {
        let new_tight = tight && d == limit;
        if !started && d == 0 {
          count += solve(pos + 1, new_tight, false, true, true, -1, 0, digits, good_sums, memo);
        } else {
          let new_started = true;
          let new_inc = if started { still_inc && d as i8 > prev } else { true };
          let new_dec = if started { still_dec && (d as i8) < prev } else { true };
          let new_prev = d as i8;
          let new_dsum = dsum + d;
          count += solve(pos + 1, new_tight, new_started, new_inc, new_dec, new_prev, new_dsum, digits, good_sums, memo);
        }
      }
      memo.insert(key, count);
      count
    }
    
    let mut memo = HashMap::new();
    solve(0, true, false, true, true, -1, 0, &digits, &good_sums, &mut memo)
  }
}