Coding Sample Questions | Part 7 | Codewindow.in

Problem Statement :

There’s a staircase with N steps, and you can climb 1 or 2 steps at a time. Given N, write a function that returns the number of unique ways you can climb the staircase. The order of the steps matters.
For example, if N is 4, then there are 5 unique ways:
1, 1, 1, 1
2, 1, 1
1, 2, 1
1, 1, 2
2, 2
What if, instead of being able to climb 1 or 2 steps at a time, you could climb any number from a set of positive integers X? For example, if X = {1, 3, 5}, you could climb 1, 3, or 5 steps at a time.
Generalize your function to take in X.

Input Format:
First line of input will contain number N.

Output Format:
The Provided Pattern mentioned in the Example

Constraints:
0<N<=14

Sample Input 1 :
4

1 3 5
Sample Output 1 :
3

Solution:

Python

#https://codewindow.in
#please follow the indentation as its a must in python programing

def staircase(n, X):
    if n < 0:
        return 0
    elif n == 0:
        return 1
    elif n in X:
        return 1 + sum(staircase(n - x, X) for x in X if x < n)
    else:
        return sum(staircase(n - x, X) for x in X if x < n)
        
n=int(input())
X=list(map(int, input().split()))

print(staircase(n,X))
        

#end

Follow Us

Also checkout

Leave a Comment

Your email address will not be published. Required fields are marked *