Concatenate non zero digits and multiply by sum ii

Math String Prefix Sum

24.1% acceptance

Feb 25, 2026

You are given a string s of length m consisting of digits. You are also given a 2D integer array queries, where queries[i] = [li, ri]. For each queries[i], extract the substring s[li..ri]. Then, perform the following: Form a new integer x by concatenating all the non-zero digits from the substring in their original order. If there are no non-zero digits, x = 0. Let sum be the sum of digits in x. The answer is x * sum. Return an array of integers answer where answer[i] is the answer to the ith query. Since the answers may be very large, return them modulo 109 + 7.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn sum_and_multiply(s: String, queries: Vec<Vec<i32>>) -> Vec<i32> {
    const MOD: i64 = 1_000_000_007;
    let bytes = s.as_bytes();
    let m = bytes.len();

    // prefix_nz[i]  = count of non-zero digits in s[0..i)
    // prefix_sum[i] = sum   of non-zero digits in s[0..i)
    // prefix_x[i]   = number formed by concatenating non-zero digits in s[0..i) mod MOD
    let mut prefix_nz  = vec![0usize; m + 1];
    let mut prefix_sum = vec![0i64;   m + 1];
    let mut prefix_x   = vec![0i64;   m + 1];

    for i in 0..m {
      let d = (bytes[i] - b'0') as i64;
      if d != 0 {
        prefix_nz[i + 1]  = prefix_nz[i] + 1;
        prefix_sum[i + 1] = prefix_sum[i] + d;
        prefix_x[i + 1]   = (prefix_x[i] * 10 + d) % MOD;
      } else {
        prefix_nz[i + 1]  = prefix_nz[i];
        prefix_sum[i + 1] = prefix_sum[i];
        prefix_x[i + 1]   = prefix_x[i];
      }
    }

    // Precompute powers of 10 mod MOD (up to m).
    let mut pow10 = vec![1i64; m + 1];
    for i in 1..=m {
      pow10[i] = pow10[i - 1] * 10 % MOD;
    }

    queries.iter().map(|q| {
      let l = q[0] as usize;
      let r = q[1] as usize;
      let nz = prefix_nz[r + 1] - prefix_nz[l];
      if nz == 0 {
        return 0;
      }
      let sum = (prefix_sum[r + 1] - prefix_sum[l]) % MOD;
      // x(l,r) = prefix_x[r+1] - prefix_x[l] * 10^nz  (mod MOD)
      let x = (prefix_x[r + 1] - prefix_x[l] * pow10[nz] % MOD + MOD) % MOD;
      (x * sum % MOD) as i32
    }).collect()
  }
}