Jobs

Interviews

Discussions

Find the Divisibility Array of a String

Medium

Asked by:

16 views

Topics:

ArraysStrings

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 <= 10⁵
word.length == n
word consists of digits from 0 to 9
1 <= m <= 10⁹

Try coding it in LeetCode

Find the Divisibility Array of a String

Medium

Asked by:

16 views

Topics:

ArraysStrings

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 <= 10⁵
word.length == n
word consists of digits from 0 to 9
1 <= m <= 10⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for k, and can it be zero?
Can the input string `word` be empty or null?
Can the digits in the string `word` be non-numeric characters?
What should be returned if a digit at some index 'i' is '0' but the current prefix is not divisible by k (since 0 is divisible by any k)? Should the result at index i be 0 or 1?
Is `k` guaranteed to be a positive integer?

Brute Force Solution

Approach

The goal is to figure out, for each position in a number written as a string, whether the number up to that position is perfectly divisible by a given number. The brute force method involves checking the divisibility at every single position by recalculating the number from the start of the string for each position.

Here's how the algorithm would work step-by-step:

Start at the very beginning of the string representing the number.
Consider only the first digit of the number and see if that single digit is divisible by the given number.
Make a note of whether it is divisible or not.
Now, take the first two digits of the number and treat them as a two-digit number. See if this two-digit number is divisible by the given number.
Again, make a note of whether it is divisible or not.
Keep doing this, each time adding one more digit to the number you are considering. So, first one digit, then two digits, then three digits, and so on, until you have considered the entire number.
At each step, check if the number formed so far is divisible by the given number, and note the result (yes or no).
In the end, you will have a list of 'yes' or 'no' answers, one for each digit in the original number, telling you whether the number formed up to that point is divisible by the given number.

Code Implementation

def find_divisibility_array(number_string, divisor):
    divisibility_array = []
    current_number = 0

    for digit_index in range(len(number_string)):
        # Rebuild the number from the start of the string.
        current_number = int(number_string[:digit_index+1])

        # Check if the current number is divisible by the divisor
        if current_number % divisor == 0:
            divisibility_array.append(1)

        else:
            divisibility_array.append(0)

    return divisibility_array

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the string of length n once. In each iteration, it extends the current number being considered by one digit and checks for divisibility. The divisibility check itself takes constant time. Therefore, the overall time complexity is directly proportional to the length of the input string, resulting in O(n).

Space Complexity

O(N) – The algorithm creates a list or array to store the divisibility results ('yes' or 'no') for each position in the input string. The length of this list grows linearly with the length of the input string, denoted as N. Therefore, the auxiliary space used is proportional to the input size N. This means we are using O(N) additional space.

Optimal Solution

Approach

We want to figure out for each part of a number (represented as a string), if that part is divisible by another number. The clever trick is to keep track of the remainder as we move from left to right. We use this remainder to quickly calculate the remainder for the next larger part of the number.

Here's how the algorithm would work step-by-step:

Start with a remainder of zero.
Look at the first digit of the number.
Combine the current remainder with this digit to form a new number.
Check if this new number is divisible by the divisor.
Record whether it is divisible (yes or no).
Calculate the new remainder by finding the remainder when the new number is divided by the divisor.
Move to the next digit in the number.
Repeat the process of combining the previous remainder, checking divisibility, recording the result, and calculating the new remainder until you have processed all digits.

Code Implementation

def find_divisibility_array(number_string, divisor):
    divisibility_array = []
    current_remainder = 0

    for digit_char in number_string:
        current_digit = int(digit_char)
        
        # Combine the previous remainder with the current digit
        combined_number = current_remainder * 10 + current_digit

        #Check if the combined number is divisible by the divisor
        if combined_number % divisor == 0:
            divisibility_array.append(1)
        else:
            divisibility_array.append(0)

        # Calculate the new remainder for the next iteration
        current_remainder = combined_number % divisor

    return divisibility_array

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string 'word' of length 'n' exactly once. Inside the loop, it performs a constant number of operations: calculating a new number using the previous remainder and the current digit, checking for divisibility using the modulo operator, recording the result, and updating the remainder. Since the number of operations within the loop is constant and the loop runs 'n' times, the overall time complexity is directly proportional to 'n', resulting in O(n).

Space Complexity

O(N) – The algorithm creates a new array to store the divisibility results, where each element indicates whether the corresponding prefix of the input string's number is divisible by the divisor. The size of this array is directly proportional to the length of the input string. Therefore, the auxiliary space used is O(N), where N is the length of the input string representing the number.

Edge Cases

Case	How to Handle
Null or empty input string `word`	Return an empty array or throw an IllegalArgumentException as appropriate for invalid input.
Divisor `m` is zero	Throw an ArithmeticException or IllegalArgumentException as division by zero is undefined.
Single digit string and small divisor (e.g., "1", m = 2)	The algorithm should correctly calculate and return [1 % m].
Large input string that could cause integer overflow when calculating the prefix modulo m	Use long or BigInteger to avoid overflow when calculating the prefix modulo m.
String representing a very large number (e.g., 1000 digits) and a small divisor	Ensure the algorithm's time complexity is linear with the length of the input string, and does not recursively compute the integer value.
Divisor `m` is 1	The resulting divisibility array should be all ones since every number is divisible by 1.
Divisor `m` is a very large number, much larger than the accumulated value of the prefix at any point.	The modulus operation should still work correctly, potentially optimizing for the case where the prefix is always less than m.
String contains leading zeros	Leading zeros should be treated as part of the number and contribute to the divisibility calculation.

Null or empty input string `word`

How to Handle:

Return an empty array or throw an IllegalArgumentException as appropriate for invalid input.

Divisor `m` is zero

How to Handle:

Throw an ArithmeticException or IllegalArgumentException as division by zero is undefined.

Single digit string and small divisor (e.g., "1", m = 2)

How to Handle:

The algorithm should correctly calculate and return [1 % m].

Large input string that could cause integer overflow when calculating the prefix modulo m

How to Handle:

Use long or BigInteger to avoid overflow when calculating the prefix modulo m.

String representing a very large number (e.g., 1000 digits) and a small divisor

How to Handle:

Ensure the algorithm's time complexity is linear with the length of the input string, and does not recursively compute the integer value.

Divisor `m` is 1

How to Handle:

The resulting divisibility array should be all ones since every number is divisible by 1.

Divisor `m` is a very large number, much larger than the accumulated value of the prefix at any point.

How to Handle:

The modulus operation should still work correctly, potentially optimizing for the case where the prefix is always less than m.

String contains leading zeros

How to Handle:

Leading zeros should be treated as part of the number and contribute to the divisibility calculation.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for k, and can it be zero?
Can the input string `word` be empty or null?
Can the digits in the string `word` be non-numeric characters?
What should be returned if a digit at some index 'i' is '0' but the current prefix is not divisible by k (since 0 is divisible by any k)? Should the result at index i be 0 or 1?
Is `k` guaranteed to be a positive integer?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the very beginning of the string representing the number.
Consider only the first digit of the number and see if that single digit is divisible by the given number.
Make a note of whether it is divisible or not.
Now, take the first two digits of the number and treat them as a two-digit number. See if this two-digit number is divisible by the given number.
Again, make a note of whether it is divisible or not.
Keep doing this, each time adding one more digit to the number you are considering. So, first one digit, then two digits, then three digits, and so on, until you have considered the entire number.
At each step, check if the number formed so far is divisible by the given number, and note the result (yes or no).
In the end, you will have a list of 'yes' or 'no' answers, one for each digit in the original number, telling you whether the number formed up to that point is divisible by the given number.

Code Implementation

def find_divisibility_array(number_string, divisor):
    divisibility_array = []
    current_number = 0

    for digit_index in range(len(number_string)):
        # Rebuild the number from the start of the string.
        current_number = int(number_string[:digit_index+1])

        # Check if the current number is divisible by the divisor
        if current_number % divisor == 0:
            divisibility_array.append(1)

        else:
            divisibility_array.append(0)

    return divisibility_array

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start with a remainder of zero.
Look at the first digit of the number.
Combine the current remainder with this digit to form a new number.
Check if this new number is divisible by the divisor.
Record whether it is divisible (yes or no).
Calculate the new remainder by finding the remainder when the new number is divided by the divisor.
Move to the next digit in the number.
Repeat the process of combining the previous remainder, checking divisibility, recording the result, and calculating the new remainder until you have processed all digits.

Code Implementation

def find_divisibility_array(number_string, divisor):
    divisibility_array = []
    current_remainder = 0

    for digit_char in number_string:
        current_digit = int(digit_char)
        
        # Combine the previous remainder with the current digit
        combined_number = current_remainder * 10 + current_digit

        #Check if the combined number is divisible by the divisor
        if combined_number % divisor == 0:
            divisibility_array.append(1)
        else:
            divisibility_array.append(0)

        # Calculate the new remainder for the next iteration
        current_remainder = combined_number % divisor

    return divisibility_array

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string `word`	Return an empty array or throw an IllegalArgumentException as appropriate for invalid input.
Divisor `m` is zero	Throw an ArithmeticException or IllegalArgumentException as division by zero is undefined.
Single digit string and small divisor (e.g., "1", m = 2)	The algorithm should correctly calculate and return [1 % m].
Large input string that could cause integer overflow when calculating the prefix modulo m	Use long or BigInteger to avoid overflow when calculating the prefix modulo m.
String representing a very large number (e.g., 1000 digits) and a small divisor	Ensure the algorithm's time complexity is linear with the length of the input string, and does not recursively compute the integer value.
Divisor `m` is 1	The resulting divisibility array should be all ones since every number is divisible by 1.
Divisor `m` is a very large number, much larger than the accumulated value of the prefix at any point.	The modulus operation should still work correctly, potentially optimizing for the case where the prefix is always less than m.
String contains leading zeros	Leading zeros should be treated as part of the number and contribute to the divisibility calculation.

Null or empty input string `word`

How to Handle:

Return an empty array or throw an IllegalArgumentException as appropriate for invalid input.

Divisor `m` is zero

How to Handle:

Throw an ArithmeticException or IllegalArgumentException as division by zero is undefined.

Single digit string and small divisor (e.g., "1", m = 2)

How to Handle:

The algorithm should correctly calculate and return [1 % m].

Large input string that could cause integer overflow when calculating the prefix modulo m

How to Handle:

Use long or BigInteger to avoid overflow when calculating the prefix modulo m.

String representing a very large number (e.g., 1000 digits) and a small divisor

How to Handle:

Ensure the algorithm's time complexity is linear with the length of the input string, and does not recursively compute the integer value.

Divisor `m` is 1

How to Handle:

The resulting divisibility array should be all ones since every number is divisible by 1.

Divisor `m` is a very large number, much larger than the accumulated value of the prefix at any point.

How to Handle:

The modulus operation should still work correctly, potentially optimizing for the case where the prefix is always less than m.

String contains leading zeros

How to Handle:

Leading zeros should be treated as part of the number and contribute to the divisibility calculation.