LeetCode 2575 - Find the Divisibility Array of a String

The problem gives us a numeric string word and an integer m. For every prefix of the string, we must determine whether that prefix represents a number divisible by m. A prefix word[0...i] means the substring starting at index 0 and ending at index i, inclusive.

leetcodemediumarraymathstring

LeetCode Problem 2575

Difficulty: šŸŸ” Medium
Topics: Array, Math, String

Solution

Problem Understanding

The problem gives us a numeric string word and an integer m. For every prefix of the string, we must determine whether that prefix represents a number divisible by m.

A prefix word[0...i] means the substring starting at index 0 and ending at index i, inclusive. Since the string contains only digits, every prefix can be interpreted as a decimal integer.

For each prefix:

  • If the numeric value of the prefix is divisible by m, we place 1 in the result array.
  • Otherwise, we place 0.

The final answer is an array div of length n, where n is the length of the string.

For example, suppose:

word = "1010"
m = 10

The prefixes are:

  • "1" ā†’ 1 % 10 != 0 ā†’ 0
  • "10" ā†’ 10 % 10 == 0 ā†’ 1
  • "101" ā†’ 101 % 10 != 0 ā†’ 0
  • "1010" ā†’ 1010 % 10 == 0 ā†’ 1

So the answer becomes:

[0, 1, 0, 1]

The constraints are extremely important:

  • n can be as large as 10^5
  • m can be as large as 10^9

A naive implementation that converts every prefix into a full integer would become inefficient very quickly. In fact, prefixes may contain up to 100000 digits, which cannot fit into standard integer types in many languages.

The constraints strongly suggest that we need a mathematical approach that processes the string incrementally without constructing enormous integers.

Several edge cases are important:

  • A single-character string.
  • Prefixes containing leading zeros.
  • Very large strings where constructing integers directly would overflow.
  • Cases where every prefix is divisible.
  • Cases where no prefix is divisible.
  • Large values of m.

The problem guarantees:

  • The string contains only digits.
  • m is always positive.
  • The string length is at least 1.

These guarantees simplify handling invalid input cases.

Approaches

Brute Force Approach

The most straightforward approach is to examine every prefix independently.

For each index i:

  1. Extract the substring word[0:i+1].
  2. Convert it into an integer.
  3. Compute whether it is divisible by m.
  4. Append 1 or 0 to the result.

This works because it directly follows the problem definition.

However, this approach is far too slow for large inputs.

If the string length is n, then:

  • Creating each prefix takes O(i) time.
  • Converting it to an integer also costs O(i) time.

Across all prefixes, this leads to approximately:

$1+2+3+\cdots+n = \frac{n(n+1)}{2}$

which gives quadratic time complexity, O(n^2).

Additionally, prefixes may become extremely large, causing overflow issues in fixed-width integer types.

Optimal Approach

The key observation is that we never need the full numeric value of a prefix. We only need its remainder modulo m.

Suppose we already know:

previous_prefix % m

When we append a new digit d, the new number becomes:

$new_value = old_value \times 10 + d$

Taking modulo m:

$new_remainder = (old_remainder \times 10 + d) \bmod m$

This allows us to process the string digit by digit while keeping only the current remainder.

At each step:

  • Update the remainder.
  • If the remainder is zero, the current prefix is divisible by m.

This avoids large integer construction entirely and runs in linear time.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(nĀ²) O(n) Recomputes large prefixes repeatedly
Optimal O(n) O(n) Maintains running remainder modulo m

Algorithm Walkthrough

Step 1: Initialize the Result Array

Create an empty result array that will store 1 or 0 for each prefix.

Also initialize a variable remainder = 0.

This variable represents:

current_prefix % m

instead of storing the full number.

Step 2: Iterate Through Each Character

Process the string from left to right.

For each character:

  1. Convert the character into its numeric digit value.
  2. Update the running remainder using modular arithmetic.

The update formula is:

$remainder = (remainder \times 10 + digit) \bmod m$

This formula simulates appending a digit to the current number.

Step 3: Check Divisibility

After updating the remainder:

  • If remainder == 0, append 1.
  • Otherwise, append 0.

A remainder of zero means the current prefix is divisible by m.

Step 4: Continue Until the End

Repeat the process for every digit in the string.

At the end, return the result array.

Why it works

The algorithm maintains the invariant that after processing index i, remainder equals:

numeric_value_of(word[0:i]) % m

When a new digit is appended, decimal number construction follows:

new_number = old_number * 10 + digit

Because modulo arithmetic distributes over addition and multiplication, the updated remainder formula produces the exact modulo value of the new prefix without ever constructing the full number.

Therefore, whenever the remainder becomes zero, the corresponding prefix is divisible by m.

Python Solution

from typing import List

class Solution:
    def divisibilityArray(self, word: str, m: int) -> List[int]:
        result = []
        remainder = 0

        for ch in word:
            digit = int(ch)

            remainder = (remainder * 10 + digit) % m

            if remainder == 0:
                result.append(1)
            else:
                result.append(0)

        return result

The implementation follows the optimal algorithm directly.

The variable remainder stores the modulo value of the current prefix. Instead of building large integers, the code updates the remainder incrementally using modular arithmetic.

For every character:

  1. Convert the character into a digit.
  2. Update the running remainder.
  3. Check whether the remainder equals zero.
  4. Append the corresponding result value.

The solution processes the string exactly once, making it efficient even for the maximum constraint size.

Go Solution

func divisibilityArray(word string, m int) []int {
    result := make([]int, len(word))

    remainder := 0

    for i := 0; i < len(word); i++ {
        digit := int(word[i] - '0')

        remainder = (remainder*10 + digit) % m

        if remainder == 0 {
            result[i] = 1
        }
    }

    return result
}

The Go implementation is nearly identical to the Python version.

A fixed-size slice is created up front because the output length is known in advance.

Digits are extracted using:

word[i] - '0'

which converts a character byte into its integer value.

Integer overflow is not an issue because the remainder is always reduced modulo m, and m <= 10^9, which fits comfortably inside Go's int type on modern systems.

Worked Examples

Example 1

word = "998244353"
m = 3

We process each digit incrementally.

Index Digit Updated Remainder Divisible? Result
0 9 (0Ɨ10+9)%3 = 0 Yes 1
1 9 (0Ɨ10+9)%3 = 0 Yes 1
2 8 (0Ɨ10+8)%3 = 2 No 0
3 2 (2Ɨ10+2)%3 = 1 No 0
4 4 (1Ɨ10+4)%3 = 2 No 0
5 4 (2Ɨ10+4)%3 = 0 Yes 1
6 3 (0Ɨ10+3)%3 = 0 Yes 1
7 5 (0Ɨ10+5)%3 = 2 No 0
8 3 (2Ɨ10+3)%3 = 2 No 0

Final result:

[1,1,0,0,0,1,1,0,0]

Example 2

word = "1010"
m = 10
Index Digit Updated Remainder Divisible? Result
0 1 (0Ɨ10+1)%10 = 1 No 0
1 0 (1Ɨ10+0)%10 = 0 Yes 1
2 1 (0Ɨ10+1)%10 = 1 No 0
3 0 (1Ɨ10+0)%10 = 0 Yes 1

Final result:

[0,1,0,1]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each character is processed exactly once
Space O(n) Output array stores one value per character

The algorithm performs a constant amount of work for each digit in the string. No nested loops or repeated substring construction are used.

The only additional storage beyond the output array is a few integer variables, which require constant space. Since the output itself must contain n elements, the total space complexity is O(n).

Test Cases

from typing import List

class Solution:
    def divisibilityArray(self, word: str, m: int) -> List[int]:
        result = []
        remainder = 0

        for ch in word:
            digit = int(ch)
            remainder = (remainder * 10 + digit) % m
            result.append(1 if remainder == 0 else 0)

        return result

sol = Solution()

assert sol.divisibilityArray("998244353", 3) == [1,1,0,0,0,1,1,0,0]  # provided example
assert sol.divisibilityArray("1010", 10) == [0,1,0,1]  # provided example

assert sol.divisibilityArray("0", 1) == [1]  # single digit divisible
assert sol.divisibilityArray("5", 2) == [0]  # single digit not divisible

assert sol.divisibilityArray("0000", 5) == [1,1,1,1]  # leading zeros and all divisible
assert sol.divisibilityArray("11111", 2) == [0,0,0,0,0]  # no prefix divisible

assert sol.divisibilityArray("12", 3) == [0,1]  # second prefix divisible
assert sol.divisibilityArray("120", 12) == [0,1,1]  # multiple divisible prefixes

assert sol.divisibilityArray("999999", 9) == [1,1,1,1,1,1]  # every prefix divisible
assert sol.divisibilityArray("123456789", 1000000000) == [0,0,0,0,0,0,0,0,0]  # very large m

large_word = "1" * 1000
result = sol.divisibilityArray(large_word, 3)
assert len(result) == 1000  # stress test for large input size

Test Case Summary

Test Why
"998244353", 3 Validates the official example
"1010", 10 Tests divisibility by 10
"0", 1 Smallest valid input
"5", 2 Single non-divisible digit
"0000", 5 Leading zeros
"11111", 2 No divisible prefixes
"12", 3 Later prefix becomes divisible
"120", 12 Multiple divisible prefixes
"999999", 9 Every prefix divisible
"123456789", 1000000000 Large modulus value
Large repeated string Stress test for performance

Edge Cases

Leading Zeros

Inputs such as "0000" can cause issues in naive implementations that incorrectly interpret prefixes or strip leading zeros. In this problem, prefixes must still be treated as valid decimal numbers.

The modular arithmetic approach handles this naturally. Appending zero simply updates the remainder correctly, and prefixes like "00" are evaluated as zero, which is divisible by any positive m.

Extremely Large Prefix Values

A naive solution may attempt to convert prefixes into integers directly. With a string length up to 100000, prefixes can become far larger than standard integer limits.

This implementation never stores the full number. It only stores the current remainder modulo m, which always remains within the range [0, m-1]. This completely avoids overflow problems.

Large Modulus Values

When m is very large, such as 10^9, some implementations may incorrectly assume divisibility patterns or use unsafe arithmetic.

The algorithm remains correct because all operations are simple modular updates. Since the remainder is reduced after every step, intermediate values stay manageable and efficient.