Count the number of powerful integers

Math String Dynamic Programming

46.3% acceptance

Feb 25, 2026

555

You are given three integers start, finish, and limit. You are also given a 0-indexed string s representing a positive integer. A positive integer x is called powerful if it ends with s (in other words, s is a suffix of x) and each digit in x is at most limit. Return the total number of powerful integers in the range [start..finish]. A string x is a suffix of a string y if and only if x is a substring of y that starts from some index (including 0) in y and extends to the index y.length - 1. For example, 25 is a suffix of 5125 whereas 512 is not.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn number_of_powerful_int(start: i64, finish: i64, limit: i32, s: String) -> i64 {
    let sv: i64 = s.parse().unwrap();
    let pow_s: i64 = 10i64.pow(s.len() as u32);
    let lim = limit;

    // count_le(n, lim): count of integers in [0..n] with all digits <= lim
    let count_le = |n: i64| -> i64 {
      if n < 0 { return 0; }
      let d: Vec<i32> = n.to_string().bytes().map(|b| (b - b'0') as i32).collect();
      let k = d.len();
      let lim64 = lim as i64;
      let mut res = 0i64;
      let mut tight = true;
      for i in 0..k {
        let hi = if tight { d[i] } else { lim };
        // not-tight choices: digits 0..min(hi-1, lim) = min(hi, lim+1) choices
        let cnt_nt = (hi.min(lim + 1)) as i64;
        res += cnt_nt * (lim64 + 1).pow((k - 1 - i) as u32);
        if !tight || d[i] > lim {
          tight = false;
          break;
        }
      }
      if tight { res += 1; }
      res
    };

    // f(n): count of powerful integers in [1..n]
    let f = |n: i64| -> i64 {
      if sv > n { return 0; }
      let mut res = 1i64; // x = sv itself (has all digits <= lim by constraint)
      let m = (n - sv) / pow_s;
      let mut pow10 = 1i64;
      loop {
        if pow10 > m { break; }
        let upper = m.min(pow10 * 10 - 1);
        // count k-digit prefixes in [pow10, upper] with all digits <= lim
        res += count_le(upper) - count_le(pow10 - 1);
        pow10 *= 10;
        if pow10 > 1_000_000_000_000_000i64 { break; }
      }
      res
    };

    f(finish) - f(start - 1)
  }
}