Find the Divisibility Array of a String - Video Solutions

Problem Overview: You are given a numeric string word and an integer m. For each prefix of the string, determine whether the number formed by that prefix is divisible by m. The result is a binary array where 1 means the prefix is divisible and 0 means it is not.

Approach 1: Iterative Modulo Calculation (O(n) time, O(1) space)

Construct the number incrementally while iterating through the string. Instead of converting the entire prefix into a large integer, maintain the current remainder using modular arithmetic. For each character, update the remainder with remainder = (remainder * 10 + digit) % m. If the remainder becomes 0, the current prefix is divisible by m, so record 1; otherwise record 0. This avoids large integer overflow and processes each character exactly once.

This approach relies on properties from math and sequential processing of a string. Since only the current remainder is stored, space usage stays constant. This is the optimal solution and scales efficiently even when the string length is up to 10^5.

Approach 2: Prefix Construction with BigInteger (O(n^2) time, O(n) space)

Another method builds each prefix number explicitly using a big integer representation. At every step, append the new digit to the previous value using a BigInteger (in Java) and check divisibility using mod. This works because big integer libraries support arbitrary precision arithmetic.

The drawback is that the prefix value grows with every digit. Each arithmetic operation becomes more expensive as the number length increases, leading to roughly O(n^2) total time in practice. Memory usage also grows because the full prefix number must be stored. This approach is easier to reason about conceptually but inefficient for long inputs.

Recommended for interviews: The iterative modulo approach is the expected solution. It demonstrates understanding of modular arithmetic and efficient prefix processing. Interviewers want to see that you avoid constructing huge integers and instead track the remainder while iterating through the array-like structure of digits. Mentioning the BigInteger approach first can show baseline thinking, but implementing the modulo trick proves strong algorithmic intuition.