Problem Description

You are given a string word consisting of digits (0-9) and a positive integer m. The string is 0-indexed with length n.

Your task is to create a divisibility array div of the same length as word. For each position i in the array:

• div[i] = 1 if the number formed by the substring from index 0 to index i (inclusive) is divisible by m
• div[i] = 0 otherwise

For example, if word = "123" and m = 3:

• At index 0: The substring is "1", which represents the number 1. Since 1 is not divisible by 3, div[0] = 0
• At index 1: The substring is "12", which represents the number 12. Since 12 is divisible by 3, div[1] = 1
• At index 2: The substring is "123", which represents the number 123. Since 123 is divisible by 3, div[2] = 1
• The result would be [0, 1, 1]

The solution uses a clever approach to avoid overflow issues with large numbers. Instead of converting the entire substring to an integer each time, it maintains a running remainder x. For each new digit, it updates the remainder using the formula x = (x * 10 + digit) % m. This works because of the modular arithmetic property: (a * b + c) % m = ((a % m) * b + c) % m.

The algorithm processes each character in word, updates the running remainder, and appends 1 to the result array if the remainder is 0 (meaning divisible by m), or 0 otherwise.

Intuition

The naive approach would be to convert each prefix substring to an integer and check if it's divisible by m. However, this runs into a major problem: the string could be very long, creating numbers far too large to store in standard integer types.

The key insight is recognizing that we don't need the actual number - we only need to know if it's divisible by m. This means we only care about the remainder when divided by m.

Consider how we build numbers digit by digit. When we have a number like 12 and want to append 3 to get 123, we multiply 12 by 10 and add 3: 12 * 10 + 3 = 123.

Now, here's the crucial mathematical property: when checking divisibility, we can work with remainders throughout the entire process. The remainder of a sum or product can be computed from the remainders of its parts:

• (a + b) % m = ((a % m) + (b % m)) % m
• (a * b) % m = ((a % m) * (b % m)) % m

This means instead of computing 123 % m, we can:

1. Start with remainder of 1: 1 % m
2. For the next digit 2: ((1 % m) * 10 + 2) % m gives us the remainder of 12
3. For the next digit 3: ((12 % m) * 10 + 3) % m gives us the remainder of 123

By maintaining only the remainder at each step (which is always less than m), we avoid overflow issues entirely. Whenever this remainder equals 0, we know the current prefix is divisible by m.

This transforms an impossible problem (storing potentially massive numbers) into a simple one (tracking a single remainder value that never exceeds m - 1).

Learn more about Math patterns.

Solution Approach

The implementation follows a straightforward traversal pattern with modular arithmetic:

1. Initialize variables:

   • Create an empty list ans to store the divisibility array
   • Set x = 0 to track the running remainder

2. Process each digit:

   • Iterate through each character c in the string word
   • Update the remainder using the formula: x = (x * 10 + int(c)) % m
     • x * 10 shifts the previous remainder to make room for the new digit
     • + int(c) adds the current digit value
     • % m keeps only the remainder, preventing overflow

3. Record divisibility:

   • After updating x, check if x == 0
   • If true, append 1 to ans (current prefix is divisible by m)
   • Otherwise, append 0 to ans

4. Return the result:

   • After processing all digits, return the complete divisibility array ans

Example walkthrough with word = "123" and m = 3:

• Initial: x = 0, ans = []
• Process '1': x = (0 * 10 + 1) % 3 = 1, append 0 → ans = [0]
• Process '2': x = (1 * 10 + 2) % 3 = 0, append 1 → ans = [0, 1]
• Process '3': x = (0 * 10 + 3) % 3 = 0, append 1 → ans = [0, 1, 1]

The time complexity is O(n) where n is the length of the string, as we process each character exactly once. The space complexity is O(n) for storing the result array.

Example Walkthrough

Let's walk through the solution with word = "4872" and m = 6.

We want to check if each prefix ("4", "48", "487", "4872") is divisible by 6.

Initial State:

• x = 0 (running remainder)
• ans = [] (result array)

Step 1: Process digit '4'

• Update remainder: x = (0 * 10 + 4) % 6 = 4
• Check divisibility: 4 ≠ 0, so prefix "4" is NOT divisible by 6
• Append 0 to result: ans = [0]

Step 2: Process digit '8'

• Update remainder: x = (4 * 10 + 8) % 6 = 48 % 6 = 0
• Check divisibility: 0 == 0, so prefix "48" IS divisible by 6
• Append 1 to result: ans = [0, 1]

Step 3: Process digit '7'

• Update remainder: x = (0 * 10 + 7) % 6 = 7 % 6 = 1
• Check divisibility: 1 ≠ 0, so prefix "487" is NOT divisible by 6
• Append 0 to result: ans = [0, 1, 0]

Step 4: Process digit '2'

• Update remainder: x = (1 * 10 + 2) % 6 = 12 % 6 = 0
• Check divisibility: 0 == 0, so prefix "4872" IS divisible by 6
• Append 1 to result: ans = [0, 1, 0, 1]

Final Result: [0, 1, 0, 1]

This means:

• "4" (4) is not divisible by 6
• "48" (48) is divisible by 6
• "487" (487) is not divisible by 6
• "4872" (4872) is divisible by 6

The key insight is that we never store the actual numbers (4, 48, 487, 4872). We only track remainders (4, 0, 1, 0), which always stay between 0 and 5, avoiding any overflow issues even for extremely long strings.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string word. This is because the algorithm iterates through each character in the string exactly once, performing constant-time operations (multiplication, addition, modulo, and append) for each character.

The space complexity is O(n), not O(1) as stated in the reference answer. While the algorithm uses only a constant amount of extra variables (x and c), the ans list grows proportionally with the input size, storing one integer (0 or 1) for each character in the input string. Therefore, the space required for the output list is O(n).

Note: If we consider only the auxiliary space (excluding the space needed for the output), then the space complexity would be O(1), as we only use a fixed amount of extra variables regardless of input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Attempting to Convert Entire Substring to Integer

The most critical pitfall is trying to convert the substring directly to an integer for divisibility checking:

Incorrect Approach:

def divisibilityArray(self, word: str, m: int) -> List[int]:
    result = []
    for i in range(len(word)):
        # WRONG: This will cause overflow for large strings!
        num = int(word[:i+1])
        result.append(1 if num % m == 0 else 0)
    return result

Why it fails: The string word can be extremely long (up to 10^5 characters), creating numbers far exceeding Python's integer limits in other languages or causing severe performance issues.

Solution: Use the modular arithmetic approach shown in the correct implementation, maintaining only the remainder at each step.

2. Incorrect Remainder Update Formula

A subtle mistake is incorrectly updating the remainder:

Incorrect:

# Missing parentheses or wrong order of operations
remainder = remainder * 10 + int(digit_char) % m  # WRONG!

This applies modulo only to the new digit, not the entire expression.

Correct:

remainder = (remainder * 10 + int(digit_char)) % m

3. Using Wrong Initial Value for Remainder

Incorrect:

remainder = 1  # WRONG: Should start at 0

Starting with a non-zero remainder would incorrectly process the first digit, as it would compute (1 * 10 + first_digit) % m instead of just first_digit % m.

4. Forgetting to Handle Edge Cases

While the problem guarantees valid input, in practice you might want to validate:

• Empty string (though problem states positive length)
• Non-digit characters
• Division by zero (m = 0)

Robust version with validation:

def divisibilityArray(self, word: str, m: int) -> List[int]:
    if not word or m == 0:
        return []
  
    result = []
    remainder = 0
  
    for digit_char in word:
        if not digit_char.isdigit():
            raise ValueError(f"Invalid character: {digit_char}")
        remainder = (remainder * 10 + int(digit_char)) % m
        result.append(1 if remainder == 0 else 0)
  
    return result

5. Confusion About What Constitutes "Divisible"

Some might incorrectly check if the remainder equals 1 or use the wrong condition:

Incorrect:

result.append(1 if remainder == 1 else 0)  # WRONG!
result.append(remainder)  # WRONG: Should be binary 0 or 1

Correct: A number is divisible by m when remainder is exactly 0.