Concatenate Non-Zero Digits and Multiply by Sum II

Problem summary

We are given a string s of digits and a list of queries. Each query is [li, ri], and for the substring s[li..ri] we must:

• form an integer x by concatenating all non-zero digits in their original order (if there are none, x = 0)
• let sum be the sum of the digits of x
• report x * sum

Because x can be enormous, every answer is returned modulo 10^9 + 7.

With both m (string length) and the number of queries up to 10^5, we cannot rebuild x from scratch for each query. We need to answer every query in O(1) after some preprocessing.

The trap: you cannot store x

The most natural first attempt is to precompute the actual concatenated number for every prefix and then slice out the piece a query needs. That fails immediately: x can have up to 10^5 digits, so it never fits in an int or even a long.

Once you reduce a value modulo 10^9 + 7, the real digits are gone forever — you can no longer "cut" a suffix out of it with plain division. So any solution that tries to keep the true integer around is doomed. The whole point of the modulus in the statement is that we must build x under the modulus and answer queries with modular arithmetic instead.

Key observation

Concatenating a digit d onto a number v is just:

v_new = v * 10 + d

If we apply this rule across a prefix — skipping zeros, since they never enter x — we get, for every prefix, the value of "all non-zero digits so far" taken mod 10^9 + 7.

The trick is turning a prefix value into a range value. Let:

• val[i] = concatenation of all non-zero digits in s[0..i-1], mod p
• cnt[i] = number of non-zero digits in s[0..i-1]

Then the non-zero digits of s[0..r] are exactly the non-zero digits of s[0..l-1] followed by the non-zero digits of the range [l, r]. In terms of the concatenation rule, that means:

val[r + 1] = val[l] * 10^k + x

where k = cnt[r + 1] - cnt[l] is the number of non-zero digits inside the range. Rearranging:

x = val[r + 1] - val[l] * 10^k (mod p)

That gives us x for any range in O(1).

Getting the sum

The sum of the digits of x is the sum of the non-zero digits in the range — but zeros contribute 0 anyway, so it is simply the sum of all digits in [l, r]. A standard prefix sum handles it:

sum = sumPre[r + 1] - sumPre[l]

Note this stays a real integer (at most 9 * 10^5), so no modulus is needed while accumulating it, though we reduce it before the final multiply.

Full approach

1. Build three prefix arrays of length n + 1:
   • sumPre — running sum of digit values
   • val — running concatenation of non-zero digits, mod p
   • cnt — running count of non-zero digits
2. Precompute pow10[k] = 10^k mod p for every k up to n.
3. For each query [l, r]:
   • sum = sumPre[r + 1] - sumPre[l]
   • k = cnt[r + 1] - cnt[l]
   • x = (val[r + 1] - val[l] * pow10[k]) mod p (add p before the final mod to avoid a negative)
   • answer is x * sum mod p

Using n + 1-sized prefix arrays lets the range [l, r] map cleanly to indices l and r + 1, which removes the off-by-one and the l == 0 special case.

class Solution {
    public int[] sumAndMultiply(String s, int[][] queries) {
        final int MOD = 1_000_000_007;
        int n = s.length();

        long[] sumPre = new long[n + 1]; // prefix sum of digits
        long[] val = new long[n + 1];    // non-zero digits concatenated, mod MOD
        int[] cnt = new int[n + 1];      // count of non-zero digits

        for (int i = 0; i < n; i++) {
            int d = s.charAt(i) - '0';
            sumPre[i + 1] = sumPre[i] + d;
            if (d != 0) {
                val[i + 1] = (val[i] * 10 + d) % MOD;
                cnt[i + 1] = cnt[i] + 1;
            } else {
                val[i + 1] = val[i];
                cnt[i + 1] = cnt[i];
            }
        }

        long[] pow10 = new long[n + 1];
        pow10[0] = 1;
        for (int i = 1; i <= n; i++) {
            pow10[i] = pow10[i - 1] * 10 % MOD;
        }

        int m = queries.length;
        int[] answer = new int[m];
        for (int i = 0; i < m; i++) {
            int l = queries[i][0];
            int r = queries[i][1];
            long sum = sumPre[r + 1] - sumPre[l];
            int k = cnt[r + 1] - cnt[l];
            long x = ((val[r + 1] - val[l] * pow10[k]) % MOD + MOD) % MOD;
            answer[i] = (int) (x * (sum % MOD) % MOD);
        }
        return answer;
    }
}

Walkthrough

Take:

s = "10203004"
queries = [[0, 7], [1, 3], [4, 6]]

First build the prefixes (index i here means "over s[0..i-1]"):

i:        0   1   2   3   4   5   6   7   8
digit:        1   0   2   0   3   0   0   4
sumPre:   0   1   1   3   3   6   6   6  10
cnt:      0   1   1   2   2   3   3   3   4
val:      0   1   1  12  12 123 123 123 1234

Query [0, 7]

sum = sumPre[8] - sumPre[0] = 10 - 0 = 10
k   = cnt[8] - cnt[0] = 4 - 0 = 4
x   = val[8] - val[0] * 10^4 = 1234 - 0 = 1234
answer = 1234 * 10 = 12340

Query [1, 3]

Substring is "020", so x = 2.

sum = sumPre[4] - sumPre[1] = 3 - 1 = 2
k   = cnt[4] - cnt[1] = 2 - 1 = 1
x   = val[4] - val[1] * 10^1 = 12 - 1 * 10 = 2
answer = 2 * 2 = 4

Query [4, 6]

Substring is "300", so x = 3.

sum = sumPre[7] - sumPre[4] = 6 - 3 = 3
k   = cnt[7] - cnt[4] = 3 - 2 = 1
x   = val[7] - val[4] * 10^1 = 123 - 12 * 10 = 3
answer = 3 * 3 = 9

Final answer: [12340, 4, 9].

Complexity analysis

Time Complexity: O(m + q)

• one linear pass builds all prefix arrays and the powers of ten
• each of the q queries is answered in O(1)

Space Complexity: O(m)

For the four prefix/power arrays.

Common mistakes

1. Trying to store the real value of x

x can have up to 10^5 digits. It never fits in a fixed-width integer, and once reduced mod p you cannot recover its digits. Build it modularly from the start.

2. Off-by-one on the sum range

sumPre[r] - sumPre[l] (with n-sized prefixes) drops the digit at index l. Use n + 1-sized prefixes so the range maps to sumPre[r + 1] - sumPre[l].

3. Forgetting to shift by 10^k, not 10^(r - l)

The shift exponent is the number of non-zero digits in the range (cnt[r + 1] - cnt[l]), not the length of the substring. Zeros are skipped when forming x, so they do not shift anything.

4. Negative result after subtraction

val[r + 1] - val[l] * pow10[k] can be negative under the modulus. Add p before the final % p, otherwise you get a wrong (negative) answer in languages where % can return a negative value.

5. Overflow in the intermediate products

val[l] * pow10[k] and x * sum both reach roughly 10^18. Use a 64-bit type (long, long long, int64), or BigInt in JavaScript/TypeScript, before taking the modulus.