3621. Number of Integers With Popcount-Depth Equal to K I Hard

1/**
2 * [3621] Number of Integers With Popcount-Depth Equal to K I
3 *
4 * You are given two integers n and k.
5 * For any positive integer x, define the following sequence:
6 * 
7 * 	p0 = x
8 * 	pi+1 = popcount(pi) for all i >= 0, where popcount(y) is the number of set bits (1's) in the binary representation of y.
9 * 
10 * This sequence will eventually reach the value 1.
11 * The popcount-depth of x is defined as the smallest integer d >= 0 such that pd = 1.
12 * For example, if x = 7 (binary representation "111"). Then, the sequence is: 7 → 3 → 2 → 1, so the popcount-depth of 7 is 3.
13 * Your task is to determine the number of integers in the range [1, n] whose popcount-depth is exactly equal to k.
14 * Return the number of such integers.
15 *  
16 * <strong class="example">Example 1:
17 * <div class="example-block">
18 * Input: <span class="example-io">n = 4, k = 1</span>
19 * Output: <span class="example-io">2</span>
20 * Explanation:
21 * The following integers in the range [1, 4] have popcount-depth exactly equal to 1:
22 * <table style="border: 1px solid black;">
23 * 	<thead>
24 * 		<tr>
25 * 			<th align="center" style="border: 1px solid black;">x</th>
26 * 			<th align="center" style="border: 1px solid black;">Binary</th>
27 * 			<th align="left" style="border: 1px solid black;">Sequence</th>
28 * 		</tr>
29 * 	</thead>
30 * 	<tbody>
31 * 		<tr>
32 * 			<td align="center" style="border: 1px solid black;">2</td>
33 * 			<td align="center" style="border: 1px solid black;">"10"</td>
34 * 			<td align="left" style="border: 1px solid black;">2 &rarr; 1</td>
35 * 		</tr>
36 * 		<tr>
37 * 			<td align="center" style="border: 1px solid black;">4</td>
38 * 			<td align="center" style="border: 1px solid black;">"100"</td>
39 * 			<td align="left" style="border: 1px solid black;">4 &rarr; 1</td>
40 * 		</tr>
41 * 	</tbody>
42 * </table>
43 * Thus, the answer is 2.
44 * </div>
45 * <strong class="example">Example 2:
46 * <div class="example-block">
47 * Input: <span class="example-io">n = 7, k = 2</span>
48 * Output: <span class="example-io">3</span>
49 * Explanation:
50 * The following integers in the range [1, 7] have popcount-depth exactly equal to 2:
51 * <table style="border: 1px solid black;">
52 * 	<thead>
53 * 		<tr>
54 * 			<th style="border: 1px solid black;">x</th>
55 * 			<th style="border: 1px solid black;">Binary</th>
56 * 			<th style="border: 1px solid black;">Sequence</th>
57 * 		</tr>
58 * 	</thead>
59 * 	<tbody>
60 * 		<tr>
61 * 			<td style="border: 1px solid black;">3</td>
62 * 			<td style="border: 1px solid black;">"11"</td>
63 * 			<td style="border: 1px solid black;">3 &rarr; 2 &rarr; 1</td>
64 * 		</tr>
65 * 		<tr>
66 * 			<td style="border: 1px solid black;">5</td>
67 * 			<td style="border: 1px solid black;">"101"</td>
68 * 			<td style="border: 1px solid black;">5 &rarr; 2 &rarr; 1</td>
69 * 		</tr>
70 * 		<tr>
71 * 			<td style="border: 1px solid black;">6</td>
72 * 			<td style="border: 1px solid black;">"110"</td>
73 * 			<td style="border: 1px solid black;">6 &rarr; 2 &rarr; 1</td>
74 * 		</tr>
75 * 	</tbody>
76 * </table>
77 * Thus, the answer is 3.
78 * </div>
79 *  
80 * Constraints:
81 * 
82 * 	1 <= n <= 10^15
83 * 	0 <= k <= 5
84 * 
85 */
86pub struct Solution {}
87
88// problem: https://leetcode.com/problems/number-of-integers-with-popcount-depth-equal-to-k-i/
89// discuss: https://leetcode.com/problems/number-of-integers-with-popcount-depth-equal-to-k-i/discuss/?currentPage=1&orderBy=most_votes&query=
90
91// submission codes start here
92
93impl Solution {
94    pub fn popcount_depth(n: i64, k: i32) -> i64 {
95        
96    }
97}
98
99// submission codes end
100
101#[cfg(test)]
102mod tests {
103    use super::*;
104
105    #[test]
106    fn test_3621() {
107    }
108}
109