so here's my question assume we had a list of numbers with a known upper and lower bound on the numbers there is no zero in the list (and also no leading zeros)
this list was before separated with spaces but all the spaces are removed and now a string of digits is left given this string and the upper and lower bound, how can I calculate the number of all possible combinations
for example
the string : 1337
lower bound : 2
upper bound : 1500
the answer is 4
{13, 3, 7} {13, 37} {133, 7} {1337}
another example string: 405 lower bound: 0 upper bound: 100
the answer is 1 since we can't have zeros or leading zeros in the list the only valid combination is {40 ,5}
I've come across this problem and have no idea where to start so any help is appreciated
CodePudding user response:
You can solve this with dynamic programming.
Let A be an array such that A[i] is the answer based on the digits up to the i'th digit (zero-indexed).
Then A[i] = the sum of:
1 if the the digits up to i are a valid number
A[i-k] for each k such that the digits k 1 through i are valid.
Example:
the string : 1337
lower bound : 2
upper bound : 1500
A[0] = 0 because 1 isn't valid.
A[1] = 1 A[0] because 13 is valid and 3 is valid, so A[1] = 1
A[2] = 1 A[1] A[0] for similar reasoning, so A[2] = 2
A[3] = 1 A[0] A[1] A[2] so A[3] = 4
The final entry of the array is your answer: 4.
CodePudding user response:
For an O(n)
solution, using Dave's method, we can use prefix sums for the dynamic state and pointers for the valid window.
1 3 3 7 8 [2, 1500]
0
^
0 1
^ ^
0 1 3
^ ^
0 1 3 7
^ ^
0 1 3 7 14 (7 = 1 7 - 1)
^ ^
{13,378}
{133,78}
{1337,8}
{13,3,78}
{13,37,8}
{133,7,8}
{13,3,7,8}