Problem Statement in English

You’re given a string s, which consists of digits from 0 to 9 only. You’re also given an array of queries, where each query is a pair of integers (i, j). For each query, you’re asked to concatenate the non-zero digits from s[i] to s[j] and multiply the resulting number by the sum of the non-zero digits from s[i] to s[j].

You’re asked to return an array of the results of each query, each modulo’d with $10^9 + 7$.

Approach

There’s a couple parts to this problem:

  1. We need to find the sum of the non-zero digits from s[i] to s[j].
  2. We need to find the product of the non-zero digits from s[i] to s[j].

Part 1: Sum of Non-Zero Digits

We can use a prefix sum array, call it prefixSum, to find the sum of the non-zero digits from s[i] to s[j].

We iterate through the string and keep track of the sum of the non-zero digits we’ve seen so far. At each index i, we store the sum of the digits until and including the value of index i - 1.

We can then use the prefix sum array to find the sum of the non-zero digits from s[i] to s[j] by subtracting the sum of the non-zero digits from s[i] from the sum of the non-zero digits from s[j + 1].

Part 2: Number of Non-Zero Digits

This is handy for us in the next part. We use a prefix array, call it prefixCountNonZero to store the number of non-zero digits we’ve encountered until index i - 1 at index i. You’ll see why we’re doing this in part 5.

Part 3: Concatenation of Non-Zero Digits

We again use a prefix array, call it prefixNumber, to store the number obtained by concatenating the non-zero digits until and including the value of index i - 1 at index i.

Part 4: Querying the Sum in the Range [i, j]

This is the easier part. We can use the prefixSum that we built earlier. The result for the sum of non-zero digits from s[i] to s[j] is prefixSum[j + 1] - prefixSum[i].

Part 5: Querying the Number in the Range [i, j]

In order to get the number obtained by concatenating the non-zero digits from s[i] to s[j], we can use the prefixNumber array, along with the prefixCountNonZero array.

We get the number of zeroes encountered at index i and j from the prefixCountNonZero array.

We then use the prefixNumber array to get the number obtained by concatenating the non-zero digits until index i and j + 1.

In order to strip prefixNumber[i] from prefixNumber[j + 1], we need to shift prefixNumber[i] to the left by the difference between the number of non zero digits encountered at index i and j + 1.

So we extract the difference in number of non zero digits encountered at index i and j + 1 by doing the following: prefixCountNonZero[j + 1] - prefixCountNonZero[i].

Next we need to actually perform the left shift. We can do this efficiently by precomputing the powers of $10$ modulo MOD beforehand.

So when we perform the left shift, we can simply multiply prefixNumber[j + 1] by pow[prefixCountNonZero[r] - prefixCountNonZero[l]] and then take the modulo MOD.

Part 6: Putting it all together

For each query we can now get the number and the sum of the digits of the number obtained by concatenating the non-zero digits from s[i] to s[j], multiply them and add them to the result array.

And we’re done!

Solution in Python


MOD, MAX = 1_00_00_00_007, 1_00_001
pow = [1] * MAX
for i in range(1, MAX):
    pow[i] = (pow[i - 1] * 10) % MOD

class Solution:
    def sumAndMultiply(self, s: str, queries: list[list[int]]) -> list[int]:
        n, res = len(s), []
        prefixSum, prefixNumber, prefixCountNonZero = [[0] * (n + 1) for _ in range(3)]

        for i in range(n):
            d = int(s[i])
            prefixSum[i + 1] = prefixSum[i] + d
            prefixNumber[i + 1] = (prefixNumber[i] * 10 + d) % MOD if d else prefixNumber[i]
            prefixCountNonZero[i + 1] = prefixCountNonZero[i] + (d > 0)

        res = []

        for l, r in queries:
            r += 1

            shifted = (prefixNumber[l] * pow[prefixCountNonZero[r] - prefixCountNonZero[l]]) % MOD
            x = (prefixNumber[r] - shifted) % MOD

            res.append((x * (prefixSum[r] - prefixSum[l])) % MOD)

        return res

Complexity

  • Time: $O(n + q)$
    where n is the length of the string s and q is the number of queries. We iterate through the string once to compute the prefix sums and prefix numbers, and then iterate through the queries to compute the results. Both iterations take linear time.

  • Space: $O(n)$
    Where n is the length of the string s. We store prefix sums and prefix numbers for each position in the string.

Mistakes I Made

I had to look this up :(

And we are done.