Separate Numbers

Hard
0/120
profile
Contributed by
0 upvote

Problem statement

You are given a string ‘NUM’, the string is made up of digits (0-9),. Your task is to find the number of ways to split the string of digits into a list of non-decreasing positive integers and no integer should have leading zeros.

Note : 
The answer may be very large so return it modulo ‘10^9 + 7’.
For Example : 
You are given ‘NUM’ = “329”, Here you can split the string as [3, 29] and [329]. Since there are 2 ways the answer will be 2.
Note that a split [32, 9] is invalid because the list is not in non-decreasing order.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains a single integer ‘T’ representing the number of test cases.

The first and only line of each test case contains a string ‘NUM’ representing the string given in the problem.
Output Format : 
For each test case print a single integer representing the number of ways you can split the string with the given conditions.

Print a separate line for each test case.
Constraints : 
1  <= T <= 10
1 <= NUM.size <= 500
NUM[i] is a digit from 0 to 9

Time Limit: 1 sec
Note : 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Sample Input 1 :
2
329
4256
Sample Output 1 :
2
3
Explanation for Sample Input 1 :
For the first test case, ‘NUM’ = “329”, Here you can split the string as [3, 29] and [329]. Since there are 2 ways to split the string the answer will be 2.

For the second test case ‘NUM’ = “4256”, Here you can split the string as [4, 256], [42, 56], [4256]. Since there are 3 ways to split the string the answer will be 3.
Sample Input 2 :
2
901
023
Sample Output 2 :
1
0
Hint

Try the naive approach to the solution

Approaches (2)
Brute Force

In this approach, we can see that if any string starts with a 0 then it has no was to be separated into a list of non-decreasing positive integers.

 

Let's imagine we know the number of ways to split characters according to the rules before each position in the string and all possible lengths of the previous part. Then for the next position, the number of ways to split characters from start to this position can be calculated recursively.

And what if we know for each position in the string number of ways to split it into parts no longer than D. Then for D +1 we can calculate it from previous values for each position.

 

We will create a function ‘checkString(nums, start1, start2, length)’ which will check if the number formed by starting at ‘start1’ index is less than the number formed by starting at the ‘start2’ index, where both are of ‘length’ length

 

Algorithm:

  • In the checkString(nums, start1, start2, length)
    • While ‘length’ is greater than 0
      • If ‘nums[start1]’ is less than ‘nums[start2]’ return True
      • If ‘nums[start2]’ is less than ‘nums[start1]’ return False.
      • Increase ‘start1’ and ‘start2’ by 1.
    • Return the ‘True’
  • In the given function
    • Set ‘MOD’ as 10<sup>9</sup> + 7
    • If nums[0]’ is ‘0’ return 0
    • If the length of ‘nums’ is 1 return 1
    • Set ‘n’ as the length of ‘nums’
    • Create two arrays of ‘n + 1’ lengths, ‘prev’ and ‘next’
    • Set ‘prev[0]’ and ‘next[0]’ as 1
    • Iterate ‘d’ from 1 to ‘n’
      • Copy all the values of ‘prev’ from index ‘1’ to ‘n’ into ‘next’
      • Iterate ‘j1’ from 0 to ‘n - d’
        • Set ‘j2’ as ‘j1’ - ‘d’, and i1 as ‘j1’ + ‘d’
        • If ‘nums’[j1]’ is ‘0’ continue the loop
        • If i1 is greater than ‘0’ or nums[i1] is not ‘0’ and checkString(nums, i1, j1, d)
          • Increase next[j2] by next[j1]
        • Otherwise
          • Increase next[j2] by prev[j1]
        • Set ‘next[j2]’ as ‘next[j2]’ mod ‘MOD’
    • Finally, return ‘prev[n]’
Time Complexity

O( N ^ 3 ), where N is the length of the given string.

 

We are iterating over all the length of each digit and trying to place the comma at each position, for we check if the numbers are non decreasing which will take ~N^3.

 

Hence the final time complexity is O( N ^ 3 ).

Space Complexity

O( N ), where N is the length of the given string.

 

We are maintaining two arrays of ~N length each.

Hence the overall time complexity O( N )

Code Solution
(100% EXP penalty)
Separate Numbers
Full screen
Console