Sunday 22 May 2016

Stariway to Kth floor problem

Question

There are N stairs that you need to take to the kth floor. You can either climb 1 stair at a time or 2 stair at a time. In how many ways you can cover N stairs.


Solution

Solution is simple recursive one. At a particular step 

  • If remaining step >=2 then you can either climb 1 step or 2 steps
  • Else If remaining step == 1 you dont have a choice, have to climb 1 step
  • Else you have reached your destination and have crossed n stairs - increment way

Java solution is as follows - 

    public static int findWays(int stairsClimbed, int totalStairs) {
        
        if(stairsClimbed == totalStairs) {
            return 1;
        }
        
        if((totalStairs - stairsClimbed) >= 2) {
            return findWays(stairsClimbed + 2, totalStairs) + findWays(stairsClimbed + 1, totalStairs);
        }
        else if ((totalStairs - stairsClimbed) == 1) {
            return findWays(stairsClimbed + 1, totalStairs);
        }
        return 0;
    }


You can find detailed Java solution with test cases on git repository - StairwayClimbWaysFinder .

PS : Git link has a bonus solution as well :)


Related Links

t> UA-39527780-1 back to top