Leetcode 2575: Find the Divisibility Array of a String
Given a string word consisting of digits and an integer m, return an array where each element is 1 if the numeric value of the prefix word[0,…,i] is divisible by m, otherwise 0.
Problem
Approach
Steps
Complexity
Input: The input consists of a string word and an integer m.
Example: For example, word = '2020', m = 4.
Constraints:
• 1 <= n <= 10^5
• word consists of digits from 0 to 9
• 1 <= m <= 10^9
Output: The output is an array of 0s and 1s where each element denotes whether the corresponding prefix of word is divisible by m.
Example: For word = '123456789' and m = 7, the output is [0, 0, 0, 0, 0, 0, 0, 1, 0].
Constraints:
• The length of the divisibility array is the same as the length of word.
Goal: To determine if each prefix of the string word is divisible by m.
Steps:
• 1. Initialize a variable num to store the current numeric value of the prefix.
• 2. For each digit in word, update num by multiplying the previous value by 10 and adding the current digit.
• 3. Check if num is divisible by m, if yes, set div[i] = 1, otherwise div[i] = 0.
Goal: The input string contains digits, and m is a positive integer within the specified range.
Steps:
• 1 <= n <= 10^5
• 1 <= m <= 10^9
• word consists of digits from 0 to 9.
Assumptions:
• The word string is non-empty and consists of digits from '0' to '9'.
• Input: For word = '2020' and m = 4, the output is [0, 1, 0, 1].
• Explanation: The prefixes '20' and '2020' are divisible by 4.
Approach: The approach uses the cumulative computation of the prefix numeric values and checks for divisibility with m.
Observations:
• The problem requires checking divisibility for multiple prefixes efficiently.
• We can compute each prefix number iteratively and check divisibility in constant time.
Steps:
• 1. Initialize a variable num to 0.
• 2. Loop through each character in the word, updating num by adding the numeric value of the current character to the current num value (num = num * 10 + digit).
• 3. For each step, check if num is divisible by m. If yes, set div[i] = 1, otherwise set div[i] = 0.
Empty Inputs:
• The input word will always have at least one character.
Large Inputs:
• For large inputs (word length up to 10^5), the approach ensures efficient computation by processing each character in linear time.
Special Values:
• If m is a large number, ensure the calculations do not overflow (use modulo operation).
Constraints:
• Handle edge cases such as very small or very large values of m.
vector<int> divisibilityArray(string word, int m) {
int n = word.size();
vector<int> ans(n, 0);
long num = 0;
for(int i = 0; i < n; i++) {
num = num * 10 + (word[i] - '0');
num %= m;
if(num % m == 0) ans[i] = 1;
else ans[i] = 0;
}
return ans;
}
1 : Function Declaration
vector<int> divisibilityArray(string word, int m) {
Declares the function `divisibilityArray` with a string input `word` and integer `m` as parameters. Returns a vector of integers.
2 : Initialize Length
int n = word.size();
Calculates the size of the input string `word` and stores it in variable `n`.
3 : Initialize Result Array
vector<int> ans(n, 0);
Creates a vector `ans` of size `n`, initialized with zeros, to store the divisibility results.
4 : Initialize Variable
long num = 0;
Initializes a variable `num` to 0, which will be used to compute the cumulative number modulo `m`.
5 : Iterate String
for(int i = 0; i < n; i++) {
Starts a loop to iterate through each character of the string `word`.
6 : Update Cumulative Value
num = num * 10 + (word[i] - '0');
Updates the cumulative number `num` by adding the current character's numerical value.
7 : Apply Modulo Operation
num %= m;
Applies the modulo operation to `num` to ensure it remains within the range of `m`.
8 : Check Divisibility
if(num % m == 0) ans[i] = 1;
Checks if `num` is divisible by `m`. If true, sets the corresponding index in `ans` to 1.
9 : Set Non Divisible
else ans[i] = 0;
If `num` is not divisible by `m`, sets the corresponding index in `ans` to 0.
10 : Return Result
return ans;
Returns the vector `ans` containing the divisibility results.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) as we process each character of the word exactly once.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the array storing the divisibility results.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus