Using only 1, 2, 3 steps reach to nth step

Question

I was doing an online interview some days back and came across this task that we can reach the nth step by using only steps 1 or 2 or 3.

Updated Question: 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.

This is my solution using dynamic programming. But during the interview, I saw that there were 6 hidden test cases that were failing.

public static long countWays(int n)
    {
        if(n==0 || n==1) return 1;

        long[] res = new long[n + 1];
        res[0] = 1;
        res[1] = 1;
        res[2] = 2;
 
        for (int i = 3; i <= n; i++)
            res[i] = res[i - 1] + res[i - 2]
                     + res[i - 3];
 
        return res[n];
    }
 

During the interview, only 5 test cases were passing out of 11. The remaining 6 are hidden test cases.

The range for n is 0 to 10 power 8.

I was not able to understand where I was doing a mistake, already this code is in O(n) time complexity. Is there a better way to do this or am I missing something?

Kif

It would be a lot clearer if you explained what you mean by "step" here. When you write "steps 1 or 2 or 3" it sounds like you are referring to some steps of some procedure which you did not describe. Also, if n could be as large as 10^8, there is no way the correct result of the arithmetic you're doing would fit within a long, since the sequence grows exponentially. – Onieonion

@Pshemo, I added details under updated section, please check. – Kif

Also, 10^8 is a very large number, and an O(n) algorithm is probably not fast enough for most online judges. – Onieonion

@kaya3, I added details under the updated section. The return type of the program was long, so I have created my array type to be long. – Kif

@kaya3, got it, so what is the better way for this task? can you please help me. – Kif

You are not required to find all combinations, only their quantity. The correct answer is to calculate the answer rather than exhaustively find all combinations. For that, you'll have to figure it out, either through pure math, or by finding a pattern in the output of of the brute a force method for a range of small n values. – Instrumentalism

If the problem as stated expects you to return a long then it is unsolvable, since the correct answer will generally not fit in a long value. Typically in such algorithm problems, you would be expected to output the result modulo some convenient large prime number, such as 10^9 + 7. – Onieonion

@kaya3, yes it was mentioned like that ` large prime number, such as 10^9 + 7`, but I am not aware of what that statement means. Can you please elaborate more on that. – Kif

As for other approaches, the problem is very similar to computing Fibonacci numbers, so I suggest you start there. There is a classic method which involves solving the difference equation to find an expression for the n-th term in closed form, which then allows you to compute a number like x^n where x is the solution of (in this case) a cubic polynomial; this can be done using a square-and-multiply algorithm in O(log n) time. Another approach is to represent the recurrence relation as a matrix equation, and then compute A^n for the appropriate matrix A (also logarithmic time). – Onieonion

If it was mentioned in the problem statement then you need to include it in your question. If you admittedly didn't understand that part of the problem statement, then perhaps that explains why your solution wasn't correct, so start by trying to learn what it means. – Onieonion

I am using dynamic programming similar to the fibonacci numbers approach. I am totally lost from your line There is a classic method which involves solving the difference equation to and remaining. Can you please refer me some tutorial where I can learn this concept, I want to solve this program. – Kif

youtube.com/watch?v=5o-kdjv7FD0 it's actually fib(n) + 1. – Crossbreed

@GiorgiTsiklauri, I am already using exact same approach mentioned in the youtube link. – Kif

@Bohemian, can you please help me how to get that, I tried but not able to get any sequence. – Kif

Have a look at "Method 3: Matrix Exponentiation (O(logn) Approach)" from geeksforgeeks.org/count-ways-reach-nth-stair-using-step-1-2-3 – Fastening

@Onieonion there are 0 possible ways a child can run up 10^8 stairs. In fact, I'd set the maximum quite a bit lower than that :) – Labourer

Answer 1

You can write down the recurrence relation in this problem

S_k = S_k-1 + S_k-2 + S_k-3

in the following matrix form:

| S[k]   |   | 1  1  1 |   | S[k-1] |   
| S[k-1] | = | 1  0  0 | * | S[k-2] |
| S[k-2] |   | 0  1  0 |   | S[k-3] |   

Which means that the k-th power of the matrix can quickly give you S_k:

            k
| 1  1  1 |     | S[2] |   | S[k+2] | 
| 1  0  0 |   * | S[1] | = | S[k+1] |
| 0  1  0 |     | S[0] |   | S[k]   |

So to solve this problem you basically need to find the n-th power of this matrix.

You can raise something to the n-th power in O(log n) time using the exponentiation by squaring algorithm.

Another useful observation is that you need only 3 numbers S_k, S_k-1 and S_k-2 to the represent the k-th power of the matrix:

            k
| 1  1  1 |     | S[k] + S[k-1] + S[k-2]    S[k] + S[k-1]      S[k]   |
| 1  0  0 |   = | S[k]                      S[k-1] + S[k-2]    S[k-1] |
| 0  1  0 |     | S[k-1]                    S[k] - S[k-1]      S[k-2] |

And from this, by multiplying k-th and m-th powers of the matrix you can get the following relations:

S_k+m = S_kS_m-2 + S_k-2S_m + S_k-1S_m-2 + S_k-2S_m-1 + S_k-2S_m-2 + S_k-1S_m-1
S_k+m-1 = S_kS_m-1 + S_k-1S_m + S_k-1S_m-1 + S_k-2S_m-2
S_k+m-2 = S_k-1S_m-2 + S_k-2S_m-1 + S_kS_m – S_k-1S_m-1

Putting all of this together into code you get the following solution:

public class Solution {
    private static final int M = 1_000_000_007;

    // The set of equations for S[k+m], S[k+m-1], S[k+m-2]
    // a[t] is S[k-t] and b[t] is S[m-t]
    private static long[] mul(long[] a, long[] b) {
        long r0110 = a[0]*b[1] + a[1]*b[0];
        long r0011 = a[0]*b[0] + a[1]*b[1];
        return new long[] {
            (a[0]*b[2] + a[2]*b[0] + r0110 + r0011) % M,
            (a[1]*b[2] + a[2]*b[1] + r0011) % M,
            (r0110 + a[2]*b[2] - a[1]*b[1]) % M
        };
    }

    public static long countWays(int n) {
        long[] result = {1, 0, 0};
        long[] square = {1, 0, 0};
        // Exponentiation by squaring
        for (int i = n; i != 0; i /= 2) {
            if (i % 2 == 1) result = mul(result, square);
            square = mul(square, square);
        }
        return result[0];
    }
}

Reinforcement

Answer 2

I wrote three solutions for this problem. Please take a look at github

There is a long discussion about using linear algebra to solve it.

Shani

While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. - From Review – Conquian