Find Number of Ways to Reach the K-th Stair
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 stair0. - Go up to stair
i + 2^jump. Then,jumpbecomesjump + 1.
Return the total number of ways Alice can reach stair k.
Note that it is possible that Alice reaches stair k, and performs some operations to reach stair k again.
Example 1
Input
k = 0Output
2Alice can reach stair 0 either by going down once from stair 1, or by going down, going up by 2^0, and going down again.
Example 2
Input
k = 1Output
4There are 4 valid operation sequences that place Alice on stair 1, including starting there immediately and returning to it through allowed moves.
Constraints
- 0 <= k <= 10^9