A program was supposed to print an array of integers. The program forgot to print whitespaces and the array is printed as a string of digits s and all we know is that all integers in the array were in the range [1, k] and there are no leading zeros in the array.
Given the string s and the integer k, return the number of the possible arrays that can be printed as s using the mentioned program. Since the answer may be very large, return it modulo 109 + 7.
Example 1:
Input: s = "1000", k = 10000 Output: 1 Explanation: The only possible array is [1000]
Example 2:
Input: s = "1000", k = 10 Output: 0 Explanation: There cannot be an array that was printed this way and has all integer >= 1 and <= 10.
Example 3:
Input: s = "1317", k = 2000 Output: 8 Explanation: Possible arrays are [1317],[131,7],[13,17],[1,317],[13,1,7],[1,31,7],[1,3,17],[1,3,1,7]
Constraints:
1 <= s.length <= 105s consists of only digits and does not contain leading zeros.1 <= k <= 109When 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:
This recursion tries every place to end the next number, starting from the left. A branch dies when the next number would start with zero or grow larger than the limit. Each way of consuming the whole string contributes one, and every returned total is reduced by the modulus.
Here's how the algorithm would work step-by-step:
class Solution:
def numberOfArrays(self, digit_string: str, max_value: int) -> int:
def count_valid_splits_from_index(start_index):
# Base case: If we've successfully processed the entire string, we've found one valid way.
if start_index == len(digit_string):
return 1
# A number cannot start with '0', so if the current substring does, it's an invalid split.
if digit_string[start_index] == '0':
return 0
total_ways_from_this_point = 0
current_number = 0
# Iterate through all possible next numbers starting from the current position.
for end_index in range(start_index, len(digit_string)):
current_number = current_number * 10 + int(digit_string[end_index])
# If the number formed exceeds the maximum allowed value, any longer number will also exceed it.
if current_number > max_value:
break
total_ways_from_this_point += count_valid_splits_from_index(end_index + 1)
# The modulo is applied here as per problem constraints, though it's for large results.
return total_ways_from_this_point % (10**9 + 7)
return count_valid_splits_from_index(0)This fill computes how many legal ways exist for every suffix, from the end of the digits backward. The end suffix has one way, an empty split. Each earlier start adds the ways of the suffixes that follow a number which fits under the limit and does not start with zero.
Here's how the algorithm would work step-by-step:
class Solution:
def numberOfArrays(self, digit_string: str, max_value: int) -> int:
string_length = len(digit_string)
modulus_value = 10**9 + 7
# Memoization array to store results for subproblems, avoiding redundant calculations.
# `ways_to_split[i]` will hold the number of valid ways to parse the suffix `digit_string[i:]`.
ways_to_split = [0] * (string_length + 1)
ways_to_split[string_length] = 1
for start_index in range(string_length - 1, -1, -1):
# If the current substring starts with '0', no valid number can be formed.
if digit_string[start_index] == '0':
continue
current_number = 0
for end_index in range(start_index, string_length):
current_number = current_number * 10 + int(digit_string[end_index])
# A number is valid only if it does not exceed the given maximum value.
if current_number > max_value:
break
# If a valid number is formed, add the number of ways the rest of the string can be split.
ways_to_split[start_index] = (ways_to_split[start_index] + ways_to_split[end_index + 1]) % modulus_value
return ways_to_split[0]| Case | How to Handle |
|---|---|
| The piece at the current start begins with zero | Return zero ways from that start, because a number cannot have a leading zero. |
| The start index has reached the end of the digits | Return one, because the digits have been fully split into a valid array. |
| Adding another digit would push the current number past the limit | Stop lengthening that number, because every longer continuation is larger too. |
| The whole string is a single zero | Return zero, because the only possible piece starts with zero. |
| Many cuts of one digit are valid | Add the ways coming from each later suffix, and reduce the sum by the modulus. |
| The running total of ways exceeds the modulus | Keep only the remainder modulo one billion and seven after combining suffix counts. |