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

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:

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:

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:

.

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:

and

And adding both sides and we have:

So, we just have to compute the combination of , 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

–EOF (The Ultimate Computing & Technology Blog) —