Skip to content

2575. Find the Divisibility Array of a String 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
 public:
  vector<int> divisibilityArray(string word, int m) {
    vector<int> ans;
    long long prevRemainder = 0;

    for (const char c : word) {
      const long long remainder = (prevRemainder * 10 + (c - '0')) % m;
      ans.push_back(remainder == 0 ? 1 : 0);
      prevRemainder = remainder;
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
  def divisibilityArray(self, word: str, m: int) -> List[int]:
    ans = []
    prevRemainder = 0

    for c in word:
      remainder = (prevRemainder * 10 + int(c)) % m
      ans.append(1 if remainder == 0 else 0)
      prevRemainder = remainder

    return ans