Sum of k digit numbers in a range

Math Divide and Conquer Combinatorics Number Theory

49.8% acceptance

Mar 15, 2026

You are given three integers l, r, and k. Consider all possible integers consisting of exactly k digits, where each digit is chosen independently from the integer range [l, r] (inclusive). If 0 is included in the range, leading zeros are allowed. Return an integer representing the sum of all such numbers. Since the answer may be very large, return it modulo 10^9 + 7.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn sum_of_numbers(l: i32, r: i32, k: i32) -> i32 {
    let modp: i64 = 1_000_000_007;
    let n = (r - l + 1) as i64; // number of digit choices
    let digit_sum = ((l as i64 + r as i64) * n / 2) % modp; // sum of all digits in range

    // Each k-digit number: d_{k-1} * 10^{k-1} + ... + d_1 * 10 + d_0
    // Sum over all numbers = sum over positions p from 0..k-1 of:
    //   10^p * (sum of digit at position p across all numbers)
    // For position p, there are n^{k-1} numbers per digit choice,
    // so sum of digits at position p = digit_sum * n^{k-1}
    // Total = digit_sum * n^{k-1} * (10^0 + 10^1 + ... + 10^{k-1})
    //       = digit_sum * n^{k-1} * (10^k - 1) / 9

    // Need modular inverse of 9
    fn pow_mod(mut base: i64, mut exp: i64, modp: i64) -> i64 {
      let mut result = 1i64;
      base %= modp;
      while exp > 0 {
        if exp & 1 == 1 {
          result = result * base % modp;
        }
        exp >>= 1;
        base = base * base % modp;
      }
      result
    }

    let k = k as i64;

    if n == 0 {
      return 0;
    }

    let n_pow_k_minus_1 = pow_mod(n, k - 1, modp);
    let ten_pow_k = pow_mod(10, k, modp);

    // (10^k - 1) / 9 mod p
    // = (10^k - 1) * 9^{-1} mod p
    let inv9 = pow_mod(9, modp - 2, modp);
    let geometric = (ten_pow_k - 1 + modp) % modp * inv9 % modp;

    let result = digit_sum % modp * n_pow_k_minus_1 % modp * geometric % modp;
    result as i32
  }
}