Watch 10 video solutions for Number of Ways to Reach a Position After Exactly k Steps, a medium level problem involving Math, Dynamic Programming, Combinatorics. This walkthrough by Bro Coders has 3,841 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1000Problem Overview: You start at startPos on a number line and can move either left or right by 1 step. After exactly k moves, you must land on endPos. The task is to count how many different sequences of moves reach the target. The answer can be large, so return it modulo 1e9 + 7.
Approach 1: Combinatorics and Parity Check (Time: O(k), Space: O(1))
Each step is either +1 (right) or -1 (left). Let d = |endPos - startPos|. To reach the target in exactly k steps, the difference between right and left moves must equal d. If k < d or (k - d) is odd, reaching the target is impossible because extra moves must cancel in pairs. Otherwise, compute the number of ways to choose the right moves using combinations: C(k, (k + d) / 2). The problem reduces to a binomial coefficient calculation under modulo arithmetic. This approach relies on basic math reasoning and combinatorics and avoids exploring all paths explicitly.
Approach 2: Dynamic Programming (Time: O(k²), Space: O(k²))
Model the process as state transitions. Let dp[step][pos] represent the number of ways to reach a position after a given number of moves. From position x, the next step can go to x - 1 or x + 1. Start with dp[0][startPos] = 1 and iterate for k steps, updating counts for adjacent positions. Because positions can become negative or large, shift indices by an offset or track relative distance from startPos. After filling the table, return dp[k][endPos]. This approach directly simulates all reachable states and demonstrates the classic transition pattern used in dynamic programming.
Recommended for interviews: The combinatorics solution is what most interviewers expect once you notice the parity constraint and the relationship between left/right moves. It reduces the problem to a single binomial coefficient and runs in linear time for factorial or iterative combination computation. The dynamic programming approach is easier to derive during the interview and shows solid state‑transition thinking, but it is less efficient. Showing the DP first and then optimizing to the combinatorics formula demonstrates strong problem‑solving progression.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Combinatorics + Parity Check | O(k) | O(1) | Best for interviews and production; converts the problem into a binomial coefficient calculation. |
| Dynamic Programming | O(k²) | O(k²) | Useful when deriving the solution step‑by‑step or when practicing DP state transitions. |