Number of ways to reach Nth floor by taking at-most K leaps

0 0 7 minutes read

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 leap
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 Code
public 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 Code
if __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 leap
using 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 Code
public 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

<?php
error_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:

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 zambiatek!