You are given a 0-indexed string word of length n consisting of digits, and a positive integer m.
The divisibility arraydiv 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 ofword.
Example 1:
Input: word = "998244353", m = 3
Output: [1,1,0,0,0,1,1,0,0]
Explanation: There are only 4 prefixes that are divisible by 3: "9", "99", "998244", and "9982443".
Example 2:
Input: word = "1010", m = 10
Output: [0,1,0,1]
Explanation: There are only 2 prefixes that are divisible by 10: "10", and "1010".
Constraints:
1 <= n <= 105
word.length == n
word consists of digits from 0 to 9
1 <= m <= 109
Solutions
Solution 1: Traversal + Modulo
We iterate over the string word, using a variable $x$ to record the modulo result of the current prefix with $m$. If $x$ is $0$, then the divisible array value at the current position is $1$, otherwise it is $0$.
The time complexity is $O(n)$, where $n$ is the length of the string word. The space complexity is $O(1)$.
/** * Note: The returned array must be malloced, assume caller calls free(). */int*divisibilityArray(char*word,intm,int*returnSize){intn=strlen(word);int*ans=malloc(sizeof(int)*n);longlongx=0;for(inti=0;i<n;i++){x=(x*10+word[i]-'0')%m;ans[i]=x==0?1:0;}*returnSize=n;returnans;}