DDSA Solutions

3756. Concatenate Non-Zero Digits and Multiply by Sum II

MediumView on LeetCode
StringMathPrefix Sum
Time: O(n + q)
Space: O(n)

Problem Overview

Each query is LC 3754 on a substring.

Intuition

Each query is LC 3754 on a substring. Precompute prefix digit sums, non-zero counts, and the modulo concatenation value p[i] for the first i characters. For [l,r], the substring’s x satisfies p[r+1] = p[l]·10^n0 + x, so extract x in O(1) per query.

Algorithm

  1. 1Precompute POW10[i] = 10^i mod (1e9+7).
  2. 2Build sumD, cntN0, and p prefix arrays over s (1-indexed).
  3. 3For each query [l,r]: n0 = cntN0[r+1] − cntN0[l], sd = sumD[r+1] − sumD[l].
  4. 4x = (p[r+1] − p[l]·POW10[n0]) mod MOD.
  5. 5answer = (x · sd) mod MOD.

Example Walkthrough

Input: s = "10203004", queries = [[0,7],[1,3],[4,6]]

  1. 1.Query [0,7]: x = 1234, sd = 10 → 12340.
  2. 2.Query [1,3] on "020": x = 2, sd = 2 → 4.
  3. 3.Query [4,6] on "300": x = 3, sd = 3 → 9.

Output: [12340, 4, 9]

Common Pitfalls

  • •Use 1-indexed prefixes; query bounds l,r are 0-indexed inclusive.
  • •Add MOD before modulo when subtracting p[l]·10^n0 from p[r+1].
  • •sumD counts all digits; zeros add 0, so it equals the sum of non-zero digits in the range.
3756.cs
C#
// Approach: Prefix arrays — sumD (digit sum), cntN0 (non-zero count), p (concatenated value mod).
// For query [l,r]: x = p[r+1] − p[l]·10^n0, answer = x·sd mod 1e9+7.
// Time: O(n + q) Space: O(n)
public class Solution
{
    private const int MX = 100001;
    private const int MOD = 1_000_000_007;
    private static readonly long[] POW10 = new long[MX];

    static Solution()
    {
        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[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;
    }
}
Was this solution helpful?

Related Problems