Paint the Stairs

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
1 upvote

Problem statement

You are given an integer ‘N’ denoting the number of stairs. You have two colors: red and green. Count the number of ways to paint the stairs with colors red and green such that no two adjacent stairs have red colors painted on both of them.

Return the number of ways modulo 10^9 + 7.

Example: 
Input: ‘N’ = 2 

Output: 3

The number of ways to paint the stairs is: (red, green), (green, red), (green, green), and (red, red). But two adjacent stairs cannot have the color red painted on both of them, (red, red) is not allowed. 
Hence, there are 3 ways to paint 2 stairs.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line will contain the integer 'T', denoting the number of test cases.

The first line of each test case contains an integer number ‘N’’.
Output format : 
For each test case, you don’t need to print anything just return the count of the number of ways to paint ‘N’ stairs.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= N <= 10^5

Time Limit: 1 sec
Sample Input 1 :
2
1
3
Sample Output 1 :
2
5
Explanation Of Sample Input 1 :
For the first case:
We can paint 1 stair with either green or red color. Hence the total number of ways to paint the colors is 2.

For the second case:
All valid ways to paint the stairs are (red, green, red), (green, red, green), (red, green, green), (green. green, red), and (green, green, green).
Sample Input 2 :
2
10
15
Sample Output 2 :
144 
1597
Hint

Can you think of a way to explore all the ways recursively.

Approaches (3)
Recursion

In the naive approach, we can recursively explore all the valid ways and then count each of the ways. We can use backtracking to find all the ways. For any ‘X’th stair if that stair is of color red then for the ‘X’+1th stair we have only one option and that is to color green. If that stair is of the color green then for the ‘X’+1th stair we have two options, either color it green or red.

So if colorStair(N, color) is our recursive function then :

If current stair is red:

colorStair(N, red) = colorStair(N-1, green)

Else 

colorStair(N, green) = colorStair(N-1, red) + colorStair(N-1, green)

The base case of this recursive function is if ‘N’ = 0 then we have found a valid combination of colors, so return 1.

 

The steps are as follows:-

// Recursive function to explore all ways

function countWaysUtil( int n, int prevColor, int mod ):

  1. If 'N' is 0 then return 1.
  2. If 'prevColor' is 0 then select 1 for the current stair and then recursively call countWaysUtil for ('N'-1)th stair with 1 as 'prevColor'.
  3. Else recursively call countWaysUtil for ('N'-1)th stair, first with 0 as 'prevColor' then 1 as 'prevColor', add their values and return it.


 

function countWays( int n ):

  1. Call countWaysUtil function with 'N'th stair as red and 'N'th stair as green Add the total number of ways returned and store it into the 'totalWays' variable.
  2. Return the value of 'totalWays' variable.
Time Complexity

O( 2^N ), Where ‘N’ is the number of stairs. 

 

In the recursive function, if the color is green then we have two choices and we are exploring both of them. So the recursive calls are growing as 1, 2, 4, 8…. 2^N. 

Hence the time complexity is O( 2^N ).

Space Complexity

O( N )

 

The recursion stack will store at most ‘N’ function calls since the function backtracks after that.

Hence space complexity is O( N ).

Code Solution
(100% EXP penalty)
Paint the Stairs
Full screen
Console