extract all possible combination of numbers within a range in a string of digits

user_19324999 0
Viewed 70

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

computer-science algorithm
2 Answers

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.

user_20410770

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}
user_20347870
Related