Count of integers

Math String Dynamic Programming

38.2% acceptance

Feb 25, 2026

570

You are given two numeric strings num1 and num2 and two integers max_sum and min_sum. We denote an integer x to be good if: num1 <= x <= num2 min_sum <= digit_sum(x) <= max_sum. Return the number of good integers. Since the answer may be large, return it modulo 10^9 + 7. Note that digit_sum(x) denotes the sum of the digits of x.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn count(num1: String, num2: String, min_sum: i32, max_sum: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;

    // Count integers in [0..=s] with digit_sum in [min_s, max_s]
    fn solve(s: &[u8], min_s: i32, max_s: i32) -> i64 {
      const MOD: i64 = 1_000_000_007;
      let n = s.len();
      // dp[tight][started][sum]
      let cap = (max_s + 1) as usize;
      let mut dp = vec![vec![vec![0i64; cap]; 2]; 2];
      dp[1][0][0] = 1;

      for pos in 0..n {
        let mut ndp = vec![vec![vec![0i64; cap]; 2]; 2];
        for ti in 0..2usize {
          for si in 0..2usize {
            for sum in 0..cap {
              let cnt = dp[ti][si][sum];
              if cnt == 0 { continue; }
              let limit = if ti == 1 { (s[pos] - b'0') as usize } else { 9 };
              for d in 0..=limit {
                let nti = if ti == 1 && d == limit { 1 } else { 0 };
                let nsi = if si == 1 || d > 0 { 1 } else { 0 };
                let nsum = if nsi == 1 { sum + d } else { 0 };
                if nsum < cap {
                  ndp[nti][nsi][nsum] = (ndp[nti][nsi][nsum] + cnt) % MOD;
                }
              }
            }
          }
        }
        dp = ndp;
      }

      let mut res = 0i64;
      for ti in 0..2 {
        for sum in min_s as usize..cap {
          res = (res + dp[ti][1][sum]) % MOD;
        }
      }
      res
    }

    let ans2 = solve(num2.as_bytes(), min_sum, max_sum);
    let ans1 = solve(num1.as_bytes(), min_sum, max_sum);
    let d1: i32 = num1.bytes().map(|b| (b - b'0') as i32).sum();
    let good1 = if d1 >= min_sum && d1 <= max_sum { 1i64 } else { 0i64 };

    ((ans2 - ans1 + good1 + MOD) % MOD) as i32
  }
}