3756. Concatenate Non-Zero Digits and Multiply by Sum II
Problem Description
You are given a string s made up of digits, together with a list of queries where each query is a pair [l, r] describing an inclusive range of positions inside s.
Each query is answered in two steps. First, take the substring s[l..r], delete every '0' from it, and read the digits that remain — kept in their original order — as a single integer x. If the substring contains nothing but zeros, then x = 0. Second, let sum be the sum of the digits of x. The answer to the query is the product x * sum.
Return an array holding one answer per query. Because the products can be enormous, report each answer modulo 10^9 + 7.
Consider s = "10203004" with queries = [[0,7],[1,3],[4,6]]:
- The range
[0, 7]covers the whole string. Dropping the zeros leaves the digits1, 2, 3, 4, sox = 1234. Its digit sum is1 + 2 + 3 + 4 = 10, and the answer is1234 * 10 = 12340. - The range
[1, 3]covers"020". Only the digit2survives, sox = 2, the digit sum is2, and the answer is4. - The range
[4, 6]covers"300", which keeps only3, giving3 * 3 = 9.
The output is [12340, 4, 9].
With s = "1000" and queries = [[0,3],[1,1]], the first range keeps only the digit 1, so the answer is 1 * 1 = 1. The second range is the single character "0": there are no non-zero digits, so x = 0, sum = 0, and the answer is 0. The output is [1, 0].
With s = "9876543210" and queries = [[0,9]], removing the zero leaves x = 987654321 with digit sum 45. The raw product is 44444444445, and after taking it modulo 10^9 + 7 the reported answer is 444444137.
Constraints:
1 <= s.length <= 10^5sconsists of digits only.1 <= queries.length <= 10^5- Every query
[l, r]satisfies0 <= l <= r < s.length.
How We Pick the Algorithm
Why Prefix Sum?
This problem maps to Prefix Sum through a short path in the full flowchart.
Three prefix arrays (digit sum, non-zero digit count, concatenated value mod 1e9+7) turn every substring query into a constant-time formula.
Open in FlowchartIntuition
Answering one query directly is easy: scan the substring, collect the non-zero digits, build the number, and multiply by the digit sum. The trouble is scale. Both the string length and the number of queries reach 10^5, so rebuilding each substring from scratch costs up to 10^5 * 10^5 = 10^10 character visits — far too slow. We need each query to cost roughly constant time, which points toward precomputing prefix information once and combining it per query.
Two observations make that possible.
First, the digit sum of x is simply the digit sum of the whole substring. Deleting zeros removes only digits that contribute nothing to the sum, so sum for the range [l, r] is an ordinary range sum of digit values. A standard prefix-sum array digitSum answers that in O(1).
Second, the concatenated value x can also be expressed through prefixes. Imagine reading s left to right and appending every non-zero digit to one growing number. Let concatVal[i] be the value of that number after processing the first i characters, stored modulo 10^9 + 7, and let nzCount[i] be how many non-zero digits appeared so far. Now look at a range [l, r] containing k = nzCount[r+1] - nzCount[l] non-zero digits. The number concatVal[r+1] consists of the digits from the prefix s[0..l-1] followed by the k digits from the range. In positional notation that means:
concatVal[r+1] = concatVal[l] * 10^k + x (mod 10^9 + 7)
Solving for the unknown gives x = concatVal[r+1] - concatVal[l] * 10^k, taken modulo 10^9 + 7. With powers of ten precomputed, every query reduces to two array lookups, one multiplication, and one subtraction. This is the same shift-and-subtract identity used to extract substring values in rolling-hash techniques, applied here with base 10.
A pleasant side effect: a range with no non-zero digits gives k = 0 and concatVal[r+1] = concatVal[l], so the formula yields x = 0 automatically, and the range sum yields sum = 0 as well. No special case is needed.
Solution Approach
Solution 1: Prefix Sums with Modular Arithmetic
The preprocessing pass builds four arrays over the string of length m, each of size m + 1, where index i summarizes the prefix s[0..i-1]:
digitSum[i]— the sum of all digit values in the prefix. Zeros add nothing, so this doubles as the sum of non-zero digits.nzCount[i]— how many non-zero digits the prefix contains.concatVal[i]— the value, modulo10^9 + 7, of the number formed by concatenating the prefix's non-zero digits. A zero leaves it unchanged; a non-zero digitdupdates it asconcatVal[i] = (concatVal[i-1] * 10 + d) mod p.pow10[k]— the value10^k mod p, needed to shift a prefix value left bykdigit positions.
All four arrays are filled in a single left-to-right scan plus one loop for the powers, costing O(m) total.
Each query [l, r] is then answered with three constant-time computations:
- Count the non-zero digits in the range:
k = nzCount[r+1] - nzCount[l]. - Extract the concatenated value:
x = (concatVal[r+1] - concatVal[l] * pow10[k]) mod p. Because the subtraction happens under the modulus, languages with truncating remainders (Java, C++, JavaScript) must addpbefore the final reduction to keep the result non-negative. - Take the range digit sum
total = digitSum[r+1] - digitSum[l]and reportx * total mod p.
The digit sum never exceeds 9 * 10^5, so total fits comfortably in ordinary integers; the products concatVal[l] * pow10[k] and x * total, however, reach roughly 10^18 and require 64-bit arithmetic (or BigInt in TypeScript).
Complexity Analysis:
- Time complexity:
O(m + q), wheremis the length ofsandqis the number of queries. Preprocessing is one linear scan, and each query is answered in constant time. - Space complexity:
O(m)for the four prefix arrays. The output array is not counted as extra space.
Example Walkthrough
Take s = "10203004" with queries = [[0,7],[1,3],[4,6]], the first example.
Phase 1: Build the prefix arrays
Scanning the string once produces the following tables, where column i describes the prefix consisting of the first i characters:
i | char processed | digitSum[i] | nzCount[i] | concatVal[i] |
|---|---|---|---|---|
| 0 | — | 0 | 0 | 0 |
| 1 | '1' | 1 | 1 | 1 |
| 2 | '0' | 1 | 1 | 1 |
| 3 | '2' | 3 | 2 | 12 |
| 4 | '0' | 3 | 2 | 12 |
| 5 | '3' | 6 | 3 | 123 |
| 6 | '0' | 6 | 3 | 123 |
| 7 | '0' | 6 | 3 | 123 |
| 8 | '4' | 10 | 4 | 1234 |
Notice how a '0' copies the previous row's nzCount and concatVal forward, while a non-zero digit d bumps the count and appends d to the running number (concatVal = concatVal * 10 + d).
Phase 2: Answer each query in constant time
Query [0, 7] — the whole string.
k = nzCount[8] - nzCount[0] = 4 - 0 = 4.
x = concatVal[8] - concatVal[0] * 10^4 = 1234 - 0 = 1234.
total = digitSum[8] - digitSum[0] = 10.
Answer: 1234 * 10 = 12340.
Query [1, 3] — the substring "020".
k = nzCount[4] - nzCount[1] = 2 - 1 = 1.
x = concatVal[4] - concatVal[1] * 10^1 = 12 - 10 = 2.
total = digitSum[4] - digitSum[1] = 3 - 1 = 2.
Answer: 2 * 2 = 4.
The subtraction shows the identity at work: concatVal[4] = 12 is the two-digit number 1 followed by 2. Shifting the prefix value concatVal[1] = 1 left by k = 1 digit and subtracting peels the leading 1 away, leaving exactly the 2 contributed by the range.
Query [4, 6] — the substring "300".
k = nzCount[7] - nzCount[4] = 3 - 2 = 1.
x = concatVal[7] - concatVal[4] * 10^1 = 123 - 120 = 3.
total = digitSum[7] - digitSum[4] = 6 - 3 = 3.
Answer: 3 * 3 = 9.
The final output is [12340, 4, 9], matching the expected result. On real inputs every intermediate value is stored modulo 10^9 + 7; the numbers here are small enough that the modulus never triggers.
Solution Implementation
1from typing import List
2
3
4class Solution:
5 def sumAndMultiply(self, s: str, queries: List[List[int]]) -> List[int]:
6 MOD = 10**9 + 7
7 n = len(s)
8
9 # Prefix arrays where index i covers s[0..i-1]:
10 # digit_sum[i] : sum of all digits in the prefix
11 # nz_count[i] : number of non-zero digits in the prefix
12 # concat_val[i] : value (mod 1e9+7) of the number formed by
13 # concatenating the prefix's non-zero digits
14 digit_sum = [0] * (n + 1)
15 nz_count = [0] * (n + 1)
16 concat_val = [0] * (n + 1)
17
18 # pow10[k] = 10^k mod 1e9+7, used to shift a prefix value left.
19 pow10 = [1] * (n + 1)
20 for i in range(1, n + 1):
21 pow10[i] = pow10[i - 1] * 10 % MOD
22
23 for i, ch in enumerate(s):
24 d = ord(ch) - ord("0")
25 digit_sum[i + 1] = digit_sum[i] + d
26 if d == 0:
27 # Zeros are dropped: neither the count nor the value changes.
28 nz_count[i + 1] = nz_count[i]
29 concat_val[i + 1] = concat_val[i]
30 else:
31 nz_count[i + 1] = nz_count[i] + 1
32 concat_val[i + 1] = (concat_val[i] * 10 + d) % MOD
33
34 ans = []
35 for l, r in queries:
36 # Number of non-zero digits inside s[l..r].
37 k = nz_count[r + 1] - nz_count[l]
38 # Remove the prefix s[0..l-1] contribution: it sits k digit
39 # places to the left inside concat_val[r+1], so shift it and
40 # subtract. Python's % always returns a non-negative result.
41 x = (concat_val[r + 1] - concat_val[l] * pow10[k]) % MOD
42 # Digit sum of x equals the digit sum of the whole substring,
43 # because the dropped zeros contribute nothing to the sum.
44 total = digit_sum[r + 1] - digit_sum[l]
45 ans.append(x * total % MOD)
46 return ans
471class Solution {
2 /**
3 * Answers each [l, r] query with x * digitSum(x) mod 1e9+7, where x is
4 * the number formed by concatenating the non-zero digits of s[l..r].
5 *
6 * Three prefix arrays make every query O(1):
7 * digitSum[i] - sum of all digits in s[0..i-1]
8 * nzCount[i] - number of non-zero digits in s[0..i-1]
9 * concatVal[i] - value (mod 1e9+7) of the non-zero digits of
10 * s[0..i-1] read as one number
11 *
12 * @param s the digit string
13 * @param queries inclusive index pairs [l, r]
14 * @return one answer per query, each taken modulo 1e9+7
15 */
16 public int[] sumAndMultiply(String s, int[][] queries) {
17 final long MOD = 1_000_000_007L;
18 int n = s.length();
19
20 long[] digitSum = new long[n + 1];
21 int[] nzCount = new int[n + 1];
22 long[] concatVal = new long[n + 1];
23
24 // pow10[k] = 10^k mod 1e9+7, used to shift a prefix value left.
25 long[] pow10 = new long[n + 1];
26 pow10[0] = 1;
27 for (int i = 1; i <= n; i++) {
28 pow10[i] = pow10[i - 1] * 10 % MOD;
29 }
30
31 for (int i = 0; i < n; i++) {
32 int d = s.charAt(i) - '0';
33 digitSum[i + 1] = digitSum[i] + d;
34 if (d == 0) {
35 // Zeros are dropped: neither the count nor the value changes.
36 nzCount[i + 1] = nzCount[i];
37 concatVal[i + 1] = concatVal[i];
38 } else {
39 nzCount[i + 1] = nzCount[i] + 1;
40 concatVal[i + 1] = (concatVal[i] * 10 + d) % MOD;
41 }
42 }
43
44 int[] ans = new int[queries.length];
45 for (int i = 0; i < queries.length; i++) {
46 int l = queries[i][0], r = queries[i][1];
47 // Number of non-zero digits inside s[l..r].
48 int k = nzCount[r + 1] - nzCount[l];
49 // Remove the prefix s[0..l-1] contribution: it sits k digit
50 // places to the left inside concatVal[r+1], so shift it and
51 // subtract. Add MOD before the final % so the truncating
52 // remainder cannot produce a negative value.
53 long x = ((concatVal[r + 1] - concatVal[l] * pow10[k] % MOD) % MOD + MOD) % MOD;
54 // Digit sum of x equals the digit sum of the whole substring,
55 // because the dropped zeros contribute nothing to the sum.
56 long total = digitSum[r + 1] - digitSum[l];
57 ans[i] = (int) (x * total % MOD);
58 }
59 return ans;
60 }
61}
621class Solution {
2public:
3 vector<int> sumAndMultiply(string s, vector<vector<int>>& queries) {
4 const long long MOD = 1'000'000'007LL;
5 int n = s.size();
6
7 // Prefix arrays where index i covers s[0..i-1]:
8 // digitSum[i] : sum of all digits in the prefix
9 // nzCount[i] : number of non-zero digits in the prefix
10 // concatVal[i] : value (mod 1e9+7) of the number formed by
11 // concatenating the prefix's non-zero digits
12 vector<long long> digitSum(n + 1, 0);
13 vector<int> nzCount(n + 1, 0);
14 vector<long long> concatVal(n + 1, 0);
15
16 // pow10[k] = 10^k mod 1e9+7, used to shift a prefix value left.
17 vector<long long> pow10(n + 1, 1);
18 for (int i = 1; i <= n; ++i) {
19 pow10[i] = pow10[i - 1] * 10 % MOD;
20 }
21
22 for (int i = 0; i < n; ++i) {
23 int d = s[i] - '0';
24 digitSum[i + 1] = digitSum[i] + d;
25 if (d == 0) {
26 // Zeros are dropped: neither the count nor the value changes.
27 nzCount[i + 1] = nzCount[i];
28 concatVal[i + 1] = concatVal[i];
29 } else {
30 nzCount[i + 1] = nzCount[i] + 1;
31 concatVal[i + 1] = (concatVal[i] * 10 + d) % MOD;
32 }
33 }
34
35 vector<int> ans;
36 ans.reserve(queries.size());
37 for (const auto& q : queries) {
38 int l = q[0], r = q[1];
39 // Number of non-zero digits inside s[l..r].
40 int k = nzCount[r + 1] - nzCount[l];
41 // Remove the prefix s[0..l-1] contribution: it sits k digit
42 // places to the left inside concatVal[r+1], so shift it and
43 // subtract. Add MOD before the final % so the truncating
44 // remainder cannot produce a negative value.
45 long long x = ((concatVal[r + 1] - concatVal[l] * pow10[k] % MOD) % MOD + MOD) % MOD;
46 // Digit sum of x equals the digit sum of the whole substring,
47 // because the dropped zeros contribute nothing to the sum.
48 long long total = digitSum[r + 1] - digitSum[l];
49 ans.push_back(static_cast<int>(x * total % MOD));
50 }
51 return ans;
52 }
53};
541/**
2 * Answers each [l, r] query with x * digitSum(x) mod 1e9+7, where x is the
3 * number formed by concatenating the non-zero digits of s[l..r].
4 *
5 * Precomputes three prefix arrays so every query is O(1):
6 * digitSum[i] - sum of all digits in s[0..i-1]
7 * nzCount[i] - number of non-zero digits in s[0..i-1]
8 * concatVal[i] - value (mod 1e9+7) of the non-zero digits of s[0..i-1]
9 * read as one number
10 *
11 * @param s - digit string
12 * @param queries - inclusive index pairs [l, r]
13 * @returns one answer per query, each taken modulo 1e9+7
14 */
15function sumAndMultiply(s: string, queries: number[][]): number[] {
16 const MOD = 1_000_000_007n;
17 const n = s.length;
18
19 const digitSum: number[] = new Array(n + 1).fill(0);
20 const nzCount: number[] = new Array(n + 1).fill(0);
21 // concatVal and pow10 hold values below 1e9+7, but intermediate
22 // products exceed 2^53, so BigInt is used for the modular math.
23 const concatVal: bigint[] = new Array(n + 1).fill(0n);
24 const pow10: bigint[] = new Array(n + 1).fill(1n);
25
26 for (let i = 1; i <= n; i++) {
27 pow10[i] = (pow10[i - 1] * 10n) % MOD;
28 }
29
30 for (let i = 0; i < n; i++) {
31 const d = s.charCodeAt(i) - 48;
32 digitSum[i + 1] = digitSum[i] + d;
33 if (d === 0) {
34 // Zeros are dropped: neither the count nor the value changes.
35 nzCount[i + 1] = nzCount[i];
36 concatVal[i + 1] = concatVal[i];
37 } else {
38 nzCount[i + 1] = nzCount[i] + 1;
39 concatVal[i + 1] = (concatVal[i] * 10n + BigInt(d)) % MOD;
40 }
41 }
42
43 const ans: number[] = [];
44 for (const [l, r] of queries) {
45 // Number of non-zero digits inside s[l..r].
46 const k = nzCount[r + 1] - nzCount[l];
47 // Remove the prefix s[0..l-1] contribution: it sits k digit
48 // places to the left inside concatVal[r+1], so shift it and
49 // subtract. Adding MOD before the final % keeps the value
50 // non-negative, since BigInt % truncates toward zero.
51 const x = ((concatVal[r + 1] - (concatVal[l] * pow10[k]) % MOD) % MOD + MOD) % MOD;
52 // Digit sum of x equals the digit sum of the whole substring,
53 // because the dropped zeros contribute nothing to the sum.
54 const total = BigInt(digitSum[r + 1] - digitSum[l]);
55 ans.push(Number((x * total) % MOD));
56 }
57 return ans;
58}
59Time and Space Complexity
Time Complexity: O(m + q)
Let m be the length of s and q the number of queries.
-
Preprocessing: Filling
pow10takes one loop ofmsteps, and the main scan fillsdigitSum,nzCount, andconcatValin a single pass with constant work per character (a comparison, an addition, one modular multiply). This phase costsO(m). -
Query phase: Each query performs a fixed number of array lookups, one modular multiplication (
concatVal[l] * pow10[k]), one subtraction with normalization, and one final multiplication. That isO(1)per query, orO(q)overall.
The total is O(m) + O(q) = O(m + q). Compare this with recomputing every substring from scratch, which would cost O(m * q) — up to 10^10 steps at the given limits.
Space Complexity: O(m)
The four prefix arrays (digitSum, nzCount, concatVal, pow10) each hold m + 1 entries, giving O(m) auxiliary space. Aside from these, only a constant number of scalar variables (k, x, total) are used per query. The returned answer array of length q is the required output and is typically not counted as extra space.
Pattern Learn more about how to find time and space complexity quickly.
Common Pitfalls
Pitfall 1: Reading the digit sum off the reduced value of x
The prefix array stores x only modulo 10^9 + 7, so the digits of the stored value are not the digits of the real number. Take a substring of eleven 9s: the true concatenation is x = 99999999999 with digit sum 99, but the stored value is 99999999999 mod (10^9 + 7) = 999999306, whose digits sum to 63. Any solution that computes sum by peeling digits off the modular x returns wrong answers as soon as a range contains ten or more non-zero digits.
Solution: Never derive the digit sum from x. Use a separate prefix array of digit sums, which is exact because it never needs the modulus (9 * 10^5 fits easily in an integer):
total = digit_sum[r + 1] - digit_sum[l] # exact, not modular
Pitfall 2: A negative result after the modular subtraction
The extraction formula subtracts two values that both live in [0, 10^9 + 6]:
long x = (concatVal[r + 1] - concatVal[l] * pow10[k] % MOD) % MOD; // can be negative!
On large inputs concatVal[r + 1] has wrapped around the modulus, so it can be numerically smaller than the shifted prefix term — for instance 5 - 12 = -7. Java, C++, and JavaScript's BigInt all truncate toward zero, so -7 % MOD stays -7, and the final product comes out negative or simply wrong. Python is the exception: its % always returns a non-negative value, which is why a working Python solution can fail when ported line by line.
Solution: Normalize after the subtraction by adding the modulus once:
long x = ((concatVal[r + 1] - concatVal[l] * pow10[k] % MOD) % MOD + MOD) % MOD;
Pitfall 3: 64-bit overflow and lost precision in the shift product
Both concatVal[l] and pow10[k] can be close to 10^9, so their product approaches 10^18. That overflows 32-bit integers immediately, and in JavaScript/TypeScript it also exceeds Number.MAX_SAFE_INTEGER = 2^53 - 1: 999999999 * 999999999 = 999999998000000001 cannot be represented exactly as a floating-point number, so results are silently off by a few units.
Solution: Perform the modular products in a 64-bit integer type — long in Java, long long in C++ — reducing with % MOD after each multiplication. In TypeScript use BigInt for concatVal, pow10, and every multiplication, converting back to number only for the final answer, which is guaranteed to be below 10^9 + 7.
Ready to land your dream job?
Unlock your dream job with a 5-minute quiz for a personalized study roadmap!
Get My RoadmapWhich algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Subarray Sum Equals Target This problem applies the prefix sum technique from the introduction problems prefix_sum_intro instead of testing every possible subarray a running prefix sum turns the search into a hash table lookup Given an integer array arr and a target value return a subarray whose sum equals the target Return the answer
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Want a Structured Path to Master System Design Too? Don’t Miss This!