< Back





2575. Find the Divisibility Array of a String

We're provided a string of digits and an integer, m, that we're asked to find which prefixes of the
string, from 0 to n, are divisible by m. We're asked to return an array consisting of 1s and 0s,
where 1 represents that the prefix from word[:i+1] is divisible by m, and 0 means it's not.

We could just cast word[:i+1] to an int and conduct a modulo operation to determine if the prefix
is divisible by m, however, the input string can be so large that the Python int() operation will
run into a runtime error. Thus, we have to conduct a modulo operation for each prefix and retain the
remainder for use during the next iteration of i.

The solution is as follows:


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

          for w in word:
              prev = ((prev * 10) + int(w)) % m

              if not prev:
                  ans.append(1)
              else:
                  ans.append(0)

          return ans


_ Time Complexity:

  O(n) - Where n is the size of word, we traverse the entire array.

_ Space Complexity:

  O(1) - The answer doesn't count as space used, and we only use constant space to track the
  remainder.