# Number of Ways to Reach a Position After Exactly k Steps
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-ways-to-reach-a-position-after-exactly-k-steps)
Canonical: https://scaleengineer.com/dsa/problems/number-of-ways-to-reach-a-position-after-exactly-k-steps
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Combinatorics](https://scaleengineer.com/dsa/patterns/combinatorics)
---
## Problem
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 <= 1000`

# Approaches
## Top-Down Dynamic Programming with Memoization
A recursive approach can be formulated by considering the choices at each step. From any position, we can move left or right. This leads to a recursive function `solve(currentPos, stepsLeft)`. However, this simple recursion involves many redundant calculations for the same state `(currentPos, stepsLeft)`. We can optimize this using memoization, a technique where we store the results of expensive function calls and return the cached result when the same inputs occur again. This is a top-down dynamic programming approach.
**Time:** O(k * D) or O(k^2). Each state `(stepsLeft, currentPos)` is computed only once. The number of steps ranges from 0 to `k`. The range of positions `D` we can reach is `startPos +/- k`, which is `O(k)`. Therefore, the total time complexity is `O(k * k) = O(k^2)`. · **Space:** O(k * D) or O(k^2). The space is dominated by the memoization table, which stores results for each `(stepsLeft, currentPos)` state. The number of steps is `k`, and the range of positions `D` is `O(k)`. An additional `O(k)` is used for the recursion stack.
**Pros:** Conceptually similar to the brute-force recursion, making it relatively easy to understand and implement.; Avoids recomputing results for the same subproblems, drastically improving efficiency over simple recursion.
**Cons:** Can lead to a `StackOverflowError` for very large `k` due to deep recursion, although `k <= 1000` is generally safe.; The space complexity of `O(k^2)` might be large for bigger constraints.
### Explanation
We define a function `solve(currentPos, stepsLeft)` that computes the number of ways to reach `endPos` from `currentPos` in `stepsLeft` moves.

- **Base Cases:**
    - If `stepsLeft` is 0, we have found a path if and only if `currentPos == endPos`. So we return 1, otherwise 0.
    - A crucial optimization (pruning): If the remaining distance `abs(endPos - currentPos)` is greater than `stepsLeft`, it's impossible to reach the target. We can return 0 immediately.
- **Recursive Step:** The number of ways to reach the target from `(currentPos, stepsLeft)` is the sum of ways from the two possible next states: `(currentPos - 1, stepsLeft - 1)` and `(currentPos + 1, stepsLeft - 1)`.
- **Memoization:** We use a 2D array, `memo[stepsLeft][currentPos + offset]`, to store the results. The `offset` is used to map potentially negative positions to non-negative array indices. Before computing, we check if the result for the current state is already in our memoization table. If so, we return it. Otherwise, we compute it, store it, and then return it.

The initial call is `solve(startPos, k)`.

```java
class Solution {
    private int MOD = 1_000_000_007;
    private Integer[][] memo;
    private int offset = 1000; // Offset to handle negative positions

    public int numberOfWays(int startPos, int endPos, int k) {
        // With offset, max index is startPos + k + offset <= 1000 + 1000 + 1000 = 3000
        memo = new Integer[k + 1][3002]; 
        return solve(startPos, endPos, k);
    }

    private int solve(int currentPos, int endPos, int stepsLeft) {
        if (Math.abs(endPos - currentPos) > stepsLeft) {
            return 0;
        }
        if (stepsLeft == 0) {
            return currentPos == endPos ? 1 : 0;
        }

        if (memo[stepsLeft][currentPos + offset] != null) {
            return memo[stepsLeft][currentPos + offset];
        }

        long ways = (long)solve(currentPos - 1, endPos, stepsLeft - 1) + 
                    solve(currentPos + 1, endPos, stepsLeft - 1);

        return memo[stepsLeft][currentPos + offset] = (int)(ways % MOD);
    }
}
```
### Algorithm
- Create a memoization table `memo` (e.g., a 2D array or a map of maps) initialized with a value indicating 'not computed'.
- Define a recursive function `solve(currentPos, stepsLeft)`:
    - **Pruning:** If `abs(endPos - currentPos) > stepsLeft`, it's impossible to reach the target, so return 0.
    - **Base Case:** If `stepsLeft == 0`, return 1 if `currentPos == endPos`, otherwise return 0.
    - Check if `memo[stepsLeft][currentPos + offset]` has been computed. If yes, return the stored value.
    - **Recursive Step:** Calculate `ways = solve(currentPos - 1, stepsLeft - 1) + solve(currentPos + 1, stepsLeft - 1)`.
    - Store `ways % MOD` in the memoization table and return it.
- The initial call is `solve(startPos, k)`.

## Bottom-Up Dynamic Programming
This approach is an iterative version of the memoized recursion. Instead of starting from the top (the original problem) and breaking it down, we start from the bottom (base cases) and build our way up to the solution. This avoids recursion overhead and is sometimes more efficient in practice.
**Time:** O(k * D) or O(k^2). We have a loop that runs `k` times, and inside it, another loop that runs `D` times, where `D` is the range of possible positions. Since `D` is `O(k)`, the total time complexity is `O(k^2)`. · **Space:** O(D) or O(k). With space optimization, we only need two arrays of size `D` (the range of positions), where `D` is `O(k)`. Without optimization, it would be `O(k * D)` or `O(k^2)`.
**Pros:** Avoids recursion, eliminating the risk of stack overflow and potentially offering better performance due to no function call overhead.; The space can be easily optimized to `O(k)`.
**Cons:** Can be slightly less intuitive to formulate than the top-down approach for some problems.; The time complexity remains `O(k^2)`, which is not the most optimal for this specific problem.
### Explanation
We use a DP table, `dp[i][j]`, to store the number of ways to reach position `j` in exactly `i` steps.

- **State:** `dp[i][j]` = number of ways to be at position `j` after `i` steps.
- **Initialization:** At step 0, we are at `startPos`. So, `dp[0][startPos + offset] = 1`, and all other `dp[0][...]` are 0. An offset is used to handle array indices.
- **Transition:** To reach position `j` in `i` steps, we must have come from `j-1` or `j+1` at step `i-1`. The transition is: `dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % MOD`.
- We iterate from `i = 1` to `k`, filling the `dp` table row by row.
- **Space Optimization:** Notice that `dp[i]` only depends on `dp[i-1]`. We can optimize space by using only two 1D arrays: one for the previous state (`i-1`) and one for the current state (`i`). After computing the current state, it becomes the previous state for the next iteration. This reduces space from `O(k^2)` to `O(k)`.
- The final answer is `dp[k][endPos + offset]`.

```java
class Solution {
    public int numberOfWays(int startPos, int endPos, int k) {
        int MOD = 1_000_000_007;
        
        if (Math.abs(startPos - endPos) > k || (k - Math.abs(startPos - endPos)) % 2 != 0) {
            return 0;
        }

        int offset = 1001;
        int maxRange = 3002;
        int[] dp = new int[maxRange];
        
        dp[startPos + offset] = 1;

        for (int i = 1; i <= k; i++) {
            int[] nextDp = new int[maxRange];
            // Iterate over a safe range of indices
            for (int j = 1; j < maxRange - 1; j++) {
                nextDp[j] = (dp[j - 1] + dp[j + 1]) % MOD;
            }
            dp = nextDp;
        }

        return dp[endPos + offset];
    }
}
```
### Algorithm
- Create a 1D array `dp` of size `max_range` to store the ways for the current number of steps. An `offset` is used to map positions to array indices.
- Initialize `dp[startPos + offset] = 1`.
- Loop for `i` from 1 to `k` (representing the number of steps):
    - Create a new array `next_dp` of the same size.
    - Loop through all possible positions `j` that can be reached.
    - Calculate `next_dp[j + offset] = (dp[j-1 + offset] + dp[j+1 + offset]) % MOD`.
    - After the inner loop, replace `dp` with `next_dp` for the next iteration.
- The final result is `dp[endPos + offset]`.

## Combinatorial Approach
This problem can be solved directly using a mathematical formula. The problem is equivalent to finding the number of paths of a specific length on a 1D lattice. This can be framed as a combinatorial problem of arranging a certain number of left and right steps.
**Time:** O(k + log MOD). `O(k)` is for pre-computing factorials and their inverses. The `power` function for modular inverse takes `O(log MOD)`. After pre-computation, calculating the combination is `O(1)`. · **Space:** O(k) to store the pre-computed factorials and inverse factorials.
**Pros:** Extremely efficient, with a time complexity that is near-linear in `k`.; Provides a direct, closed-form solution without iteration over states.
**Cons:** Requires understanding of combinatorics and modular arithmetic, including modular inverse, which can be more complex than dynamic programming.
### Explanation
Let `R` be the number of steps to the right and `L` be the number of steps to the left.

We have two constraints:
1.  Total steps: `R + L = k`
2.  Final position: `startPos + R - L = endPos`, which simplifies to `R - L = endPos - startPos`.

Solving this system of linear equations for `R` and `L` gives:
- `R = (k + endPos - startPos) / 2`
- `L = (k - (endPos - startPos)) / 2`

For a valid solution to exist, `R` and `L` must be non-negative integers. This leads to two conditions:
1.  `k >= abs(endPos - startPos)`: The number of steps must be at least the distance to the target.
2.  `(k - (endPos - startPos))` must be an even number: The parity of the steps must match the parity of the distance.

If these conditions are not met, the answer is 0. Otherwise, the problem is to find the number of ways to arrange `R` right steps and `L` left steps in a sequence of `k` total steps. This is a classic combination problem, and the answer is given by the binomial coefficient "k choose R", or `C(k, R)`.

`C(k, R) = k! / (R! * (k-R)!)`

Since we need the answer modulo `10^9 + 7` (a prime number), we can compute this using pre-computed factorials and modular inverses. The modular inverse of `a` can be found using Fermat's Little Theorem: `a^(p-2) ≡ a^(-1) (mod p)`.

```java
class Solution {
    private int MOD = 1_000_000_007;
    private long[] fact;
    private long[] invFact;

    public int numberOfWays(int startPos, int endPos, int k) {
        int diff = endPos - startPos;

        if (Math.abs(diff) > k || (k - diff) % 2 != 0) {
            return 0;
        }

        precomputeFactorials(k);

        int rightSteps = (k + diff) / 2;
        
        return combinations(k, rightSteps);
    }
    
    private void precomputeFactorials(int n) {
        fact = new long[n + 1];
        invFact = new long[n + 1];
        fact[0] = 1;
        invFact[0] = 1;
        for (int i = 1; i <= n; i++) {
            fact[i] = (fact[i - 1] * i) % MOD;
        }
        invFact[n] = power(fact[n], MOD - 2);
        for (int i = n - 1; i >= 1; i--) {
            invFact[i] = (invFact[i + 1] * (i + 1)) % MOD;
        }
    }

    private int combinations(int n, int k) {
        if (k < 0 || k > n) {
            return 0;
        }
        long numerator = fact[n];
        long denominator = (invFact[k] * invFact[n - k]) % MOD;
        return (int) ((numerator * denominator) % MOD);
    }

    private long power(long base, int exp) {
        long res = 1;
        base %= MOD;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % MOD;
            base = (base * base) % MOD;
            exp /= 2;
        }
        return res;
    }
}
```
### Algorithm
- Calculate the displacement `diff = endPos - startPos`.
- Check for impossible cases: if `abs(diff) > k` or `(k - diff) % 2 != 0`, return 0.
- If possible, calculate the required number of right steps: `R = (k + diff) / 2`.
- The problem is now to choose `R` positions for right steps out of `k` total steps, which is the binomial coefficient `C(k, R)`.
- Pre-compute factorials and their modular inverses up to `k` to calculate `C(k, R)` efficiently.
- Calculate `C(k, R) = (fact[k] * invFact[R] * invFact[k-R]) % MOD`.
- Return the result.

# Solutions
### Java

```java
class Solution {
private
  Integer[][] f;
private
  final int mod = (int)1 e9 + 7;
public
  int numberOfWays(int startPos, int endPos, int k) {
    f = new Integer[k + 1][k + 1];
    return dfs(Math.abs(startPos - endPos), k);
  }
private
  int dfs(int i, int j) {
    if (i > j || j < 0) {
      return 0;
    }
    if (j == 0) {
      return i == 0 ? 1 : 0;
    }
    if (f[i][j] != null) {
      return f[i][j];
    }
    int ans = dfs(i + 1, j - 1) + dfs(Math.abs(i - 1), j - 1);
    ans %= mod;
    return f[i][j] = ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numberOfWays(int startPos, int endPos, int k) {
    const int mod = 1e9 + 7;
    int f[k + 1][k + 1];
    memset(f, -1, sizeof(f));
    function<int(int, int)> dfs = [&](int i, int j) -> int {
      if (i > j || j < 0) {
        return 0;
      }
      if (j == 0) {
        return i == 0 ? 1 : 0;
      }
      if (f[i][j] != -1) {
        return f[i][j];
      }
      f[i][j] = (dfs(i + 1, j - 1) + dfs(abs(i - 1), j - 1)) % mod;
      return f[i][j];
    };
    return dfs(abs(startPos - endPos), k);
  }
};

```

### Python

```python
class Solution:
    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int: @ cache def dfs(i: int, j: int) -> int: if i > j or j < 0: return 0 if j == 0: return 1 if i == 0 else 0 return (dfs(i + 1, j - 1) + dfs(abs(i - 1), j - 1)) % mod mod = 10 ** 9 + 7 return dfs(abs(startPos - endPos), k)

```