Skip to main content
Talentd

Count Substrings Divisible By Last Digit - Solution & Explanation

HardStringDynamic Programming3 min readAsked at: Google
Practice this problem

Problem Statement

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.

Approach Overview

Problem Overview: Given a string of digits, count every substring where the integer value of the substring is divisible by its last digit. Substrings ending with digit 0 are ignored because division by zero is invalid. The challenge is evaluating divisibility efficiently without converting every substring to an integer.

Approach 1: Brute Force Enumeration (O(n^2) time, O(1) space)

Generate every substring ending at each index and compute its numeric value incrementally. For each ending index i, extend the substring backward and maintain the current value using base‑10 expansion. If the last digit d is non‑zero and the substring value modulo d equals zero, increment the count. This approach directly follows the problem definition but requires checking up to O(n^2) substrings, which becomes too slow for large inputs.

Approach 2: Dynamic Programming with Remainder States (O(n) time, O(1) space)

The key observation: the last digit d determines the divisibility rule. Since d ranges from 1 to 9, track substring remainders for each possible modulus. Maintain counts of substrings ending at the current position with remainder r modulo d. When a new digit x appears, update remainders using the transition new_r = (old_r * 10 + x) % d. Also start a new single‑digit substring at the current index.

This effectively builds all substrings ending at the current index without explicitly enumerating them. For the current last digit d, any substring ending here with remainder 0 modulo d is valid. Because d is at most 9, the number of states is constant, making the algorithm linear. The technique is a classic remainder DP pattern often used in dynamic programming problems involving divisibility.

The algorithm iterates through the string once, updating remainder counts for moduli 1 through 9. Each step processes a constant number of states, so the total complexity stays O(n) with constant memory.

Recommended for interviews: Start by explaining the brute force idea to demonstrate understanding of substring enumeration. Then pivot to the optimized remainder‑tracking DP. Interviewers expect candidates to recognize that the divisor is limited (1–9) and exploit that constraint to keep only a small set of remainder states. This shows strong problem‑solving and optimization skills.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Substring EnumerationO(n^2)O(1)Small input sizes or when first reasoning about the problem
Dynamic Programming with Remainder TrackingO(n)O(1)General case and interview‑ready optimal solution

Video Solution

3448. Count Substrings Divisible By Last Digit | 3D DP | With Dry Run • Aryan Mittal • 3,552 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Count Substrings Divisible By Last Digit easy or hard?
LeetCode classifies this problem as Hard with an acceptance rate around 23%. The difficulty comes from recognizing that brute force substring checks are too slow and exploiting the small range of possible divisors with a remainder‑based DP optimization.
Count Substrings Divisible By Last Digit Python/Java solution
Most implementations maintain a small DP table indexed by modulus and remainder. Each iteration updates the table using the formula (old_r * 10 + digit) % d and accumulates counts where the remainder becomes zero for the current last digit. The same logic translates cleanly to Python, Java, C++, and Go.
How to solve Count Substrings Divisible By Last Digit in O(n)?
Iterate through the digit string once and maintain counts of substring remainders for mod values 1 through 9. When adding a new digit x, update states using the transition (old_remainder * 10 + x) % d. For the current last digit d (non‑zero), every substring ending here with remainder 0 modulo d contributes to the answer.
What is the best approach for Count Substrings Divisible By Last Digit?
The optimal solution uses dynamic programming with remainder tracking. For each digit position, track how many substrings ending there produce each remainder for mod values 1 through 9. When the current last digit is d, count substrings whose remainder modulo d equals 0. Because the divisor range is small, the algorithm runs in O(n) time with constant space.
Is Count Substrings Divisible By Last Digit asked at Google/Amazon/Meta?
Problems involving substring divisibility and remainder tracking appear in interviews at large companies such as Google, Amazon, and Meta. Variants often test understanding of modular arithmetic, prefix states, and dynamic programming over strings.
What data structure is used in Count Substrings Divisible By Last Digit?
The solution primarily uses arrays or small fixed counters to store remainder frequencies for each modulus from 1 to 9. This behaves like a compact dynamic programming table where each state tracks how many substrings produce a specific remainder.
What is the time complexity of Count Substrings Divisible By Last Digit?
The optimized approach runs in O(n) time where n is the length of the string. Each character updates a constant number of remainder states for mod values 1–9. Space complexity remains O(1) since the number of tracked states does not grow with input size.

Ready to solve this problem?

Practice Count Substrings Divisible By Last Digit with our built-in code editor and test cases.

Practice on FleetCode
Previous

Number of Divisible Substrings