Statistics

Problem Statement for "DeserializeSequence"

Problem Statement

Given a sequence of positive integers in nondescending order you can make a string by concatenating the sequence elements together. For example, the sequence [1,1,13,934] could become the string "01113934". Given a String str containing digits return how many distinct nondescending sequences could have produced str. Two sequences are distinct if they differ in some position, or have different lengths. When put into str, the sequence element could have been padded with leading zeros. For example, [1,2] could become "12", "00010002", "010002" as well as numerous other possible strings. You should assume the integers in the original sequence were between 1 and 1000000 inclusive.

Definition

Class:
DeserializeSequence
Method:
howMany
Parameters:
String
Returns:
int
Method signature:
int howMany(String str)
(be sure your method is public)

Constraints

  • str must contain between 1 and 50 characters inclusive.
  • Each character of str must be a digit ('0' - '9').

Examples

  1. "1234"

    Returns: 5

    The 5 possible sequences are: [1,2,3,4] [1,2,34] [1,234] [1234] [12,34]

  2. "000000000001"

    Returns: 1

    [1] is the only possible sequence here.

  3. "1000000000000"

    Returns: 0

    No possible sequences.

  4. "9876543210"

    Returns: 5

  5. "11111111111111111111111111111111111111111111111111"

    Returns: 9192

  6. "99999999999999999999999999999999999999999999999999"

    Returns: 9192

  7. "01234567890123456789012345678901234567890123456789"

    Returns: 1

  8. "01234567890123456789012345678901234567890000006789"

    Returns: 0

  9. "91919191919191919191919191919191919191919191919191"

    Returns: 261

  10. "10010010010010010010010010010010010010010010010010"

    Returns: 1217

  11. "123456789876543212345678987654321"

    Returns: 6

  12. "056723859897809708891720897401235298"

    Returns: 0

  13. "54178991578409123049108759"

    Returns: 3

  14. "00000111112222233333444445555566666777778888899999"

    Returns: 5942

  15. "999998888877777666665555544444333332222211111"

    Returns: 0

  16. "11111111111111111111111119999999999999999999999999"

    Returns: 9192

  17. "64759785162140436046023132270364266132872271316731"

    Returns: 0

  18. "51804153084121281073270677068788574654138873291694"

    Returns: 1

  19. "48890210448421966175713942393846139557749131538637"

    Returns: 0

  20. "47972286581680292625312567567845873411519103224764"

    Returns: 0

  21. "98697462513682181855656910276118186569260153375644"

    Returns: 1

  22. "32305448697244425906003787901125406091914778415747"

    Returns: 0

  23. "22954446290943481540318236048644313856292315368595"

    Returns: 0

  24. "23175163484901846640490442727045766737634593035777"

    Returns: 0

  25. "35144059683169872903828335902343747528354620962516"

    Returns: 0

  26. "26054511613037193992817442536382125532833174709203"

    Returns: 0

  27. "65018221051981711016896996705078373883607688597363"

    Returns: 0

  28. "22119737326607545579442309386494435008392385807658"

    Returns: 0

  29. "23557333122166346129667878925081225693848801368342"

    Returns: 0

  30. "12046251738076865856641507882669212254883519388776"

    Returns: 0

  31. "72691177825989628891353457350628887248974976397227"

    Returns: 0

  32. "2205030653"

    Returns: 13

  33. "4120985914"

    Returns: 9

  34. "66057063275699"

    Returns: 14

  35. "9389274"

    Returns: 4

  36. "508851590880"

    Returns: 16

  37. "14723559267"

    Returns: 17

  38. "5709585563"

    Returns: 13

  39. "1202791389"

    Returns: 20

  40. "992476549"

    Returns: 9

  41. "706073155"

    Returns: 6

  42. "80563505"

    Returns: 4

  43. "6885368211532289452"

    Returns: 24

  44. "1343625288"

    Returns: 17

  45. "7810278789278"

    Returns: 15

  46. "93249"

    Returns: 4

  47. "32452365323233262"

    Returns: 12

  48. "9876543210"

    Returns: 5

  49. "10010010010010010010010010010010010010010010010010"

    Returns: 1217

  50. "1000000"

    Returns: 1

  51. "10001001010001000011001000100000011110100101010010"

    Returns: 53

  52. "0105177821993492100320022188860042353"

    Returns: 0

  53. "21474836480000000000000000000000000000000000000001"

    Returns: 0

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: