## [f]izzbuzzer

### Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

# Count ways to reach the n stair

Sharing is caring!

Problem statement
There are $n$ stairs, a person standing at the bottom wants to reach the top. The person can climb either $1$ stair or $2$ stairs at a time. Count the number of ways, the person can reach the top.

Solution
We can solve this problem recursively. If the person were to take $1$ step, then we need to solve the problem for $n-1$ stairs. That is, finding the number of ways to traverse the remaining $n-1$ stairs. If the person were to take $2$ steps then the problem gets reduced to finding the number of ways to traverse the remaining $n-2$ stairs. Assuming we have a function count(n) that returns the number of ways to traverse $n$ stairs, we would have:

Finally, we need to define our termination conditions:
If there only $3$ stairs left, we know that a person can traverse them in three different ways ($1+1+1$ or $1+2$ or $2+1$). If there only $2$ stairs left, we know that a person can traverse them in two different ways ($1+1$ or $2$). If there is only $1$ stair left, we know that a person can traverse them in one way only. These are our recursion-termination conditions.

• `count(3) = 3`
• `count(2) = 2`
• `count(1) = 1`

Above we can see that count(n) is actually equal to fibonacci(n+1):

• `count(3) = fibonacci(4) = 3`
• `count(2) = fibonacci(3) = 2`
• `count(1) = fibonacci(2) = 1`

(Remember: $f_0 = 0, f_1= 1, f_2 = 1, f_3 = 2, f_4 = 3, \dots$).

We can solve this problem using the fibonacci series. Let us go ahead and define our fibonacci(n) function:

public static int fibonacci(int n) {
if (n <= 1) {
return n;
} else {
return fibonacci(n-1) + fibonacci(n-2);
}
}

Putting it all together we have:

public class NumberOfWays {
public static int fibonacci(int n) {
if (n <= 1) {
return n;
} else {
return fibonacci(n-1) + fibonacci(n-2);
}
}

public static int count(int s) {
return fibonacci(s + 1);
}

public static void main (String args[]) {
int s = 4;
System.out.println("Number of ways = "+ count(s));
}
}