Count Substrings Divisible By Last Digit

Number: 3696

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given a string s that consists only of digits, count the number of non‐empty substrings whose numeric value is divisible by its last digit (when that digit is nonzero). Note that a substring may have leading zeros. For example, if s = "12936" then there are 15 total substrings; after ruling out those substrings that are not divisible by their (nonzero) last digit, the answer is 11.

Key Insights

Only substrings ending in a nonzero digit d are considered; the divisibility test is “number % d == 0.”
Although one might consider checking every substring (O(n^2)), the constraint n ≤ 10^5 forces an optimized solution.
The idea is to “precompute” the integer value of every prefix modulo d so that the value of any substring s[j...i] can be computed in O(1) time using the formula: value = pre[i+1] – pre[j] * 10^(i+1–j)
Since the divisor is the last digit (a number 1–9) there are only a few cases. In particular: • For divisors that are “nice” (for example d = 1, 2, 5), the divisibility condition simplifies. • For digits d that are coprime with 10 (namely 1,3,7,9) one may “cancel” the powers of 10 modulo d (using modular inverses) so that the condition becomes a simple equality between values computed from prefixes. • For other digits (such as 4, 6, 8) the behavior of 10^L modulo d is “degenerate” (often quickly becoming 0 or constant), so one can break the counting into small‐length substrings (for which one checks the condition exactly) and long substrings (which, under certain conditions, are automatically valid).
In the final solution the strategy is to precompute prefix remainders (for each relevant modulus d) and then, while scanning the string, count valid substrings ending at each index by handling each last‐digit case separately.

Space and Time Complexity

Time Complexity: O(n) – we do a single pass through the string and update auxiliary dictionaries (or counters) for each case. Space Complexity: O(n) – for storing prefix remainder arrays and frequency counters.

Solution

The approach works by processing each ending index i (where s[i] represents the last digit d of a substring) separately. Since d is a digit from 1 to 9 (we ignore zero since “nonzero last digit” is required) the divisibility condition is “number (i.e. s[j…i]) is divisible by d”. We precompute prefix remainders for each d. Then for each ending index, we “reverse‐engineer” the condition: pre[i+1] – pre[j] * 10^(i+1–j) ≡ 0 (mod d) This is rewritten as: pre[i+1] ≡ pre[j] * 10^(i+1–j) (mod d) The structure of powers of 10 modulo d depends on d. For example, when d ∈ {1,2,5} the behavior is simple so that if pre[i+1] % d == 0 then every possible starting index j makes the substring valid (thus contributing i+1 substrings). For digits coprime with 10 (e.g. 3,7,9) we may “divide” by 10^(i+1) modulo d by precomputing its modular inverse. In that case the condition is equivalent to: F(i+1) = F(j) where F(k) = pre[k] * inv(10^k) mod d. A frequency dictionary of F values for indices less than or equal to i (i.e. j in [0, i]) lets us quickly count the number of substrings ending at i. Finally for d=4,6,8 the powers of 10 quickly become 0 or constant so the count can be broken into parts (e.g. the single‐digit substring always works; for longer lengths one must check the condition and, in some cases, all such substrings are valid when the entire prefix is 0 modulo d).

We precompute the required prefix modulo arrays and (when needed) the arrays of 10’s powers modulo d. Then we scan through s once. For each index we branch by the last digit’s case and add to the answer accordingly. Similar helper dictionaries are maintained per modulus for the frequency counts.

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java. Each version is commented thoroughly so that the purpose of variables and each major step is clear.

# Python solution
# Note: This is one valid approach – we distinguish cases by the last digit d.
# For digits in {1,2,5} the divisibility condition simplifies.
# For digits coprime with 10 (3,7,9) we use a transformation using modular inverses.
# For other digits (4,6,8) we break the count into substrings of small lengths where the behavior of 10^L mod d is non‐standard.
# Due to space, the code below illustrates the overall structure and key ideas.

def countSubstringsDivisible(s: str) -> int:
    n = len(s)
    total = 0
    # Precompute prefix arrays for each d (we compute only as needed)
    # For d in {1,2,5} we need a simple prefix mod
    pre_mod = {d: [0]*(n+1) for d in [1,2,5]}
    for d in [1,2,5]:
        for i in range(n):
            pre_mod[d][i+1] = (pre_mod[d][i] * 10 + int(s[i])) % d

    # For d in {3,7,9} (coprime with 10) precompute prefix mod and power10 mod arrays,
    # and modular inverses will be computed as needed.
    def modinv(a, m):
        # compute modular inverse of a under mod m using extended Euclidean algorithm
        # (m is prime or at least a and m are coprime)
        g, x, _ = egcd(a, m)
        if g != 1:
            return None
        return x % m

    def egcd(a, b):
        if a == 0:
            return (b, 0, 1)
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

    pre_mod_coprime = {}
    pow10 = {}
    inv10pow = {}
    for d in [3,7,9]:
        pre_mod_coprime[d] = [0]*(n+1)
        pow10[d] = [1]*(n+1)
        inv10pow[d] = [1]*(n+1)
        inv10 = modinv(10, d)  # 10 is invertible since d and 10 are coprime
        for i in range(n):
            pre_mod_coprime[d][i+1] = (pre_mod_coprime[d][i] * 10 + int(s[i])) % d
            pow10[d][i+1] = (pow10[d][i] * 10) % d
            # Precompute inverse of 10^(i+1) as (inv10)^(i+1)
            inv10pow[d][i+1] = (inv10pow[d][i] * inv10) % d

    # Frequency dictionaries for transformed prefix for d in {3,7,9}
    freq = {d: {} for d in [3,7,9]}
    # Initially, for j=0, F(0)=pre_mod_coprime[d][0]*inv10pow[d][0]=0*1=0.
    for d in [3,7,9]:
        freq[d][0] = 1

    # For d in {4,6,8} we precompute prefix mod arrays separately.
    pre_mod_noncoprime = {}
    for d in [4,6,8]:
        pre_mod_noncoprime[d] = [0]*(n+1)
        for i in range(n):
            pre_mod_noncoprime[d][i+1] = (pre_mod_noncoprime[d][i] * 10 + int(s[i])) % d

    # For d=6, note that 10 mod6 =4 and remains constant for exponent>=1.
    # We use a frequency dictionary that will store for j indices the value: ( pre_mod_noncoprime[6][j] * 4 ) mod6.
    freq6 = {}
    # For j=0:
    freq6[(0*4)%6] = 1

    # Process each ending index i.
    # We update our frequency dictionaries as we move along.
    for i in range(n):
        d = int(s[i])
        # We only consider nonzero last digit.
        if d == 0:
            # Skip substrings ending with '0'
            # Also update the frequency dictionaries for future use.
            # For digits d in coprime groups and for 6 and noncoprime updates:
            for dd in [3,7,9]:
                key = ( pre_mod_coprime[dd][i+1] * inv10pow[dd][i+1] ) % dd
                freq[dd][key] = freq[dd].get(key, 0) + 1
            # For d=6:
            key6 = (pre_mod_noncoprime[6][i+1] * 4) % 6
            freq6[key6] = freq6.get(key6, 0) + 1
            continue

        # Case 1: d in {1,2,5}
        if d in [1,2,5]:
            # For these, condition simplifies: the entire substring s[j...i] is divisible by d exactly when:
            # pre_mod[d][i+1] == 0.
            if pre_mod[d][i+1] % d == 0:
                # All starting positions 0..i produce a substring ending at i.
                total += (i + 1)
        # Case 2: d in {3,7,9} (coprime with 10)
        elif d in [3,7,9]:
            # Compute the transformed value F(i+1) = pre_mod_coprime[d][i+1] * inv10pow[d][i+1] mod d.
            F = ( pre_mod_coprime[d][i+1] * inv10pow[d][i+1] ) % d
            # All starting positions j (with j from 0 to i) for which F(j) equals F(i+1) yield a valid substring.
            count_here = freq[d].get(F, 0)
            total += count_here
            # Update frequency for index i+1:
            freq[d][F] = freq[d].get(F, 0) + 1
        # Case 3: d in {4,6,8} with non-coprime behavior
        elif d == 4:
            # For d=4, observe that:
            # • The single-digit substring (i.e. j == i) is always valid.
            count_here = 1
            # • For substrings with length >= 2 (i.e. j from 0 to i-1) the property turns out to hold if pre_mod_noncoprime[4][i+1] == 0.
            if i >= 1 and pre_mod_noncoprime[4][i+1] % 4 == 0:
                count_here += i  # there are i choices of j in [0, i-1]
            total += count_here
        elif d == 6:
            # For d=6, note that 10 mod6 = 4 so for any substring of length>=1,
            # the condition becomes: pre_mod_noncoprime[6][i+1] == (pre_mod_noncoprime[6][j] * 4) mod6.
            # We count j in [0, i] satisfying this.
            # The single-digit substring (j == i) always satisfies the condition.
            count_here = 0
            # Query frequency dictionary:
            count_here += freq6.get(pre_mod_noncoprime[6][i+1] % 6, 0)
            total += count_here
            # Now update freq6 with index i+1.
            key6 = (pre_mod_noncoprime[6][i+1] * 4) % 6
            freq6[key6] = freq6.get(key6, 0) + 1
        elif d == 8:
            # For d=8, the powers of 10 modulo 8 behave as:
            # 10^1 mod8 = 2, 10^2 mod8 = (2*10 mod8 = 4), 10^3 mod8 = (4*10 mod8 = 0) and then remain 0.
            # Hence, for an ending index i:
            # • The single-digit substring (j == i) always counts.
            # • The two-digit substring (j == i-1) is valid if:
            #       pre_mod_noncoprime[8][i+1] == (pre_mod_noncoprime[8][i] * 10 mod8),
            #   i.e. if pre_mod_noncoprime[8][i+1] == (pre_mod_noncoprime[8][i] * 2) mod8.
            # • For any substring of length >= 3 (i.e. j <= i-2), note that 10^(L) mod8 = 0, so the condition
            #   becomes pre_mod_noncoprime[8][i+1] == 0.
            count_here = 1  # single-digit always works
            if i >= 1:
                # Check the two-digit substring (length 2)
                if (pre_mod_noncoprime[8][i] * 10) % 8 == pre_mod_noncoprime[8][i+1]:
                    count_here += 1
            if i >= 2 and pre_mod_noncoprime[8][i+1] % 8 == 0:
                # All substrings with length >= 3 counted by number of starting indices j (0 <= j <= i-1) excluding the one for length=2
                count_here += (i - 1)
            total += count_here
    return total

# Example usage:
print(countSubstringsDivisible("12936"))  # Expected output: 11

← Back to All Questions