We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Ways to Reach a Position After Exactly k Steps

Number: 2477

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given two positive integers startPos and endPos, you start at position startPos on an infinite number line. In each step you can move one unit left or right. Given a positive integer k, determine the number of different ways (order matters) to reach endPos in exactly k steps. If the number exceeds 10^9+7, return it modulo 10^9+7.

Key Insights

  • The net displacement must be exactly |endPos - startPos|, and any extra moves must cancel out.
  • If d is the distance (|endPos - startPos|), then you need (k - d) extra moves that come in canceling pairs. Therefore, (k - d) must be even.
  • Let r be the number of right moves. Then, from the equations:
    • r + l = k and r - l = (endPos - startPos), we extract r = (k + (endPos - startPos)) / 2.
  • The answer is given by the binomial coefficient C(k, r) modulo 10^9+7.

Space and Time Complexity

Time Complexity: O(k) for precomputing factorials and modular inverses.
Space Complexity: O(k) for storing factorials and inverse factorials.

Solution

The solution involves combinatorics. First, check for feasibility: if the absolute distance d between startPos and endPos is greater than k or if (k - d) is odd, no solution exists. Otherwise, compute the exact number of steps to the right using r = (k + (endPos - startPos)) / 2. The total number of valid ways is then given by the binomial coefficient C(k, r) (i.e., choosing r steps to be right out of k steps). To compute C(k, r) modulo 10^9+7, we precompute factorials and their modular inverses using Fermat's Little Theorem.

Code Solutions

Below are the implementations in Python, JavaScript, C++, and Java with inline comments.

mod = 10**9 + 7

# Function to compute modular inverse using Fermat's Little Theorem
def modinv(a, mod):
    return pow(a, mod - 2, mod)

# Precompute factorials and inverses up to n
def precompute_factorials(n, mod):
    fact = [1] * (n + 1)
    inv = [1] * (n + 1)
    for i in range(2, n + 1):
        fact[i] = fact[i - 1] * i % mod
    inv[n] = modinv(fact[n], mod)
    for i in range(n, 0, -1):
        inv[i - 1] = inv[i] * i % mod
    return fact, inv

# Compute nCr modulo mod using precomputed factorials and inverses
def nCr(n, r, fact, inv, mod):
    if r < 0 or r > n:
        return 0
    return fact[n] * inv[r] % mod * inv[n - r] % mod

def numberOfWays(startPos, endPos, k):
    # Calculate the required displacement.
    d = abs(endPos - startPos)
    # Check if it is possible to reach endPos in exactly k steps.
    if d > k or (k - d) % 2 != 0:
        return 0
    # Calculate number of right moves required.
    r = (k + (endPos - startPos)) // 2
    # Precompute factorials and inverses up to k.
    fact, inv = precompute_factorials(k, mod)
    return nCr(k, r, fact, inv, mod)

# Example test
print(numberOfWays(1, 2, 3))
← Back to All Questions