NumberSplit | Topcoder Archive

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

```
6
```
```
Returns: 1
```
A single-digit number is already the last number.
```
97
```
```
Returns: 4
```
For two-digit numbers, there is always only one possible sequence. Here: 97 -> 63 -> 18 -> 8 (4 numbers).
```
234
```
```
Returns: 5
```
The example from the problem statement.
```
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.
```
99999
```
```
Returns: 29
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.