Qty no. strings

Question

This question was asked in the coding round of the company in our placements.

For a string consisting of numbers from 1 to 9. We need to arrange the string so that it is divided into groups. We need to consider no. possible rows, such that the sum of the group <= the sum of the next consecutive group.

Example1
input: 1234
output: 6
Rows:

• {1,2,3,4}
• {1,2,34}
• {12,3,4}
• {12.34}
• {} 1234
• {1234}

the first combination is here, 1 <2 <3 <4. the second combination, 1 <2 (3 + 4). and so on.

Example2
entrance: 516
output: 3
Rows:

• {5.16}
• {51.6}
• {516}

Now, the time taken by brute force to generate all the rows is O (2 ^ (n-1)). My question is how to solve it better than brute force?

Restriction: input line length 1 <= n <= 1000

Answer 1

This problem can be effectively solved with the help of dynamic programming . I solved this with a two dimensional array called dp . To find the number of valid splits in which the last character end th is the last and the last line starts with the character start th, we need to use the previously computed and cached value for the number of valid splits that ends with start-1 th character. This number is the sum of all cached values ​​in dp[prev_start][start - 1] , where prev_start can be any value between [0, start) , so the sum of elements from s[prev_start:start-1] not more than the sum of elements from s[start:end] . Here is the solution in Python3 :

 def get_count(s): N = len(s) # Initialize memoization matrix # First row all ones, all others zeros dp = list() dp.append([1] * N) for i in range(N - 1): dp.append([0] * N) # Convert characters to integers s = [ord(i) - ord('0') for i in s] for start in range(1, N): for end in range(start, N): for prev_start in range(0, start): if sum(s[prev_start:start]) <= sum(s[start:end+1]): dp[start][end] += dp[prev_start][start - 1] return sum([dp[i][N - 1] for i in range(N)]) print(get_count('516')) 

Note: the time complexity is O (n ^ 4), but you can easily optimize it to O (n ^ 3).