Count Substrings Divisible By Last Digit - Solution & Explanation

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.