RedundantStrings
SRM 238 · 2005-04-14 · by AdminBrett
SRM 238 · 2005-04-14 · by AdminBrett · Recursion, Simple Math
Problem Statement
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.
Only considering strings composed of a's and b's, return the number of redundant strings that have the given length.
Constraints
- length will be between 1 and 60 inclusive.
Examples
0)
60 Returns: 1074793396
1)
1 Returns: 0
There are no redundant strings of length 1.
2)
2 Returns: 2
Both "aa" and "bb" are redundant.
3)
4 Returns: 4
Here the redundant strings are "aaaa", "bbbb", "abab", and "baba".
4)
58 Returns: 536870914
Submissions are judged against all 76 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class RedundantStrings with a public method int howMany(int length) · 76 test cases · 2 s / 256 MB per case