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.