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:
i - 1. This operation cannot be used consecutively or on stair 0.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:
Example 2:
Input: k = 1
Output: 4
Explanation:
The 4 possible ways of reaching stair 1 are:
Constraints:
0 <= k <= 109In #3154 Find Number of Ways to Reach the K-th Stair, the operations allow jumping upward with exponentially increasing steps and occasionally moving down by one step (with constraints). A brute-force simulation quickly becomes infeasible because the jump size grows exponentially and many sequences of operations are possible.
The key observation is that after performing i upward jumps, the total upward movement becomes a predictable value due to powers of two. If we also perform d downward moves, the final stair can be represented mathematically as a combination of these jumps and decrements. This transforms the problem into counting valid placements of downward moves among the jump operations.
By enumerating possible numbers of jumps and computing how many downward moves are required to land exactly on stair k, we can use combinatorics (binomial coefficients) to count valid sequences. Only a small range of jump counts needs to be checked, making the solution efficient. The optimized approach runs in about O(log k) time with O(1) space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Combinatorics with Jump Enumeration | O(log k) | O(1) |
| Memoized DFS / Dynamic Programming | O(log k * states) | O(log k) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
On using <code>x</code> operations of the second type and <code>y</code> operations of the first type, the stair <code>2<sup>x</sup> - y</code> is reached.
Since first operations cannot be consecutive, there are exactly <code>x + 1</code> positions (before and after each power of 2) to perform the second operation.
Using combinatorics, we have <sup>x + 1</sup>C<sub>y</sub> number of ways to select the positions of second operations.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Problems like this are common in high-level technical interviews because they combine combinatorics, dynamic programming, and mathematical reasoning. While the exact problem may not appear, similar patterns involving counting sequences and power-based jumps are frequently tested.
The combinatorial solution does not require complex data structures—only mathematical calculations and simple variables. However, if using a recursive or memoized approach, a hash map or memo table can store previously computed states to avoid recomputation.
The optimal approach uses combinatorics by analyzing how exponential jumps contribute to the final position. By enumerating the number of jumps and calculating how many downward steps are needed, we count valid arrangements using binomial coefficients. This reduces the problem to about O(log k) time.
Each upward jump increases in size exponentially, typically doubling from the previous jump. This means the total upward distance after several jumps can be expressed using powers of two, allowing the final stair position to be modeled with a simple mathematical formula.