Statistics

Problem Statement for "RedundantStrings"

Problem Statement

A string composed of a's and b's is either redundant or non-redundant. A string is redundant if and only if it can be expressed as a shorter string replicated multiple times. For example, the string "ababab" is redundant since it is 3 copies of "ab" concatenated together. The string "ab" is called a root of "ababab". The string "aaaa" has 2 roots: "aa" and "a". A nice result in formal languages states that every redundant string has exactly 1 non-redundant root (it may have many redundant roots).

Only considering strings composed of a's and b's, return the number of redundant strings that have the given length.

Definition

Class:
RedundantStrings
Method:
howMany
Parameters:
int
Returns:
int
Method signature:
int howMany(int length)
(be sure your method is public)

Constraints

  • length will be between 1 and 60 inclusive.

Examples

  1. 60

    Returns: 1074793396

  2. 1

    Returns: 0

    There are no redundant strings of length 1.

  3. 2

    Returns: 2

    Both "aa" and "bb" are redundant.

  4. 4

    Returns: 4

    Here the redundant strings are "aaaa", "bbbb", "abab", and "baba".

  5. 58

    Returns: 536870914

  6. 59

    Returns: 2

  7. 10

    Returns: 34

  8. 30

    Returns: 33814

  9. 1

    Returns: 0

  10. 2

    Returns: 2

  11. 3

    Returns: 2

  12. 4

    Returns: 4

  13. 5

    Returns: 2

  14. 6

    Returns: 10

  15. 7

    Returns: 2

  16. 8

    Returns: 16

  17. 9

    Returns: 8

  18. 10

    Returns: 34

  19. 11

    Returns: 2

  20. 12

    Returns: 76

  21. 13

    Returns: 2

  22. 14

    Returns: 130

  23. 15

    Returns: 38

  24. 16

    Returns: 256

  25. 17

    Returns: 2

  26. 18

    Returns: 568

  27. 19

    Returns: 2

  28. 20

    Returns: 1036

  29. 21

    Returns: 134

  30. 22

    Returns: 2050

  31. 23

    Returns: 2

  32. 24

    Returns: 4336

  33. 25

    Returns: 32

  34. 26

    Returns: 8194

  35. 27

    Returns: 512

  36. 28

    Returns: 16396

  37. 29

    Returns: 2

  38. 30

    Returns: 33814

  39. 31

    Returns: 2

  40. 32

    Returns: 65536

  41. 33

    Returns: 2054

  42. 34

    Returns: 131074

  43. 35

    Returns: 158

  44. 36

    Returns: 266176

  45. 37

    Returns: 2

  46. 38

    Returns: 524290

  47. 39

    Returns: 8198

  48. 40

    Returns: 1048816

  49. 41

    Returns: 2

  50. 42

    Returns: 2113462

  51. 43

    Returns: 2

  52. 44

    Returns: 4194316

  53. 45

    Returns: 33272

  54. 46

    Returns: 8388610

  55. 47

    Returns: 2

  56. 48

    Returns: 16842496

  57. 49

    Returns: 128

  58. 50

    Returns: 33555424

  59. 51

    Returns: 131078

  60. 52

    Returns: 67108876

  61. 53

    Returns: 2

  62. 54

    Returns: 134479360

  63. 55

    Returns: 2078

  64. 56

    Returns: 268435696

  65. 57

    Returns: 524294

  66. 58

    Returns: 536870914

  67. 59

    Returns: 2

  68. 60

    Returns: 1074793396

  69. 55

    Returns: 2078

  70. 60

    Returns: 1074793396

  71. 5

    Returns: 2

  72. 16

    Returns: 256

  73. 30

    Returns: 33814

  74. 9

    Returns: 8

  75. 8

    Returns: 16

  76. 32

    Returns: 65536

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: