3154. Find Number of Ways to Reach the K-th Stair Hard

1/**
2 * [3154] Find Number of Ways to Reach the K-th Stair
3 *
4 * You are given a non-negative integer k. There exists a staircase with an infinite number of stairs, with the lowest stair numbered 0.
5 * 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:
6 * 
7 * 	Go down to stair i - 1. This operation cannot be used consecutively or on stair 0.
8 * 	Go up to stair i + 2^jump. And then, jump becomes jump + 1.
9 * 
10 * Return the total number of ways Alice can reach stair k.
11 * Note that it is possible that Alice reaches the stair k, and performs some operations to reach the stair k again.
12 *  
13 * <strong class="example">Example 1:
14 * <div class="example-block">
15 * Input: <span class="example-io">k = 0</span>
16 * Output: <span class="example-io">2</span>
17 * Explanation:
18 * The 2 possible ways of reaching stair 0 are:
19 * 
20 * 	Alice starts at stair 1.
21 * 	
22 * 		Using an operation of the first type, she goes down 1 stair to reach stair 0.
23 * 	
24 * 	
25 * 	Alice starts at stair 1.
26 * 	
27 * 		Using an operation of the first type, she goes down 1 stair to reach stair 0.
28 * 		Using an operation of the second type, she goes up 2^0 stairs to reach stair 1.
29 * 		Using an operation of the first type, she goes down 1 stair to reach stair 0.
30 * 	
31 * 	
32 * </div>
33 * <strong class="example">Example 2:
34 * <div class="example-block">
35 * Input: <span class="example-io">k = 1</span>
36 * Output: <span class="example-io">4</span>
37 * Explanation:
38 * The 4 possible ways of reaching stair 1 are:
39 * 
40 * 	Alice starts at stair 1. Alice is at stair 1.
41 * 	Alice starts at stair 1.
42 * 	
43 * 		Using an operation of the first type, she goes down 1 stair to reach stair 0.
44 * 		Using an operation of the second type, she goes up 2^0 stairs to reach stair 1.
45 * 	
46 * 	
47 * 	Alice starts at stair 1.
48 * 	
49 * 		Using an operation of the second type, she goes up 2^0 stairs to reach stair 2.
50 * 		Using an operation of the first type, she goes down 1 stair to reach stair 1.
51 * 	
52 * 	
53 * 	Alice starts at stair 1.
54 * 	
55 * 		Using an operation of the first type, she goes down 1 stair to reach stair 0.
56 * 		Using an operation of the second type, she goes up 2^0 stairs to reach stair 1.
57 * 		Using an operation of the first type, she goes down 1 stair to reach stair 0.
58 * 		Using an operation of the second type, she goes up 2^1 stairs to reach stair 2.
59 * 		Using an operation of the first type, she goes down 1 stair to reach stair 1.
60 * 	
61 * 	
62 * </div>
63 *  
64 * Constraints:
65 * 
66 * 	0 <= k <= 10^9
67 * 
68 */
69pub struct Solution {}
70
71// problem: https://leetcode.com/problems/find-number-of-ways-to-reach-the-k-th-stair/
72// discuss: https://leetcode.com/problems/find-number-of-ways-to-reach-the-k-th-stair/discuss/?currentPage=1&orderBy=most_votes&query=
73
74// submission codes start here
75
76impl Solution {
77    pub fn ways_to_reach_stair(k: i32) -> i32 {
78        0
79    }
80}
81
82// submission codes end
83
84#[cfg(test)]
85mod tests {
86    use super::*;
87
88    #[test]
89    fn test_3154() {
90    }
91}
92