Sketch on a paper

Sometimes when you sketch something on a paper, solution comes easily. This one for example, I tried the most simplistic solution with a Big Integer, but ran into TLE. Looked at the hints, then you need to figure out the remainder i given the remainder i-1 (to some degree, this becomes a DP problem). On a piece of paper the relationship between i and i-1 becomes very obvious. Code is down below, cheers, ACC.

Find the Divisibility Array of a String - LeetCode

2575. Find the Divisibility Array of a String

Medium

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.

 

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

Accepted

12,916

Submissions

45,026

public int[] DivisibilityArray(string word, int m)
{
    int[] retVal = new int[word.Length];
    long[] remainder = new long[word.Length];

    remainder[0] = (long)(word[0] - '0') % m;
    retVal[0] = remainder[0] == 0 ? 1 : 0;

    for (int i = 1; i < word.Length; i++)
    {
        long d = (long)(word[i] - '0');
        remainder[i] = (10 * remainder[i - 1] + d) % m;
        retVal[i] = remainder[i] == 0 ? 1 : 0;
    }
    return retVal;
}