#2575

Medium

LeetCode Problem Workspace

Find the Divisibility Array of a String

Calculate the divisibility array for a string by checking if prefixes are divisible by a given number.

Problem Statement

You are given a string 'word' consisting of digits, and a positive integer 'm'. For each prefix of the string, check if its numeric value is divisible by 'm'. The divisibility array should store 1 if the prefix is divisible by 'm', otherwise 0.

Return the divisibility array for the given string 'word'. The result is an integer array where each index corresponds to a prefix of the string, with 1 for divisibility and 0 otherwise.

Examples

Example 1

Input: word = "998244353", m = 3

Output: [1,1,0,0,0,1,1,0,0]

There are only 4 prefixes that are divisible by 3: "9", "99", "998244", and "9982443".

Example 2

Input: word = "1010", m = 10

Output: [0,1,0,1]

There are only 2 prefixes that are divisible by 10: "10", and "1010".

Constraints

1 <= n <= 105
word.length == n
word consists of digits from 0 to 9
1 <= m <= 109

Solution Approach

Prefix Calculation with Modulo

To solve this problem, calculate the remainder of each prefix when divided by 'm' using the modulo operation. This allows you to avoid constructing large numbers by using their remainders and ensures efficient handling of large strings.

Efficient Divisibility Check

Instead of converting prefixes to integers, compute the remainder iteratively. For each new digit in the prefix, multiply the current remainder by 10 and add the new digit, then take the result modulo 'm'.

Time and Space Optimization

Use an iterative approach to calculate the remainders, avoiding the need for converting the string into numbers repeatedly. This approach ensures you only store the current remainder and divisibility results.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the length of the string, as you calculate the remainder for each prefix. With each step, the remainder is updated in constant time, making the solution O(n), where n is the length of the string. The space complexity is O(n) due to storing the divisibility array.

What Interviewers Usually Probe

Look for candidates who optimize the remainder calculation process and handle large strings efficiently.
Check how candidates handle large inputs and edge cases, such as very large 'm' values.
Evaluate if the candidate can avoid converting strings to integers repeatedly, using modular arithmetic instead.

Common Pitfalls or Variants

Common pitfalls

Converting entire prefixes to integers instead of using modular arithmetic.
Not handling large values of 'm' efficiently, leading to potential performance issues.
Overcomplicating the solution by checking divisibility with brute force instead of using the modulo operation.

Follow-up variants

Consider different values for 'm', including large and small values, to test the scalability of the solution.
Explore edge cases like an input string of length 1 or 'm' being much larger than any prefix.
Try variations with strings containing only a single repeating digit.

FAQ

How do I approach the 'Find the Divisibility Array of a String' problem?

You can solve the problem by calculating the remainder of each prefix modulo 'm' to check divisibility efficiently without converting the entire prefix to an integer.

What is the time complexity of the solution?

The time complexity is O(n), where n is the length of the string, since you only need to iterate through the string once to calculate the remainders.

What are some common mistakes in solving this problem?

A common mistake is converting the entire prefix to an integer instead of using the modulo operation, which can be inefficient for large inputs.

How does modular arithmetic help in this problem?

Modular arithmetic allows you to efficiently check if a prefix is divisible by 'm' without needing to handle large integer values, reducing time and space complexity.

What should I do if 'm' is much larger than the length of the string?

Even if 'm' is large, you can still use modular arithmetic to avoid working with large numbers, ensuring your solution scales with both 'm' and string length.

terminal

Solution

Solution 1: Traversal + Modulo

We iterate over the string `word`, using a variable $x$ to record the modulo result of the current prefix with $m$. If $x$ is $0$, then the divisible array value at the current position is $1$, otherwise it is $0$.

1

2

3

4

5

6

7

8

class Solution:
    def divisibilityArray(self, word: str, m: int) -> List[int]:
        ans = []
        x = 0
        for c in word:
            x = (x * 10 + int(c)) % m
            ans.append(1 if x == 0 else 0)
        return ans

Continue Practicing

#2125 number of laser beams in a bank #2019 the score of students solving math expression #2573 find the string with lcp