Algorithms for Coding Interviews in Java/

...

/

Solution: Staircase Problem

Solution: Staircase Problem

This review contains a detailed analysis of the different ways to solve the staircase problem.

We'll cover the following...

Solution #1: Brute force

Let’s look at the brute force solution first:

Press + to interact
class StairCaseProblem
{ 
  //returning count of ways to reach the nth stair
  //either using 1 hop, 2 hops or 3 hops
  public static int countWays(int n) 
  {
    if (n < 0)
      return 0;
    else if (n == 0)
      return 1;
    else
      return countWays(n-1) + countWays(n-2)+ countWays(n-3);
  }
  //main function
  public static void main(String args[]) 
  {
    System.out.println(countWays(3));
  }
};

Explanation

The main idea is that if you have n stairs, then you can hop either 1 step, 2 steps or 3 steps.

  1. If you hop 1 step, then you have n−1n-1 remaining stairs
  2. If you hop 2 steps, then you have n−2n-2 remaining stairs
  3. If you hop 3 steps, then you have n−3n-3
...