#2400

Number of Ways to Reach a Position After Exactly k Steps

expert · 1050 · lc medium +32 · verified · 36.8% accepted · 840 likes · top 15%

Description

You stand at integer position startPos on an infinite number line and want to reach position endPos by taking exactly k steps. Each step moves you one unit to the left or right.

Count and return the number of distinct ways to accomplish this. Since the answer may be large, return it modulo 10⁹ + 7.

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.

Code

1

2

3

class Solution:
    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:

class Solution:
    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int: