888. Exactly K Steps Away
A rail inspection cart sits at integer position start on an endless straight track. In every step it must move exactly one unit left or exactly one unit right; it may not stay still, and it may revisit positions and cross the origin freely.
Return how many different sequences of exactly k steps leave the cart at position end. Two sequences differ if some step goes in a different direction. Because the count can be huge, return it modulo 1_000_000_007 (10^9 + 7). With k = 0 the cart does not move, so the answer is 1 when start == end and 0 otherwise.
Example 1
- Input:
- start = 2, end = 4, k = 4
- Output:
- 4
- Explanation:
The robot must gain net +2 in 4 moves, so exactly three moves go right and one left; there are 4 positions for the left move.
Example 2
- Input:
- start = 1, end = 2, k = 4
- Output:
- 0
- Explanation:
Net displacement is 1 but 4 moves of size 1 always have even parity, so ending one cell away is impossible.
Example 3
- Input:
- start = 3, end = -1, k = 6
- Output:
- 6
- Explanation:
Net -4 in 6 moves means one move right and five left; the right move can be any of 6 positions, so 6 ways.
Constraints
- -105 ≤ start, end ≤ 105
- 0 ≤ k ≤ 105
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 800 msC++ 200 msJava 400 msJavaScript 400 msTypeScript 400 ms
Expected complexity
- Time
- O(k log MOD)
- Space
- O(k)