# Teaching Kids Programming – Number of Ways to Reach a Position After Exactly k Steps (Combinations + Math + Dynamic Programming Algorithms)

Teaching Kids Programming – Number of Ways to Reach a Position After Exactly k Steps (Combinations + Math + Dynamic Programming Algorithms) | ninjasquad

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given two positive integers startPos and endPos. Initially, you are standing at position startPos on an infinite number line. With one step, you can move either one position to the left, or one position to the right.

Given a positive integer k, return the number of different ways to reach the position endPos starting from startPos, such that you perform exactly k steps. Since the answer may be very large, return it modulo 109 + 7.

Two ways are considered different if the order of the steps made is not exactly the same.

Note that the number line includes negative integers.

Example 1:
Input: startPos = 1, endPos = 2, k = 3
Output: 3
Explanation: We can reach position 2 from 1 in exactly 3 steps in three ways:
– 1 -> 2 -> 3 -> 2.
– 1 -> 2 -> 1 -> 2.
– 1 -> 0 -> 1 -> 2.
It can be proven that no other way is possible, so we return 3.

Example 2:
Input: startPos = 2, endPos = 5, k = 10
Output: 0
Explanation: It is impossible to reach position 5 from position 2 in exactly 10 steps.

Constraints:
1 <= startPos, endPos, k <= 1000

Hints:
How many steps to the left and to the right do you need to make exactly?
Does the order of the steps matter?
Use combinatorics to find the number of ways to order the steps.

### Number of Ways to Reach a Position After Exactly k Steps (Dynamic Programming Algorithms)

If the distance between start and end is larger than k, then it is impossible to reach the destination using exactly k steps, thus returning zero. Also, if the oddity (being odd or even) of k and distance is not the same e.g. if k is odd and distance is even or k is even and distance is odd, it is also impossible to reach destination using exactly k steps.

We can easily come up with a dp function e.g. f:

$tex_a136590a87c936839b16ce00125933f4 Teaching Kids Programming - Number of Ways to Reach a Position After Exactly k Steps (Combinations + Math + Dynamic Programming Algorithms) algorithms Combination Dynamic Programming math Memoization Recursion recursive teaching kids programming youtube video$

s = start
e = end
k = steps

With one step, we can either move left or move right, and the end is not changing. If the k step is zero:

$tex_23849615e7d0a509cdee8312c434f7a6 Teaching Kids Programming - Number of Ways to Reach a Position After Exactly k Steps (Combinations + Math + Dynamic Programming Algorithms) algorithms Combination Dynamic Programming math Memoization Recursion recursive teaching kids programming youtube video$
$tex_010109a156202b88c275697c0b17791f Teaching Kids Programming - Number of Ways to Reach a Position After Exactly k Steps (Combinations + Math + Dynamic Programming Algorithms) algorithms Combination Dynamic Programming math Memoization Recursion recursive teaching kids programming youtube video$ where s is not equal to e.

Thus, we can implement the Dynamic Programming Algorithm using Recursion with Memoization aka using the @cache or a hash table remember to states e.g. intermediate results so that they are not expanded excessively.

 ```1 2 3 4 5 6 7 8 9 10 11 12 13 ``` ```class Solution:     def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:             @cache         def dfs(s, e, k):             d = abs(e - s)             if d > k:                 return 0             if d & 1 != k & 1:                 return 0             if k == 0:                 return 1 if s == e else 0             return dfs(s - 1, e, k - 1) + dfs(s + 1, e, k - 1)                 return dfs(startPos, endPos, k) % (10**9+7)```
```class Solution:
def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:
@cache
def dfs(s, e, k):
d = abs(e - s)
if d > k:
return 0
if d & 1 != k & 1:
return 0
if k == 0:
return 1 if s == e else 0
return dfs(s - 1, e, k - 1) + dfs(s + 1, e, k - 1)
return dfs(startPos, endPos, k) % (10**9+7)```

The states to compute and remember is limited because we will immediately return zero if the distance is larger than k.

We can store the DP values in a two dimensional array e.g. dp[k][d] which means the number of ways to move to distance d with k steps, and we have:

$tex_affdb5f17f119240759c6f05d815a9a9 Teaching Kids Programming - Number of Ways to Reach a Position After Exactly k Steps (Combinations + Math + Dynamic Programming Algorithms) algorithms Combination Dynamic Programming math Memoization Recursion recursive teaching kids programming youtube video$.

We can iteratively solve the DP equation just like Pascal triangle. However, the implementation is not trivial, and we need to make sure the boundary conditions are properly handled.

### Number of Ways to Reach a Position After Exactly k Steps (Combinations + Math)

Let’s say, we take L steps to move left, and R steps to move right, thus we have:

$tex_3d2d244a1b14d244b296f55415e84feb Teaching Kids Programming - Number of Ways to Reach a Position After Exactly k Steps (Combinations + Math + Dynamic Programming Algorithms) algorithms Combination Dynamic Programming math Memoization Recursion recursive teaching kids programming youtube video$
and $tex_c1aafe03457244b181f15885bf393e33 Teaching Kids Programming - Number of Ways to Reach a Position After Exactly k Steps (Combinations + Math + Dynamic Programming Algorithms) algorithms Combination Dynamic Programming math Memoization Recursion recursive teaching kids programming youtube video$

And adding both sides and we have:

$tex_ca7fd2fe65e2097dfa5b9ffa31848cec Teaching Kids Programming - Number of Ways to Reach a Position After Exactly k Steps (Combinations + Math + Dynamic Programming Algorithms) algorithms Combination Dynamic Programming math Memoization Recursion recursive teaching kids programming youtube video$

So, we just have to compute the combination of $tex_0770e019f923c953270d9f0e50666371 Teaching Kids Programming - Number of Ways to Reach a Position After Exactly k Steps (Combinations + Math + Dynamic Programming Algorithms) algorithms Combination Dynamic Programming math Memoization Recursion recursive teaching kids programming youtube video$, R steps out of k to move right.

 ```1 2 3 4 5 6 ``` ```class Solution:     def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:             d = endPos - startPos         if abs(d) > k or (d & 1 != k & 1):             return 0         return comb(k, (k+d)//2) % (10**9+7)```
```class Solution:
def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:
d = endPos - startPos
if abs(d) > k or (d & 1 != k & 1):
return 0
return comb(k, (k+d)//2) % (10**9+7)```

We know there are ways to compute the Combination Number: Teaching Kids Programming – Three Algorithms to Compute the Combination Number

GD Star Rating