A single row has n parking spots in a line. Each spot is either empty or holds one car. For safety, no two occupied spots may be next to each other. Count the number of valid occupancy patterns for the whole row. The empty row (all spots empty) counts as one valid pattern. The answer always fits in a 64-bit integer for the given constraints, so print the exact count (no modulo).
A single line with one integer n.
A single integer: the number of valid occupancy patterns.
Example 1
Input
3
Expected
5
Explanation
Valid patterns of 3 spots (0=empty,1=car): 000,001,010,100,101 = 5.
Example 2
Input
0
Expected
1
Explanation
A row with no spots has exactly one pattern (the empty pattern).
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →