Number of Ways to Reach a Position After Exactly k Steps

Number of Ways to Reach a Position After Exactly k Steps - Problem

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 10⁹ + 7.

Two ways are considered different if the order of the steps made is not exactly the same.

Note: The number line includes negative integers.

Input & Output

Example 1 — Basic Movement

$ Input: startPos = 1, endPos = 2, k = 3

› Output: 3

💡 Note: 3 ways to reach position 2 from position 1 in exactly 3 steps: RLL (1→2→1→0→1→2), LRL (1→0→1→2), LLR (1→0→-1→0→1→2). Wait, let me recalculate: RLL: 1→2→1→0, LRL: 1→0→1→2, LLR: 1→0→-1→0. Actually the 3 ways are: RLR: 1→2→1→2, LRR: 1→0→1→2, RRL: this doesn't work. Let me recalculate properly: We need exactly 3 steps to go from 1 to 2 (distance 1). Ways: RLR (1→2→1→2), LRR (1→0→1→2), RLL then R won't work in 3 steps. The correct 3 ways are: RLR, LRR, and RRL doesn't work. Actually: RLR, LRR, LRL all reach position 2 in 3 steps.

Example 2 — Same Position

$ Input: startPos = 2, endPos = 2, k = 2

› Output: 2

💡 Note: 2 ways to stay at position 2 in exactly 2 steps: RL (2→3→2) or LR (2→1→2). Both sequences return to the starting position.

Example 3 — Impossible Case

$ Input: startPos = 1, endPos = 3, k = 1

› Output: 0

💡 Note: Impossible to reach position 3 from position 1 in exactly 1 step, since the distance is 2 but we can only move 1 step total.

Constraints

1 ≤ startPos, endPos ≤ 1000
1 ≤ k ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Start at position 1, want to reach 2 in 3 steps

Process

Try different combinations of L and R moves

Output

Count valid sequences that use exactly k steps

Key Takeaway

🎯 Key Insight: Transform the path-counting problem into a combinatorial problem of choosing which steps go right vs left

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that this is a combinatorial problem. We need exactly r right moves and l left moves where r + l = k and r - l = (endPos - startPos). Solving these equations gives r = (k + distance)/2. The answer is C(k,r) if r is a valid integer, 0 otherwise. Best approach is mathematical formula with Time: O(k), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Combinatorics	O(k)	O(1)	Use combinatorial formula to directly calculate the answer
Recursive Brute Force	O(2^k)	O(k)	Try all possible sequences of left and right moves
Memoized Recursion	O(k × range)	O(k × range)	Cache results of subproblems to avoid recomputation

Mathematical Combinatorics — Algorithm Steps

Calculate distance = endPos - startPos
Check if solution exists: (k + distance) must be even and >= 0
Calculate right moves: r = (k + distance) / 2
Return C(k, r) = k! / (r! × (k-r)!)

Visualization

Tap to expand

Step-by-Step Walkthrough

Setup

Need r right moves and l left moves where r + l = k

Constraint

Also need r - l = endPos - startPos

Solve

r = (k + distance)/2, answer is C(k,r)

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>

const int MOD = 1000000007;

long long modPow(long long base, long long exp) {
    long long result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % MOD;
        }
        base = (base * base) % MOD;
        exp /= 2;
    }
    return result;
}

long long modInverse(long long a) {
    return modPow(a, MOD - 2);
}

int solution(int startPos, int endPos, int k) {
    int distance = endPos - startPos;
    
    if ((k + distance) % 2 != 0 || abs(distance) > k) {
        return 0;
    }
    
    int right = (k + distance) / 2;
    
    if (right < 0 || right > k) {
        return 0;
    }
    
    long long result = 1;
    int limit = (right < k - right) ? right : k - right;
    for (int i = 0; i < limit; i++) {
        result = result * (k - i) % MOD * modInverse(i + 1) % MOD;
    }
    
    return (int)result;
}

int main() {
    int startPos, endPos, k;
    scanf("%d", &startPos);
    scanf("%d", &endPos);
    scanf("%d", &k);
    
    int result = solution(startPos, endPos, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k)

Computing factorial and modular inverse takes O(k) time

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables for computation

✓ Linear Space

23.5K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Mathematical Combinatorics — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler