Problem Description

You are standing on an infinite number line at position startPos. Your goal is to reach position endPos by taking exactly k steps. In each step, you can move either one position to the left or one position to the right.

Given:

• startPos: your starting position (positive integer)
• endPos: your target position (positive integer)
• k: the exact number of steps you must take (positive integer)

You need to find the total number of different ways to reach endPos from startPos using exactly k steps. Two ways are considered different if the sequence of moves (left or right) is different, even if they visit the same positions.

For example, if you need to move from position 1 to position 3 in 3 steps:

• You could go: right → right → right (positions: 1 → 2 → 3 → 4, then you're at 4, not 3)
• You could go: right → right → left (positions: 1 → 2 → 3 → 2, then you're at 2, not 3)
• You could go: left → right → right (positions: 1 → 0 → 1 → 2, then you're at 2, not 3)
• Actually, to reach position 3 from position 1 in exactly 3 steps, you need combinations like: right → right → right (but this gives position 4), so you'd need moves that total to a net movement of +2 positions.

The number line extends infinitely in both directions and includes negative positions. Since the answer can be very large, return it modulo 10^9 + 7.

Intuition

The key insight is to think about the problem in terms of distance from the target rather than absolute positions. If we need to move from startPos to endPos, what really matters is the distance between them: abs(startPos - endPos).

Let's say we're currently at distance i from the target and have j steps remaining. At each step, we can either:

1. Move toward the target (reducing distance by 1)
2. Move away from the target (increasing distance by 1)

But here's the clever part: when we're at distance i and move toward the target, we end up at distance i - 1. However, if i = 0 (we're at the target) and we move "toward" it, we actually move past it and end up at distance 1. This is why we use abs(i - 1) in the solution.

The problem becomes a counting problem: in how many ways can we make moves such that after exactly k steps, we're at distance 0 from the target?

This naturally leads to a recursive approach:

• Base case: If we have 0 steps left (j = 0), we can only succeed if we're already at the target (i = 0)
• Invalid case: If the distance to target i is greater than remaining steps j, it's impossible to reach the target
• Recursive case: Count the ways by considering both possible moves (toward or away from target)

The recursion has overlapping subproblems - we might reach the same state (distance i, steps remaining j) through different paths. This makes memoization effective, as we can cache and reuse previously computed results for each (i, j) pair.

The mathematical elegance is that by thinking in terms of distance rather than position, we transform a problem on an infinite line into a bounded problem where the states are limited by the number of steps k.

Learn more about Math, Dynamic Programming and Combinatorics patterns.

Solution Approach

The solution uses memoization with recursive depth-first search (DFS) to count the number of ways to reach the target position.

Implementation Details

We define a recursive function dfs(i, j) where:

• i represents the current distance from the target position
• j represents the number of steps remaining

The initial call is dfs(abs(startPos - endPos), k), starting with the initial distance between start and end positions and k steps available.

Base Cases and Recursive Logic

1. Impossible cases (i > j or j < 0):

   • If the distance to target exceeds remaining steps, it's impossible to reach the target
   • Return 0

2. No steps remaining (j = 0):

   • We can only succeed if we're already at the target (i = 0)
   • Return 1 if i == 0, otherwise return 0

3. Recursive case (we have steps remaining):

   • Move away from target: Go from distance i to distance i + 1, using one step
     • Number of ways: dfs(i + 1, j - 1)
   • Move toward target: Go from distance i to distance abs(i - 1), using one step
     • Number of ways: dfs(abs(i - 1), j - 1)
     • We use abs(i - 1) because when at the target (i = 0), moving "toward" it actually takes us to distance 1

The total number of ways is the sum of both possibilities, taken modulo 10^9 + 7.

Optimization with Memoization

The @cache decorator automatically memoizes the function results. This prevents recalculating the same (i, j) state multiple times, significantly improving efficiency from exponential to polynomial time complexity.

Why This Works

The algorithm works because:

• Every sequence of k moves can be uniquely described by how we handle the distance at each step
• The problem has optimal substructure: the solution for (i, j) depends only on the solutions for (i + 1, j - 1) and (abs(i - 1), j - 1)
• The state space is bounded: i ranges from 0 to at most k, and j ranges from 0 to k

The time complexity is O(k^2) as we have at most k × k unique states, and the space complexity is also O(k^2) for the memoization cache.

Example Walkthrough

Let's walk through a concrete example: finding the number of ways to move from startPos = 2 to endPos = 5 in exactly k = 3 steps.

Initial Setup:

• Distance to target: abs(2 - 5) = 3
• We start with dfs(3, 3) - we're 3 units away with 3 steps remaining

Step-by-step recursion:

Starting from dfs(3, 3):

• We have 3 steps to cover distance 3
• Two choices:
  1. Move away: dfs(4, 2) - now 4 units away with 2 steps left
  2. Move toward: dfs(2, 2) - now 2 units away with 2 steps left

Let's trace dfs(2, 2):

• We have 2 steps to cover distance 2
• Two choices:
  1. Move away: dfs(3, 1) - now 3 units away with 1 step left
  2. Move toward: dfs(1, 1) - now 1 unit away with 1 step left

Following dfs(1, 1):

• We have 1 step to cover distance 1
• Two choices:
  1. Move away: dfs(2, 0) - 2 units away with 0 steps → returns 0 (not at target)
  2. Move toward: dfs(0, 0) - 0 units away with 0 steps → returns 1 (success!)

Now let's check dfs(3, 1):

• Distance 3 > remaining steps 1
• This is impossible, returns 0

Going back to trace dfs(4, 2):

• Distance 4 > remaining steps 2
• This is impossible, returns 0

Building up the answer:

• dfs(0, 0) = 1 (at target with no steps left)
• dfs(1, 1) = dfs(2, 0) + dfs(0, 0) = 0 + 1 = 1
• dfs(3, 1) = 0 (impossible: distance > steps)
• dfs(2, 2) = dfs(3, 1) + dfs(1, 1) = 0 + 1 = 1
• dfs(4, 2) = 0 (impossible: distance > steps)
• dfs(3, 3) = dfs(4, 2) + dfs(2, 2) = 0 + 1 = 1

Result: There is exactly 1 way to reach position 5 from position 2 in 3 steps.

This corresponds to the move sequence: Left → Right → Right → Right (visiting positions 2 → 1 → 2 → 3 → 4 → 5). Note that we must move away first (going left to position 1) before moving toward the target, because starting 3 units away with only 3 steps means we need every step to count toward reaching the target after the initial repositioning.

Solution Implementation

Time and Space Complexity

The time complexity is O(k^2), and the space complexity is O(k^2).

The function uses memoization with @cache decorator on the recursive dfs function. The dfs function takes two parameters: i (representing the absolute distance from target) and j (representing remaining steps).

For time complexity:

• The parameter i can range from 0 to at most k (since we can't move more than k distance in k steps)
• The parameter j ranges from 0 to k (the number of steps)
• Each unique state (i, j) is computed only once due to memoization
• Therefore, there are at most O(k) * O(k) = O(k^2) unique states to compute

For space complexity:

• The memoization cache stores all computed states, which is O(k^2) entries
• The recursion depth is at most k (as j decreases by 1 in each recursive call until it reaches 0)
• The recursion stack space O(k) is dominated by the cache space O(k^2)
• Therefore, the total space complexity is O(k^2)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Understanding of the Problem Transformation

Pitfall: Many developers initially try to track the actual position on the number line, leading to a much larger state space and incorrect solutions. They might write something like:

@cache
def dfs(current_pos, remaining_steps):
    if remaining_steps == 0:
        return 1 if current_pos == endPos else 0
    # Try moving left and right from current position
    return dfs(current_pos - 1, remaining_steps - 1) + dfs(current_pos + 1, remaining_steps - 1)

Why it's wrong: This approach has an unbounded state space since positions can range from negative to positive infinity, making memoization ineffective and causing potential memory issues.

Solution: Transform the problem to track the distance from the target rather than absolute position. Since only the distance matters for counting paths, this reduces the state space significantly:

# Correct: Track distance from target
initial_distance = abs(startPos - endPos)
return count_ways(initial_distance, k)

2. Forgetting the Modulo Operation

Pitfall: Applying modulo only at the final return, not during intermediate calculations:

# Wrong: Only applying modulo at the end
ways_moving_away = count_ways(current_distance + 1, remaining_steps - 1)
ways_moving_toward = count_ways(abs(current_distance - 1), remaining_steps - 1)
return ways_moving_away + ways_moving_toward  # Missing modulo!

Why it's wrong: For large values of k, intermediate results can exceed integer limits before the final modulo operation, causing overflow.

Solution: Apply modulo at each addition to keep numbers manageable:

# Correct: Apply modulo during calculation
return (ways_moving_away + ways_moving_toward) % MOD

3. Mathematical Parity Check Optimization Gone Wrong

Pitfall: Some might try to optimize by checking if reaching the target is mathematically possible based on parity:

# Attempting to optimize with parity check
distance = abs(startPos - endPos)
if (distance + k) % 2 != 0:
    return 0  # Can't reach if parity doesn't match

Why it's problematic: While the parity check is mathematically correct (you need the same parity for distance and k to reach the target), adding this check without adjusting the base cases in the recursive function can lead to inconsistencies or missed edge cases.

Solution: Either implement the parity check comprehensively with all edge cases, or rely on the recursive solution to naturally handle impossible cases:

# The recursive solution naturally handles this through its base cases
if current_distance > remaining_steps:
    return 0  # Impossible to reach

4. Incorrect Handling of the abs(i - 1) Case

Pitfall: Not understanding why we use abs(current_distance - 1) when moving toward the target:

# Wrong: Simply using current_distance - 1
ways_moving_toward = count_ways(current_distance - 1, remaining_steps - 1)

Why it's wrong: When at distance 0 (at the target), moving "toward" the target actually moves us away to distance 1. Without the absolute value, we'd get negative distance which is incorrect.

Solution: Always use absolute value to handle the case when we're at or near the target:

# Correct: Using abs to handle all cases
ways_moving_toward = count_ways(abs(current_distance - 1), remaining_steps - 1)