# Find the Divisibility Array of a String
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-divisibility-array-of-a-string)
Canonical: https://scaleengineer.com/dsa/problems/find-the-divisibility-array-of-a-string
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Array, String
---
## Problem
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`

# Approaches
## Brute Force with BigInteger
This approach directly simulates the problem statement. For each prefix of the input string `word`, it converts the prefix into a number and then checks if that number is divisible by `m`.
**Time:** O(n^2). The loop runs `n` times. Inside the loop, creating a substring of length `i+1` takes O(i) time. Creating a `BigInteger` from a string of length `i+1` and performing the `mod` operation also takes time proportional to the length of the string, roughly O(i). Therefore, the total time is the sum of `i` from 0 to `n-1`, which is O(n^2). This will be too slow for `n = 10^5`. · **Space:** O(n). We need O(n) space for the output array. In each iteration, we create a substring and a `BigInteger` object, the largest of which will have a size proportional to `n`. So, the auxiliary space is O(n).
**Pros:** Simple and direct implementation of the problem statement.; Correctly handles arbitrarily large numbers.
**Cons:** Inefficient time complexity (O(n^2)), leading to a "Time Limit Exceeded" error on large inputs.; Repeatedly recomputes the value of prefixes from scratch, which is redundant.
### Explanation
The main challenge is that the numeric value of a prefix can be very large, exceeding the capacity of standard data types like `long`. To handle arbitrarily large integers, we can use the `java.math.BigInteger` class.
The algorithm iterates from `i = 0` to `n-1`, where `n` is the length of the string.
In each iteration `i`, it extracts the substring `word[0...i]`.
This substring is then converted into a `BigInteger` object.
The `mod` operation of `BigInteger` is used to find the remainder when this number is divided by `m`.
If the remainder is zero, `div[i]` is set to 1; otherwise, it's set to 0.
This process is repeated for all prefixes.

```java
import java.math.BigInteger;

class Solution {
    public int[] divisibilityArray(String word, int m) {
        int n = word.length();
        int[] div = new int[n];
        BigInteger bigM = BigInteger.valueOf(m);

        for (int i = 0; i < n; i++) {
            String prefix = word.substring(0, i + 1);
            BigInteger num = new BigInteger(prefix);
            if (num.mod(bigM).equals(BigInteger.ZERO)) {
                div[i] = 1;
            } else {
                div[i] = 0;
            }
        }
        return div;
    }
}
```
### Algorithm
- Initialize an integer array `div` of size `n`.
- Iterate with an index `i` from `0` to `n-1`.
- Extract the prefix substring `prefix = word.substring(0, i + 1)`.
- Create a `BigInteger` from the `prefix`: `BigInteger num = new BigInteger(prefix)`.
- Create a `BigInteger` for the divisor `m`: `BigInteger bigM = BigInteger.valueOf(m)`.
- Calculate the remainder: `BigInteger remainder = num.mod(bigM)`.
- If `remainder.equals(BigInteger.ZERO)`, set `div[i] = 1`.
- Otherwise, set `div[i] = 0`.
- After the loop, return the `div` array.

## Iterative Modular Arithmetic
This is an optimized approach that avoids handling large numbers directly by using properties of modular arithmetic. It calculates the remainder of the current prefix number based on the remainder of the previous prefix number.
**Time:** O(n). We iterate through the string of length `n` exactly once. All operations inside the loop (character access, arithmetic) take constant time. · **Space:** O(n). The space is dominated by the output array `div`. The auxiliary space used is O(1) for the `remainder` variable. If the output array is not counted, the space complexity is O(1).
**Pros:** Highly efficient with linear time complexity.; Avoids creating large number objects and expensive operations, making it very fast.; Constant auxiliary space (excluding the output array).
**Cons:** Requires understanding of modular arithmetic to come up with the solution.
### Explanation
Let `num_i` be the number formed by the prefix `word[0...i]`. We can express `num_i` in terms of `num_{i-1}`: `num_i = num_{i-1} * 10 + digit_i`, where `digit_i` is the numeric value of `word.charAt(i)`.
We are interested in `num_i % m`. Using modular arithmetic properties, we have:
`num_i % m = (num_{i-1} * 10 + digit_i) % m`
This can be further broken down:
`num_i % m = ((num_{i-1} % m) * 10 + digit_i) % m`
This gives us a recurrence relation. If we let `rem_i = num_i % m`, then `rem_i = (rem_{i-1} * 10 + digit_i) % m`.
We can iterate through the string, maintaining a running remainder. We start with a remainder of 0. For each digit, we update the remainder using the formula above. If the updated remainder is 0, the current prefix number is divisible by `m`.
This way, we only deal with numbers that are at most `m-1` (the remainder), avoiding overflow and the need for `BigInteger`.

```java
class Solution {
    public int[] divisibilityArray(String word, int m) {
        int n = word.length();
        int[] div = new int[n];
        long remainder = 0;

        for (int i = 0; i < n; i++) {
            int digit = word.charAt(i) - '0';
            remainder = (remainder * 10 + digit) % m;
            if (remainder == 0) {
                div[i] = 1;
            } else {
                div[i] = 0;
            }
        }
        return div;
    }
}
```
### Algorithm
- Initialize an integer array `div` of size `n`.
- Initialize a `long` variable `remainder` to `0`. We use `long` to prevent potential overflow when `remainder` is multiplied by 10 before the modulo operation.
- Iterate through the `word` string with an index `i` from `0` to `n-1`.
- Get the numeric value of the current character: `digit = word.charAt(i) - '0'`.
- Update the `remainder`: `remainder = (remainder * 10 + digit) % m`.
- If `remainder == 0`, set `div[i] = 1`.
- Otherwise, set `div[i] = 0`.
- After the loop, return the `div` array.

# Solutions
### Java

```java
class Solution {
public
  int[] divisibilityArray(String word, int m) {
    int n = word.length();
    int[] ans = new int[n];
    long x = 0;
    for (int i = 0; i < n; ++i) {
      x = (x * 10 + word.charAt(i) - '0') % m;
      if (x == 0) {
        ans[i] = 1;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> divisibilityArray(string word, int m) {
    vector<int> ans;
    long long x = 0;
    for (char &c : word) {
      x = (x * 10 + c - '0') % m;
      ans.push_back(x == 0 ? 1 : 0);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def divisibilityArray(self, word: str, m: int) -> List[int]: ans = [] x = 0 for c in word: x = (x * 10 + int(c)) % m ans . append(1 if x == 0 else 0) return ans

```