Link to Question

MEDIUM

Number of Ways to Reach a Position After Exactly k Steps

You are given two positive integers startPos and endPos and a non-negative integer k. In one step, you can either go left or right. That is, if you are at position x, you can go to x - 1 or x + 1.

Given the three integers startPos, endPos, and 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 10^9 + 7.

Example

Input:

startPos = 1, endPos = 2, k = 3

Output:

3

Explanation:
We can reach position 2 from position 1 in exactly 3 steps in the following ways:

• 1 → 2 → 1 → 2
• 1 → 2 → 3 → 2
• 1 → 0 → 1 → 2

---

Constraints

• 1 ≤ startPos, endPos, k ≤ 1000

---

Solution 1: Mathematical Approach

• Time Complexity: O(k), where k is the number of steps.
• Space Complexity: O(1), using constant extra space.

The key insight is that we need to make right moves and left moves such that:

• right - left = diff (where diff = abs(endPos - startPos))
• right + left = k

This gives us right = (k + diff) / 2 and left = (k - diff) / 2. The answer is the binomial coefficient C(k, right) if both right and left are non-negative integers.

C++

class Solution {
public:
    int numberOfWays(int startPos, int endPos, int k) {
        const int MOD = 1e9 + 7;
        int diff = abs(endPos - startPos);

        // Check if it's possible
        if (diff > k || (k - diff) % 2 != 0) {
            return 0;
        }

        int right = (k + diff) / 2;
        return combination(k, right, MOD);
    }

private:
    int combination(int n, int k, int mod) {
        if (k > n - k) k = n - k;

        long long res = 1;
        for (int i = 0; i < k; i++) {
            res = (res * (n - i)) % mod;
            res = (res * modInverse(i + 1, mod)) % mod;
        }
        return (int)res;
    }

    int modInverse(int a, int mod) {
        int m = mod;
        int y = 0, x = 1;

        while (a > 1) {
            int q = a / mod;
            int t = mod;
            mod = a % mod;
            a = t;
            t = y;
            y = x - q * y;
            x = t;
        }

        if (x < 0) x += m;
        return x;
    }
};

Solution 2: Dynamic Programming

• Time Complexity: O(k × MAX_POS), where MAX_POS is the range of positions.
• Space Complexity: O(k × MAX_POS), due to the DP table.

C++

class Solution {
public:
    int numberOfWays(int startPos, int endPos, int k) {
        const int MOD = 1e9 + 7;
        const int MAX_POS = 2000; // To handle negative positions

        // dp[i][j] = ways to reach position j after i steps
        vector<vector<int>> dp(k + 1, vector<int>(MAX_POS, 0));

        // Base case: start position
        dp[0][startPos + 1000] = 1;

        // Fill DP table
        for (int step = 1; step <= k; step++) {
            for (int pos = 0; pos < MAX_POS; pos++) {
                if (pos > 0) {
                    dp[step][pos] = (dp[step][pos] + dp[step - 1][pos - 1]) % MOD;
                }
                if (pos < MAX_POS - 1) {
                    dp[step][pos] = (dp[step][pos] + dp[step - 1][pos + 1]) % MOD;
                }
            }
        }

        return dp[k][endPos + 1000];
    }
};