Number of Ways to Reach a Position After Exactly k Steps — Medium Problem & Solution

You stand on an infinite number line at startPos. In one step you move one unit left or right.

Difficulty: Medium
Topics: Math, Dynamic Programming, 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

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 > k or if k - d is 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 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]

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 213 math problems · the whole catalogue