A monkey is standing below at a staircase having N steps. Considering it can take a leap of 1 to N steps at a time, calculate how many ways it can reach the top of the staircase?
Examples:
Input : 2
Output : 2
It can either take (1, 1) or (2) to
reach the top. So, total 2 ways
Input : 3
Output : 4
Possibilities : (1, 1, 1), (1, 2), (2, 1),
(3). So, total 4 ways
There are 3 different ways to think of the problem.
- In all possible solutions, a step is either stepped on by the monkey or can be skipped. So using the fundamental counting principle, the first step has 2 ways to take part, and for each of these, 2nd step also has 2 ways, and so on. but the last step always has to be stepped on.
2 x 2 x 2 x .... x 2(N-1 th step) x 1(Nth step)
= 2(N-1) different ways.
- Let’s define a function F(n) for the use case. F(n) denotes all possible way to reach from bottom to top of a staircase having N steps, where min leap is 1 step and max leap is N step. Now, for the monkey, the first move it can make is possible in N different ways ( 1 step, 2 steps, 3 steps .. N steps). If it takes the first leap as 1 step, it will be left with N-1 more steps to conquer, which can be achieved in F(N-1) ways. And if it takes the first leap as 2 steps, it will have N-2 steps more to cover, which can be achieved in F(N-2) ways. Putting together,
F(N) = F(N-1) + F(N-2) + F(N-3) + ... +
F(2) + F(1) + F(0)
Now,
F(0) = 1
F(1) = 1
F(2) = 2
F(3) = 4
Hence,
F(N) = 1 + 1 + 2 + 4 + ... + F(n-1)
= 1 + 2^0 + 2^1 + 2^2 + ... + 2^(n-2)
= 1 + [2^(n-1) - 1]
C++
#include <iostream>
int calculateLeaps(int n)
{
if (n == 0 || n == 1) {
return 1;
}
else {
int leaps = 0;
for (int i = 0; i < n; i++)
leaps += calculateLeaps(i);
return leaps;
}
}
int main()
{
int calculateLeaps(int);
std::cout << calculateLeaps(4) << std::endl;
return 0;
}
|
Java
class GFG {
static int calculateLeaps(int n)
{
if (n == 0 || n == 1) {
return 1;
}
else {
int leaps = 0;
for (int i = 0; i < n; i++)
leaps += calculateLeaps(i);
return leaps;
}
}
public static void main(String[] args)
{
System.out.println(calculateLeaps(4));
}
}
|
Python3
def calculateLeaps(n):
if n == 0 or n == 1:
return 1;
else:
leaps = 0;
for i in range(0,n):
leaps = leaps + calculateLeaps(i);
return leaps;
print(calculateLeaps(4));
|
C#
using System;
class GFG {
static int calculateLeaps(int n)
{
if (n == 0 || n == 1) {
return 1;
}
else {
int leaps = 0;
for (int i = 0; i < n; i++)
leaps += calculateLeaps(i);
return leaps;
}
}
public static void Main()
{
Console.WriteLine(calculateLeaps(4));
}
}
|
PHP
<?php
function calculateLeaps($n)
{
if ($n == 0 || $n == 1)
{
return 1;
}
else
{
$leaps = 0;
for ($i = 0; $i < $n; $i++)
$leaps += calculateLeaps($i);
return $leaps;
}
}
echo calculateLeaps(4), "\n";
?>
|
Javascript
<script>
function calculateLeaps(n)
{
if (n == 0 || n == 1) {
return 1;
}
else {
let leaps = 0;
for (let i = 0; i < n; i++)
leaps += calculateLeaps(i);
return leaps;
}
}
document.write(calculateLeaps(4));
</script>
|
- Output:
8
Time Complexity: O(2n)
Auxiliary Space: O(n) due to recursive stack space
2. The above solution can be improved by using Dynamic programming (Bottom-Up Approach)
Leaps(3)
3/ 2| 1\
Leaps(0) Leaps(1) Leaps(2)
/ | \ 3/ 2| 1\
Leaps(-3) Leaps(-2) Leaps(-1) Lepas(-1) Leaps(0) Leaps(1)
C++
#include <iostream>
using namespace std;
int calculateLeaps(int n, int dp[]){
if(n == 0){
return 1 ;
}else if(n < 0){
return 0 ;
}
if(dp[n] != 0 ){
return dp[n] ;
}
int count = 0;
for(int i = 0 ; i < n ; i++ ){
count += calculateLeaps(i, dp) ;
}
dp[n] = count ;
return count ;
}
int main() {
int n = 4 ;
int dp[n+1] = {0} ;
cout<<calculateLeaps(n,dp) ;
return 0;
}
|
Java
import java.io.*;
class GFG
{
public static int calculateLeaps(int n, int dp[])
{
if(n == 0)
{
return 1 ;
}
else if(n < 0)
{
return 0 ;
}
if(dp[n] != 0)
{
return dp[n] ;
}
int count = 0;
for(int i = 0 ; i < n ; i++)
{
count += calculateLeaps(i, dp);
}
dp[n] = count;
return count;
}
public static void main (String[] args)
{
int n = 4;
int dp[] = new int[n+1];
System.out.println(calculateLeaps(n,dp));
}
}
|
Python3
def calculateLeaps(n, dp):
if(n == 0):
return 1
elif(n < 0):
return 0
if(dp[n] != 0 ):
return dp[n]
count = 0
for i in range(n):
count += calculateLeaps(i, dp)
dp[n] = count
return count
n = 4
dp = [0]*(n+1)
print(calculateLeaps(n,dp))
|
C#
using System;
class GFG
{
public static int calculateLeaps(int n, int[] dp)
{
if(n == 0)
{
return 1 ;
}
else if(n < 0)
{
return 0 ;
}
if(dp[n] != 0)
{
return dp[n] ;
}
int count = 0;
for(int i = 0 ; i < n ; i++)
{
count += calculateLeaps(i, dp);
}
dp[n] = count;
return count;
}
public static void Main (string[] args)
{
int n = 4;
int[] dp = new int[n+1];
Console.WriteLine(calculateLeaps(n,dp));
}
}
|
Javascript
<script>
function calculateLeaps(n, dp){
if(n == 0){
return 1
}else if(n < 0){
return 0
}
if(dp[n] != 0 ){
return dp[n]
}
let count = 0
for(let i = 0 ; i < n ; i++ ){
count += calculateLeaps(i, dp)
}
dp[n] = count
return count
}
let n = 4
let dp = new Array(n+1).fill(0)
document.write(calculateLeaps(n,dp))
</script>
|
Time Complexity: O(n) // maximum different states
Auxiliary Space : O(n) + O(n) -> O(n) // auxiliary stack space + dp array size
3. Let’s break this problem into small subproblems. The monkey has to step on the last step, the first N-1 steps are optional. The monkey can step on 0 steps before reaching the top step, which is the biggest leap to the top. Or it can decide to step on only once in between, which can be achieved in n-1 ways [ (N-1)C1 ]. And so on, it can step on only 2 steps before reaching the top in (N-1)C2 ways. Putting together..
F(N) = (N-1)C0 + (N-1)C1 + (N-1)C2 + … + (N-1)C(N-2) + (N-1)C(N-1)
Which is sum of binomial coefficient.
= 2^(n-1)
C++
#include <bits/stdc++.h>
using namespace std;
int calculateLeaps(int n)
{
if (n == 0)
return 1;
return (1 << (n - 1));
}
int main()
{
int calculateLeaps(int);
std::cout << calculateLeaps(4) << std::endl;
return 0;
}
|
Java
class GFG {
static int calculateLeaps(int n)
{
if (n == 0)
return 1;
return (1 << (n - 1));
}
public static void main(String[] args)
{
System.out.println(calculateLeaps(4));
}
}
|
Python3
def calculateLeaps(n):
if (n == 0):
return 1;
return (1 << (n - 1));
print(calculateLeaps(4));
|
C#
using System;
class GFG {
static int calculateLeaps(int n)
{
if (n == 0)
return 1;
return (1 << (n - 1));
}
public static void Main()
{
Console.WriteLine(calculateLeaps(4));
}
}
|
PHP
<?php
function calculateLeaps($n)
{
if ($n == 0)
return 1;
return (1 << ($n - 1));
}
echo calculateLeaps(4);
?>
|
Javascript
<script>
function calculateLeaps(n)
{
if (n == 0)
return 1;
return (1 << (n - 1));
}
document.write(calculateLeaps(4));
</script>
|
Output:
8
Time Complexity: O(1)
Auxiliary Space: O(1)
This article is contributed by Partha Pratim Mallik. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
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!
