2575. Find the Divisibility Array of a String
Problem Description
In this problem, we have a string word
which is made up of digit characters (0 to 9) and a positive integer m
. The idea is to create a divisibility array div
from this string. This array will have the same length as the word
and each of its elements will either be a 1
or a 0
. The rule for the divisibility array is as follows: if the number represented by the substring of word
from index 0
to index i
can be divided by m
without any remainder, then div[i]
will be 1
. Otherwise, div[i]
will be 0
. The task is to return this divisibility array.
An example for clarity: If our word
is "1234"
and m=2
, our div
array should be [0, 1, 0, 0]
because only the substring "12"
is divisible by 2
.
Intuition
The approach to solving this problem involves a consideration of how numbers in base 10 are constructed and how divisibility checks are performed. A key insight is that if we are to calculate whether various prefixes of a number are divisible by m
, it's not efficient to compute the entire number from scratch at each step.
Instead, we employ a modular arithmetic property that allows us to update our current value by taking into account only the newly added digit. Specifically, if we want to shift a number x
by one decimal place and then add a digit d
, this can be expressed as 10*x + d
. However, since we're only interested in divisibility by m
, we can work with x
and d
modulo m
to keep the numbers small and manageable.
Respectively, with each new digit encountered in the word
, we multiply our running tally x
by 10 and add the numerical value of the current digit, always taking the modulo m
after each operation. This keeps x
as the remainder of the number composed of digits seen so far divided by m
. If at any point x
becomes 0
, the number composed of digits up to that point is divisible by m
, and we add 1
to our answer array; otherwise, we add 0
.
We iterate over each character in the word
, apply the process described above, and construct our divisibility array incrementally. This method is efficient and avoids redundant calculations, allowing us to get the answer in linear time with respect to the length of word
.
Learn more about Math patterns.
Solution Approach
The provided solution uses a straightforward approach where no additional complex data structures or patterns are employed. The algorithm relies on basic arithmetic operations, specifically the modulus operation, and it follows the incremental construction philosophy:
-
Initialize an empty list
ans
which will eventually hold the resulting divisibility array. -
Begin with a variable
x
set to0
. This variable represents the current numeric value as we process each character of the input stringword
, considering the modulom
. -
Iterate over each character
c
in the stringword
. For each character,- Convert the character to its integer value.
- Update
x
by multiplying it by10
(shifting the number to the left by one decimal place) and adding the integer value of the current character to include it in our numeric value. - Perform the modulus operation with
m
to updatex
to contain the remainder of the new number modulom
.
-
Check if
x
is0
after the modulus operation. If it is, append1
to the listans
since the number composed of all digits up to this point is divisible bym
. Ifx
is not0
, append0
to the list. -
Proceed to the next character and repeat steps 3 and 4 until all characters are processed.
-
Once done, return the list
ans
as the final divisibility array.
The Python code provided efficiently implements this approach, using a loop to iterate over each character in word
and modifying the variable x
iteratively. The modulus operation is used to ensure that the numerical value considered at each step is within manageable bounds and directly corresponds to the divisibility condition.
It's important to note that this approach, while simple, takes advantage of the modulus operation's property that (a * b) % m = ((a % m) * (b % m)) % m
. This property allows us to keep intermediate values small and perform continuous divisibility checks without having to compute or store large numbers, hence maintaining a constant space complexity with respect to the value of the numbers involved.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach using a small example. Suppose we have the string word = "2034"
and the divisor m = 3
. We want to generate a divisibility array div
such that if the number represented by the substring of word
from index 0
to index i
is divisible by 3
, then div[i]
is 1
; otherwise, it is 0
.
-
Initialize an empty list
ans
to hold the resulting divisibility array. -
Let variable
x
be the running total, initialized to0
. -
We iterate over the characters in
word
. Initially,word[0] = '2'
.- Convert character '2' to its integer value, which is 2.
- Update
x
by calculating(10 * x + 2) % 3 = (0 * 10 + 2) % 3 = 2 % 3 = 2
. - Since
x
is not0
, append0
to the listans
.
-
The list
ans
is now[0]
andx
is2
. -
The next character is '0'.
- Convert '0' to integer 0.
- Update
x
by calculating(10 * x + 0) % 3 = (10 * 2 + 0) % 3 = 20 % 3 = 2
. - Since
x
is not0
, append0
to listans
.
-
The list
ans
is now[0, 0]
andx
is2
. -
The next character is '3'.
- Convert '3' to integer 3.
- Update
x
by calculating(10 * x + 3) % 3 = (10 * 2 + 3) % 3 = 23 % 3 = 2
. - Since
x
is not0
, append0
to listans
.
-
The list
ans
is now[0, 0, 0]
andx
is2
. -
The last character is '4'.
- Convert '4' to integer 4.
- Update
x
by calculating(10 * x + 4) % 3 = (10 * 2 + 4) % 3 = 24 % 3 = 0
. - Since
x
is0
, append1
to listans
.
-
The final divisibility array
ans
is[0, 0, 0, 1]
, which corresponds to the fact that the substring "2034" is divisible by3
, but the substrings "2", "20", and "203" are not.
In this example, the divisibility array div
for word = "2034"
and m = 3
is [0, 0, 0, 1]
.
Solution Implementation
1from typing import List
2
3class Solution:
4 def divisibilityArray(self, word: str, modulus: int) -> List[int]:
5 # Initialize a list to hold the final answers.
6 divisibility_checks = []
7 # Initialize a variable for computing the running remainder.
8 running_remainder = 0
9 # Iterate over each character in the input word (assumed to be digits).
10 for char in word:
11 # Update the running remainder by incorporating the new digit
12 # and taking the remainder with respect to modulus.
13 running_remainder = (running_remainder * 10 + int(char)) % modulus
14 # Append 1 to divisibility_checks if the current running_remainder is 0 (divisible by modulus)
15 # Otherwise, append 0.
16 divisibility_checks.append(1 if running_remainder == 0 else 0)
17 # Return the list of divisibility checks.
18 return divisibility_checks
19
1class Solution {
2 public int[] divisibilityArray(String word, int m) {
3 int wordLength = word.length(); // Get the length of the provided string
4 int[] divisibility = new int[wordLength]; // Create an array to store divisibility results
5
6 long numModM = 0; // Initialize variable to store the modulo m of the number formed so far
7
8 // Iterate over each character in the string
9 for (int i = 0; i < wordLength; ++i) {
10 // Aggregate the number by shifting the previous number by one decimal place
11 // and adding the new digit, then calculate modulo m of the new number
12 numModM = (numModM * 10 + (word.charAt(i) - '0')) % m;
13
14 // If the current aggregated number is divisible by m (modulo is 0)
15 // then set the corresponding position in the result array to 1
16 if (numModM == 0) {
17 divisibility[i] = 1;
18 }
19 }
20
21 return divisibility; // Return the populated divisibility result array
22 }
23}
24
1class Solution {
2public:
3 // Function to create a divisibility array from a string representation of a number
4 vector<int> divisibilityArray(string word, int modulus) {
5 // Initialize an empty vector to store the results
6 vector<int> results;
7 // Variable to keep track of the cumulative remainder
8 long long currentRemainder = 0;
9
10 // Iterate through each character of the string
11 for (char& digitChar : word) {
12 // Convert char to corresponding digit and update the cumulative remainder
13 currentRemainder = (currentRemainder * 10 + digitChar - '0') % modulus;
14 // Check if the current cumulative remainder is divisible by 'modulus' and add the result to 'results'
15 results.push_back(currentRemainder == 0 ? 1 : 0);
16 }
17 // Return the final divisibility array
18 return results;
19 }
20};
21
1/**
2 * Computes an array indicating the divisibility of a number (constructed sequentially
3 * from the input string "word") by the given divisor "m".
4 *
5 * @param {string} word - A string representing the digit sequence to form the number.
6 * @param {number} m - The divisor to check divisibility against.
7 * @returns {number[]} An array with binary values, 1 if divisible and 0 if not, at each step.
8 */
9function divisibilityArray(word: string, m: number): number[] {
10 // Initialize the answer array to be returned
11 const answer: number[] = [];
12
13 // We'll use x to calculate the remainder on each step.
14 let remainder = 0;
15
16 // Iterate over each character in the input "word"
17 for (const digit of word) {
18 // Update the remainder: multiply by 10 (shift left in decimal)
19 // then add the current digit value, and take modulus by "m"
20 remainder = (remainder * 10 + Number(digit)) % m;
21
22 // Add 1 to the answer array if divisible by "m", otherwise add 0
23 answer.push(remainder === 0 ? 1 : 0);
24 }
25
26 // Return the populated answer array
27 return answer;
28}
29
Time and Space Complexity
Time Complexity
The time complexity of the given code is O(n)
, where n
is the length of the word
string. This complexity arises because the code iterates over each character in the word
string exactly once. Within the loop, it performs constant time operations: a multiplication, an addition, a modulo operation, and a conditional check. Since none of these operations depend on the size of the string, they don't add any additional factor to the complexity.
Space Complexity
The space complexity of the code is O(n)
, with n
being the length of the word
string. The additional space is used to store the ans
list, which contains an integer for each character in the word
. No other significant space-consuming structures or recursive calls are involved, so the space complexity is linear with respect to the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!