A coastal signal network operates n + 1 relay beacons, numbered 0 through n in a single line. Beacon 0 always stays dark, with brightness 0, and beacon 1 always glows at brightness 1 (these two rules apply whenever n >= 1). Every other beacon's brightness is derived automatically from beacons with smaller indices, following one of two rules depending on whether its index is even or odd:
Given n, build the brightness values for beacons 0 through n using this rule and report the highest brightness value that appears anywhere in the chain.
A single line containing one integer n.
A single integer: the maximum brightness value among beacons 0 through n.
Example 1
Input
7
Expected
3
Explanation
Beacons 0..7 get brightness 0,1,1,2,1,3,2,3: beacon2(even)=beacon1=1; beacon3(odd)=beacon1+beacon2=1+1=2; beacon4(even)=beacon2=1; beacon5(odd)=beacon2+beacon3=1+2=3; beacon6(even)=beacon3=2; beacon7(odd)=beacon3+beacon4=2+1=3. The brightest beacon reaches 3, so the answer is 3.
Example 2
Input
3
Expected
2
Explanation
Beacons 0..3 get brightness 0,1,1,2: beacon2(even)=beacon1=1; beacon3(odd)=beacon1+beacon2=1+1=2. The brightest value seen is 2.
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 →