1

I was solving a test on an online platform and the problem statement was similar to this.

Stuart has to go from one place to other (A-> B) and he can jump either 1 step, 2 step or 3 steps at a time. There can be n number of stoppers between A to B.

We need to find the number of ways he can do this.

I feel this is similar to the classic climb stairs problem with little difference that there you finally had to reach the n-th step whereas in this particular problem you have to get down which makes n+1 step probably. Am I right?

So the code I wrote is this:

function countWays(n) {
    
    if (n < 0) return 0;
    if (n === 0) return 1;
    if (n === 1) return 2; //If you have one stop-over, there's two ways to reach. One is take one jump and then one more. Second is take two jumps at once and reach the destination

    return countWays(n-1) + countWays(n-2) + countWays(n-3);
 
}

console.log(countWays(4))

This didn't get accepted. So I'm just wondering what's wrong in this. Should I have added base case for n==2 as well?

if (n === 2) return 4

This still doesn't do any good though as for n = 3 it would return 6 whereas visually I can see there would be 7 ways if there 3 stop overs.

Another question I want to ask is,

In the classic stair case the base case for n === 0 would be 1. Would it still be the same here? This confuses me a bit as when there's no more step to climb how can the result be 1. On the hand hand here, when n === 1 you still have one way that you must take to reach the destination.

Also, for f(3) the logic and intuition says it should be:

number of ways to reach first stopover + f(2)

And number of ways to reach first stopover would be just one since there's only one way you can do so (by taking one jump.)

However, I can't put if(n == 1) return 1 in the base case as it would be incorrect. Let's say there's only one stop-over (n = 1) there's actually two ways to reach:

  1. Jump 2 steps
  2. Jump 1 steps and then one more.

So this is also creating a bit confusion.

Improve this question

2 Answers 2

Reset to default
2

I feel this is similar to the classic climb stairs problem ... whereas in this particular problem you have to get down which makes n+1 step probably. Am I right?

Yes.

Should I have added base case for n==2 as well?

Yes, or you could more easily add the n == -1 case, because that represents the case where you arrived at the destination, and represents a possibility (1). This looks odd, but it is consistent with your previous observation that the way this problem is stated differs with 1 step compared to the phrasing you were more used to. The case where n < -1 is where you overshoot the destination, and so that is when you want to return 0. You actually don't need other cases than the exact arrival (n == -1) and the overshooting (n < -1). The rest follows from it.

Here is your code adapted:

function countWays(n) {
    if (n < -1) return 0; // Overshooting: not a possibility.
    if (n === -1) return 1; // Destination reached: this is a possibility and thus counts as one.
    return countWays(n-1) + countWays(n-2) + countWays(n-3);
}

for (let n = 0; n < 5; n++) {
    console.log(n, countWays(n));
}

Now this is not efficient, as for larger n, you will make the same recursive calls over and over again. You could use bottom up tabulation to have an efficient solution:

function countWays(n) {
    let [a, b, c] = [0, 0, 1];
    while (n-- > -1) {
        [a, b, c] = [b, c, a + b + c];
    }
    return c;
}

for (let n = 0; n < 5; n++) {
    console.log(n, countWays(n));
}

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Right by modifying the classic one a little bit, I could get down to this: ``` if(n+1<0) return 0; if(n+1 == 0) return 1; return countWays(n-1) + countWays(n-2) + countWays(n-3); ``` Which is similar to yours. Btw in the classic one, for n==0 it returns 1. A bit confusing as when there's no more to climb how can that be 1. Could you please explain?
When you already are at the destination you apparently had a successful outcome. As you need to count the number of ways to have success, being there should count as 1 (even though the path has a zero length, it is still a successful path).
0

As the problem states, imagine you are standing at point A and want to reach point B. There are n stoppers in between, meaning you are not at the first stop and do not want to stop at the last one.

A -> n -> B

  • If n == 0, it means the starting point and the destination are the same. In this case, there is only one possible way to reach the destination.
  • If n == 1, there is one stopper between A and B. There are two possible ways to reach B:
    1. Jump one step from A to the stopper, then another one step from the stopper to B.
    2. Jump two steps directly from A to B.
  • Hence, for n = 1, there are two possible ways.
  • If n == 2, meaning there are two stoppers between A and B, there are four possible ways to reach B:
    1. A → Stop1 → Stop2 → B
    2. A → Stop1 → B
    3. A → Stop2 → B
    4. A → B directly (3-step)

To solve this problem efficiently, we store the number of ways in a dp array

int[] dp = new int[n+1]

and use a loop

for(int i=3; i<n+1; i++){

dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

}

Finally, the answer will be stored in dp[n].

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.