Number of Ways to Reach a Position After Exactly k Steps Solution
Number of Ways to Reach a Position After Exactly k Steps solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Number of Ways to Reach a Position After Exactly k Steps is a medium coding problem on dynamic programming, math and combinatorics, asked in Amazon, Google and Adobe interviews.
- Difficulty: Medium
- Topics: Dynamic Programming, Math, Combinatorics
- Asked at: Amazon, Google, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You stand on an infinite number line at startPos. In one step you move one unit left or right.
Return the number of different step sequences of length exactly k that end at endPos, modulo 10⁹ + 7. Two sequences differ if any single step differs.
Example 1
Input: startPos = 1, endPos = 2, k = 3
Output: 3
Explanation: `R,R,L`, `R,L,R` and `L,R,R`.
Example 2
Input: startPos = 2, endPos = 5, k = 10
Output: 0
Explanation: The distance is 3 and 10 − 3 is odd, so the parity never works out.
Example 3
Input: startPos = 0, endPos = 0, k = 2
Output: 2
Explanation: `L,R` and `R,L`.
Constraints
1 <= startPos, endPos, k <= 1000
Hints for Number of Ways to Reach a Position After Exactly k Steps
Hint 1
Only the distance
d = |endPos - startPos|matters, not the direction or the absolute positions.Hint 2
With
rrights andllefts,r + l = kandr - l = ±d, sor = (k + d) / 2— which must be a whole number.Hint 3
The answer is then the binomial coefficient
C(k, r).
How to solve Number of Ways to Reach a Position After Exactly k Steps
Reduce to a counting identity. If r steps go right and l go left, then r + l = k and r - l = d, so r = (k + d) / 2. Any arrangement of those r rights among the k steps works, giving C(k, r).
Approach
- Compute
d = |endPos - startPos|. - Return 0 if
d > kor ifk - dis odd — those are unreachable by parity. - Otherwise return
C(k, (k + d) / 2)modulo 10⁹ + 7, built with Pascal's triangle.
Why it works
The parity check is the part that is easy to miss: each step changes the position by exactly one, so the position's parity flips every step, and after k steps you can only be at a point whose distance from the start has the same parity as k. Building the binomial with Pascal's triangle rather than factorials and inverses keeps the whole solution to additions — at k <= 1000 that is 500 000 operations and needs no modular inverse at all.
Complexity
- Time —
O(k²) with Pascal's triangle, or O(k) with factorials and an inverse - Space —
O(k)
Pitfalls
- Forgetting the parity check returns a nonsense binomial with a fractional index.
- Direction does not matter — the answer is symmetric in
startPosandendPos. ksteps must be used exactly; stopping early is not allowed.
Reference solution
Python
def numberOfWays(startPos: int, endPos: int, k: int) -> int:
MOD = 10**9 + 7
d = abs(endPos - startPos)
if d > k or (k - d) % 2 != 0:
return 0
row = [0] * (k + 1)
row[0] = 1
for i in range(1, k + 1):
for j in range(i, 0, -1):
row[j] = (row[j] + row[j - 1]) % MOD
return row[(k + d) // 2]Java
public static int numberOfWays(int startPos, int endPos, int k) {
final int MOD = 1000000007;
int d = Math.abs(endPos - startPos);
if (d > k || (k - d) % 2 != 0) return 0;
int[] row = new int[k + 1];
row[0] = 1;
for (int i = 1; i <= k; i++) {
for (int j = i; j >= 1; j--) row[j] = (row[j] + row[j - 1]) % MOD;
}
return row[(k + d) / 2];
}C++
int numberOfWays(int startPos, int endPos, int k) {
const int MOD = 1000000007;
int d = abs(endPos - startPos);
if (d > k || (k - d) % 2 != 0) return 0;
vector<int> row(k + 1, 0);
row[0] = 1;
for (int i = 1; i <= k; i++) {
for (int j = i; j >= 1; j--) row[j] = (row[j] + row[j - 1]) % MOD;
}
return row[(k + d) / 2];
}JavaScript
var numberOfWays = function(startPos, endPos, k) {
var MOD = 1000000007;
var d = Math.abs(endPos - startPos);
if (d > k || (k - d) % 2 !== 0) return 0;
var row = [], i, j;
for (i = 0; i <= k; i++) row.push(0);
row[0] = 1;
for (i = 1; i <= k; i++) {
for (j = i; j >= 1; j--) row[j] = (row[j] + row[j - 1]) % MOD;
}
return row[(k + d) / 2];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 402 dynamic programming problems · the whole catalogue
Learn the technique: Dynamic Programming