Skip to content

2400. Number of Ways to Reach a Position After Exactly k Steps 👍

  • Time: $O(nk)$
  • Space: $O(k)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
 public:
  int numberOfWays(int startPos, int endPos, int k) {
    // leftStep + rightStep = k
    // rightStep - leftStep = endPos - startPos
    //        2 * rightStep = k + endPos - startPos
    //            rightStep = (k + endPos - startPos) / 2
    const int val = k + endPos - startPos;
    if (val < 0 || val % 2 == 1)
      return 0;
    const int rightStep = val / 2;
    const int leftStep = k - rightStep;
    if (leftStep < 0)
      return 0;
    return nCk(leftStep + rightStep, min(leftStep, rightStep));
  }

 private:
  static constexpr int kMod = 1'000'000'007;

  // C(n, k) = C(n - 1, k) + C(n - 1, k - 1)
  int nCk(int n, int k) {
    // dp[i] := C(n so far, i)
    vector<int> dp(k + 1);
    dp[0] = 1;

    while (n-- > 0)  // Calculate n times.
      for (int j = k; j > 0; --j) {
        dp[j] += dp[j - 1];
        dp[j] %= kMod;
      }

    return dp[k];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
  public int numberOfWays(int startPos, int endPos, int k) {
    // leftStep + rightStep = k
    // rightStep - leftStep = endPos - startPos
    //        2 * rightStep = k + endPos - startPos
    //            rightStep = (k + endPos - startPos) / 2
    final int val = k + endPos - startPos;
    if (val < 0 || val % 2 == 1)
      return 0;
    final int rightStep = val / 2;
    final int leftStep = k - rightStep;
    if (leftStep < 0)
      return 0;
    return nCk(leftStep + rightStep, Math.min(leftStep, rightStep));
  }

  // C(n, k) = C(n - 1, k) + C(n - 1, k - 1)
  private int nCk(int n, int k) {
    final int MOD = 1_000_000_007;
    // dp[i] := C(n so far, i)
    int[] dp = new int[k + 1];
    dp[0] = 1;

    while (n-- > 0) // Calculate n times.
      for (int j = k; j > 0; --j) {
        dp[j] += dp[j - 1];
        dp[j] %= MOD;
      }

    return dp[k];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
  def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:
    # leftStep + rightStep = k
    # rightStep - leftStep = endPos - startPos
    #        2 * rightStep = k + endPos - startPos
    #            rightStep = (k + endPos - startPos) // 2
    val = k + endPos - startPos
    if val < 0 or val % 2 == 1:
      return 0
    rightStep = val // 2
    leftStep = k - rightStep
    if leftStep < 0:
      return 0
    return self._nCk(leftStep + rightStep, min(leftStep, rightStep))

  # C(n, k) = C(n - 1, k) + C(n - 1, k - 1)
  def _nCk(self, n: int, k: int) -> int:
    MOD = 1_000_000_007
    # dp[i] := C(n so far, i)
    dp = [1] + [0] * k

    for _ in range(n):  # Calculate n times.
      for j in range(k, 0, -1):
        dp[j] += dp[j - 1]
        dp[j] %= MOD

    return dp[k]