Number of Divisible Substrings

Number of Divisible Substrings

What is this problem about?

The Number of Divisible Substrings problem gives you a string of digits and asks how many substrings represent numbers divisible by their length. This coding problem maps digits to values, computes prefix sums, and uses a hash map to count valid substrings efficiently.

Why is this asked in interviews?

Amdocs, Paytm, Wayfair, and IBM ask this to test prefix sum with hash map counting — a powerful pattern for counting substrings satisfying a numeric property. The hash table, counting, string, and prefix sum interview pattern is the core, and the mapping from characters to numeric values is an additional twist.

Algorithmic pattern used

Digit-to-value mapping + prefix sum hash map. Map each digit character to a value (e.g., 'a'→1, 'b'→2, etc. or digit→its numeric value). For a substring of length L starting at position i, the sum S divided by L must be an integer. Rearranging: for each possible divisor d (1 to 9 for single digits), count substrings where sum(s[i..j]) - d*(j-i+1) == 0. Using prefix sums P, this becomes P[j+1] - P[i] == d*(j-i+1) → P[j+1] - d*(j+1) == P[i] - d*i. Use a hash map of (P[i] - d*i) values for each d.

Example explanation

s = "1248". Map digits to values: 1,2,4,8. For d=1: prefix sums = [0,1,3,7,15]. P[j]-1*j values: 0-0=0,1-1=0,3-2=1,7-3=4,15-4=11. Hash map accumulates; count pairs. For d=2: check substrings where avg=2... Continue for all d from 1-9. Sum all counts.

Common mistakes candidates make

• Checking each substring sum individually (O(n²)).
• Not iterating over all possible divisor values d.
• Incorrect prefix sum formula — forgetting to subtract d * i from the hash key.
• Integer overflow in prefix sum computation.

Interview preparation tip

Substring property problems with "sum divided by length equals constant d" always reduce to prefix sums. Rearrange to get P[j] - d*j == P[i] - d*i. Count pairs using a hash map. This technique generalizes to "count subarrays with average = k" and "count subarrays with sum divisible by k." Practice this rearrangement technique — it converts a quadratic substring scan to linear hash-map counting across many interview problems.