Find the Divisibility Array of a String

Problem Description

Ah, the classic “Find the Divisibility Array of a String” problem! It’s like trying to figure out if your friend can actually count their change after a shopping spree. You know, the one who always claims they have enough money but ends up asking you for a dollar?

In this problem, you are given a string word that represents a non-negative integer, and an integer m. Your task is to determine for each prefix of the string whether it is divisible by m. If it is, you return 1, and if it isn’t, you return 0.

So, if your friend had a string of numbers instead of coins, you’d be the one checking if they can actually buy that overpriced coffee!

Code Solution


class Solution {
  public int[] divisibilityArray(String word, int m) {
    int[] ans = new int[word.length()];
    long prevRemainder = 0;

    for (int i = 0; i < word.length(); ++i) {
      final long remainder = (prevRemainder * 10 + (word.charAt(i) - '0')) % m;
      ans[i] = remainder == 0 ? 1 : 0;
      prevRemainder = remainder;
    }

    return ans;
  }
}

Approach

The approach here is as straightforward as your friend’s math skills (or lack thereof). We maintain a running remainder as we iterate through each character of the string. For each character, we update the remainder based on the previous remainder and the current digit. If the remainder is zero, we mark that prefix as divisible by m.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n), where n is the length of the string. We traverse the string once.
Space Complexity	O(n) for the output array that stores the results.

Real-World Example

Imagine you’re at a party, and everyone is trying to figure out how many slices of pizza each person can have without leaving anyone hungry. You keep track of the number of slices (like the digits in the string) and check if the total number of slices can be evenly divided among your friends (like checking divisibility by m). If it can, everyone gets a slice; if not, someone’s going to be left out, and you’ll have to deal with their hangry attitude!