Climbing stairs to reach the top

Try it on GfG Practice

There are n stairs, and a person standing at the bottom wants to climb stairs to reach the top. The person can climb either 1 stair or 2 stairs at a time, the task is to count the number of ways that a person can reach at the top.

Note: This problem is similar to Count ways to reach Nth stair (Order does not matter) with the only difference that in this problem, we count all distinct ways where different orderings of the steps are considered unique.

Examples:

Input: n = 1
Output: 1
Explanation: There is only one way to climb 1 stair.

Input: n = 2
Output: 2
Explanation: There are two ways to reach 2th stair: {1, 1} and {2}.

Input: n = 4
Output: 5
Explanation: There are five ways to reach 4th stair: {1, 1, 1, 1}, {1, 1, 2}, {2, 1, 1}, {1, 2, 1} and {2, 2}.

Using Recursion – O(2^n) Time and O(n) Space

We can easily identify the recursive nature of this problem. A person can reach n^th stair either from (n-1)^th stair or (n-2)^th stair. Thus, for each stair n, we calculate the number of ways to reach the (n-1)^th and (n-2)^th stairs, and add them to get the total number of ways to reach the n^th stair. This gives us the following recurrence relation:

countWays(n) = countWays(n-1) + countWays(n-2)

Note: The above recurrence relation is same as Fibonacci numbers.

// C++ program to count number of ways to reach
// nth stair using recursion

#include <iostream>
using namespace std;

int countWays(int n) {

    // Base cases: If there are 0 or 1 stairs,
    // there is only one way to reach the top.
    if (n == 0 || n == 1)
        return 1;

    return countWays(n - 1) + countWays(n - 2);
}

int main() {
    int n = 4;
    cout << countWays(n);
    return 0;
}

// C program to count number of ways to reach 
// nth stair using recursion

#include <stdio.h>

int countWays(int n) {

    // Base cases: If there are 0 or 1 stairs,
    // there is only one way to reach the top.
    if (n == 0 || n == 1)
        return 1;

    return countWays(n - 1) + countWays(n - 2);
}

int main() {
    int n = 4;
    printf("%d\n", countWays(n));
    return 0;
}

// Java program to count number of ways to reach
// nth stair using recursion

class GfG {
    static int countWays(int n) {

        // Base cases: If there are 0 or 1 stairs,
        // there is only one way to reach the top.
        if (n == 0 || n == 1)
            return 1;

        return countWays(n - 1) + countWays(n - 2);
    }

    public static void main(String[] args) {
        int n = 4;
        System.out.println(countWays(n));
    }
}

# Python program to count number of ways to reach
# nth stair using recursion

def countWays(n):

    # Base cases: If there are 0 or 1 stairs,
    # there is only one way to reach the top.
    if n == 0 or n == 1:
        return 1

    return countWays(n - 1) + countWays(n - 2)

n = 4
print(countWays(n))

// C# program to count number of ways to reach
 // nth stair using recursion

using System;

class GfG {
    static int countWays(int n) {

        // Base cases: If there are 0 or 1 stairs,
        // there is only one way to reach the top.
        if (n == 0 || n == 1)
            return 1;

        return countWays(n - 1) + countWays(n - 2);
    }

    static void Main() {
        int n = 4;
        Console.WriteLine(countWays(n));
    }
}

// JavaScript program to count number of ways to reach
// nth stair using recursion

function countWays(n) {

    // Base cases: If there are 0 or 1 stairs,
    // there is only one way to reach the top.
    if (n === 0 || n === 1)
        return 1;

    return countWays(n - 1) + countWays(n - 2);
}

const n = 4;
console.log(countWays(n));

5

Time Complexity: O(2ⁿ), as we are making two recursive calls for each stair.
Auxiliary Space: O(n), as we are using recursive stack space.

Using Top-Down DP (Memoization) – O(n) Time and O(n) Space

If we notice carefully, we can observe that the above recursive solution holds the following two properties of Dynamic Programming:

1. Optimal Substructure:

Number of ways to reach the nth stair, i.e., countWays(n), depends on the optimal solutions of the subproblems countWays(n-1) and countWays(n-2). By combining these optimal substructures, we can efficiently calculate the total number of ways to reach the nth stair.

2. Overlapping Subproblems:

While applying a recursive approach in this problem, we notice that certain subproblems are computed multiple times. For example, when calculating countWays(4), we recursively calculate countWays(3) and countWays(2), which in turn will recursively compute countWays(2) again. This redundancy leads to overlapping subproblems.

Overlapping Subproblems in Climbing Stairs

• There is only one parameter that changes in the recursive solution and it can go from 0 to n. So we create a 1D array of size n+1 for memoization.
• We initialize this array as -1 to indicate nothing is computed initially.
• Now we modify our recursive solution to first check if the value is -1, then only make recursive calls. This way, we avoid re-computations of the same subproblems.

// C++ program to count number of ways to reach 
// nth stair using memoization

#include <iostream>
#include <vector>
using namespace std;

int countWaysRec(int n, vector<int>& memo) {
  
  	// Base cases
    if (n == 0 || n == 1)
        return 1;

  	// if the result for this subproblem is 
  	// already computed then return it
    if (memo[n] != -1) 
        return memo[n];
    
    return memo[n] = countWaysRec(n - 1, memo) +
      				 	countWaysRec(n - 2, memo);
}

int countWays(int n) {
  
  	// Memoization array to store the results
  	vector<int> memo(n + 1, -1);
  	return countWaysRec(n, memo);
}

int main() {
    int n = 4;
    cout << countWays(n);
    return 0;
}

// C program to count number of ways to reach nth stair
// using memoization

#include <stdio.h>

int countWaysRec(int n, int memo[]) {
  
    // Base cases
    if (n == 0 || n == 1)
        return 1;

    // if the result for this subproblem is 
    // already computed then return it
    if (memo[n] != -1) 
        return memo[n];
 
    return memo[n] = countWaysRec(n - 1, memo) + 
        				countWaysRec(n - 2, memo); 
}

int countWays(int n) {
  
    // Memoization array to store the results
    int* memo = (int*)malloc((n + 1) * sizeof(int));
    for (int i = 0; i <= n; i++)
        memo[i] = -1;

    return countWaysRec(n, memo);
}

int main() {
    int n = 4;
    printf("%d\n", countWays(n));
    return 0;
}

// Java program to count number of ways to reach nth stair
// using memoization

import java.util.Arrays;

class GfG {
    static int countWaysRec(int n, int[] memo) {
      
        // Base cases
        if (n == 0 || n == 1)
            return 1;

        // if the result for this subproblem is 
        // already computed then return it
        if (memo[n] != -1) 
            return memo[n];
 
        return memo[n] = countWaysRec(n - 1, memo) + 
           					countWaysRec(n - 2, memo); 
    }

    static int countWays(int n) {
      
        // Memoization array to store the results
        int[] memo = new int[n + 1];
        Arrays.fill(memo, -1);
        return countWaysRec(n, memo);
    }

    public static void main(String[] args) {
        int n = 4;
        System.out.println(countWays(n));
    }
}

# Python program to count number of ways to reach nth stair 
# using memoization

def countWaysRec(n, memo):
  
    # Base cases
    if n == 0 or n == 1:
        return 1

    # if the result for this subproblem is 
    # already computed then return it
    if memo[n] != -1:
        return memo[n]

    memo[n] = countWaysRec(n - 1, memo) + countWaysRec(n - 2, memo)
    return memo[n]

def countWays(n):
  
    # Memoization array to store the results
    memo = [-1] * (n + 1)
    return countWaysRec(n, memo)

if __name__ == "__main__":
    n = 4
    print(countWays(n))

// C# program to count number of ways to reach nth stair
// using memoization

using System;

class GfG {
    static int CountWaysRec(int n, int[] memo) {
      
        // Base cases
        if (n == 0 || n == 1)
            return 1;

        // if the result for this subproblem is 
        // already computed then return it
        if (memo[n] != -1) 
            return memo[n];

        return memo[n] = CountWaysRec(n - 1, memo) + CountWaysRec(n - 2, memo); ;
    }

    static int CountWays(int n) {
      
        // Memoization array to store the results
        int[] memo = new int[n + 1];
        Array.Fill(memo, -1);
        return CountWaysRec(n, memo);
    }

    static void Main() {
        int n = 4;
        Console.WriteLine(CountWays(n));
    }
}

// JavaScript program to count number of ways to reach nth stair
// using memoization

function countWaysRec(n, memo) {

    // Base cases
    if (n === 0 || n === 1)
        return 1;

    // if the result for this subproblem is 
    // already computed then return it
    if (memo[n] !== -1) 
        return memo[n];

    memo[n] = countWaysRec(n - 1, memo) + countWaysRec(n - 2, memo); 
    return memo[n];
}

function countWays(n) {

    // Memoization array to store the results
    let memo = Array(n + 1).fill(-1);
    return countWaysRec(n, memo);
}

const n = 4;
console.log(countWays(n));

5

Time Complexity: O(n), as we compute each subproblem only once using memoization.
Auxiliary Space: O(n), due to the memoization array and the recursive stack space(both take linear space only).

Using Bottom-Up DP (Tabulation) – O(n) Time and O(n) Space

The approach is similar to the previous one; just instead of breaking down the problem recursively, we iteratively build up the solution by calculating in bottom-up manner. Maintain a dp[] table such that dp[i] stores the number of ways to reach ith stair.

• Base Case: For i = 0 and i = 1, dp[i] = 1
• Recursive Case: For i > 1, dp[i] = dp[i – 1] + dp[i – 2]

illustration:

// C++ program to count number of ways 
// to reach nth stair using Tabulation

#include <iostream>
#include <vector>
using namespace std;

int countWays(int n) {
    vector<int> dp(n + 1, 0);
  
    // Base cases
    dp[0] = 1;
    dp[1] = 1;
	
    for (int i = 2; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2]; 
  
    return dp[n];
}

int main() {
    int n = 4;
    cout << countWays(n);
    return 0;
}

// C program to count number of ways to
// reach nth stair using Tabulation

#include <stdio.h>

int countWays(int n) {
    int dp[n + 1];
  
    // Base cases
    dp[0] = 1;
    dp[1] = 1;

    for (int i = 2; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2]; 
  
    return dp[n];
}

int main() {
    int n = 4;
    printf("%d\n", countWays(n));
    return 0;
}

// Java program to count number of ways 
// to reach nth stair using Tabulation

class GfG {
    static int countWays(int n) {
        int[] dp = new int[n + 1];
  
        // Base cases
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= n; i++)
            dp[i] = dp[i - 1] + dp[i - 2]; 
  
        return dp[n];
    }

    public static void main(String[] args) {
        int n = 4;
        System.out.println(countWays(n));
    }
}

# Python program to count number of ways 
# to reach nth stair using Tabulation

def countWays(n):
    dp = [0] * (n + 1)
  
    # Base cases
    dp[0] = 1
    dp[1] = 1

    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]; 
  
    return dp[n]

n = 4
print(countWays(n))

// C# program to count number of ways to
// reach nth stair using tabulation

using System;

class GfG {
    static int countWays(int n) {
        int[] dp = new int[n + 1];
  
        // Base cases
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= n; i++)
            dp[i] = dp[i - 1] + dp[i - 2]; 
  
        return dp[n];
    }

    static void Main() {
        int n = 4;
        Console.WriteLine(countWays(n));
    }
}

// JavaScript program to count number of ways 
// to reach nth stair using tabulation

function countWays(n) {
    const dp = new Array(n + 1).fill(0);
  
    // Base cases
    dp[0] = 1;
    dp[1] = 1;

    for (let i = 2; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2]; 
  
    return dp[n];
}

const n = 4;
console.log(countWays(n));

5

Using Space Optimized DP – O(n) Time and O(1) Space

In the above approach, we observe that each subproblem only depends on the results of previous two subproblems, that is dp[i] depends on dp[i – 1] and dp[i – 2] only. So, we can optimize the space complexity by using just two variables to store these last two values.

// C++ program to count number of ways to
// reach nth stair using Space Optimized DP

#include <iostream>
#include <vector>
using namespace std;

int countWays(int n) {
  
    // variable prev1, prev2 to store the
  	// values of last and second last states 
    int prev1 = 1;
    int prev2 = 1;
  
  	for (int i = 2; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
  
  	// In last iteration final value
  	// of curr is stored in prev.
    return prev1;
}

int main() {
    int n = 4;
    cout << countWays(n);
    return 0;
}

// C program to count number of ways to
// reach nth stair using Space Optimized DP

#include <stdio.h>

int countWays(int n) {
  
    // variable prev1, prev2 to store the
    // values of last and second last states 
    int prev1 = 1;
    int prev2 = 1;
  
    for (int i = 2; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
  
    // In last iteration final value
    // of curr is stored in prev.
    return prev1;
}

int main() {
    int n = 4;
    printf("%d\n", countWays(n));
    return 0;
}

// Java program to count number of ways to
// reach nth stair using Space Optimized DP

class GfG {
    static int countWays(int n) {
  
        // variable prev1, prev2 - to store the 
        // values of last and second last states 
        int prev1 = 1;
        int prev2 = 1;
  
        for (int i = 2; i <= n; i++) {
            int curr = prev1 + prev2;
            prev2 = prev1;
            prev1 = curr;
        }
  
        // In last iteration final value
        // of curr is stored in prev.
        return prev1;
    }

    public static void main(String[] args) {
        int n = 4;
        System.out.println(countWays(n));
    }
}

# Python program to count number of ways to
# reach nth stair using Space Optimized DP

def countWays(n):
  
    # variable prev1, prev2 - to store the
    # values of last and second last states 
    prev1 = 1
    prev2 = 1
  
    for i in range(2, n + 1):
        curr = prev1 + prev2
        prev2 = prev1
        prev1 = curr
  
    # In last iteration final value
    # of curr is stored in prev.
    return prev1

n = 4
print(countWays(n))

// C# program to count number of ways to
// reach nth stair using Space Optimized DP

using System;

class GfG {
    static int countWays(int n) {
  
        // variable prev1, prev2 - to store the
        // values of last and second last states 
        int prev1 = 1;
        int prev2 = 1;
  
        for (int i = 2; i <= n; i++) {
            int curr = prev1 + prev2;
            prev2 = prev1;
            prev1 = curr;
        }
  
        // In last iteration final value
        // of curr is stored in prev.
        return prev1;
    }

    static void Main() {
        int n = 4;
        Console.WriteLine(countWays(n));
    }
}

// JavaScript program to count number of ways to
// reach nth stair using Space Optimized DP

function countWays(n) {
  
    // variable prev1, prev2 - to store the
    // values of last and second last states 
    let prev1 = 1;
    let prev2 = 1;
  
    for (let i = 2; i <= n; i++) {
        let curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
  
    // In last iteration final value
    // of curr is stored in prev.
    return prev1;
}

const n = 4;
console.log(countWays(n));

5

Using Matrix Exponentiation – O(logn) Time and O(1) Space

This problem is quite similar to the Fibonacci approach, with only one difference in the base case (the Fibonacci sequence value for 0 is 0, whereas in this problem it is 1). To know more about how to calculate fibonacci number using Matrix Exponentiation, please refer to this post.

// C++ Program to count no. of ways to reach
// nth stairs using matrix Exponentiation

#include <iostream>
#include <vector>
using namespace std;

// function to multiply two 2x2 Matrices
void multiply(vector<vector<int>>& a, vector<vector<int>>& b) {
  
    // Matrix to store the result
    vector<vector<int>> res(2, vector<int>(2));

    // Matrix Multiplication
    res[0][0] = a[0][0] * b[0][0] + a[0][1] * b[1][0];
    res[0][1] = a[0][0] * b[0][1] + a[0][1] * b[1][1];
    res[1][0] = a[1][0] * b[0][0] + a[1][1] * b[1][0];
    res[1][1] = a[1][0] * b[0][1] + a[1][1] * b[1][1];

    // Copy the result back to the first matrix
    a[0][0] = res[0][0];
    a[0][1] = res[0][1];
    a[1][0] = res[1][0];
    a[1][1] = res[1][1];
}

// Function to find (m[][] ^ expo)
vector<vector<int>> power(vector<vector<int>>& m, int expo) {
  
    // Initialize result with identity matrix
    vector<vector<int>> res = { { 1, 0 }, { 0, 1 } };

    while (expo) {
        if (expo & 1)
            multiply(res, m);
        multiply(m, m);
        expo >>= 1;
    }

    return res;
}

int countWays(int n) {
  
    // base case
    if (n == 0 || n == 1)
        return 1;

    vector<vector<int>> m = { { 1, 1 }, { 1, 0 } };
  
    // Matrix initialMatrix = {{f(1), 0}, {f(0), 0}}, where f(0)
    // and f(1) are first two terms of sequence
    vector<vector<int>> initialMatrix = { { 1, 0 }, { 1, 0 } };

    // Multiply matrix m (n - 1) times
    vector<vector<int>> res = power(m, n - 1);

    multiply(res, initialMatrix);

    return res[0][0];
}

int main() {
    int n = 4;
    cout << countWays(n);
    return 0;
}

// C Program to count no. of ways to reach
// nth stairs using matrix Exponentiation

#include <stdio.h>

void multiply(long long a[2][2], long long b[2][2]) {
    
    // Matrix to store the result
    long long res[2][2];

    // Matrix Multiplication
    res[0][0] = a[0][0] * b[0][0] + a[0][1] * b[1][0];
    res[0][1] = a[0][0] * b[0][1] + a[0][1] * b[1][1];
    res[1][0] = a[1][0] * b[0][0] + a[1][1] * b[1][0];
    res[1][1] = a[1][0] * b[0][1] + a[1][1] * b[1][1];

    // Copy the result back to the first matrix
    a[0][0] = res[0][0];
    a[0][1] = res[0][1];
    a[1][0] = res[1][0];
    a[1][1] = res[1][1];
}

void power(long long m[2][2], int expo, long long res[2][2]) {
    
    // Initialize result with identity matrix
    res[0][0] = 1; res[0][1] = 0;
    res[1][0] = 0; res[1][1] = 1;

    while (expo) {
        if (expo & 1)
            multiply(res, m);
        multiply(m, m);
        expo >>= 1;
    }
}

int countWays(int n) {
    
    // base case
    if (n == 0 || n == 1)
        return 1;

    long long m[2][2] = { { 1, 1 }, { 1, 0 } };
    
    // Matrix initialMatrix = {{f(1), 0}, {f(0), 0}}, where f(0)
    // and f(1) are first two terms of sequence
    long long initialMatrix[2][2] = { { 1, 0 }, { 1, 0 } };

    // Multiply matrix m (n - 1) times
    long long res[2][2];
    power(m, n - 1, res);

    multiply(res, initialMatrix);

    return res[0][0];
}

int main() {
    int n = 4;
    printf("%d\n",countWays(n));
    return 0;
}

// Java Program to count no. of ways to reach
// nth stairs using matrix Exponentiation

class GfG {
    static void multiply(int[][] a, int[][] b) {
        
        // Matrix to store the result
        int[][] res = new int[2][2];

        // Matrix Multiplication
        res[0][0] = a[0][0] * b[0][0] + a[0][1] * b[1][0];
        res[0][1] = a[0][0] * b[0][1] + a[0][1] * b[1][1];
        res[1][0] = a[1][0] * b[0][0] + a[1][1] * b[1][0];
        res[1][1] = a[1][0] * b[0][1] + a[1][1] * b[1][1];

        // Copy the result back to the first matrix
        a[0][0] = res[0][0];
        a[0][1] = res[0][1];
        a[1][0] = res[1][0];
        a[1][1] = res[1][1];
    }

    static int[][] power(int[][] m, int expo) {
        
        // Initialize result with identity matrix
        int[][] res = { { 1, 0 }, { 0, 1 } };

        while (expo > 0) {
            if ((expo & 1) == 1)
                multiply(res, m);
            multiply(m, m);
            expo >>= 1;
        }

        return res;
    }

    static int countWays(int n) {
        
        // base case
        if (n == 0 || n == 1)
            return 1;

        int[][] m = { { 1, 1 }, { 1, 0 } };
        
        // Matrix initialMatrix = {{f(1), 0}, {f(0), 0}}, where f(0)
        // and f(1) are first two terms of sequence
        int[][] initialMatrix = { { 1, 0 }, { 1, 0 } };

        // Multiply matrix m (n - 1) times
        int[][] res = power(m, n - 1);

        multiply(res, initialMatrix);

        return res[0][0];
    }

    public static void main(String[] args) {
        int n = 4;
        System.out.println(countWays(n));
    }
}

# Python Program to count no. of ways to reach
# nth stairs using matrix Exponentiation

def multiply(a, b):
    
    # Matrix to store the result
    res = [[0, 0], [0, 0]]

    # Matrix Multiplication
    res[0][0] = a[0][0] * b[0][0] + a[0][1] * b[1][0]
    res[0][1] = a[0][0] * b[0][1] + a[0][1] * b[1][1]
    res[1][0] = a[1][0] * b[0][0] + a[1][1] * b[1][0]
    res[1][1] = a[1][0] * b[0][1] + a[1][1] * b[1][1]

    # Copy the result back to the first matrix
    a[0][0] = res[0][0]
    a[0][1] = res[0][1]
    a[1][0] = res[1][0]
    a[1][1] = res[1][1]

def power(m, expo):
    
    # Initialize result with identity matrix
    res = [[1, 0], [0, 1]]

    while expo > 0:
        if expo & 1:
            multiply(res, m)
        multiply(m, m)
        expo >>= 1

    return res

def countWays(n):
    
    # base case
    if n == 0 or n == 1:
        return 1

    m = [[1, 1], [1, 0]]
    
    # Matrix initialMatrix = {{f(1), 0}, {f(0), 0}}, where f(0)
    # and f(1) are first two terms of sequence
    initialMatrix = [[1, 0], [1, 0]]

    # Multiply matrix m (n - 1) times
    res = power(m, n - 1)

    multiply(res, initialMatrix)

    # Return the final result as an integer
    return res[0][0]

n = 4
print(countWays(n))

// C# Program to count no. of ways to reach
// nth stairs using matrix Exponentiation

using System;

class GfG {
    static void multiply(int[,] a, int[,] b) {
        
        // Matrix to store the result
        int[,] res = new int[2, 2];

        // Matrix Multiplication
        res[0, 0] = a[0, 0] * b[0, 0] + a[0, 1] * b[1, 0];
        res[0, 1] = a[0, 0] * b[0, 1] + a[0, 1] * b[1, 1];
        res[1, 0] = a[1, 0] * b[0, 0] + a[1, 1] * b[1, 0];
        res[1, 1] = a[1, 0] * b[0, 1] + a[1, 1] * b[1, 1];

        // Copy the result back to the first matrix
        a[0, 0] = res[0, 0];
        a[0, 1] = res[0, 1];
        a[1, 0] = res[1, 0];
        a[1, 1] = res[1, 1];
    }

    static int[,] power(int[,] m, int expo) {
        
        // Initialize result with identity matrix
        int[,] res = { { 1, 0 }, { 0, 1 } };

        while (expo > 0) {
            if ((expo & 1) == 1)
                multiply(res, m);
            multiply(m, m);
            expo >>= 1;
        }

        return res;
    }

    static int countWays(int n) {
        
        // base case
        if (n == 0 || n == 1)
            return 1;

        int[,] m = { { 1, 1 }, { 1, 0 } };
        
        // Matrix initialMatrix = {{f(1), 0}, {f(0), 0}}, where f(0)
        // and f(1) are first two terms of sequence
        int[,] initialMatrix = { { 1, 0 }, { 1, 0 } };

        // Multiply matrix m (n - 1) times
        int[,] res = power(m, n - 1);

        multiply(res, initialMatrix);

        return res[0, 0];
    }

    static void Main() {
        int n = 4;
        Console.WriteLine(countWays(n));
    }
}

// JavaScript Program to count no. of ways to reach
// nth stairs using matrix Exponentiation

function multiply(a, b) {
    
    // Matrix to store the result
    const res = [
        [0, 0],
        [0, 0]
    ];

    // Matrix Multiplication
    res[0][0] = a[0][0] * b[0][0] + a[0][1] * b[1][0];
    res[0][1] = a[0][0] * b[0][1] + a[0][1] * b[1][1];
    res[1][0] = a[1][0] * b[0][0] + a[1][1] * b[1][0];
    res[1][1] = a[1][0] * b[0][1] + a[1][1] * b[1][1];

    // Copy the result back to the first matrix
    a[0][0] = res[0][0];
    a[0][1] = res[0][1];
    a[1][0] = res[1][0];
    a[1][1] = res[1][1];
}

function power(m, expo) {
    
    // Initialize result with identity matrix
    const res = [
        [1, 0],
        [0, 1]
    ];

    while (expo > 0) {
        if (expo & 1) 
            multiply(res, m);
        multiply(m, m);
        expo >>= 1;
    }

    return res;
}

function countWays(n) {
    
    // base case
    if (n === 0 || n === 1)
        return 1;

    const m = [
        [1, 1],
        [1, 0]
    ];
    
    // Matrix initialMatrix = {{f(1), 0}, {f(0), 0}}, where f(0)
    // and f(1) are first two terms of sequence
    const initialMatrix = [
        [1, 0],
        [1, 0]
    ];

    // Multiply matrix m (n - 1) times
    const res = power(m, n - 1);

    multiply(res, initialMatrix);

    return res[0][0];
}

const n = 4;
console.log(countWays(n));

5

kartik

Follow

Improve

Article Tags :

• DSA
• Dynamic Programming
• Mathematical
• Accolite
• Amazon
• Intel
• Linkedin
• Morgan Stanley
• Samsung
• sliding-window
• Snapdeal

+7 More

Practice Tags :

• Accolite
• Amazon
• Intel
• Linkedin
• Morgan Stanley
• Samsung
• Snapdeal
• Dynamic Programming
• Mathematical
• sliding-window

+6 More