Find the Divisibility Array of a String

MEDIUM

Description

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 <= 10⁵
word.length == n
word consists of digits from 0 to 9
1 <= m <= 10⁹

Approaches

Checkout 2 different approaches to solve Find the Divisibility Array of a String. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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.

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;
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: 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 and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Find the Divisibility Array of a String. Click on different languages to view the code.

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;
  }
}

Video Solution

Watch the video walkthrough for Find the Divisibility Array of a String

Patterns:

Math

Data Structures:

ArrayString