Climbing Stairs

Solving this LeetCode coding problem with math

Problem: You are climbing a staircase. It takes n steps to reach the top. Each time you either climb 1 or 2 steps. In how many distinct ways can you climb to the top.

After reading the problem for the first time, one can see that it is a counting problem. We basically have to find the different combinations of 1 and 2 that sum up to n (because those are the combinations that will get us to the top: not above or below the top). We then have to find the different permutations(arrangements) of the combinations we have found. This will give us the different possible ways that we can get to the top and the total number of those ways will be the solution to the our problem.

Now let’s try the solution in the previous paragraph to some values of n so that we can write an algorithm based on it to solve the coding problem. Let x represent steps of length one and y steps of length two. We’re going to find the number of distinct ways of climbing to the top if it takes n={1,2,3,…6} steps.

Figure 1: Number of distinct ways of climbing to the top for some values of n

Our Solution to the coding problem

From figure 1, it can be seen that the first combination, which is the easiest to form, is just n 1s. Subsequent combinations contain two less of 1s and one more of 2s until there aren’t enough 1s to lose to form a 2. For even values of n, the there exists a combination of only 2s but for odd values of n the combination with the most number of 2s has one 1. From the above observations we can attempt to write a generalisation for the possible combinations of steps in climbing a n tall stairs. To climb a stairs of length n, the different possible combinations of steps are: n 1s and 0 2s, (n-2) 1s and 1 2s, (n-4) 1s and 2 2s,…, 1 1s and (n-1)/2 2s (for odd values of n) or 0 1s n/2 2s (for even values of n). Thus, the number of distinct ways that you can climb to the top of a stairs of length can be given by:

Figure 2: Formula for the number of ways of climbing a stairs of length n

Implementation of the above algorithm in python language

Figure 3: Implementation of the algorithm in figure 2 in python language

An alternative Solution

If we carefully observe figure 1, we can see that there is a trend in the number of distinct ways of climbing to the top. Let f(n) be the number of distinct ways of climbing to the top of a stairs of length n. We can see from figure 1 that f(3)=f(2)+f(1), f(4)=f(3)+f(2), f(5)=f(4)+f(3) and finally f(6)=f(5)+f(4). We can then postulate that f(n+1)=f(n)+f(n-1). But before we can use it comfortably, we need to prove it first ^_^

Proof of the postulation

Figure 4: Proof of postulation

A new algorithm

Figure 5: A new algorithm based on the postulation

Comparison of the two algorithms

Figure 6: Performance of the first algorithm on the Leetcode test cases

Figure 7: Performance of the second algorithm on the Leetcode test cases

Conclusion

The first solution requires the importation of a library for the python implementation. In other programming languages where there is no in-built factorial function, you will have to write another function to calculate the factorial. This is not time efficient, even though the function for factorial is quite known in the coding community. Additionally, it’s going to have a significantly high runtime.

The second solution on the other hand is quite simple to implement in any language at all and it requires no external libraries to work. It also has a significantly low runtime and if it is implemented such that the number of ways are not stored in a list but updated in a variable over time, it will use lesser memory than the one seen in figure 7.

Ultimately, I prefer the second solution because of its simplicity and elegance.

Lemme know your thoughts on the two solutions or any other solution you have in mind in the comments section.

Leave a clap if you enjoyed this :)