Given n stairs and we have 2 colour yellow and green the task is that we have to paint given stairs by given colour with condition is that we cannot paints two yellow steps directly after each other.
Examples :
Input : n = 1 Output : 2 A single stair can be colored either as green or yellow. Input : n = 3 Output : 5
Case 1: When we have 1 stair, we can paint either yellow or green.
Case 2: When we have 2 stairs, we can paint first stair by either yellow or green but for next stair we can only paint by green because we cannot paint two yellow steps directly after each other. So total cases are three YG, GG, GY.
Case 3: When we have 3 stairs then we can paint it by in 5 ways.
If we take a closer look, we can notice that it follows Fibonacci Series.
C++
// C++ Program to find the number of ways to paint stairs#include <bits/stdc++.h>using namespace std;// Function to find the number of waysint ways(int n){ int W[n + 1]; // take base case for 1 and 2 W[1] = 2; W[2] = 3; for (int i = 3; i <= n; i++) W[i] = W[i - 1] + W[i - 2]; return W[n];}// Driven codeint main(){ int n = 3; printf("%d", ways(n)); return 0;} |
Java
// java Program to find the number of// ways to paint stairsimport java.io.*;public class GFG { // Function to find the number of ways static int ways(int n) { int []W = new int[n+1]; // take base case for 1 and 2 W[1] = 2; W[2] = 3; for (int i = 3; i <= n; i++) W[i] = W[i - 1] + W[i - 2]; return W[n]; } // Driven code static public void main (String[] args) { int n = 3; System.out.println(ways(n)); }}// This code is contributed by vt_m. |
Python3
# Python3 code to find the number# of ways to paint stairs# Function to find the number of waysdef ways( n ): W = list() # take base case for 1 and 2 W.append(0) W.append(2) W.append(3) i = 3 while i <= n: W.append(W[i - 1] + W[i - 2]) i = i + 1 return W[n]# Driver coden = 3print(ways(n))# This code is contributed by "Sharad_Bhardwaj". |
C#
// C# Program to find the number of// ways to paint stairsusing System;public class GFG { // Function to find the number of ways static int ways(int n) { int []W =new int[n+1]; // take base case for 1 and 2 W[1] = 2; W[2] = 3; for (int i = 3; i <= n; i++) W[i] = W[i - 1] + W[i - 2]; return W[n]; } // Driven code static public void Main () { int n = 3; Console.WriteLine(ways(n)); }}// This code is contributed by vt_m. |
PHP
<?php// PHP Program to find the// number of ways to paint stairs// Function to find the// number of waysfunction ways($n){ // take base case // for 1 and 2 $W[1] = 2; $W[2] = 3; for ($i = 3; $i <= $n; $i++) $W[$i] = $W[$i - 1] + $W[$i - 2]; return $W[$n];}// Driven code$n = 3;echo ways($n);// This code is contributed by ajit?> |
Javascript
<script>// Javascript Program to find the number of// ways to paint stairs // Function to find the number of ways function ways(n) { let W = []; // take base case for 1 and 2 W[1] = 2; W[2] = 3; for (let i = 3; i <= n; i++) W[i] = W[i - 1] + W[i - 2]; return W[n]; }// Driver code let n = 3; document.write(ways(n)); </script> |
Output :
5
Time Complexity : O(n)
Extra Space : O(n)
We can solve this problem in O(Log n) time also using matrix exponentiation solution for n-th Fibonacci Number.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
