DEV Community

Cover image for 8.1 Triple Step
yuliakononchuk
yuliakononchuk

Posted on • Edited on

1 1

8.1 Triple Step

NB: This post is a part of the series of solving the challenges from 'Cracking The Coding Interview' book with JavaScript. I'll post only the challenges I've figured out on my own - and will try to describe my reasoning behind the solution. Any ideas on how to solve it differently or in a more optimal way are very welcome 😊

A child is running up a staircase with n steps and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the child can run up the stairs.

Hmm, this sounds a lot like a recursive algorithm 🤔To me the easiest way to think about it is to start backwards. Imagine that we have 5 steps and need to calculate all combinations of hops that can cover these 5 steps. We know that the child can hop either one step, 2 steps, or 3 steps at once - which means that she got to step 5 from either from step 4, or step 3, or step 2. In other words, if n equals 5, then the number of different ways to get to n is a number of ways to get to (n-1) + ways to get to (n-2) + ways to get to (n-3). Let's call the function that would calculate the number of all possible ways to get to step x getStaircaseCombinations(x).

But how did the child get to step 4 (the n-1 from above)? She must have been either on step 3, step 2, or step 1 before, and you can observe the same pattern all over again. In other words, for each step k we would need to return getStaircaseCombinations(k-1) + getStaircaseCombinations(k-2) + getStaircaseCombinations(k-3).

At which point do we stop? We know that the combination is correct if the sum of steps a child has made equals exactly to 5. We're going backwards, subtracting from 5 - which means that the correct combination should bring us to 0. So, when we're reaching 0 the combination must be valid and we should return 1. The alternative scenario is that we're ending up with a number less than 0: for instance, a child may have jumped to step 5 from step 2 (n-3) and to step 2 from step -1 (yet again, n-3). However, step -1 does not exist, a child would always start with step 0 - which means our combination does not work. So, for the cases resulting in a negative number we would return 0 and not count such combinations in.

This logic results in:

function getStaircaseCombinations(stairs) {
  if (stairs < 0) { return 0; }
  if (stairs === 0) { return 1; }
  return (
    getStaircaseCombinations(stairs - 1) +
    getStaircaseCombinations(stairs - 2) + 
    getStaircaseCombinations(stairs - 3)
  )
};
Enter fullscreen mode Exit fullscreen mode

Finally, you can notice that in the code above we're calculating the same path several times. For instance, for n=5 you would need to calculate the number of step combinations for 'how to reach step 3' twice: for the case of (n-2) and the case of ((n-1)–1) - and the bigger n gets, the more double-work this code will be doing.

In order to avoid this, we can use memoization technique. The logic is as follows:

✔️start with the empty array of results
✔️if array of results doesn't contain yet the number of combinations for x (and only then!), calculate it and store it in the array as results[x]
✔️return the number of combinations for x stored in the array

The slightly adjusted code that allows for memoization will look like:

function getStaircaseCombinations(stairs) {
  let combinations = [];
  function calculateCombinations(n) {
    if (n < 0) { return 0; }
    if (n === 0) { return 1; }
    if (combinations[n] === undefined) {
      combinations[n] = 
        calculateCombinations(n - 1) + 
        calculateCombinations(n - 2) + 
        calculateCombinations(n - 3);
    }
    return combinations[n];
  };
  calculateCombinations(stairs);
  return combinations[stairs];
}
Enter fullscreen mode Exit fullscreen mode

Sentry image

Hands-on debugging session: instrument, monitor, and fix

Join Lazar for a hands-on session where you’ll build it, break it, debug it, and fix it. You’ll set up Sentry, track errors, use Session Replay and Tracing, and leverage some good ol’ AI to find and fix issues fast.

RSVP here →

Top comments (1)

Collapse
 
gunplun profile image
Gunnar Plunkett • Edited

Pretty sure this can be done iteratively in O(1) space, since you actually only need to remember the previous three steps.

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay