8. Design an algorithm that finds the number of ways in which you can traverse N meters by doing jumps of 1, 2, 3, 4, or 5 meter lengths. Assume that N can be a very large number. What is the resulting complexity? JavaScript. Interview Question at toptal.com.
By: Chrysanthus Date Published: 27 Oct 2025
Note:
Dynamic Programming will be used.The sequence of jumps can be of the set m={1} with 1 being maximum.
The sequence of jumps can be of the set m={1, 2} with 2 being maximum.
The sequence of jumps can be of the set m={1, 2, 3} with 3 being maximum.
The sequence of jumps can be of the set m={1, 2, 3, 4} with 4 being maximum.
The sequence of jumps can be of the set m={1, 2, 3, 4, 5} with 5 being maximum.
The sequence of jumps can be of the set m={1, 2, 3, 4, 5, 6} with 6 being maximum.
And so on . . .
The question uses the sequence of jumps, {1, 2, 3, 4, 5} with 5 being maximum. The dynamic programming table (2D array) below, provides sequences from m={} to m={1, 2, 3, 4, 5}. The maximum of each sequence is quoted as m in the table, and even in the code.
A jump means reaching the end of a meter. Traversing a meter also means reaching the end of the meter. For example, given m={1, 2} and N=2 for length of a path (number of meters), there are two ways of traversing the two meters. One way is to jump by 1 step to reach the end of the first meter and then jump another 1 meter to reach the end of the second meter. The other way is just to jump 2 meters at once, in order to reach the end of the second meter.
For all traversing, the end of the last meter is not crossed, except for the case when N=0. When N=0, there is only one way to traverse the 0 meter. Accept that without proof. If m={1}, the number of ways is 1 for N=0. If m={1, 2}, the number of ways is still 1 for N=0. If m={1, 2, 3}, the number of ways is still 1 for N=0; and so on. In this case, the 0 meter is crossed, and that is the only case for crossing the last meter, where in this case, the last meter does not even exist.
"N can be a very large number" means that N is at least 10 times m, where m here, refers to the largest number in the set of m.
Illustration
In this section, it is explained how to produce the 2D dp array using examples of m and N. "dp" means dynamic programming. The main set used is m={1, 2, 3}.m={1, 2, 3} and different values of N
Let m={1, 2, 3} and N=0When m={1, 2, 3} and N=0, there is only one way to traverse the N meters (see above).
Let m={1, 2, 3} and N=1
There is only one way which is the jump:
1
Let m={1, 2, 3} and N=2
Two ways:
either
1, 1
or
2
Let m={1, 2, 3} and N=3
Four ways:
either
1, 1, 1
or
2, 1
or
1, 2
or
3
Let m={1, 2, 3} and N=4
Seven ways:
either
1, 1, 1, 1
or
2, 1, 1
or
1, 2, 1
or
1, 1, 2
or
2, 2
or
3, 1
or
1, 3
Note that here, N=4 = 3+1 = m+1, where m in this case is the highest value in the set for m. When m={1, 2, 3} and N=4, the number of ways is the sum of the 3 previous ways, with N=3, N=2 and N=1; which is four + two + one = seven.
With this trend, when m={1, 2, 3} and N=5, the number of ways should be the sum of the 3 previous ways, with N=4, N=3, and N=2; which is seven + four + two = thirteen.
The above illustration has been made with m={1, 2, 3} for different values of N. In the code, these different values of N is actually referred to, with the variable k. The next and last illustration will be done with m={1, 2} for different values of N.
m={1, 2} and different values of N
Let m={1, 2} and N=0When m={1, 2} and N=0, there is only one way to traverse the N meters (see above).
Let m={1, 2} and N=1
There is only one way which is the jump:
1.
A jump of 2 has excess.
Let m={1, 2} and N=2
Two ways:
either
1, 1
or
2
Let m={1, 2} and N=3
Three ways:
either
1, 1, 1
or
2, 1
or
1, 2
Note that here, N=3 = 2+1 = m+1, where m in this case is the highest value in the set for m. When m={1, 2} and N=3, the number of ways is the sum of the 2 previous ways, with N=2 and N=1; which is two + one = three.
Let m={1, 2} and N=4
Five ways:
either
1, 1, 1, 1
or
2, 1, 1
or
1, 2, 1
or
1, 1, 2
or
2, 2
With this trend, when m={1, 2} and N=4, as can be seen above, the number of ways is the sum of the 2 previous ways, with N=3 and N=2; which is three + two = five.
The above illustration has been made with m={1, 2} for different values of N. In the code, these different values of N is actually referred to, with the variable k.
The strategy for these illustrations can be used to obtain answers for different combinations of the set m and the value N.
The 2D dp Array
The above strategy is used to produce the following two dimensional dp array:m/k 0 1 2 3 4 5 6 7 8 9 10 11Each value for m represents a set for the sequence m, where the variable, m in the table (2D array), represents the highest integer in its set.
0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
1 1 1 1 1 1 1 1 1 1 1 1 1
2 1 1 2 3 5 8 13 21 34 55 89 144
3 1 1 2 4 7 13 24 44 81 149 274 504
4 1 1 2 4 8 15 29 56 108 208 401 773
5 1 1 2 4 8 16 31 61 120 236 464 912
The variable, k represents the different values of N in the table (2D array).
The Logical Pattern
Observe from the table that, for a given value of m, the answer for a value of N, is the sum of the previous m answers.For example, when m={1, 2, 3, 4, 5} and N=7,
answer = 61 = n(7) = 31 + 16 + 8 + 4 + 2 = 61
When m={1, 2, 3, 4} and N=7,
answer = 56 = n(7) = 29 + 15 + 8 + 4 = 56
When m={1, 2, 3} and N=7,
answer = 44 = n(7) = 24 + 13 + 7 = 44
When m={1, 2} and N=7,
answer = 21 = n(7) = 13 + 8 = 21
When m={1} and N=7,
answer = 1 = n(7) = 1 = 1; just count once
When m={} and N=7,
answer = ∞ = n(7) = ∞ = ∞
The first row of the table, with values of infinity, should not be part of the solution (code).
In general,
n[k] = n[k-1] + n[k-2] + - - - + n[k-m]
This needs a one dimensional array called n, and not a two dimensional array as anticipated above. In the case of m={1, 2, 3, 4, 5} for the question,
n[k] = n[k-1] + n[k-2] + n[k-3] + n[k-4] + n[k-5]
The code solution for the question, should address the last row in the table above (2D dp array), from m=5.
Answer for given m and N
The next question in search of the complete solution, is how to get the next answer (2D array dp cell value) for a particular value of m and N.
The solution for the problem, is to find all the values for a row in the dp table. In the course of doing that, each cell value for a particular m and N is obtained.
Explanation with Row 3
Here, k can take different values up to N (inclusive), but m remains at 3. For quick reference by the reader, row 3 above is retyped here; thus:
1 1 2 4 7 13 24 44 81 149 274 504
where the first number on the left is for k=0. (do not forget that when k=0, the first number in any row is 1.)
k=0
Number of ways of arranging (any sequence) to cross 0, in the set m={1, 2, 3} is given as 1 (see above). Only when N=0, the path can be crossed. Otherwise, the path (traversing) ends at the end of the last meter.
k = 1
Number of ways of arranging (1,) to sum to 1, in the set m={1, 2, 3} is 1. Remember, any of the numbers in the set m={1, 2, 3}, can be used more than once. Also, considering the highest sequence number, 3 as m, then it should be noticed that k is less than m here. This stage has a count of 1, which is equal to k, the lesser of k and m.
k=2
Number of ways of arranging (1, 2) to sum to 2, in the set m={1, 2, 3} is 2. Remember, any of the numbers in the set m={1, 2, 3}, can be used more than once. Also, considering the highest sequence number, 3 as m, then it should be noticed that k is less than m here. This stage has a count of 2, which is equal to k, the lesser of k and m.
The number of ways, 2 can also be obtained by adding the two previous answers of 1 and 1.
k=3
Number of ways of arranging (1, 2, 3) to sum to 3, in the set m={1, 2, 3} is 4. Remember, any of the numbers in the set m={1, 2, 3}, can be used more than once. Also, considering the highest sequence number, 3 as m, then it should be noticed that k is of the same value as m here (so either can be considered the less). This stage has a count of 3, which is equal to k or m (neither of which is the bigger).
The number of ways, 4 can also be obtained by adding the three previous answers of 1, 1 and 2. Henceforth, with increasing value of k, the number of ways (answer), is the sum of the previous three answers, when m={1, 2, 3}.
k=4
Number of ways of arranging (1, 2, 3) to sum to 7, in the set m={1, 2, 3} is 7. Remember, any of the numbers in the set m={1, 2, 3}, can be used more than once. Also, considering the highest sequence number, 3 as m, then it should be noticed that m is less than k here. This stage has a count of 3, which is equal to m, the lesser of k and m.
The number of ways, 7 can also be obtained by adding the three previous answers of 1, 2 and 4.
k=5
Number of ways of arranging (1, 2, 3) to sum to 13, from the set m={1, 2, 3} is 13. Remember, any of the numbers in the set m={1, 2, 3}, can be used more than once. Also, considering the highest sequence number, 3 as m, then it should be noticed that m is less than k here. This stage has a count of 3, which is equal to m, the lesser of k and m.
The number of ways, 13 can also be obtained by adding the three previous answers of 2, 4 and 7.
The answers (number of ways) of the higher values of k are similarly obtained.
The other rows for the 2D dp array are similarly obtained, but with different sets of m (such as m={1,2} and m={1, 2, 3, 4}).
The question for this article, requires that m={1, 2, 3, 4, 5}. The question does not specify any value for N (k), so N=7 is chosen for the code below.
The complete algorithm below, produces the last row of the 2D array above, from k=0 to k=7 and not k=11. The last value (on the right) corresponding to k=7 is returned.
O(N) Code
Remember that N is very large, in order not to result in N^2 number of operations. A summary for the complete algorithm here, is as follows:Beginning from k=1 with n[k] = 0, add all the previous answers, for the new answers of k, until k=m. After that, add all the previous m answers for the new answer, where k is greater than m, until the variable, i=m (see below). The program is:
<script type='text/javascript'>The output is:
"use strict";
function ways(N, m) { //m is the maximum sequence number in set, m
const n = new Array(N+1);
n[0] = 1; //first value of array n, for N = 0
for (let k=1; k<=N; k++) {
n[k] = 0; //initial sum to obtain cell value
for (let i=0; i <= Math.min(m, k); i++)
n[k] = n[k] + n[k - i];
}
return n[N];
}
let ret = ways(7, 5);
document.write(ret + '<br>');
</script>
61
This solution has a time complexity of O(N).
Thanks for reading.