3756. Concatenate Non-Zero Digits and Multiply by Sum II

Array
String
Prefix Sum
Math
Number Theory

TIME

O(m + q)

SPACE

O(m)

Intuition

Two pieces per query: the digit sum and the concatenated value x (mod p = 1e9 + 7).

Sum: dropping zeros doesn't change the digit sum (zeros add 0), so sum = sum of all digit values in s[l..r]. A prefix-sum array answers this in O(1).
x mod p: x is the concatenation of the non-zero digits, which can be up to m digits long, far too big to build. But we only need it mod p. The place value of a non-zero digit depends on how many non-zero digits follow it inside the query range, which prefix counts give us.

Approach

Let cnt[i] = number of non-zero digits in s[0..i-1]. For a non-zero digit d_q at position q in query [l, r], the count of non-zero digits after it is cnt[r+1] - cnt[q+1], so its contribution is d_q * 10^{cnt[r+1] - cnt[q+1]}. Factor out the query-dependent power:

x  =  10^{cnt[r+1]}  *  sum_{q in [l,r]}  d_q * 10^{-cnt[q+1]}   (mod p)

The per-position weight w_q = d_q * inv10^{cnt[q+1]} (mod p) doesn't depend on the query, so:

Precompute pow10[], inv10pow[], prefix counts cnt[], prefix digit sums sumPref[], and prefix weight sums wPref[] (where wPref[i] = sum of w_q for q < i).
Per query:
- S = (wPref[r+1] - wPref[l]) mod p
- x = pow10[cnt[r+1]] * S mod p
- sum = sumPref[r+1] - sumPref[l]
- answer = x * (sum mod p) mod p

inv10 = modpow(10, p-2, p) (Fermat), since p is prime and gcd(10, p) = 1.

Complexity

Time: O(m + q), linear preprocessing, O(1) per query
Space: O(m), the prefix arrays

Edge Cases

All-zero substring → S = 0 → x = 0, and sum = 0 → answer 0
Single zero digit query → 0
Leading zeros inside the range are naturally skipped (they carry weight 0 and don't advance cnt)
Keep every intermediate mod p; use long and add p before % p on subtractions to avoid negatives

Code

from typing import List


class Solution:
    def concatenateAndMultiply(self, s: str, queries: List[List[int]]) -> List[int]:
        """
        3756. Concatenate Non-Zero Digits and Multiply by Sum II
        Time: O(m + q)
        Space: O(m)
        """
        MOD = 10**9 + 7
        m = len(s)

        # Powers of 10 and inverse powers of 10, indexed by non-zero-digit count.
        pow10 = [1] * (m + 1)
        for i in range(1, m + 1):
            pow10[i] = pow10[i - 1] * 10 % MOD
        inv10 = pow(10, MOD - 2, MOD)
        inv10pow = [1] * (m + 1)
        for i in range(1, m + 1):
            inv10pow[i] = inv10pow[i - 1] * inv10 % MOD

        # Prefix arrays.
        cnt = [0] * (m + 1)       # non-zero-digit count in s[0..i-1]
        sum_pref = [0] * (m + 1)  # digit-value sum in s[0..i-1]
        w_pref = [0] * (m + 1)    # sum of weights w_q for q < i
        for i in range(m):
            d = ord(s[i]) - 48
            nz = 1 if d != 0 else 0
            cnt[i + 1] = cnt[i] + nz
            sum_pref[i + 1] = sum_pref[i] + d
            # w_q = d * 10^{-cnt[q+1]}; zero digits contribute 0
            w = d * inv10pow[cnt[i + 1]] % MOD if d != 0 else 0
            w_pref[i + 1] = (w_pref[i] + w) % MOD

        ans = []
        for l, r in queries:
            S = (w_pref[r + 1] - w_pref[l]) % MOD
            x = pow10[cnt[r + 1]] * S % MOD
            total = sum_pref[r + 1] - sum_pref[l]
            ans.append(x * (total % MOD) % MOD)
        return ans

/**
 * 3756. Concatenate Non-Zero Digits and Multiply by Sum II
 * Time: O(m + q)
 * Space: O(m)
 */
class Solution {
    private static final int MOD = 1_000_000_007;

    public int[] concatenateAndMultiply(String s, int[][] queries) {
        int m = s.length();

        // Powers of 10 and inverse powers of 10, indexed by non-zero-digit count.
        long[] pow10 = new long[m + 1];
        long[] inv10pow = new long[m + 1];
        pow10[0] = 1;
        for (int i = 1; i <= m; i++) {
            pow10[i] = pow10[i - 1] * 10 % MOD;
        }
        long inv10 = modpow(10, MOD - 2);
        inv10pow[0] = 1;
        for (int i = 1; i <= m; i++) {
            inv10pow[i] = inv10pow[i - 1] * inv10 % MOD;
        }

        // Prefix arrays.
        int[] cnt = new int[m + 1];       // non-zero-digit count in s[0..i-1]
        long[] sumPref = new long[m + 1]; // digit-value sum in s[0..i-1]
        long[] wPref = new long[m + 1];   // sum of weights w_q for q < i
        for (int i = 0; i < m; i++) {
            int d = s.charAt(i) - '0';
            cnt[i + 1] = cnt[i] + (d != 0 ? 1 : 0);
            sumPref[i + 1] = sumPref[i] + d;
            long w = (d != 0) ? d * inv10pow[cnt[i + 1]] % MOD : 0;
            wPref[i + 1] = (wPref[i] + w) % MOD;
        }

        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int l = queries[i][0], r = queries[i][1];
            long S = (wPref[r + 1] - wPref[l] + MOD) % MOD;
            long x = pow10[cnt[r + 1]] * S % MOD;
            long total = (sumPref[r + 1] - sumPref[l]) % MOD;
            ans[i] = (int) (x * total % MOD);
        }
        return ans;
    }

    private long modpow(long base, long exp) {
        long result = 1;
        base %= MOD;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                result = result * base % MOD;
            }
            base = base * base % MOD;
            exp >>= 1;
        }
        return result;
    }
}