Number of Ways to Reach a Position After Exactly k Steps

Medium
1041.

Number of Ways to Reach a Position After Exactly k Steps

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.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} startPos
 * @param {number} endPos
 * @param {number} k
 * @return {number}
 */
var numberOfWays = function(startPos, endPos, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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

  1. Hint 1

    Only the distance d = |endPos - startPos| matters, not the direction or the absolute positions.

  2. Hint 2

    With r rights and l lefts, r + l = k and r - l = ±d, so r = (k + d) / 2 — which must be a whole number.

  3. 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

  1. Compute d = |endPos - startPos|.
  2. Return 0 if d > k or if k - d is odd — those are unreachable by parity.
  3. 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 startPos and endPos.
  • k steps 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