Statistics

Problem Statement for "NumberSplit"

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

  1. 6

    Returns: 1

    A single-digit number is already the last number.

  2. 97

    Returns: 4

    For two-digit numbers, there is always only one possible sequence. Here: 97 -> 63 -> 18 -> 8 (4 numbers).

  3. 234

    Returns: 5

    The example from the problem statement.

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

  5. 99999

    Returns: 29

  6. 10

    Returns: 2

  7. 32

    Returns: 2

  8. 99

    Returns: 3

  9. 102

    Returns: 3

  10. 60009

    Returns: 4

  11. 39

    Returns: 4

  12. 77

    Returns: 5

  13. 117

    Returns: 6

  14. 139

    Returns: 7

  15. 419

    Returns: 8

  16. 619

    Returns: 9

  17. 777

    Returns: 10

  18. 4

    Returns: 1

  19. 300

    Returns: 2

  20. 109

    Returns: 3

  21. 950

    Returns: 4

  22. 1604

    Returns: 5

  23. 841

    Returns: 6

  24. 776

    Returns: 7

  25. 796

    Returns: 8

  26. 4212

    Returns: 9

  27. 22071

    Returns: 10

  28. 44255

    Returns: 11

  29. 33145

    Returns: 12

  30. 22222

    Returns: 13

  31. 6896

    Returns: 14

  32. 90542

    Returns: 15

  33. 31723

    Returns: 16

  34. 77875

    Returns: 17

  35. 29551

    Returns: 18

  36. 28856

    Returns: 19

  37. 63526

    Returns: 20

  38. 41821

    Returns: 21

  39. 34718

    Returns: 22

  40. 68606

    Returns: 23

  41. 89174

    Returns: 24

  42. 69178

    Returns: 25

  43. 94816

    Returns: 26

  44. 99774

    Returns: 27

  45. 89924

    Returns: 28

  46. 98994

    Returns: 29

  47. 99991

    Returns: 30

  48. 94389

    Returns: 31

  49. 100000

    Returns: 2

  50. 97

    Returns: 4

  51. 9998

    Returns: 18

  52. 100000

    Returns: 2

  53. 234

    Returns: 5

  54. 23579

    Returns: 19

  55. 99999

    Returns: 29

  56. 876

    Returns: 7

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.
This problem was used for: