Spaced-Out Bit Strings
Problem
A row of n seats must be assigned so that no two neighbouring seats are both occupied. Model it as a binary string of length n where 1 means occupied.
Return how many binary strings of length n contain no two adjacent 1s.
Example 1
- Input:
- n = 3
- Output:
- 5
000, 001, 010, 100 and 101. The strings 011, 110 and 111 have adjacent 1s.
Example 2
- Input:
- n = 1
- Output:
- 2
Both 0 and 1 are valid.
Constraints
- 1 ≤ n ≤ 70
- The answer fits in a 64-bit float without loss (it is below 2^53).
Hint
Show the first hint
Classify valid strings of length i by their last character.
Walkthrough
How to approach it
01Clarify before coding
- Is n at least 1? Yes.
- Do leading zeros count as different strings? Yes: every position is a seat, so 001 and 01 are different lengths and never compared.
- How big can the answer get? For n = 70 it is about 5·10^14, safe in a JavaScript number and a Python int.
02Brute force
Generate all 2^n strings and reject those containing 11.
Cost: O(2^n · n): already a billion strings at n = 30, hopeless at n = 70.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.