# Find Number of Ways to Reach the K-th Stair
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-number-of-ways-to-reach-the-k-th-stair)
Canonical: https://scaleengineer.com/dsa/problems/find-number-of-ways-to-reach-the-k-th-stair
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Combinatorics](https://scaleengineer.com/dsa/patterns/combinatorics), [Memoization](https://scaleengineer.com/dsa/patterns/memoization)
---
## 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 + 2jump`. And then, `jump` becomes `jump + 1`.

Return the _total_ number of ways Alice can reach stair `k`.

**Note** that it is possible that Alice reaches the stair `k`, and performs some operations to reach the stair `k` again.

**Example 1:**

**Input:** k = 0

**Output:** 2

**Explanation:**

The 2 possible ways of reaching stair 0 are:

* Alice starts at stair 1\.  
  * Using an operation of the first type, she goes down 1 stair to reach stair 0.
* Alice starts at stair 1\.  
  * Using an operation of the first type, she goes down 1 stair to reach stair 0.
  * Using an operation of the second type, she goes up 20 stairs to reach stair 1.
  * Using an operation of the first type, she goes down 1 stair to reach stair 0.

**Example 2:**

**Input:** k = 1

**Output:** 4

**Explanation:**

The 4 possible ways of reaching stair 1 are:

* Alice starts at stair 1\. Alice is at stair 1.
* Alice starts at stair 1\.  
  * Using an operation of the first type, she goes down 1 stair to reach stair 0.
  * Using an operation of the second type, she goes up 20 stairs to reach stair 1.
* Alice starts at stair 1\.  
  * Using an operation of the second type, she goes up 20 stairs to reach stair 2.
  * Using an operation of the first type, she goes down 1 stair to reach stair 1.
* Alice starts at stair 1\.  
  * Using an operation of the first type, she goes down 1 stair to reach stair 0.
  * Using an operation of the second type, she goes up 20 stairs to reach stair 1.
  * Using an operation of the first type, she goes down 1 stair to reach stair 0.
  * Using an operation of the second type, she goes up 21 stairs to reach stair 2.
  * Using an operation of the first type, she goes down 1 stair to reach stair 1.

**Constraints:**

* `0 <= k <= 109`

# Approaches
## Brute-Force Recursion
A straightforward recursive approach that explores all possible paths. The state of the recursion is defined by `(current_stair, current_jump, can_go_down)`. This method directly models the operations available to Alice and explores the state graph without any optimization.
**Time:** Exponential, roughly O(2^N) where N is related to the number of moves. It explores a vast number of redundant paths and is too slow for the given constraints. · **Space:** O(D), where D is the maximum recursion depth. This can be very large.
**Pros:** Simple to conceptualize as it directly follows the problem description.
**Cons:** Extremely inefficient and not feasible for the given constraints due to an enormous state space.; Prone to stack overflow for deep recursion paths.; Defining correct and effective termination/pruning conditions is very difficult.
### Explanation
This approach directly translates the problem statement into a recursive function. We define a state by `(stair, jump, canGoDown)`. `stair` is the current stair, `jump` is the power for the next upward jump, and `canGoDown` is a boolean flag to enforce the rule that "go down" operations cannot be consecutive.
The function `countWays(stair, jump, canGoDown)` calculates the number of ways to reach `k` from this state. It sums the results from the recursive calls for the "go up" and "go down" moves. A crucial issue is defining the termination/base cases correctly to avoid infinite recursion and count paths properly. Due to the massive state space (`k` up to 10^9), this approach is not practical and will time out.

```java
// This is a conceptual illustration. A direct implementation is not feasible
// for the given constraints due to the massive state space and termination issues.
public int waysToReachK_conceptual(int k) {
    // A practical implementation would need bounds for stair and jump to terminate.
    return solve(1, 0, true, k);
}

private int solve(long stair, int jump, boolean canGoDown, int k) {
    // Pruning is essential but difficult to get right.
    // If we are too far above k, it might be impossible to return.
    if (stair > k + 2 && (1L << jump) > stair - k) { // Heuristic pruning
        return 0;
    }
    if (jump > 35) { // Heuristic pruning
        return (stair == k) ? 1 : 0;
    }

    int count = 0;
    if (stair == k) {
        count = 1;
    }

    // Explore Go Up move
    count += solve(stair + (1L << jump), jump + 1, true, k);

    // Explore Go Down move
    if (canGoDown && stair > 0) {
        count += solve(stair - 1, jump, false, k);
    }

    return count;
}
```
### Algorithm
*   Define a recursive function, say `countWays(stair, jump, canGoDown)`.
*   The function explores two possible moves from the current state:
    *   **Go Up:** Move to `stair + 2^jump`, increment `jump` to `jump + 1`, and allow the next move to be a "go down" move. Recursively call `countWays(stair + 2^jump, jump + 1, true)`.
    *   **Go Down:** If `stair > 0` and `canGoDown` is true, move to `stair - 1`. The `jump` value remains the same, and the next move cannot be a "go down" move. Recursively call `countWays(stair - 1, jump, false)`.
*   The function's return value is the sum of ways from the subsequent recursive calls. A way is counted if the path eventually lands on stair `k`.
*   The base case for the recursion is when the number of up-moves (`jump`) or the current `stair` exceeds a practical limit, beyond which it's impossible to reach `k`. If `stair == k`, we add 1 to our count for the current path.
*   The initial call would be `countWays(1, 0, true)`.

## Dynamic Programming with Memoization
This approach improves upon the brute-force recursion by using memoization to store and reuse the results for states that have already been computed. To make the state more manageable, we can define it relative to the target `k`, as `(jump, diff, canGoDown)`, where `diff = current_stair - k`.
**Time:** O(J * D), where J is O(log(k)) and D is O(k). The complexity is O(k * log(k)), which is too slow for the given constraints. · **Space:** O(J * D), where J is the max jump value (~32) and D is the range of `diff`. Since D can be O(k), this is O(log(k) * k), which is too large.
**Pros:** Much faster than brute-force for smaller values of `k`.; Correctly applies the dynamic programming principle to avoid recomputing subproblems.
**Cons:** The state space for `diff` is proportional to `k`, which can be up to 10^9. This makes the memoization table too large to be practical.; Will cause Memory Limit Exceeded or Time Limit Exceeded for large `k`.
### Explanation
This method refines the recursive approach by avoiding recomputation of the same subproblems using dynamic programming. We define a state relative to the target `k` to try and reduce the state space. The state is `(jump, diff, canGoDown)`, where `diff = current_stair - k`.
The function `solve(jump, diff, canGoDown)` computes the number of ways to reach a state with `diff = 0`.
The state transitions are:
- **Go Up:** From `(jump, diff)`, we move to `(jump + 1, diff + 2^jump)`.
- **Go Down:** From `(jump, diff)`, we move to `(jump, diff - 1)`.
The main challenge remains the size of the state space for `diff`. `diff` can range from `-k` up to a positive value. For `k=10^9`, this is too large. This approach is only practical for small `k`.

```java
// This approach is only feasible for small k.
// For k <= 10^9, the 'diff' can be very large and negative, making the memoization map huge.
class Solution {
    Map<String, Integer> memo;
    int targetK;

    public int waysToReachStair(int k) {
        this.targetK = k;
        // Using a HashMap for memoization. The key represents the state.
        this.memo = new HashMap<>();
        return solve(1, 0, true);
    }

    private int solve(long stair, int jump, boolean canGoDown) {
        // Pruning: if we are too far, it's impossible to come back.
        // The number of down moves needed is stair - k. The max we can do is jump + 1.
        if (stair - targetK > jump + 1) {
            return 0;
        }
        // Further pruning
        if (jump > 31) {
            return (stair == targetK) ? 1 : 0;
        }

        String key = stair + "," + jump + "," + canGoDown;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        int count = (stair == targetK) ? 1 : 0;

        // Go Up
        count += solve(stair + (1L << jump), jump + 1, true);

        // Go Down
        if (canGoDown && stair > 0) {
            count += solve(stair - 1, jump, false);
        }

        memo.put(key, count);
        return count;
    }
}
```
### Algorithm
*   Define a recursive function `solve(jump, diff, canGoDown)` with a memoization table (e.g., a HashMap).
*   The state is defined by `jump` (the next jump power), `diff` (the difference `current_stair - k`), and `canGoDown` (boolean flag).
*   The base case: if `diff == 0`, we are at stair `k`, so we add 1 to our count.
*   Pruning: If `jump` is too large (e.g., > 32) or `diff` makes it impossible to reach `k`, return 0. For example, if `diff > jump + 1`, we need more "down" steps than available slots between "up" moves.
*   Check the memoization table. If the result for the current state `(jump, diff, canGoDown)` is already computed, return it.
*   Recursively call for the two moves:
    *   **Go Up:** `solve(jump + 1, diff + 2^jump, true)`.
    *   **Go Down:** If `canGoDown` and `k + diff > 0`, call `solve(jump, diff - 1, false)`.
*   Store the sum of the results in the memoization table and return it.
*   The initial call is `solve(0, 1 - k, true)`.

## Combinatorial Approach
This is the most efficient approach, which reframes the problem as a combinatorial selection problem. It analyzes the net effect of the moves and counts the valid arrangements of "go up" and "go down" operations, leading to a direct calculation without exploring the state space.
**Time:** O((log k)^2). The loop for `j` runs about `log k` times. Inside the loop, calculating combinations `C(j+1, d)` takes O(d) which is at most O(j). The total time is the sum of `j` from 0 to `log k`, which is O((log k)^2). · **Space:** O(1). We only use a few variables for the loop and calculations.
**Pros:** Extremely efficient and runs in logarithmic time with respect to `k`.; Handles the large constraint on `k` with constant space.; Provides an exact answer without exploring any paths.
**Cons:** Requires a mathematical insight into the problem structure which might not be immediately obvious.
### Explanation
This approach leverages a key insight: the `jump` value for the `i`-th "go up" move is always `i-1`, regardless of any "go down" moves made in between.

If we make exactly `j` "go up" moves, the total positive displacement is `sum_{i=0}^{j-1} 2^i = 2^j - 1`. Starting from stair 1, these moves alone would land us on stair `2^j`. To end up on stair `k`, we need to make `d = 2^j - k` "go down" moves.

The number of down moves `d` must be non-negative, so `2^j >= k`.

The rule against consecutive "go down" moves means each down-move must be separated by at least one up-move. This gives us `j+1` potential slots to place the `d` down-moves: one before each of the `j` up-moves, and one after the last one.
`_ U_0 _ U_1 _ ... _ U_{j-1} _`

We need to choose `d` of these `j+1` slots to place our down-moves. This is a combination problem, and the number of ways is `C(j+1, d)`. This also implies that `d` cannot be greater than `j+1`.

So, the algorithm is to sum `C(j+1, 2^j - k)` for all `j` that satisfy `0 <= 2^j - k <= j+1`. We can iterate `j` from 0 up to a small limit (around 31) and add the results.

```java
class Solution {
    public int waysToReachStair(int k) {
        int ways = 0;
        // j is the number of 'up' moves. 2^30 > 10^9, so j won't exceed ~31.
        for (int j = 0; j < 32; j++) {
            long powerOf2 = 1L << j;
            long downs = powerOf2 - k;

            if (downs < 0) {
                continue;
            }
            
            // The number of available slots for down moves is j + 1.
            // One slot before all jumps, and one slot after each of the j jumps.
            if (downs > j + 1) {
                // For j > 1, 2^j - k > j + 1 is equivalent to 2^j - j - 1 > k.
                // Since 2^j - j - 1 is an increasing function for j>=1,
                // we can break the loop if this condition is met.
                if (j > 1 && (powerOf2 - j - 1 > k)) {
                    break;
                }
                continue;
            }

            ways += combinations(j + 1, (int) downs);
        }
        return ways;
    }

    // Helper function to calculate combinations C(n, k)
    private int combinations(int n, int k) {
        if (k < 0 || k > n) {
            return 0;
        }
        if (k == 0 || k == n) {
            return 1;
        }
        if (k > n / 2) {
            k = n - k;
        }
        long res = 1;
        for (int i = 1; i <= k; i++) {
            res = res * (n - i + 1) / i;
        }
        return (int) res;
    }
}
```
### Algorithm
*   Analyze the net displacement. If we perform `j` "go up" moves, the total upward displacement is `2^0 + 2^1 + ... + 2^(j-1) = 2^j - 1`. Starting from stair 1, we would reach stair `1 + (2^j - 1) = 2^j`.
*   To reach stair `k`, we must perform `d` "go down" moves. The final position will be `2^j - d`. Setting this to `k` gives `d = 2^j - k`.
*   Since `d` must be non-negative, we must have `2^j >= k`.
*   The "no consecutive down-moves" rule implies that a down-move must be followed by an up-move (unless it's the final move). This means we can place at most one down-move between any two consecutive up-moves, one before the first up-move, and one after the last up-move.
*   This gives `j+1` available "slots" to place the `d` down-moves.
*   The problem reduces to choosing `d` slots out of `j+1`. The number of ways is the binomial coefficient `C(j+1, d)`. This also implies `d <= j+1`.
*   Iterate through the number of up-moves `j` from 0 upwards (up to ~31, as `2^31` is > `10^9`).
*   For each `j`, calculate `d = 2^j - k`. If `0 <= d <= j+1`, calculate `C(j+1, d)` and add it to the total count.
*   The loop can be optimized to stop when `2^j - j - 1 > k`.

# Solutions
### Java

```java
class Solution {
private
  Map<Long, Integer> f = new HashMap<>();
private
  int k;
public
  int waysToReachStair(int k) {
    this.k = k;
    return dfs(1, 0, 0);
  }
private
  int dfs(int i, int j, int jump) {
    if (i > k + 1) {
      return 0;
    }
    long key = ((long)i << 32) | jump << 1 | j;
    if (f.containsKey(key)) {
      return f.get(key);
    }
    int ans = i == k ? 1 : 0;
    if (i > 0 && j == 0) {
      ans += dfs(i - 1, 1, jump);
    }
    ans += dfs(i + (1 << jump), 0, jump + 1);
    f.put(key, ans);
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int waysToReachStair(int k) {
    this->k = k;
    return dfs(1, 0, 0);
  }

private:
  unordered_map<long long, int> f;
  int k;
  int dfs(int i, int j, int jump) {
    if (i > k + 1) {
      return 0;
    }
    long long key = ((long long)i << 32) | jump << 1 | j;
    if (f.contains(key)) {
      return f[key];
    }
    int ans = i == k ? 1 : 0;
    if (i > 0 && j == 0) {
      ans += dfs(i - 1, 1, jump);
    }
    ans += dfs(i + (1 << jump), 0, jump + 1);
    f[key] = ans;
    return ans;
  }
};

```

### Python

```python
class Solution:
    def waysToReachStair(self, k: int) -> int: @ cache def dfs(i: int, j: int, jump: int) -> int: if i > k + 1: return 0 ans = int(i == k) if i > 0 and j == 0: ans += dfs(i - 1, 1, jump) ans += dfs(i + (1 << jump), 0, jump + 1) return ans return dfs(1, 0, 0)

```