Loading...
Loading...
Loading...
Farhan is decorating his hostel room with a strip of n bulbs. Each bulb is either on or off. The cheap adapter overheats if two neighbouring bulbs are on at the same time.
Write on as 1 and off as 0. For n = 3 the safe patterns are 000, 001, 010, 100 and 101. Print the number of safe patterns for n bulbs.
Example 1
Input
3
Output
5
000, 001, 010, 100 and 101: 5 patterns. 011, 110 and 111 have two 1s side by side.
Example 2
Input
1
Output
2
One bulb can be on or off: 2 patterns.
Try the problem first. Open one hint at a time.
Fill the bulbs from left to right. What you may put next depends only on the previous bulb.
Write a method count(left, prevOn): the number of ways to fill left more bulbs when the previous bulb is on or off.
A 0 is always allowed. A 1 is allowed only when the previous bulb is off. When left is 0, there is exactly one way: stop.
The plain recursion repeats the same calls billions of times for n = 90. Save each result in a long[][] table and reuse it.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor