Given N stairs and a person standing at the bottom wants to reach the top. He could climb any number of steps from the given array arr[] of positive integers. The task is to find the count of all possible ways to reach the top.
Examples:
Input: arr[] = {1, 3, 5}, N = 5
Output: 5
(0 -> 1 -> 2 -> 3 -> 4 -> 5), (0 -> 1 -> 2 -> 5),
(0 -> 1 -> 4 -> 5), (0 -> 3 -> 4 -> 5)
and (0 -> 5) are the only possible ways.Input: arr[] = {1, 2, 3}, N = 10
Output: 274
Naive approach: Using recursion, find all the possible ways and count them.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Recursive function to return the// total ways to reach the n'th stairint countWays(int n, int arr[], int len){ // Base case if (n == 0) return 1; // To store the number of ways int no_ways = 0; // Iterate each element of the given array for (int i = 0; i < len; i++) { // Here consider only the values of // "n - arr[i]" >= 0 because negative values // of n in the stair function are // not defined if (n - arr[i] >= 0) { no_ways += countWays(n - arr[i], arr, len); } } return no_ways;}// Driver codeint main(){ int arr[] = { 1, 3, 5 }; int len = sizeof(arr) / sizeof(int); int n = 5; cout << countWays(n, arr, len); return 0;} |
Java
// Java implementation of the approachclass GFG { // Recursive function to return the // total ways to reach the n'th stair static int countWays(int n, int arr[], int len) { // Base case if (n == 0) return 1; // To store the number of ways int no_ways = 0; // Iterate each element of the given array for (int i = 0; i < len; i++) { // Here consider only the values of // "n - arr[i]" >= 0 because negative values // of n in the stair function are // not defined if (n - arr[i] >= 0) { no_ways += countWays(n - arr[i], arr, len); } } return no_ways; } // Driver code public static void main(String args[]) { int arr[] = { 1, 3, 5 }; int len = arr.length; ; int n = 5; System.out.println(countWays(n, arr, len)); }} |
Python
# Python3 implementation of the approach# Recursive function to return the# total ways to reach the n'th stairdef countWays(n, arr): # Base case if (n == 0): return 1 # To store the number of ways no_ways = 0 # Iterate each element of the given array for i in arr: # Here consider only the values of # "n - arr[i]" >= 0 because negative values # of n in the stair function are # not defined if (n - i >= 0): no_ways = no_ways + countWays(n - i, arr) return no_ways# Driver codearr = [1, 3, 5]n = 5print(countWays(n, arr)) |
C#
// C# implementation of the approachusing System;class GFG{// Recursive function to return the// total ways to reach the n'th stairstatic int countWays(int n, int []arr, int len){ // Base case if (n == 0) return 1; // To store the number of ways int no_ways = 0; // Iterate each element // of the given array for (int i = 0; i < len; i++) { // Here consider only the values of // "n - arr[i]" >= 0 because negative values // of n in the stair function are // not defined if (n - arr[i] >= 0) { no_ways += countWays(n - arr[i], arr, len); } } return no_ways;}// Driver codepublic static void Main(){ int []arr = { 1, 3, 5 }; int len = arr.Length; int n = 5; Console.Write(countWays(n, arr, len));}}// This code is contributed by Mohit Kumar |
Javascript
<script>// JavaScript implementation of the approach// Recursive function to return the// total ways to reach the n'th stairfunction countWays(n, arr, len) { // Base case if (n == 0) return 1; // To store the number of ways let no_ways = 0; // Iterate each element of the given array for (let i = 0; i < len; i++) { // Here consider only the values of // "n - arr[i]" >= 0 because negative values // of n in the stair function are // not defined if (n - arr[i] >= 0) { no_ways += countWays(n - arr[i], arr, len); } } return no_ways;}// Driver codelet arr = [1, 3, 5];let len = arr.length;let n = 5;document.write(countWays(n, arr, len));</script> |
Output:
5
Efficient approach: In this method instead of using a recursive approach, go for a dynamic programming based approach.
- Create an array count[] of size equal to the total number of steps + 1 with all elements initialized to 0 and initialize the first element i.e. count[0] to 1.
- Initialize a variable no_ways = 0 inside the for loop and every time starting from 0 for the new ways of climbing the stairs.
- Add count[i – x[j]] to no_ways only if i – x[j] ≥ 0.
- Finally, return count[N] which is essentially the number of ways to climb the Nth stair.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the total number// of ways to reach the n'th stairint countWays(int n, int arr[], int len){ // To store the number of ways // to reach the ith stair int count[n + 1] = { 0 }; count[0] = 1; // Base case if (n == 0) return 1; // For every stair for (int i = 1; i <= n; i++) { // To store the count of ways // till the current stair int no_ways = 0; // Every step from the array for (int j = 0; j < len; j++) { // Here consider only // the values of "i - arr[j]" >= 0 // because negative values // indicates reverse climbing // of steps if (i - arr[j] >= 0) { no_ways += count[i - arr[j]]; } count[i] = no_ways; } } return count[n];}// Driver codeint main(){ int arr[] = { 1, 3, 5 }; int len = sizeof(arr) / sizeof(int); int n = 5; cout << countWays(n, arr, len); return 0;} |
Java
// java implementation of the approachclass GFG { // Function to return the total number // of ways to reach the n'th stair static int countWays(int n, int arr[], int len) { // To store the number of ways // to reach the ith stair int count[] = new int[n + 1]; count[0] = 1; // Base case if (n == 0) return 1; // For every stair for (int i = 1; i <= n; i++) { // To store the count of ways // till the current stair int no_ways = 0; // Every step from the array for (int j = 0; j < len; j++) { // Here consider only // the values of "i - arr[j]" >= 0 // because negative values // indicates reverse climbing // of steps if (i - arr[j] >= 0) { no_ways += count[i - arr[j]]; } count[i] = no_ways; } } return count[n]; } // Driver code public static void main(String args[]) { int arr[] = { 1, 3, 5 }; int len = arr.length; int n = 5; System.out.print(countWays(n, arr, len)); }} |
Python3
# Python3 implementation of the approach# Function to return the total number # of ways to reach the n'th stairdef countWays(n, arr): # To store the number of ways # to reach the ith stair count = [0] * (n + 1) count[0] = 1 # Base case if (n == 0): return 1 # For every stair for i in range(1, n + 1): # To store the count of ways # till the current stair no_ways = 0 # Every step from the array for j in arr: # Here consider only # the values of "i - arr[j]" >= 0 # because negative values # indicates reverse climbing # of steps if (i - j >= 0): no_ways += count[i - j] count[i] = no_ways return count[n]# Driver codearr = [1, 3, 5]n = 5print(countWays(n, arr)) |
C#
// C# implementation of the approachusing System;class GFG { // Function to return the total number // of ways to reach the n'th stair static int countWays(int n, int []arr, int len) { // To store the number of ways // to reach the ith stair int []count = new int[n + 1]; count[0] = 1; // Base case if (n == 0) return 1; // For every stair for (int i = 1; i <= n; i++) { // To store the count of ways // till the current stair int no_ways = 0; // Every step from the array for (int j = 0; j < len; j++) { // Here consider only // the values of "i - arr[j]" >= 0 // because negative values // indicates reverse climbing // of steps if (i - arr[j] >= 0) { no_ways += count[i - arr[j]]; } count[i] = no_ways; } } return count[n]; } // Driver code public static void Main() { int []arr = { 1, 3, 5 }; int len = arr.Length; int n = 5; Console.WriteLine(countWays(n, arr, len)); }}// This code is contributed by AnkitRai01 |
Javascript
<script> // javascript implementation of the approach // Function to return the total number // of ways to reach the n'th stair function countWays(n, arr, len) { // To store the number of ways // to reach the ith stair let count = new Array(n + 1); count[0] = 1; // Base case if (n == 0) return 1; // For every stair for (let i = 1; i <= n; i++) { // To store the count of ways // till the current stair let no_ways = 0; // Every step from the array for (let j = 0; j < len; j++) { // Here consider only // the values of "i - arr[j]" >= 0 // because negative values // indicates reverse climbing // of steps if (i - arr[j] >= 0) { no_ways += count[i - arr[j]]; } count[i] = no_ways; } } return count[n]; } let arr = [ 1, 3, 5 ]; let len = arr.length; let n = 5; document.write(countWays(n, arr, len));// This code is contributed by divyeshrabadiya07.</script> |
Output:
5
Time Complexity: O(N * len) where N is the number of stairs and len is the length of the array.
Auxiliary Space: O(len), where len is the length of the array.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] There you can find 33489 additional Information to that Topic: geeksforgeeks.org/count-ways-to-reach-the-nth-stair-using-any-step-from-the-given-array/ […]