Given N number of stairs. Also given the number of steps that one can cover at most in one leap (K). The task is to find the number of possible ways one (only consider combinations) can climb to the top of the building in K leaps or less from the ground floor.
Examples:
Input: N = 5, K = 3
Output: 5
To reach stair no-5 we can choose following combination of leaps:
1 1 1 1 1
1 1 1 2
1 2 2
1 1 3
2 3
Therefore the answer is 5.
Input: N = 29, K = 5
Output: 603
Let combo[i] be the number of ways to reach the i-th floor. Hence the number of ways to reach combo[i] from combo[j] by taking a leap of i-j will be combo[i] += combo[j]. So iterate for all possible leaps, and for each possible leaps keep adding the possible combinations to the combo array. The final answer will be stored in combo[N].
Below is the implementation of the above approach.
C++
// C++ program to reach N-th stair // by taking a maximum of K leap #include <bits/stdc++.h> using namespace std; int solve(int N, int K) { // elements of combo[] stores the no of // possible ways to reach it by all // combinations of k leaps or less int combo[N + 1] = { 0 }; // assuming leap 0 exist and assigning // its value to 1 for calculation combo[0] = 1; // loop to iterate over all // possible leaps upto k; for (int i = 1; i <= K; i++) { // in this loop we count all possible // leaps to reach the jth stair with // the help of ith leap or less for (int j = 0; j <= N; j++) { // if the leap is not more than the i-j if (j >= i) { // calculate the value and // store in combo[j] // to reuse it for next leap // calculation for the jth stair combo[j] += combo[j - i]; } } } // returns the no of possible number // of leaps to reach the top of // building of n stairs return combo[N]; } // Driver Code int main() { // N i the no of total stairs // K is the value of the greatest leap int N = 29; int K = 5; cout << solve(N, K); return 0; } |
Java
// Java program to reach N-th // stair by taking a maximum // of K leapclass GFG{static int solve(int N, int K){ // elements of combo[] stores // the no. of possible ways // to reach it by all combinations // of k leaps or less int[] combo; combo = new int[50]; // assuming leap 0 exist // and assigning its value // to 1 for calculation combo[0] = 1; // loop to iterate over all // possible leaps upto k; for (int i = 1; i <= K; i++) { // in this loop we count all // possible leaps to reach // the jth stair with the // help of ith leap or less for (int j = 0; j <= N; j++) { // if the leap is not // more than the i-j if (j >= i) { // calculate the value and // store in combo[j] to // reuse it for next leap // calculation for the // jth stair combo[j] += combo[j - i]; } } } // returns the no of possible // number of leaps to reach // the top of building of // n stairs return combo[N];}// Driver Codepublic static void main(String args[]){ // N i the no of total stairs // K is the value of the // greatest leap int N = 29; int K = 5; System.out.println(solve(N, K));}}// This code is contributed // by ankita_saini |
Python 3
# Python3 program to reach N-th stair# by taking a maximum of K leap def solve(N, K) : # elements of combo[] stores the no of # possible ways to reach it by all # combinations of k leaps or less combo = [0] * (N + 1) # assuming leap 0 exist and assigning # its value to 1 for calculation combo[0] = 1 # loop to iterate over all # possible leaps upto k; for i in range(1, K + 1) : # in this loop we count all possible # leaps to reach the jth stair with # the help of ith leap or less for j in range(0, N + 1) : # if the leap is not more than the i-j if j >= i : # calculate the value and # store in combo[j] # to reuse it for next leap # calculation for the jth stair combo[j] += combo[j - i] # returns the no of possible number # of leaps to reach the top of # building of n stairs return combo[N] # Driver Codeif __name__ == "__main__" : # N i the no of total stairs # K is the value of the greatest leap N, K = 29, 5 print(solve(N, K))# This code is contributed by ANKITRAI1 |
C#
// C# program to reach N-th // stair by taking a maximum // of K leapusing System;class GFG{static int solve(int N, int K){ // elements of combo[] stores // the no. of possible ways // to reach it by all combinations // of k leaps or less int[] combo; combo = new int[50]; // assuming leap 0 exist // and assigning its value // to 1 for calculation combo[0] = 1; // loop to iterate over all // possible leaps upto k; for (int i = 1; i <= K; i++) { // in this loop we count all // possible leaps to reach // the jth stair with the // help of ith leap or less for (int j = 0; j <= N; j++) { // if the leap is not // more than the i-j if (j >= i) { // calculate the value and // store in combo[j] to // reuse it for next leap // calculation for the // jth stair combo[j] += combo[j - i]; } } } // returns the no of possible // number of leaps to reach // the top of building of // n stairs return combo[N];}// Driver Codepublic static void Main(){ // N i the no of total stairs // K is the value of the // greatest leap int N = 29; int K = 5; Console.WriteLine(solve(N, K));}}// This code is contributed // by Akanksha Rai(Abby_akku) |
PHP
<?phperror_reporting(0);// PHP program to reach N-th // stair by taking a maximum // of K leap function solve($N, $K) { // elements of combo[] stores // the no of possible ways to // reach it by all combinations // of k leaps or less $combo[$N + 1] = array(); // assuming leap 0 exist and // assigning its value to 1 // for calculation $combo[0] = 1; // loop to iterate over all // possible leaps upto k; for ($i = 1; $i <= $K; $i++) { // in this loop we count // all possible leaps to // reach the jth stair with // the help of ith leap or less for ($j = 0; $j <= $N; $j++) { // if the leap is not // more than the i-j if ($j >= $i) { // calculate the value and // store in combo[j] // to reuse it for next leap // calculation for the jth stair $combo[$j] += $combo[$j - $i]; } } } // returns the no of possible // number of leaps to reach // the top of building of n stairs return $combo[$N]; } // Driver Code // N i the no of total stairs // K is the value of the greatest leap $N = 29; $K = 5; echo solve($N, $K); // This code is contributed // by Akanksha Rai(Abby_akku) ?> |
Javascript
<script> // Javascript program to reach N-th // stair by taking a maximum // of K leap function solve(N, K) { // elements of combo[] stores // the no. of possible ways // to reach it by all combinations // of k leaps or less let combo = new Array(50); combo.fill(0); // assuming leap 0 exist // and assigning its value // to 1 for calculation combo[0] = 1; // loop to iterate over all // possible leaps upto k; for (let i = 1; i <= K; i++) { // in this loop we count all // possible leaps to reach // the jth stair with the // help of ith leap or less for (let j = 0; j <= N; j++) { // if the leap is not // more than the i-j if (j >= i) { // calculate the value and // store in combo[j] to // reuse it for next leap // calculation for the // jth stair combo[j] += combo[j - i]; } } } // returns the no of possible // number of leaps to reach // the top of building of // n stairs return combo[N]; } // N i the no of total stairs // K is the value of the // greatest leap let N = 29; let K = 5; document.write(solve(N, K)); // This code is contributed by decode2207.</script> |
Output:
603
Time Complexity: O(N*K)
Auxiliary Space: O(N)
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!
