Skip to content

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 x by concatenating all the non-zero digits from the substring in their original order. If there are no non-zero digits, x = 0.
  • Let sum be the sum of digits in x. The answer is x * 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 = 1234
    • sum = 1 + 2 + 3 + 4 = 10
    • Therefore, answer is 1234 * 10 = 12340.
  • s[1..3] = "020"
    • x = 2
    • sum = 2
    • Therefore, the answer is 2 * 2 = 4.
  • s[4..6] = "300"
    • x = 3
    • sum = 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 = 1
    • sum = 1
    • Therefore, the answer is 1 * 1 = 1.
  • s[1..1] = "0"
    • x = 0
    • sum = 0
    • Therefore, the answer is 0 * 0 = 0.

Example 3:

Input: s = "9876543210", queries = [[0,9]]

Output: [444444137]

Explanation:

  • s[0..9] = "9876543210"
    • x = 987654321
    • sum = 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 <= 105
  • s consists of digits only.
  • 1 <= queries.length <= 105
  • queries[i] = [li, ri]
  • 0 <= li <= ri < m

Solutions

Solution 1: Prefix Sum

We preprocess three prefix arrays:

  • sumD[i] is the sum of digits in the first \(i\) characters of the string;
  • cntN0[i] is the count of non-zero digits in the first \(i\) characters;
  • p[i] is the number formed by concatenating all non-zero digits in the first \(i\) characters, modulo \(10^9 + 7\).

For a query \([l, r]\), the number of non-zero digits in the substring is \(n_0 = cntN0[r + 1] - cntN0[l]\), and the digit sum is \(sd = sumD[r + 1] - sumD[l]\). Since \(p[r + 1] = p[l] \cdot 10^{n_0} + x\), we have \(x = p[r + 1] - p[l] \cdot 10^{n_0}\), and the answer is \(x \cdot sd\).

We precompute powers of \(10\) and answer each query in \(O(1)\).

The time complexity is \(O(n + q)\) and the space complexity is \(O(n)\), where \(n\) is the string length and \(q\) is the number of queries.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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;
}

Comments