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 ofdifferent ways to reach the position _endPos starting fromstartPos _, such that you performexactly _k steps. Since the answer may be very large, return it modulo 10^9 + 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.

Examples

Example 1

1
2
3
4
5
6
7

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

1
2
3

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

Solution

Method 1 – Combinatorics (Binomial Coefficient)

Intuition

Each step can be left or right. To reach endPos from startPos in k steps, the difference d = abs(endPos - startPos) must have the same parity as k and d <= k. The number of ways is C(k, (k+d)//2), where (k+d)//2 is the number of right moves.

Approach

  1. Compute d = abs(endPos - startPos).
  2. If d > k or (k-d) is odd, return 0.
  3. The answer is C(k, (k+d)//2) modulo 1e9+7.
  4. Precompute factorials up to k for efficiency.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int numberOfWays(int startPos, int endPos, int k) {
        const int mod = 1e9+7;
        int d = abs(endPos - startPos);
        if (d > k || (k-d)%2) return 0;
        int r = (k+d)/2;
        vector<long long> fact(k+1, 1), inv(k+1, 1);
        for (int i = 1; i <= k; ++i) fact[i] = fact[i-1]*i%mod;
        inv[k] = 1;
        for (int i = k-1; i >= 0; --i) inv[i] = inv[i+1]*(i+1)%mod;
        return fact[k]*inv[r]%mod*inv[k-r]%mod;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func numberOfWays(startPos, endPos, k int) int {
    mod := int(1e9+7)
    d := startPos - endPos
    if d < 0 { d = -d }
    if d > k || (k-d)%2 != 0 { return 0 }
    r := (k+d)/2
    fact := make([]int64, k+1)
    inv := make([]int64, k+1)
    fact[0] = 1
    for i := 1; i <= k; i++ { fact[i] = fact[i-1]*int64(i)%int64(mod) }
    inv[k] = 1
    for i := k-1; i >= 0; i-- { inv[i] = inv[i+1]*int64(i+1)%int64(mod) }
    return int(fact[k]*inv[r]%int64(mod)*inv[k-r]%int64(mod))
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int numberOfWays(int startPos, int endPos, int k) {
        int mod = 1_000_000_007;
        int d = Math.abs(endPos - startPos);
        if (d > k || (k-d)%2 != 0) return 0;
        int r = (k+d)/2;
        long[] fact = new long[k+1], inv = new long[k+1];
        fact[0] = 1;
        for (int i = 1; i <= k; i++) fact[i] = fact[i-1]*i%mod;
        inv[k] = 1;
        for (int i = k-1; i >= 0; i--) inv[i] = inv[i+1]*(i+1)%mod;
        return (int)(fact[k]*inv[r]%mod*inv[k-r]%mod);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun numberOfWays(startPos: Int, endPos: Int, k: Int): Int {
        val mod = 1_000_000_007
        val d = kotlin.math.abs(endPos - startPos)
        if (d > k || (k-d)%2 != 0) return 0
        val r = (k+d)/2
        val fact = LongArray(k+1) { 1L }
        val inv = LongArray(k+1) { 1L }
        for (i in 1..k) fact[i] = fact[i-1]*i%mod
        inv[k] = 1L
        for (i in k-1 downTo 0) inv[i] = inv[i+1]*(i+1)%mod
        return (fact[k]*inv[r]%mod*inv[k-r]%mod).toInt()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:
        mod = 10**9+7
        d = abs(endPos - startPos)
        if d > k or (k-d)%2:
            return 0
        r = (k+d)//2
        fact = [1]*(k+1)
        for i in range(1, k+1):
            fact[i] = fact[i-1]*i%mod
        inv = [1]*(k+1)
        inv[k] = pow(fact[k], mod-2, mod)
        for i in range(k-1, -1, -1):
            inv[i] = inv[i+1]*(i+1)%mod
        return fact[k]*inv[r]%mod*inv[k-r]%mod
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

impl Solution {
    pub fn number_of_ways(start_pos: i32, end_pos: i32, k: i32) -> i32 {
        let d = (end_pos - start_pos).abs();
        let k = k as usize;
        let d = d as usize;
        let modulo = 1_000_000_007;
        if d > k || (k-d)%2 != 0 { return 0; }
        let r = (k+d)/2;
        let mut fact = vec![1i64; k+1];
        for i in 1..=k { fact[i] = fact[i-1]*i as i64%modulo; }
        let mut inv = vec![1i64; k+1];
        inv[k] = pow(fact[k], modulo-2, modulo);
        for i in (0..k).rev() { inv[i] = inv[i+1]*(i as i64+1)%modulo; }
        (fact[k]*inv[r]%modulo*inv[k-r]%modulo) as i32
    }
}
fn pow(mut a: i64, mut b: i64, m: i64) -> i64 {
    let mut res = 1i64;
    while b > 0 {
        if b&1 == 1 { res = res*a%m; }
        a = a*a%m; b >>= 1;
    }
    res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    numberOfWays(startPos: number, endPos: number, k: number): number {
        const mod = 1_000_000_007
        const d = Math.abs(endPos - startPos)
        if (d > k || (k-d)%2 !== 0) return 0
        const r = (k+d)/2
        const fact = new Array(k+1).fill(1)
        for (let i = 1; i <= k; i++) fact[i] = fact[i-1]*i%mod
        const inv = new Array(k+1).fill(1)
        inv[k] = pow(fact[k], mod-2, mod)
        for (let i = k-1; i >= 0; i--) inv[i] = inv[i+1]*(i+1)%mod
        return fact[k]*inv[r]%mod*inv[k-r]%mod
    }
}
function pow(a: number, b: number, m: number): number {
    let res = 1
    while (b > 0) {
        if (b&1) res = res*a%m
        a = a*a%m; b >>= 1
    }
    return res
}

Complexity

  • ⏰ Time complexity: O(k), for factorial and inverse computation.
  • 🧺 Space complexity: O(k), for factorial and inverse arrays.