Count Substrings Divisible By Last Digit - Practice Coding Problems

Count Substrings Divisible By Last Digit - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: s = "123"

› Output: 5

💡 Note: Valid substrings: "1" (1÷1=0), "2" (2÷2=0), "3" (3÷3=0), "12" (12÷2=0), "123" (123÷3=0). Total: 5.

Example 2 — With Zeros

$ Input: s = "1020"

› Output: 3

💡 Note: Valid substrings: "1" (1÷1=0), "2" (2÷2=0), "102" (102÷2=0). Substrings ending in 0 are skipped.

Example 3 — Single Digit

$ Input: s = "5"

› Output: 1

💡 Note: Only one substring "5", and 5÷5=0, so count is 1.

Constraints

1 ≤ s.length ≤ 10³
s consists of digits only

Visualization

Tap to expand

Understanding the Visualization

Input

String of digits like '123'

Process

Check each substring against its last digit

Output

Count of valid divisible substrings

Key Takeaway

🎯 Key Insight: Use modular arithmetic to avoid overflow while checking substring divisibility

Asked in

G Google 25 M Microsoft 18 a Amazon 15

The key insight is to use modular arithmetic to avoid integer overflow when checking divisibility. We build the remainder incrementally using (remainder × 10 + digit) % last_digit. Best approach uses modular arithmetic with Time: O(n²), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n³)	O(1)	Generate all substrings, convert to numbers, check divisibility
Modular Arithmetic Optimization	O(n²)	O(1)	Use modular arithmetic to avoid integer conversion

Brute Force — Algorithm Steps

Generate all possible substrings
Convert each substring to integer
Check if divisible by last digit
Count valid substrings

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate

Create all possible substrings

Convert

Convert each to integer

Check

Test divisibility by last digit

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(char* s) {
    int count = 0;
    int n = strlen(s);
    
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            char substring[1001];
            strncpy(substring, s + i, j - i + 1);
            substring[j - i + 1] = '\0';
            
            int lastDigit = substring[strlen(substring) - 1] - '0';
            
            // Skip if last digit is 0
            if (lastDigit == 0) continue;
            
            // Convert substring to number and check divisibility
            long long num = atoll(substring);
            if (num % lastDigit == 0) {
                count++;
            }
        }
    }
    
    return count;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    int result = solution(s);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

O(n²) substrings, each taking O(n) time to convert to integer

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

32.0K Views

Medium Frequency

~25 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler