Skip to main content
Talentd

Number of Ways to Reach a Position After Exactly k Steps - Solution & Explanation

MediumMathDynamic ProgrammingCombinatorics18 min readAsked at: Google
Practice this problem

Problem Statement

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 of different ways to reach the position endPos starting from startPos, such that you perform exactly k steps. Since the answer may be very large, return it modulo 109 + 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.

 

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.

 

Constraints:

  • 1 <= startPos, endPos, k <= 1000

Approach Overview

Problem Overview: You start at startPos on a number line and can move either left or right by 1 step. After exactly k moves, you must land on endPos. The task is to count how many different sequences of moves reach the target. The answer can be large, so return it modulo 1e9 + 7.

Approach 1: Combinatorics and Parity Check (Time: O(k), Space: O(1))

Each step is either +1 (right) or -1 (left). Let d = |endPos - startPos|. To reach the target in exactly k steps, the difference between right and left moves must equal d. If k < d or (k - d) is odd, reaching the target is impossible because extra moves must cancel in pairs. Otherwise, compute the number of ways to choose the right moves using combinations: C(k, (k + d) / 2). The problem reduces to a binomial coefficient calculation under modulo arithmetic. This approach relies on basic math reasoning and combinatorics and avoids exploring all paths explicitly.

Approach 2: Dynamic Programming (Time: O(k²), Space: O(k²))

Model the process as state transitions. Let dp[step][pos] represent the number of ways to reach a position after a given number of moves. From position x, the next step can go to x - 1 or x + 1. Start with dp[0][startPos] = 1 and iterate for k steps, updating counts for adjacent positions. Because positions can become negative or large, shift indices by an offset or track relative distance from startPos. After filling the table, return dp[k][endPos]. This approach directly simulates all reachable states and demonstrates the classic transition pattern used in dynamic programming.

Recommended for interviews: The combinatorics solution is what most interviewers expect once you notice the parity constraint and the relationship between left/right moves. It reduces the problem to a single binomial coefficient and runs in linear time for factorial or iterative combination computation. The dynamic programming approach is easier to derive during the interview and shows solid state‑transition thinking, but it is less efficient. Showing the DP first and then optimizing to the combinatorics formula demonstrates strong problem‑solving progression.

Approach 1: Combinatorics and Parity Check

This approach uses combinatorics to determine the number of ways to reach endPos from startPos in exactly k steps by considering the number of right (R) and left (L) moves required. To reach from startPos to endPos, you need to have a net movement of rightSteps - leftSteps = endPos - startPos. Furthermore, since rightSteps + leftSteps = k, solving these equations gives the number of right and left steps needed. The key observation is to check if (k - abs(endPos - startPos)) is even; otherwise it is impossible to reach endPos in exactly k steps. If it is possible, we compute the number of combinations for choosing positions of 'R' in the sequence of k steps using nCr formula, i.e., C(k, rightSteps).

The function calculates whether it is possible to reach endPos by checking if the distance and steps difference meet the parity requirement. If possible, it computes the binomial coefficient C(k, n) using a loop and Fermat's little theorem for modular inverse, returning the result modulo 10^9 + 7.

Code

PythonC

Python

C

Complexity

Time Complexity: O(k), where k is the number of steps.
Space Complexity: O(1), as only a fixed number of variables are used.

Try this approach in the editor →

Approach 2: Dynamic Programming

This approach utilizes dynamic programming to solve the problem. We define dp[i][j] as the number of ways to reach position i in j steps. The transition depends on moves to the left or right: dp[i][j] = dp[i-1][j-1] + dp[i+1][j-1]. Start from dp[startPos][0] = 1 and calculate until dp[endPos][k]. The results are all computed modulo 10^9 + 7.

The solution initializes the DP table with the starting position incremented by 1000 (to handle negative indices). For each step, it calculates possible ways to reach each position by considering movement from the neighboring positions. The final answer is the number of ways to reach the endPos, returned modulo 10^9 + 7.

Code

JavaC#

Java

C#

Complexity

Time Complexity: O(k * range), where range is the possible positions due to step limits.
Space Complexity: O(range), determined by the size of the DP table.

Try this approach in the editor →

Approach 3: Memorization Search

We design a function dfs(i, j), which represents the number of ways to reach the target position when the current position is i distance from the target position and there are j steps left. The answer is dfs(abs(startPos - endPos), k).

The calculation method of the function dfs(i, j) is as follows:

  • If i \gt j or j \lt 0, it means that the current distance from the target position is greater than the remaining steps, or the remaining steps are negative. In this case, it is impossible to reach the target position, so return 0;
  • If j = 0, it means that there are no steps left. At this time, only when the current distance from the target position is 0 can the target position be reached, otherwise it is impossible to reach the target position. Return 1 or 0;
  • Otherwise, the current distance from the target position is i, and there are j steps left. There are two ways to reach the target position:
    • Move one step to the left, the current distance from the target position is i + 1, and there are j - 1 steps left. The number of methods is dfs(i + 1, j - 1);
    • Move one step to the right, the current distance from the target position is abs(i - 1), and there are j - 1 steps left. The number of methods is dfs(abs(i - 1), j - 1);
  • Finally, return the result of the sum of the two methods modulo 10^9 + 7.

To avoid repeated calculations, we use memorization search, that is, we use a two-dimensional array f to record the result of the function dfs(i, j). When the function dfs(i, j) is called, if f[i][j] is not -1, return f[i][j] directly, otherwise calculate the value of f[i][j], and return f[i][j].

The time complexity is O(k^2), and the space complexity is O(k^2). Here, k is the number of steps given in the problem.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Combinatorics and Parity Check

Time Complexity: O(k), where k is the number of steps.
Space Complexity: O(1), as only a fixed number of variables are used.

Dynamic Programming

Time Complexity: O(k * range), where range is the possible positions due to step limits.
Space Complexity: O(range), determined by the size of the DP table.

Memorization Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Combinatorics + Parity CheckO(k)O(1)Best for interviews and production; converts the problem into a binomial coefficient calculation.
Dynamic ProgrammingO(k²)O(k²)Useful when deriving the solution step‑by‑step or when practicing DP state transitions.

Video Solution

2400. Number of Ways to Reach a Position After Exactly k Steps | Leetcode Weekly 309| LeetCode 2400 • Bro Coders • 3,865 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Number of Ways to Reach a Position After Exactly k Steps easy or hard?
The problem is rated Medium because the optimal solution requires recognizing a combinatorics pattern rather than brute forcing moves. Many candidates first implement a dynamic programming solution and then reduce it to a mathematical combination formula.
Number of Ways to Reach a Position After Exactly k Steps Python/Java solution
Python solutions usually compute the binomial coefficient using modular inverse or iterative multiplication. Java implementations often precompute factorials and modular inverses or calculate combinations directly. Both approaches apply the same formula C(k, (k + d)/2) with modulo 1e9+7.
How to solve Number of Ways to Reach a Position After Exactly k Steps in O(k)?
Compute the distance d = |endPos − startPos| and check feasibility: if k < d or (k − d) is odd, return 0. Otherwise the number of right moves must be (k + d) / 2. The answer becomes the binomial coefficient C(k, (k + d)/2) computed modulo 1e9+7.
What is the best approach for Number of Ways to Reach a Position After Exactly k Steps?
The combinatorics approach with a parity check is the most efficient. Compute the distance d = |endPos − startPos| and verify that k ≥ d and (k − d) is even. The number of valid sequences becomes C(k, (k + d) / 2), which counts how many steps move right. This runs in O(k) time for combination calculation and O(1) extra space.
Is Number of Ways to Reach a Position After Exactly k Steps asked at Google/Amazon/Meta?
Variants of this problem appear in interviews at large tech companies because it combines combinatorics, parity reasoning, and dynamic programming fundamentals. Interviewers often expect candidates to first derive a DP transition and then optimize using mathematical insight.
What data structure is used in Number of Ways to Reach a Position After Exactly k Steps?
The dynamic programming approach typically uses a 2D array or hash map to store states for step count and position. The optimal combinatorics approach avoids complex data structures and relies on mathematical computation of binomial coefficients with modular arithmetic.
What is the time complexity of Number of Ways to Reach a Position After Exactly k Steps?
The optimal combinatorics solution runs in O(k) time if combinations are computed iteratively under modulo 1e9+7, with O(1) space. A dynamic programming solution that tracks reachable positions for each step takes O(k²) time and O(k²) space because each step updates a range of positions.

Ready to solve this problem?

Practice Number of Ways to Reach a Position After Exactly k Steps with our built-in code editor and test cases.

Practice on FleetCode
Previous

Climbing Stairs

Next

Number of Ways to Stay in the Same Place After Some Steps