Description
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
xby concatenating all the non-zero digits from the substring in their original order. If there are no non-zero digits,x = 0. - Let
sumbe the sum of digits inx. The answer isx * 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.
Example 1:
Input: s = "10203004", queries = [[0,7],[1,3],[4,6]]
Output: [12340, 4, 9]
Explanation:
s[0..7] = "10203004"x = 1234sum = 1 + 2 + 3 + 4 = 10- Therefore, answer is
1234 * 10 = 12340.
s[1..3] = "020"x = 2sum = 2- Therefore, the answer is
2 * 2 = 4.
s[4..6] = "300"x = 3sum = 3- Therefore, the answer is
3 * 3 = 9.
Example 2:
Input: s = "1000", queries = [[0,3],[1,1]]
Output: [1, 0]
Explanation:
s[0..3] = "1000"x = 1sum = 1- Therefore, the answer is
1 * 1 = 1.
s[1..1] = "0"x = 0sum = 0- Therefore, the answer is
0 * 0 = 0.
Example 3:
Input: s = "9876543210", queries = [[0,9]]
Output: [444444137]
Explanation:
s[0..9] = "9876543210"x = 987654321sum = 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45- Therefore, the answer is
987654321 * 45 = 44444444445. - We return
44444444445 modulo (109 + 7) = 444444137.
Constraints:
1 <= m == s.length <= 105sconsists of digits only.1 <= queries.length <= 105queries[i] = [li, ri]0 <= li <= ri < m
Solutions
I didn't fully understand the math that went into this solution, nor did I have the time to really look at it.
Language: javascript(2026-07-08 07:45)DONE
CPU Performance10.64%
Memory Performance55.00%
const MAX_N = 100_000;
const MOD = 10n ** 9n + 7n;
const pow10 = new Array(MAX_N + 1);
pow10[0] = 1n;
for (let i = 1; i <= MAX_N; i++) {
pow10[i] = (pow10[i - 1] * 10n) % MOD;
}
/**
* @param {string} s
* @param {number[][]} queries
* @return {number[]}
*/
var sumAndMultiply = function(s, queries) {
const dpX = Array(s.length + 1).fill(0n);
const dpSum = Array(s.length + 1).fill(0n);
const dpLen = Array(s.length + 1).fill(0n);
for (let i = 0; i < s.length; i++) {
const cur = BigInt(s[i]);
dpX[i + 1] = cur > 0 ? (dpX[i] * 10n + cur) % MOD : dpX[i];
dpSum[i + 1] = dpSum[i] + cur;
dpLen[i + 1] = dpLen[i] + (cur > 0 ? 1n : 0n);
}
const res = [];
for (const [l, r] of queries) {
const len = dpLen[r + 1] - dpLen[l];
const x = (dpX[r + 1] - ((dpX[l] * pow10[len]) % MOD) + MOD) % MOD;
const sum = dpSum[r + 1] - dpSum[l];
res.push(Number((x * sum) % MOD));
}
return res;
};