2575. Find the Divisibility Array of a String LeetCode Solution
In this guide, you will get 2575. Find the Divisibility Array of a String LeetCode Solution with the best time and space complexity. The solution to Find the Divisibility Array of a String problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Find the Divisibility Array of a String
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
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
2575. Find the Divisibility Array of a String LeetCode Solution in C++
class Solution {
public:
vector<int> divisibilityArray(string word, int m) {
vector<int> ans;
long prevRemainder = 0;
for (const char c : word) {
const long remainder = (prevRemainder * 10 + (c - '0')) % m;
ans.push_back(remainder == 0 ? 1 : 0);
prevRemainder = remainder;
}
return ans;
}
}; /* code provided by PROGIEZ */
2575. Find the Divisibility Array of a String LeetCode Solution in Java
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;
}
} // code provided by PROGIEZ
2575. Find the Divisibility Array of a String LeetCode Solution in Python
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 # code by PROGIEZ
