Welcome to Subscribe On Youtube
3756. Concatenate Non-Zero Digits and Multiply by Sum II
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
Solution 1
-
class Solution { private static final int MX = 100001; private static final int MOD = 1_000_000_007; private static final long[] POW10 = new long[MX]; static { POW10[0] = 1; for (int i = 1; i < MX; i++) { POW10[i] = POW10[i - 1] * 10 % MOD; } } public int[] sumAndMultiply(String s, int[][] queries) { int n = s.length(); int[] sumD = new int[n + 1]; int[] cntN0 = new int[n + 1]; long[] p = new long[n + 1]; for (int i = 1; i <= n; i++) { int d = s.charAt(i - 1) - '0'; sumD[i] = sumD[i - 1] + d; cntN0[i] = cntN0[i - 1] + (d > 0 ? 1 : 0); p[i] = d > 0 ? (p[i - 1] * 10 + d) % MOD : p[i - 1]; } int[] ans = new int[queries.length]; for (int i = 0; i < queries.length; i++) { int l = queries[i][0], r = queries[i][1]; int n0 = cntN0[r + 1] - cntN0[l]; int sd = sumD[r + 1] - sumD[l]; long x = (p[r + 1] - p[l] * POW10[n0] % MOD + MOD) % MOD; ans[i] = (int) (x * sd % MOD); } return ans; } } -
class Solution { public: vector<int> sumAndMultiply(string s, vector<vector<int>>& queries) { static const int MX = 100001; static const int MOD = 1000000007; static vector<long long> pow10 = [] { vector<long long> p(MX); p[0] = 1; for (int i = 1; i < MX; i++) { p[i] = p[i - 1] * 10 % MOD; } return p; }(); int n = s.size(); vector<int> sumD(n + 1), cntN0(n + 1); vector<long long> p(n + 1); for (int i = 1; i <= n; i++) { int d = s[i - 1] - '0'; sumD[i] = sumD[i - 1] + d; cntN0[i] = cntN0[i - 1] + (d > 0); p[i] = d ? (p[i - 1] * 10 + d) % MOD : p[i - 1]; } vector<int> ans; ans.reserve(queries.size()); for (auto& q : queries) { int l = q[0], r = q[1]; int n0 = cntN0[r + 1] - cntN0[l]; int sd = sumD[r + 1] - sumD[l]; long long x = (p[r + 1] - p[l] * pow10[n0] % MOD + MOD) % MOD; ans.push_back(x * sd % MOD); } return ans; } }; -
mx = 10**5 + 1 mod = 10**9 + 7 pow10 = [1] * mx for i in range(1, mx): pow10[i] = pow10[i - 1] * 10 % mod class Solution: def sumAndMultiply(self, s: str, queries: List[List[int]]) -> List[int]: n = len(s) sum_d = [0] * (n + 1) cnt_n0 = [0] * (n + 1) p = [0] * (n + 1) for i, d in enumerate(map(int, s), 1): sum_d[i] = sum_d[i - 1] + d cnt_n0[i] = cnt_n0[i - 1] + int(d > 0) p[i] = (p[i - 1] * 10 + d) % mod if d else p[i - 1] ans = [] for l, r in queries: n0 = cnt_n0[r + 1] - cnt_n0[l] sd = sum_d[r + 1] - sum_d[l] x = p[r + 1] - p[l] * pow10[n0] % mod ans.append(x * sd % mod) return ans -
const ( mx = 100001 mod int64 = 1000000007 ) var pow10 = func() []int64 { p := make([]int64, mx) p[0] = 1 for i := 1; i < mx; i++ { p[i] = p[i-1] * 10 % mod } return p }() func sumAndMultiply(s string, queries [][]int) []int { n := len(s) sumD := make([]int, n+1) cntN0 := make([]int, n+1) p := make([]int64, n+1) for i := 1; i <= n; i++ { d := int64(s[i-1] - '0') sumD[i] = sumD[i-1] + int(d) cntN0[i] = cntN0[i-1] if d > 0 { cntN0[i]++ p[i] = (p[i-1]*10 + d) % mod } else { p[i] = p[i-1] } } ans := make([]int, len(queries)) for i, q := range queries { l, r := q[0], q[1] n0 := cntN0[r+1] - cntN0[l] sd := int64(sumD[r+1] - sumD[l]) x := (p[r+1] - p[l]*pow10[n0]%mod + mod) % mod ans[i] = int(x * sd % mod) } return ans } -
const MX = 100001; const MOD = 1000000007n; const pow10: bigint[] = Array(MX).fill(1n); for (let i = 1; i < MX; i++) { pow10[i] = (pow10[i - 1] * 10n) % MOD; } function sumAndMultiply(s: string, queries: number[][]): number[] { const n = s.length; const sumD = Array<number>(n + 1).fill(0); const cntN0 = Array<number>(n + 1).fill(0); const p: bigint[] = Array(n + 1).fill(0n); for (let i = 1; i <= n; i++) { const d = s.charCodeAt(i - 1) - 48; sumD[i] = sumD[i - 1] + d; cntN0[i] = cntN0[i - 1] + (d > 0 ? 1 : 0); p[i] = d > 0 ? (p[i - 1] * 10n + BigInt(d)) % MOD : p[i - 1]; } const ans: number[] = []; for (const [l, r] of queries) { const n0 = cntN0[r + 1] - cntN0[l]; const sd = BigInt(sumD[r + 1] - sumD[l]); const x = (p[r + 1] - ((p[l] * pow10[n0]) % MOD) + MOD) % MOD; ans.push(Number((x * sd) % MOD)); } return ans; }