TopCoder problem "NumberSplit" used in SRM 242 (Division II Level Three)



Problem Statement

    

We start with an integer and create a sequence of successors using the following procedure: First split the decimal representation of the given number into several (at least two) parts, and multiply the parts to get a possible successor. With the selected successor, we repeat this procedure to get a third number, and so on, until we reach a single-digit number.

For example, let's say we start with the number 234. The possible successors are:

  • 23 * 4 = 92,
  • 2 * 34 = 68 and
  • 2 * 3 * 4 = 24.
If we select 68 as the successor, we then generate 6 * 8 = 48 (the only possibility), from this we generate 4 * 8 = 32 and finally 3 * 2 = 6. With this selection, we have generated a sequence of 5 integers (234, 68, 48, 32, 6).

Given the starting number, start, return the length of the longest sequence that can be generated with this procedure. In the example, the given sequence would be the longest one since the other selections in the first step would give the sequences: (234, 92, 18, 8) and (234, 24, 8), which are both shorter than (234, 68, 48, 32, 6).

 

Definition

    
Class:NumberSplit
Method:longestSequence
Parameters:int
Returns:int
Method signature:int longestSequence(int start)
(be sure your method is public)
    
 

Notes

-There can not exist an infinite sequence.
-Although we use no leading zeros in the decimal representation of the number we start with, the parts we get by splitting the number may have leading zeros (e.g. from 3021 we can get 3 * 021 = 63).
 

Constraints

-start is between 1 and 100000, inclusive.
 

Examples

0)
    
6
Returns: 1
A single-digit number is already the last number.
1)
    
97
Returns: 4
For two-digit numbers, there is always only one possible sequence. Here: 97 -> 63 -> 18 -> 8 (4 numbers).
2)
    
234
Returns: 5
The example from the problem statement.
3)
    
876
Returns: 7
Here, it is optimal to make a three way split in the first step - i.e. use 8*7*6=336 as the first successor. Although a two way split would lead to a larger number (87*6=522 or 8*76=608), both these choices would lead in the end to a shorter sequence. The optimal sequence is: 876, 8*7*6=336, 33*6=198, 19*8=152, 1*52=52, 5*2=10, 1*0=0.
4)
    
99999
Returns: 29

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4451

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=7217&pm=4451

Writer:

gepa

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Dynamic Programming, Graph Theory, Simple Math