Leonardo’s Leaps (Stair Case Puzzle)

By | May 13, 2014

This is a classic interview puzzle asked in many interviews.
Puzzle :Given N step stair, how many number of ways can you climb if you use either 1 or 2 at a time?
For example for a stair case with 3 steps there are total 3 ways to climb it :
Way 1: 1 single step then a double step
Way 2: 1 double step and then a single step
Way 3: 3 single steps

Try to find answer for some simple cases and you will automatically find the answer .
Hint : it’s a special kind of sequence of numbers


Solution :The problem is ismply calculating nth fibonacci number .
Let’s write a simple function numWays(x)
int numWays(int n){
if(n<=0)return 0; if(n=1)return 1; if(n==2)return 2; else return numWays(n-1)+numWays(n-2); } [/showhide] For more interesting puzzles see our puzzles page

One thought on “Leonardo’s Leaps (Stair Case Puzzle)

  1. Bob

    That is an excellent explanation. One question, how would you arrive at the paths themselves, not just the number of ways? For your example, the 3 sequences themselves, ie s,d d,s and s,s,s.

    Reply

Leave a Reply

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