Connection Status:
Competition Arena > NumberSplit

NumberSplit

SRM 242 · 2005-05-14 · by gepa

SRM 242 · 2005-05-14 · by gepa · Dynamic Programming, Graph Theory, Simple Math
Class Name: NumberSplit
Return Type: int
Method Name: longestSequence
Arg Types: (int)
Problem Statement

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).

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

Submissions are judged against all 56 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class NumberSplit with a public method int longestSequence(int start) · 56 test cases · 2 s / 256 MB per case

Submitting as anonymous