Count Substrings Divisible By Last Digit
Source: leetcode
Difficulty: Hard
Tags: string, dynamic-programming

You are given a string `s` consisting of digits.


Return the **number** of substrings of `s` **divisible** by their **non\-zero** last digit.


**Note**: A substring may contain leading zeros.


 


**Example 1:**



**Input:** s \= "12936"


**Output:** 11


**Explanation:**


Substrings `"29"`, `"129"`, `"293"` and `"2936"` are not divisible by their last digit. There are 15 substrings in total, so the answer is `15 - 4 = 11`.



**Example 2:**



**Input:** s \= "5701283"


**Output:** 18


**Explanation:**


Substrings `"01"`, `"12"`, `"701"`, `"012"`, `"128"`, `"5701"`, `"7012"`, `"0128"`, `"57012"`, `"70128"`, `"570128"`, and `"701283"` are all divisible by their last digit. Additionally, all substrings that are just 1 non\-zero digit are divisible by themselves. Since there are 6 such digits, the answer is `12 + 6 = 18`.



**Example 3:**



**Input:** s \= "1010101010"


**Output:** 25


**Explanation:**


Only substrings that end with digit `'1'` are divisible by their last digit. There are 25 such substrings.



 


**Constraints:**


- `1 <= s.length <= 105`
- `s` consists of digits only.




C++ solution:
class Solution {
public:
    long long countSubstrings(string s) {
        int n = s.size();
        long long ans = 0;
        vector<long long> freq3(3,0), freq9(9,0), freq7(7,0);
        freq3[0] = 1;
        freq9[0] = 1;
        freq7[0] = 1;
        int cur3 = 0, cur9 = 0;
        int P7 = 0;
        vector<int> power7(n+1, 0);
        power7[0] = 1;
        for (int i = 1; i <= n; i++){
            power7[i] = (power7[i-1] * 10) % 7;
        }
        int inv7[7];
        inv7[1] = 1;
        inv7[2] = 4;
        inv7[3] = 5;
        inv7[4] = 2;
        inv7[5] = 3;
        inv7[6] = 6;
        for (int j = 0; j < n; j++){
            int d = s[j] - '0';
            cur3 = (cur3 + d) % 3;
            cur9 = (cur9 + d) % 9;
            P7 = (P7 * 10 + d) % 7;
            int q = (int)((long long)P7 * inv7[ power7[j+1] ] % 7);
            if(d == 0){
            } else if(d == 1 || d == 2 || d == 5){
                ans += (j + 1);
            } else if(d == 3 || d == 6){
                ans += freq3[cur3];
            } else if(d == 9){
                ans += freq9[cur9];
            } else if(d == 4){
                int contrib = 1;
                if(j >= 1){
                    int two_digit = ((s[j-1]-'0') * 10 + 4);
                    if(two_digit % 4 == 0)
                        contrib += j;
                }
                ans += contrib;
            } else if(d == 8){
                int contrib = 1;
                if(j >= 1){
                    int two_digit = ((s[j-1]-'0') * 10 + 8);
                    if(two_digit % 8 == 0)
                        contrib += 1;
                }
                if(j >= 2){
                    int three_digit = ((s[j-2]-'0') * 100 + (s[j-1]-'0') * 10 + 8);
                    if(three_digit % 8 == 0)
                        contrib += (j - 1);
                }
                ans += contrib;
            } else if(d == 7){
                ans += freq7[q];
            }
            freq3[cur3]++;
            freq9[cur9]++;
            freq7[q]++;
        }
        return ans;
    }
};

Go solution:
func countSubstrings(s string) int64 {
	n := len(s)
	var ans int64
	var freq3 [3]int
	var freq9 [9]int
	var freq7 [7]int
	// initial prefix values for mod3, mod9 and mod7
	p3, p9, p7 := 0, 0, 0
	freq3[0] = 1
	freq9[0] = 1
	freq7[0] = 1
	// Precomputed modular inverses for 10^i mod 7 (period 6):
	// 10^0 mod7=1 (inv 1), 10^1 mod7=3 (inv 5), 10^2=2 (inv 4),
	// 10^3=6 (inv 6), 10^4=4 (inv 2), 10^5=5 (inv 3)
	inv7 := [6]int{1, 5, 4, 6, 2, 3}
	
	for j := 0; j < n; j++ {
		digit := int(s[j] - '0')
		// Update prefix sums.
		newP3 := (p3 + digit) % 3
		newP9 := (p9 + digit) % 9
		newP7 := (p7*10 + digit) % 7
		// Compute transformed value for mod7: F7(x)= prefix7(x)*inv(10^x mod7) mod7.
		r7 := (newP7 * inv7[(j+1)%6]) % 7
		
		switch digit {
		case 0:
			// Last digit 0: skip.
		case 1:
			// Divisible by 1 always.
			ans += int64(j + 1)
		case 2:
			// Any number ending in 2 is even.
			ans += int64(j + 1)
		case 3:
			// Number divisible by 3 if prefix3[j+1]==prefix3[i] for some i.
			ans += int64(freq3[newP3])
		case 4:
			// Divisibility by 4: one-digit substring always qualifies (4 mod4=0).
			// For substrings of length>=2, last two digits decide.
			cnt := 1
			if j >= 1 {
				twoDigit := (int(s[j-1]-'0') * 10) + digit
				if twoDigit%4 == 0 {
					cnt += j
				}
			}
			ans += int64(cnt)
		case 5:
			// Any number ending in 5 is divisible by 5.
			ans += int64(j + 1)
		case 6:
			// Ending in 6: even automatically, so check divisibility by 3.
			ans += int64(freq3[newP3])
		case 7:
			// Use mod7 transformation.
			ans += int64(freq7[r7])
		case 8:
			// Divisible by 8: check one-digit, two-digit and length>=3 (last three digits).
			cnt := 1
			if j >= 1 {
				twoDigit := (int(s[j-1]-'0') * 10) + digit
				if twoDigit%8 == 0 {
					cnt += 1
				}
			}
			if j >= 2 {
				threeDigit := (int(s[j-2]-'0')*100 + int(s[j-1]-'0')*10 + digit)
				if threeDigit%8 == 0 {
					cnt += j - 1
				}
			}
			ans += int64(cnt)
		case 9:
			// Divisible by 9 if prefix9[j+1]==prefix9[i] for some i.
			ans += int64(freq9[newP9])
		}
		// Update frequency arrays for prefixes.
		freq3[newP3]++
		freq9[newP9]++
		freq7[r7]++
		p3, p9, p7 = newP3, newP9, newP7
	}
	return ans
}

Java solution:
class Solution {
    public long countSubstrings(String s) {
        int n = s.length();
        long ans = 0;
        long[] freq3 = new long[3];
        freq3[0] = 1;
        long[] freq9 = new long[9];
        freq9[0] = 1;
        long[][] freq7 = new long[6][7];
        freq7[0][0] = 1;
        int mod3 = 0, mod9 = 0, mod7 = 0;
        int[] inv7 = {1, 5, 4, 6, 2, 3};
        for (int j = 0; j < n; j++) {
            int d = s.charAt(j) - '0';
            mod3 = (mod3 + d) % 3;
            mod9 = (mod9 + d) % 9;
            mod7 = (mod7 * 10 + d) % 7;
            int k = j + 1, kMod = k % 6;
            char c = s.charAt(j);
            if (c == '0') {
            } else if (c == '1') {
                ans += (j + 1);
            } else if (c == '2') {
                ans += (j + 1);
            } else if (c == '5') {
                ans += (j + 1);
            } else if (c == '3') {
                ans += freq3[mod3];
            } else if (c == '6') {
                ans += freq3[mod3];
            } else if (c == '9') {
                ans += freq9[mod9];
            } else if (c == '4') {
                long add = 1;
                if (j >= 1) {
                    int prev = s.charAt(j - 1) - '0';
                    int two = prev * 10 + 4;
                    if (two % 4 == 0)
                        add += j;
                }
                ans += add;
            } else if (c == '8') {
                long add = 1;
                if (j >= 1) {
                    int prev = s.charAt(j - 1) - '0';
                    int two = prev * 10 + 8;
                    if (two % 8 == 0)
                        add += 1;
                }
                if (j >= 2) {
                    int d1 = s.charAt(j - 2) - '0';
                    int d2 = s.charAt(j - 1) - '0';
                    int three = d1 * 100 + d2 * 10 + 8;
                    if (three % 8 == 0)
                        add += (j - 1);
                }
                ans += add;
            } else if (c == '7') {
                for (int r = 0; r < 6; r++) {
                    int L0 = (kMod - r + 6) % 6;
                    int target = (mod7 * inv7[L0]) % 7;
                    ans += freq7[r][target];
                }
            }
            freq3[mod3]++;
            freq9[mod9]++;
            freq7[kMod][mod7]++;
        }
        return ans;
    }
}

JavaScript solution:
"use strict";
var countSubstrings = function(s) {
    const n = s.length;
    const toDigit = ch => ch.charCodeAt(0) - 48;
    let total = 0;
    // d = 1,2,5: every substring ending in these digits qualifies.
    for (let d of [1, 2, 5]) {
        for (let j = 0; j < n; j++) {
            if (toDigit(s[j]) === d) total += (j + 1);
        }
    }
    // d = 3 (10 mod3 = 1): condition: (prefix[j+1] - prefix[i]*1)==0 <=> prefix[j+1]==prefix[i]
    {
        const mod = 3;
        let freq = new Array(mod).fill(0);
        let prefix = 0;
        freq[prefix]++;
        for (let j = 0; j < n; j++) {
            let dgt = toDigit(s[j]);
            prefix = (prefix * 10 + dgt) % mod;
            if (dgt === 3) total += freq[prefix];
            freq[prefix]++;
        }
    }
    // d = 9 (10 mod9 = 1): similar to d=3.
    {
        const mod = 9;
        let freq = new Array(mod).fill(0);
        let prefix = 0;
        freq[prefix]++;
        for (let j = 0; j < n; j++) {
            let dgt = toDigit(s[j]);
            prefix = (prefix * 10 + dgt) % mod;
            if (dgt === 9) total += freq[prefix];
            freq[prefix]++;
        }
    }
    // d = 7 (coprime with 10): use Q = prefix * inv(10^k) mod7.
    {
        const mod = 7;
        // Precomputed inverses modulo7 for 1..6.
        const inv = [0, 1, 4, 5, 2, 3, 6];
        let freq = new Array(mod).fill(0);
        let prefix = 0, p = 1;
        let Q = 0; // for k=0: prefix=0, so Q=0.
        freq[Q]++;
        for (let j = 0; j < n; j++) {
            let dgt = toDigit(s[j]);
            prefix = (prefix * 10 + dgt) % mod;
            p = (p * 10) % mod;
            let invP = inv[p];
            Q = (prefix * invP) % mod;
            if (Q < 0) Q += mod;
            if (dgt === 7) total += freq[Q];
            freq[Q]++;
        }
    }
    // d = 6 (10^e mod6 = 4 for any positive exponent)
    {
        const mod = 6;
        let freq = new Array(mod).fill(0);
        let cur = 0; // f(0)
        freq[cur]++;
        for (let j = 0; j < n; j++) {
            let dgt = toDigit(s[j]);
            let newVal = (cur * 10 + dgt) % mod;
            if (dgt === 6) {
                let qsum = 0;
                for (let r = 0; r < mod; r++) {
                    if ((4 * r) % mod === newVal) qsum += freq[r];
                }
                // Exclude the case i == j; f(j) is stored as 'cur'
                if ((4 * cur) % mod === newVal) qsum -= 1;
                total += (qsum + 1);
            }
            freq[newVal]++;
            cur = newVal;
        }
    }
    // d = 4: 10^0=1, 10^1 mod4=2, and 10^k mod4=0 for k>=2.
    {
        const mod = 4;
        let prefixArr = new Array(n + 1);
        prefixArr[0] = 0;
        for (let i = 0; i < n; i++) {
            let dgt = toDigit(s[i]);
            prefixArr[i + 1] = (prefixArr[i] * 10 + dgt) % mod;
        }
        for (let j = 0; j < n; j++) {
            if (toDigit(s[j]) === 4) {
                let cnt = 0;
                cnt++; // L = 0: single digit.
                if (j >= 1) {
                    let twoDig = parseInt(s.substring(j - 1, j + 1), 10);
                    if (twoDig % 4 === 0) cnt++;
                }
                if (j >= 2 && prefixArr[j + 1] % mod === 0) {
                    cnt += (j - 1);
                }
                total += cnt;
            }
        }
    }
    // d = 8: 10^0=1, 10^1 mod8=2, 10^2 mod8=4, and 10^k mod8=0 for k>=3.
    {
        const mod = 8;
        let prefixArr = new Array(n + 1);
        prefixArr[0] = 0;
        for (let i = 0; i < n; i++) {
            let dgt = toDigit(s[i]);
            prefixArr[i + 1] = (prefixArr[i] * 10 + dgt) % mod;
        }
        for (let j = 0; j < n; j++) {
            if (toDigit(s[j]) === 8) {
                let cnt = 0;
                cnt++; // L = 0.
                if (j >= 1) {
                    let twoDig = parseInt(s.substring(j - 1, j + 1), 10);
                    if (twoDig % 8 === 0) cnt++;
                }
                if (j >= 2) {
                    let threeDig = parseInt(s.substring(j - 2, j + 1), 10);
                    if (threeDig % 8 === 0) cnt++;
                }
                if (j >= 3 && prefixArr[j + 1] % mod === 0) {
                    cnt += (j - 2);
                }
                total += cnt;
            }
        }
    }
    return total;
};

Python solution:
class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        ans = 0
        freq3 = {0: 1}
        p3 = 0
        freq9 = {0: 1}
        p9 = 0
        freq7 = {0: 1}
        p7 = 0
        power7 = 1
        for j in range(n):
            d = ord(s[j]) - 48
            p3 = (p3 + d) % 3
            p9 = (p9 + d) % 9
            p7 = (p7 * 10 + d) % 7
            power7 = (power7 * 10) % 7
            inv_power7 = pow(power7, -1, 7)
            q7 = (p7 * inv_power7) % 7
            ch = s[j]
            if ch == '0':
                pass
            elif ch in "125":
                ans += (j + 1)
            elif ch in "36":
                ans += freq3.get(p3, 0)
            elif ch == '9':
                ans += freq9.get(p9, 0)
            elif ch == '4':
                if j == 0:
                    ans += 1
                else:
                    two = ((ord(s[j - 1]) - 48) * 10 + 4)
                    if two % 4 == 0:
                        ans += 1 + j
                    else:
                        ans += 1
            elif ch == '8':
                if j == 0:
                    ans += 1
                elif j == 1:
                    two = ((ord(s[j - 1]) - 48) * 10 + 8)
                    if two % 8 == 0:
                        ans += 2
                    else:
                        ans += 1
                else:
                    two = ((ord(s[j - 1]) - 48) * 10 + 8)
                    three = ((ord(s[j - 2]) - 48) * 100 + (ord(s[j - 1]) - 48) * 10 + 8)
                    tmp = 1
                    if two % 8 == 0:
                        tmp += 1
                    if three % 8 == 0:
                        tmp += (j - 1)
                    ans += tmp
            elif ch == '7':
                ans += freq7.get(q7, 0)
            freq3[p3] = freq3.get(p3, 0) + 1
            freq9[p9] = freq9.get(p9, 0) + 1
            freq7[q7] = freq7.get(q7, 0) + 1
        return ans

Ruby solution:
# @param {String} s
# @return {Integer}
def count_substrings(s)
  n = s.length
  ans = 0

  # Frequencies for prefix sums modulo 3, 9
  # freq[k] stores the count of indices i (including 0) such that PrefixSum(i) % mod == k
  # PrefixSum(i) is sum of digits s[0...i]. PrefixSum(0) = 0.
  # A substring s[i..j] is divisible by 3 (or 9) iff PrefixSum(j+1) % mod == PrefixSum(i) % mod.
  freq3 = { 0 => 1 } # Base case: PrefixSum(0) = 0, count is 1 for index i=0.
  cur3 = 0 # Current PrefixSum(j+1) % 3
  
  freq9 = { 0 => 1 } # Base case: PrefixSum(0) = 0
  cur9 = 0 # Current PrefixSum(j+1) % 9

  # Frequencies for transformed prefix values modulo 7
  # freq7[q] stores the count of indices i (including 0) such that Q[i] == q
  # Q[k] = (PrefixValue(k) * (10^k)^(-1)) % 7
  # PrefixValue(k) is the numerical value of s[0...k]. PrefixValue(0) = 0.
  # A substring s[i..j] is divisible by 7 iff Q[j+1] == Q[i].
  freq7 = { 0 => 1 } # Base case: Q[0] = (PrefixValue(0) * (10^0)^-1) % 7 = (0 * 1) % 7 = 0
  cur_p7 = 0 # Current PrefixValue(j+1) % 7
  current_power10_mod7 = 1 # Represents 10^k % 7, starts with k=0 for PrefixValue(0)

  (0...n).each do |j|
    d = s[j].to_i

    # Update prefix sums/values modulo 3, 9, 7 for index j+1
    cur3 = (cur3 + d) % 3
    cur9 = (cur9 + d) % 9
    cur_p7 = (cur_p7 * 10 + d) % 7

    # Update power of 10 mod 7 for the current index j+1
    # This is 10^(j+1) % 7
    current_power10_mod7 = (current_power10_mod7 * 10) % 7
    
    # Compute Q[j+1] for mod 7 logic
    # Q[j+1] = (cur_p7 * (current_power10_mod7)^(-1)) % 7
    # Modular inverse using Fermat's Little Theorem: a^(p-2) mod p since 7 is prime.
    # The inverse is a^5 mod 7.
    inv_power10 = current_power10_mod7.pow(5, 7)
    q7 = (cur_p7 * inv_power10) % 7

    # Check divisibility based on last digit d
    if d != 0
      if d == 1 || d == 2 || d == 5
        # Any number ending in d is divisible by d.
        # All substrings s[i..j] for 0 <= i <= j count. There are j+1 such substrings.
        ans += (j + 1)
      elsif d == 3 || d == 6
        # Divisible by 3 (and 2 if d=6, which is guaranteed as it ends in 6).
        # Count indices i <= j such that PrefixSum(j+1)%3 == PrefixSum(i)%3.
        ans += freq3.fetch(cur3, 0)
      elsif d == 9
        # Divisible by 9.
        # Count indices i <= j such that PrefixSum(j+1)%9 == PrefixSum(i)%9.
        ans += freq9.fetch(cur9, 0)
      elsif d == 4
        # Divisible by 4 depends on last 1 or 2 digits.
        contrib = 1 # Substring s[j..j] = "4" always counts (4 % 4 == 0).
        if j >= 1
          prev_d = s[j-1].to_i
          two_digit = prev_d * 10 + 4
          # If last two digits form a number divisible by 4, all substrings s[i..j] with i < j count.
          # These are substrings of length >= 2 ending at j. There are j such substrings (i from 0 to j-1).
          contrib += j if two_digit % 4 == 0 
        end
        ans += contrib
      elsif d == 8
        # Divisible by 8 depends on last 1, 2 or 3 digits.
        contrib = 1 # Substring s[j..j] = "8" always counts (8 % 8 == 0).
        if j >= 1
          prev_d = s[j-1].to_i
          two_digit = prev_d * 10 + 8
          # Substring s[j-1..j] counts if divisible by 8.
          contrib += 1 if two_digit % 8 == 0 
        end
        if j >= 2
          prev2_d = s[j-2].to_i
          prev_d = s[j-1].to_i
          three_digit = prev2_d * 100 + prev_d * 10 + 8
          # If last three digits form a number divisible by 8, all substrings s[i..j] with i <= j-2 count.
          # These are substrings of length >= 3 ending at j. There are j-1 such substrings (i from 0 to j-2).
          contrib += (j - 1) if three_digit % 8 == 0 
        end
        ans += contrib
      elsif d == 7
        # Divisible by 7.
        # Count indices i <= j such that Q[j+1] == Q[i].
        ans += freq7.fetch(q7, 0)
      end
    end

    # Update frequency maps. The current properties (cur3, cur9, q7) correspond to index j+1.
    # We store the frequency of properties associated with indices 0 up to j+1.
    freq3[cur3] = freq3.fetch(cur3, 0) + 1
    freq9[cur9] = freq9.fetch(cur9, 0) + 1
    freq7[q7] = freq7.fetch(q7, 0) + 1
  end

  ans
end