3448. Count Substrings Divisible By Last Digit LeetCode Solution

Last updated: March 6, 2025

In this guide, you will get 3448. Count Substrings Divisible By Last Digit LeetCode Solution with the best time and space complexity. The solution to Count Substrings Divisible By Last Digit problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Count Substrings Divisible By Last Digit solution in C++
Count Substrings Divisible By Last Digit solution in Java
Count Substrings Divisible By Last Digit solution in Python
Additional Resources

3448. Count Substrings Divisible By Last Digit LeetCode Solution image

Problem Statement of Count Substrings Divisible By Last Digit

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.

Complexity Analysis

Time Complexity: O(10^2n) = O(n)
Space Complexity: O(10^2n) = O(n)

3448. Count Substrings Divisible By Last Digit LeetCode Solution in C++

class Solution {
 public:
  long long countSubstrings(string s) {
    long ans = 0;
    // dp[i][num][rem] := the number of first `i` digits of s that have a
    // remainder of `rem` when divided by `num`
    vector<vector<vector<int>>> dp(s.length() + 1,
                                   vector<vector<int>>(10, vector<int>(10)));

    for (int i = 1; i <= s.length(); ++i) {
      const int digit = s[i - 1] - '0';
      for (int num = 1; num < 10; ++num) {
        for (int rem = 0; rem < num; ++rem)
          dp[i][num][(rem * 10 + digit) % num] += dp[i - 1][num][rem];
        ++dp[i][num][digit % num];
      }
      ans += dp[i][digit][0];
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

3448. Count Substrings Divisible By Last Digit LeetCode Solution in Java

class Solution {
  public long countSubstrings(String s) {
    long ans = 0;
    // dp[i][num][rem] := the number of first `i` digits of s that have a
    // remainder of `rem` when divided by `num`
    int[][][] dp = new int[s.length() + 1][10][10];

    for (int i = 1; i <= s.length(); ++i) {
      final int digit = s.charAt(i - 1) - '0';
      for (int num = 1; num < 10; ++num) {
        for (int rem = 0; rem < num; ++rem)
          dp[i][num][(rem * 10 + digit) % num] += dp[i - 1][num][rem];
        ++dp[i][num][digit % num];
      }
      ans += dp[i][digit][0];
    }

    return ans;
  }
}
// code provided by PROGIEZ

3448. Count Substrings Divisible By Last Digit LeetCode Solution in Python

class Solution:
  def countSubstrings(self, s: str) -> int:
    ans = 0
    # dp[i][num][rem] := the number of first `i` digits of s that have a
    # remainder of `rem` when divided by `num`
    dp = [[[0] * 10 for _ in range(10)] for _ in range(len(s) + 1)]

    for i in range(1, len(s) + 1):
      digit = int(s[i - 1])
      for num in range(1, 10):
        for rem in range(num):
          dp[i][num][(rem * 10 + digit) % num] += dp[i - 1][num][rem]
        dp[i][num][digit % num] += 1
      ans += dp[i][digit][0]

    return ans
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents