Find the Divisibility Array of a String

Find the Divisibility Array of a String

What is this problem about?

The Find the Divisibility Array of a String interview question involves large-number arithmetic and prefix analysis. You are given a numeric string word and an integer m. Your goal is to produce an array div of the same length as word, where div[i] is 1 if the number formed by the prefix word[0...i] is divisible by m, and 0 otherwise. Because the string can be very long ($10^5$ characters), the actual numbers formed can far exceed the capacity of any standard integer type.

Why is this asked in interviews?

Companies like Amazon and Google ask the Find the Divisibility Array of a String coding problem to test a candidate's understanding of Modular Arithmetic. It evaluates whether you can handle potential overflow issues by applying the properties of modulo $(a \cdot 10 + b) \pmod m = ((a \pmod m) \cdot 10 + b) \pmod m$. It tests your ability to optimize mathematical operations within a Math interview pattern.

Algorithmic pattern used

This problem follows the Linear Scan with Modular Accumulation pattern.

1. Iterate: Traverse the string from left to right.
2. Maintain Remainder: Instead of storing the full prefix number, only store the remainder of the current prefix when divided by m.
3. Update Rule: For each digit $d$, the new remainder is (currentRemainder * 10 + d) % m.
4. Check: If the newRemainder is 0, then the prefix is divisible. Record 1 in the result array; otherwise, record 0.

Example explanation

word = "998244353", m = 3

1. Digit '9': (0 * 10 + 9) % 3 = 0. Divisible! Result: [1].
2. Digit '9': (0 * 10 + 9) % 3 = 0. Divisible! Result: [1, 1].
3. Digit '8': (0 * 10 + 8) % 3 = 2. Not divisible. Result: [1, 1, 0]. ... and so on.

Common mistakes candidates make

• Integer Overflow: Attempting to convert the prefix string into a BigInteger or a very long number. This is slow and memory-intensive.
• String Slicing: Repeatedly calling substring() and converting to an integer, which is $O(N^2)$ and inefficient.
• Incorrect Modulo: Forgetting to apply the modulo operator at every step of the digit accumulation.

Interview preparation tip

Always look for ways to apply "Modulo Properties" when dealing with large numbers and divisibility. Modular arithmetic allows you to work with smaller, manageable values while still arriving at the correct divisibility conclusion.