Jobs

Interviews

Discussions

Number of Divisible Substrings

Medium

Asked by:

4 views

Topics:

ArraysStringsSliding Windows

Given a string s consisting of digits from '1' to '9' and a positive integer k, find the number of non-empty substrings of s such that the number it represents is divisible by k.

A substring is a contiguous sequence of characters within a string.

Since the answer may be very large, return it modulo 10⁹ + 7.

Example 1:

Input: s = "453", k = 3
Output: 4
Explanation: The substrings of s that are divisible by 3 are "453", "45", "53", and "3".

Example 2:

Input: s = "12", k = 2
Output: 2
Explanation: The substrings of s that are divisible by 2 are "12", and "2".

Example 3:

Input: s = "1234", k = 5
Output: 0
Explanation: There are no substrings of s that are divisible by 5.

Constraints:

1 <= s.length <= 3 * 10⁴
s[i] is a digit from '1' to '9'.
1 <= k <= 100

Try coding it in LeetCode

Number of Divisible Substrings

Medium

Asked by:

4 views

Topics:

ArraysStringsSliding Windows

Given a string s consisting of digits from '1' to '9' and a positive integer k, find the number of non-empty substrings of s such that the number it represents is divisible by k.

A substring is a contiguous sequence of characters within a string.

Since the answer may be very large, return it modulo 10⁹ + 7.

Example 1:

Input: s = "453", k = 3
Output: 4
Explanation: The substrings of s that are divisible by 3 are "453", "45", "53", and "3".

Example 2:

Input: s = "12", k = 2
Output: 2
Explanation: The substrings of s that are divisible by 2 are "12", and "2".

Example 3:

Input: s = "1234", k = 5
Output: 0
Explanation: There are no substrings of s that are divisible by 5.

Constraints:

1 <= s.length <= 3 * 10⁴
s[i] is a digit from '1' to '9'.
1 <= k <= 100

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the length of the string `num` and the value of the integer `divisor`?
Can the string `num` contain leading zeros, and if so, how should they be handled in the substrings?
Is the `divisor` guaranteed to be a positive integer?
If no substrings are divisible by the `divisor`, what should the return value be?
Are overlapping substrings considered distinct, or should each substring only be counted once?

Brute Force Solution

Approach

The brute force approach for this problem is simple: we will look at every possible substring within the given number string. For each substring, we will check if it meets the divisibility requirement.

Here's how the algorithm would work step-by-step:

Consider every substring that starts at the beginning of the main number string, one character at a time.
Next, consider every substring that starts at the second character of the main number string, again one character at a time.
Repeat this process, considering substrings that start at each possible position within the main number string.
For each substring we identify, convert it into a whole number.
Determine if the converted number is divisible by the given divisor.
If the number is divisible by the divisor, add it to a count of divisible substrings.
After going through all possible substrings, the count represents the total number of divisible substrings.

Code Implementation

def number_of_divisible_substrings_brute_force(number, divisor):
    number_string = str(number)
    string_length = len(number_string)
    divisible_substring_count = 0

    for substring_start_index in range(string_length):
        for substring_end_index in range(substring_start_index, string_length):
            # Extract substring from start to end indices.
            substring = number_string[substring_start_index : substring_end_index + 1]

            # Convert substring to an integer.
            substring_integer = int(substring)

            # Check if the substring is divisible by the divisor.
            # We check divisibility here.
            if substring_integer % divisor == 0:
                divisible_substring_count += 1

    # The result is the count of divisible substrings.
    return divisible_substring_count

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through all possible substrings of the input string. There are n possible starting positions for a substring. For each starting position, there can be up to n possible ending positions, resulting in examining all possible substrings. Converting each substring to a number and checking for divisibility takes O(1) time. Therefore, the dominant factor is the generation and checking of all possible substrings, which takes approximately n * n/2 operations. This simplifies to a time complexity of O(n²).

Space Complexity

O(1) – The brute-force approach iterates through substrings and converts each to a number. The number conversion uses a fixed amount of space for temporary storage, independent of the input string's length, N. The divisibility check also uses a fixed amount of space. No auxiliary data structures like lists or hash maps that scale with N are created; therefore, the auxiliary space complexity is constant.

Optimal Solution

Approach

The core idea is to efficiently count the substrings divisible by a certain number without exhaustively checking every substring. We can achieve this by focusing on the remainders of the running sums of digits as we traverse the string.

Here's how the algorithm would work step-by-step:

Think of each digit in the number string as a value. Pretend these values are being added up as you go through the string from left to right.
Instead of the actual sum, focus only on the remainder when this sum is divided by the special number you are interested in. Keep track of this remainder as you move along.
If two remainders are ever the same, it means the substring between those two positions is divisible by the special number.
Use a system to count how many times each remainder appears. A remainder appearing multiple times tells you how many divisible substrings there are.
For each remainder, if it appears 'n' times, then there are 'n choose 2' (n * (n-1) / 2) divisible substrings corresponding to that remainder. Also account for substrings that start from the beginning which are divisible.
Sum up the number of divisible substrings found for each remainder. This total is your final answer – the number of substrings in the number string that are divisible by the special number.

Code Implementation

def number_of_divisible_substrings(number_string, divisor):
    string_length = len(number_string)
    divisible_substring_count = 0

    for starting_index in range(string_length):
        running_total = 0

        for ending_index in range(starting_index, string_length):
            current_digit = int(number_string[ending_index])
            running_total = (running_total * 10 + current_digit) 

            # Modulo operation keeps numbers manageable.
            running_total_modulo = running_total % divisor

            if running_total_modulo == 0:
                # Divisible substring found.
                divisible_substring_count += 1

    return divisible_substring_count

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the string of length n once to calculate the running remainders. A hash map or array (of fixed size equal to the divisor) is used to store and update the frequency of each remainder. Accessing and updating the frequency count in the hash map/array takes constant time. Calculating the number of divisible substrings based on the remainder counts also takes time proportional to the number of distinct remainders, which is bounded by the divisor (a constant). Therefore, the overall time complexity is dominated by the single pass through the string, resulting in O(n).

Space Complexity

O(K) – The algorithm uses a dictionary or hash map (let's assume the size of this is K, where K is the divisor) to store the frequency of remainders encountered so far. In the worst case, all possible remainders (0 to K-1) might be encountered, requiring storage for each of them and their corresponding counts. Therefore, the auxiliary space used is proportional to K, the divisor, not the length of the input number string N. This results in a space complexity of O(K).

Edge Cases

Case	How to Handle
Null or empty input string num	Return 0 if num is null or empty, as there are no substrings to evaluate.
divisor is 0	Return 0 to avoid division by zero errors.
Single-character string '0' and divisor is not 0	Return 1 if the divisor is not zero, and the single character is '0'.
String contains leading zeros e.g. '0012'	Consider substrings starting with zeros as potentially valid integers when checking divisibility.
Large input string length causing integer overflow when converting substrings to integers	Use modulo operator (%) to avoid integer overflow during calculation.
divisor is a negative number	Take the absolute value of the divisor to deal with negative divisors consistently.
No divisible substrings exist	The solution should correctly return 0 when no substrings are divisible by the divisor.
Very large divisor and short substrings	Ensure substrings are parsed and evaluated correctly even when the divisor is significantly larger than the substring's integer value.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the length of the string `num` and the value of the integer `divisor`?
Can the string `num` contain leading zeros, and if so, how should they be handled in the substrings?
Is the `divisor` guaranteed to be a positive integer?
If no substrings are divisible by the `divisor`, what should the return value be?
Are overlapping substrings considered distinct, or should each substring only be counted once?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Consider every substring that starts at the beginning of the main number string, one character at a time.
Next, consider every substring that starts at the second character of the main number string, again one character at a time.
Repeat this process, considering substrings that start at each possible position within the main number string.
For each substring we identify, convert it into a whole number.
Determine if the converted number is divisible by the given divisor.
If the number is divisible by the divisor, add it to a count of divisible substrings.
After going through all possible substrings, the count represents the total number of divisible substrings.

Code Implementation

def number_of_divisible_substrings_brute_force(number, divisor):
    number_string = str(number)
    string_length = len(number_string)
    divisible_substring_count = 0

    for substring_start_index in range(string_length):
        for substring_end_index in range(substring_start_index, string_length):
            # Extract substring from start to end indices.
            substring = number_string[substring_start_index : substring_end_index + 1]

            # Convert substring to an integer.
            substring_integer = int(substring)

            # Check if the substring is divisible by the divisor.
            # We check divisibility here.
            if substring_integer % divisor == 0:
                divisible_substring_count += 1

    # The result is the count of divisible substrings.
    return divisible_substring_count

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Think of each digit in the number string as a value. Pretend these values are being added up as you go through the string from left to right.
Instead of the actual sum, focus only on the remainder when this sum is divided by the special number you are interested in. Keep track of this remainder as you move along.
If two remainders are ever the same, it means the substring between those two positions is divisible by the special number.
Use a system to count how many times each remainder appears. A remainder appearing multiple times tells you how many divisible substrings there are.
For each remainder, if it appears 'n' times, then there are 'n choose 2' (n * (n-1) / 2) divisible substrings corresponding to that remainder. Also account for substrings that start from the beginning which are divisible.
Sum up the number of divisible substrings found for each remainder. This total is your final answer – the number of substrings in the number string that are divisible by the special number.

Code Implementation

def number_of_divisible_substrings(number_string, divisor):
    string_length = len(number_string)
    divisible_substring_count = 0

    for starting_index in range(string_length):
        running_total = 0

        for ending_index in range(starting_index, string_length):
            current_digit = int(number_string[ending_index])
            running_total = (running_total * 10 + current_digit) 

            # Modulo operation keeps numbers manageable.
            running_total_modulo = running_total % divisor

            if running_total_modulo == 0:
                # Divisible substring found.
                divisible_substring_count += 1

    return divisible_substring_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string num	Return 0 if num is null or empty, as there are no substrings to evaluate.
divisor is 0	Return 0 to avoid division by zero errors.
Single-character string '0' and divisor is not 0	Return 1 if the divisor is not zero, and the single character is '0'.
String contains leading zeros e.g. '0012'	Consider substrings starting with zeros as potentially valid integers when checking divisibility.
Large input string length causing integer overflow when converting substrings to integers	Use modulo operator (%) to avoid integer overflow during calculation.
divisor is a negative number	Take the absolute value of the divisor to deal with negative divisors consistently.
No divisible substrings exist	The solution should correctly return 0 when no substrings are divisible by the divisor.
Very large divisor and short substrings	Ensure substrings are parsed and evaluated correctly even when the divisor is significantly larger than the substring's integer value.