Find the Divisibility Array of a String

Problem Description

You are given a 0-indexed string word of length n consisting of digits, and a positive integer m. The divisibility array div of word is an integer array of length n such that div[i] = 1 if the numeric value of word[0,...,i] is divisible by m, or div[i] = 0 otherwise. Return the divisibility array of word.

Key Insights

• The numeric value of the prefix word[0,...,i] can be computed iteratively without converting the entire substring to an integer.
• The modulus operation can be used to check divisibility efficiently.
• As we process each digit, we can maintain the current value of the prefix modulo m to determine if it is divisible.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve this problem, we will iterate through each character of the string word and maintain a running total of the numeric value of the prefix modulo m. For each character, we will update this running total by incorporating the new digit and check if the updated total is divisible by m. We will store the results in an array div where each entry corresponds to whether the prefix up to that index is divisible by m.

1. Initialize an empty array div of size n to store the results.
2. Initialize a variable current to 0 to track the current prefix value.
3. For each character in word:
   • Update current using the formula: current = (current * 10 + int(word[i])) % m.
   • If current is 0, set div[i] to 1; otherwise, set it to 0.
4. Return the div array.

Code Solutions