Skip to content

3448. Count Substrings Divisible By Last Digit 👍

Approach 1: 3D DP

  • Time: $O(10^2n) = O(n)$
  • Space: $O(10^2n) = O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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

Approach 2: 2D DP

  • Time: $O(10^2n) = O(n)$
  • Space: $O(10n) = O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  long long countSubstrings(string s) {
    long ans = 0;
    // dp[num][rem] := the number of substrings so far that have a remainder of
    // `rem` when divided by `num`
    vector<vector<int>> dp(10, vector<int>(10));

    for (const char c : s) {
      const int digit = c - '0';
      vector<vector<int>> newDp(10, vector<int>(10));
      for (int num = 1; num < 10; ++num) {
        for (int rem = 0; rem < num; ++rem)
          newDp[num][(rem * 10 + digit) % num] += dp[num][rem];
        ++newDp[num][digit % num];
      }
      dp = std::move(newDp);
      ans += dp[digit][0];
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
  public long countSubstrings(String s) {
    long ans = 0;
    // dp[num][rem] := the number of substrings so far that have a remainder of
    // `rem` when divided by `num`
    int[][] dp = new int[10][10];

    for (final char c : s.toCharArray()) {
      final int digit = c - '0';
      int[][] newDp = new int[10][10];
      for (int num = 1; num < 10; ++num) {
        for (int rem = 0; rem < num; ++rem)
          newDp[num][(rem * 10 + digit) % num] += dp[num][rem];
        ++newDp[num][digit % num];
      }
      dp = newDp;
      ans += dp[digit][0];
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
  def countSubstrings(self, s: str) -> int:
    ans = 0
    # dp[num][rem] := the number of substrings so far that have a remainder of
    # `rem` when divided by `num`
    dp = [[0] * 10 for _ in range(10)]

    for c in s:
      digit = int(c)
      newDp = [[0] * 10 for _ in range(10)]
      for num in range(1, 10):
        for rem in range(num):
          newDp[num][(rem * 10 + digit) % num] += dp[num][rem]
        newDp[num][digit % num] += 1
      dp = newDp
      ans += dp[digit][0]

    return ans