235. Strings With No Two Ones Together
Core1000 ms256 MBSolved by 0%
Print how many binary strings of length n contain no two 1s next to each
other.
n = 3 -> 000 001 010 100 101 is 5
Build the string one character at a time and the choice at each step depends
only on what the previous character was. After a 0 you may place either
digit; after a 1 you must place a 0.
So the state is just the length remaining and whether the last character was a one, which is two numbers rather than the whole string.
Constraints - `1 ≤ n ≤ 86` - The answer fits in a signed 64-bit integer.
Input
A single line containing one integer n.
Output
Print one integer, the number of valid strings of length n.
Input3
Output5
Noteis the worked example, with all five strings listed
Input1
Output2
Noteis length one, where both 0 and 1 are valid
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.