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

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

✓ Mathematical Combinatorics

⏱️ Time: O(k) Space: O(1)

The key insight is that we need exactly r right moves and l left moves where r + l = k and r - l = endPos - startPos. This becomes a combinatorial problem of choosing r positions out of k total steps.

Memoized Recursion

⏱️ Time: O(k × range) Space: O(k × range)

Same recursive approach but store results of (position, steps) pairs in a memo table to avoid recalculating the same subproblems multiple times.

Recursive Brute Force

⏱️ Time: O(2^k) Space: O(k)

For each step, recursively try both left and right moves until we've made exactly k steps. Count the ways that end at the target position.

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

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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Mathematical Combinatorics — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler