Number of Ways to Reach a Position After Exactly k Steps

medium dp math combinatorics memoization

Problem

You start at startPos on an infinite number line and must take exactly k steps, each moving +1 or -1. Return the number of distinct step sequences that end at endPos, modulo 10^9 + 7.

InputstartPos = 1, endPos = 2, k = 3

Output3

Distance d = |2-1| = 1. We need right - left = 1 and right + left = 3, so right = 2. Answer = C(3, 2) = 3.

startPos

endPos

def number_of_ways(startPos, endPos, k):
    MOD = 10**9 + 7
    d = abs(endPos - startPos)
    # need d <= k and (k - d) even; then choose 'right' = (k + d)//2 moves
    if d > k or (k - d) % 2 == 1:
        return 0
    r = (k + d) // 2
    # C(k, r) by Pascal's row
    dp = [0] * (k + 1)
    dp[0] = 1
    for i in range(1, k + 1):
        for j in range(i, 0, -1):
            dp[j] = (dp[j] + dp[j - 1]) % MOD
    return dp[r]

function numberOfWays(startPos, endPos, k) {
  const MOD = 1000000007n;
  const d = Math.abs(endPos - startPos);
  if (d > k || (k - d) % 2 === 1) return 0;
  const r = (k + d) / 2;
  const dp = new Array(k + 1).fill(0n);
  dp[0] = 1n;
  for (let i = 1; i <= k; i++) {
    for (let j = i; j >= 1; j--) {
      dp[j] = (dp[j] + dp[j - 1]) % MOD;
    }
  }
  return Number(dp[r]);
}

class Solution {
    public int numberOfWays(int startPos, int endPos, int k) {
        long MOD = 1_000_000_007L;
        int d = Math.abs(endPos - startPos);
        if (d > k || (k - d) % 2 == 1) return 0;
        int r = (k + d) / 2;
        long[] dp = new long[k + 1];
        dp[0] = 1;
        for (int i = 1; i <= k; i++) {
            for (int j = i; j >= 1; j--) {
                dp[j] = (dp[j] + dp[j - 1]) % MOD;
            }
        }
        return (int) dp[r];
    }
}

int numberOfWays(int startPos, int endPos, int k) {
    const long long MOD = 1000000007LL;
    int d = abs(endPos - startPos);
    if (d > k || (k - d) % 2 == 1) return 0;
    int r = (k + d) / 2;
    vector<long long> dp(k + 1, 0);
    dp[0] = 1;
    for (int i = 1; i <= k; i++) {
        for (int j = i; j >= 1; j--) {
            dp[j] = (dp[j] + dp[j - 1]) % MOD;
        }
    }
    return (int) dp[r];
}

Explanation

Every walk is a sequence of k moves, each either +1 (right) or -1 (left). Suppose it uses right right-moves and left left-moves. Two facts must hold: the moves total right + left = k, and the net displacement equals the gap, right - left = d where d = |endPos - startPos|.

Solving those two equations gives right = (k + d) / 2. If d > k we can never travel far enough, and if k - d is odd the equations have no integer solution (parity mismatch) — both cases give 0.

Otherwise every arrangement of those right right-moves among the k positions is a valid, distinct walk. The count of such arrangements is exactly the binomial coefficient C(k, right).

We compute C(k, right) with Pascal's triangle: a 1-D array dp where after i rounds dp[j] = C(i, j). Iterating j downward lets us update in place without overwriting values we still need, and every addition stays under the modulus.

Example: start = 1, end = 2, k = 3. Here d = 1, right = (3 + 1)/2 = 2, so the answer is C(3, 2) = 3.

Time: O(k²) Space: O(k)