We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Substrings Divisible By Last Digit

Difficulty: Hard

Problem Description

You are given a string s consisting of digits. Return the number of substrings of s divisible by their non-zero last digit. A substring may contain leading zeros.

Key Insights

  • A substring's divisibility by its last digit depends on the value of the last digit.
  • Substrings that end with the digit '0' are ignored since they cannot be non-zero divisors.
  • Every non-zero digit can be checked as a potential divisor for the substrings ending with it.
  • We can iterate through the string while keeping track of the last digit and count valid substrings.

Space and Time Complexity

Time Complexity: O(n^2) in the worst case, where n is the length of the string. This is due to checking each substring explicitly. However, optimizations can reduce this in practice. Space Complexity: O(1) since we are using a constant amount of space regardless of the input size.

Solution

We will use a nested loop approach to iterate through all possible substrings of the string. For each substring, we will check the last digit and determine if the substring is divisible by this last digit if the digit is non-zero. This will involve converting the substring to an integer to perform the divisibility check.

Code Solutions

def countSubstrings(s: str) -> int:
    count = 0
    n = len(s)

    for i in range(n):
        for j in range(i, n):
            # Extract the substring
            substring = s[i:j + 1]
            last_digit = int(substring[-1])
            if last_digit != 0:  # Only check if the last digit is non-zero
                if int(substring) % last_digit == 0:
                    count += 1

    return count
← Back to All Questions