Find Number of Ways to Reach the K-th Stair

Find Number of Ways to Reach the K-th Stair - Problem

You are given a non-negative integer k. There exists a staircase with an infinite number of stairs, with the lowest stair numbered 0.

Alice has an integer jump, with an initial value of 0. She starts on stair 1 and wants to reach stair k using any number of operations.

If she is on stair i, in one operation she can:

Go down to stair i - 1. This operation cannot be used consecutively or on stair 0.
Go up to stair i + 2^jump. And then, jump becomes jump + 1.

Return the total number of ways Alice can reach stair k.

Note: It is possible that Alice reaches stair k, and performs some operations to reach stair k again.

Input & Output

Example 1 — Basic Case

$ Input: k = 1

› Output: 2

💡 Note: Alice starts at stair 1 (already at target). She can also go up to 2 then down to 1. Two ways total.

Example 2 — Multiple Paths

$ Input: k = 2

› Output: 2

💡 Note: Path 1: Start at 1, go up by 2^0=1 to reach 2. Path 2: Start at 1, go up by 2^0=1 to 2, up by 2^1=2 to 4, down to 3, down to 2.

Example 3 — Edge Case

$ Input: k = 0

› Output: 1

💡 Note: Alice starts at 1, can only go down to 0 (one way since she cannot go down consecutively).

Constraints

0 ≤ k ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Starting Position

Alice starts at stair 1 with jump=0

Movement Rules

Up by 2^jump (jump++), Down by 1 (no consecutive)

Count Paths

Find all ways to reach target stair k

Key Takeaway

🎯 Key Insight: The exponentially growing jump sizes create predictable patterns that can be solved with combinatorial mathematics

Asked in

G Google 15 f Meta 12 Apple 8

The key insight is that Alice can place at most one down move between consecutive up moves, creating a combinatorial pattern. The mathematical approach using C(n,k) combinations provides the optimal O(log k) solution by counting valid sequences directly. Time: O(log k), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Combinatorics	O(log k)	O(1)	Use mathematical patterns and combinatorics to count paths directly
Memoized Recursion	O(k × log k)	O(k × log k)	Cache results of subproblems to avoid recomputation
Recursive Exploration	O(2^n)	O(n)	Recursively explore all possible paths from current position

Mathematical Combinatorics — Algorithm Steps

Step 1: Analyze the mathematical constraint - at most one down between ups
Step 2: Find all possible up sequences that can reach positions near k
Step 3: Use combinatorics to count valid down placements in each sequence

Visualization

Tap to expand

Step-by-Step Walkthrough

Power-of-2 Pattern

Up moves follow 2^0, 2^1, 2^2... pattern

Down Move Placement

At most one down between consecutive ups

Combinatorial Count

Use C(n,k) to count valid arrangements

Code -

solution.c — C

#include <stdio.h>

long long comb(int n, int k) {
    if (k > n || k < 0) return 0;
    if (k == 0 || k == n) return 1;
    if (k > n - k) k = n - k; // Take advantage of symmetry
    long long result = 1;
    for (int i = 0; i < k; i++) {
        result = result * (n - i) / (i + 1);
    }
    return result;
}

int solution(int k) {
    int result = 0;
    int jump = 0;
    
    // Try all possible sequences of up moves
    while (1) {
        // After 'jump' up moves, we're at position: 2^jump
        int finalPos = 1 << jump; // 2^jump
        
        if (finalPos > k + jump) break;
        
        // We need exactly (finalPos - k) down moves to reach k
        int downMoves = finalPos - k;
        
        // Check if this number of down moves is valid
        if (downMoves >= 0 && downMoves <= jump) {
            // Count ways to place 'downMoves' downs among 'jump' possible positions
            result += comb(jump, downMoves);
        }
        
        jump++;
        if (jump > 32) break; // Prevent overflow
    }
    
    return result;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(log k)

Only need to check sequences with up to log₂(k) jumps

⚡ Linearithmic

Space Complexity

O(1)

Only uses a few variables for calculations

✓ Linear Space

7.2K Views

Medium Frequency

~35 min Avg. Time

189 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