Problem

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

1
2
3
4
5

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

1
2
3
4
5
6
7
8

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

1
2
3
4
5

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 <= 10^5
  • s consists of digits only.

Examples

Solution

Method 1 – Suffix Remainder Counting

Intuition

For each substring ending at position i, we want to check if the number formed by the substring is divisible by its last digit (if non-zero). Instead of checking all substrings, we can process from right to left, keeping track of remainders for each possible last digit.

Approach

  1. Iterate from right to left in the string.
  2. For each position i, treat s[i] as the last digit d (skip if d == 0).
  3. For each possible substring ending at i, keep a count of remainders modulo d.
  4. Use a hash map or array to count how many suffixes have a given remainder for each digit.
  5. For each i, add the count of substrings ending at i that are divisible by d.
  6. Sum up the results for all positions.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    long long countDivisibleSubstrings(string s) {
        long long ans = 0;
        int n = s.size();
        for (int d = 1; d <= 9; ++d) {
            vector<int> cnt(d, 0);
            int rem = 0, p = 1;
            for (int i = n-1; i >= 0; --i) {
                rem = (rem + (s[i]-'0') * p) % d;
                if (s[i]-'0' == d) ans++;
                ans += cnt[rem];
                cnt[rem]++;
                p = (p * 10) % d;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

type Solution struct{}
func (Solution) CountDivisibleSubstrings(s string) int64 {
    var ans int64
    n := len(s)
    for d := 1; d <= 9; d++ {
        cnt := make([]int, d)
        rem, p := 0, 1
        for i := n-1; i >= 0; i-- {
            rem = (rem + int(s[i]-'0')*p) % d
            if int(s[i]-'0') == d {
                ans++
            }
            ans += int64(cnt[rem])
            cnt[rem]++
            p = (p * 10) % d
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public long countDivisibleSubstrings(String s) {
        long ans = 0;
        int n = s.length();
        for (int d = 1; d <= 9; ++d) {
            int[] cnt = new int[d];
            int rem = 0, p = 1;
            for (int i = n-1; i >= 0; --i) {
                rem = (rem + (s.charAt(i)-'0') * p) % d;
                if (s.charAt(i)-'0' == d) ans++;
                ans += cnt[rem];
                cnt[rem]++;
                p = (p * 10) % d;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun countDivisibleSubstrings(s: String): Long {
        var ans = 0L
        val n = s.length
        for (d in 1..9) {
            val cnt = IntArray(d)
            var rem = 0
            var p = 1
            for (i in n-1 downTo 0) {
                rem = (rem + (s[i]-'0') * p) % d
                if ((s[i]-'0') == d) ans++
                ans += cnt[rem]
                cnt[rem]++
                p = (p * 10) % d
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def countDivisibleSubstrings(self, s: str) -> int:
        ans = 0
        n = len(s)
        for d in range(1, 10):
            cnt = [0] * d
            rem = 0
            p = 1
            for i in range(n-1, -1, -1):
                rem = (rem + int(s[i]) * p) % d
                if int(s[i]) == d:
                    ans += 1
                ans += cnt[rem]
                cnt[rem] += 1
                p = (p * 10) % d
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

impl Solution {
    pub fn count_divisible_substrings(s: String) -> i64 {
        let n = s.len();
        let s = s.as_bytes();
        let mut ans = 0i64;
        for d in 1..=9 {
            let mut cnt = vec![0; d];
            let mut rem = 0;
            let mut p = 1;
            for i in (0..n).rev() {
                rem = (rem + (s[i] - b'0') as usize * p) % d;
                if (s[i] - b'0') as usize == d {
                    ans += 1;
                }
                ans += cnt[rem] as i64;
                cnt[rem] += 1;
                p = (p * 10) % d;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    countDivisibleSubstrings(s: string): number {
        let ans = 0;
        const n = s.length;
        for (let d = 1; d <= 9; ++d) {
            const cnt = Array(d).fill(0);
            let rem = 0, p = 1;
            for (let i = n-1; i >= 0; --i) {
                rem = (rem + Number(s[i]) * p) % d;
                if (Number(s[i]) === d) ans++;
                ans += cnt[rem];
                cnt[rem]++;
                p = (p * 10) % d;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(9 * n) because for each digit 1-9, we scan the string once.
  • 🧺 Space complexity: O(n) for counters per digit.