3352. Count K-Reducible Numbers Less Than N Hard

1/**
2 * [3352] Count K-Reducible Numbers Less Than N
3 *
4 * You are given a binary string s representing a number n in its binary form.
5 * You are also given an integer k.
6 * An integer x is called k-reducible if performing the following operation at most k times reduces it to 1:
7 * 
8 * 	Replace x with the count of <span data-keyword="set-bit">set bits</span> in its binary representation.
9 * 
10 * For example, the binary representation of 6 is "110". Applying the operation once reduces it to 2 (since "110" has two set bits). Applying the operation again to 2 (binary "10") reduces it to 1 (since "10" has one set bit).
11 * Return an integer denoting the number of positive integers less than n that are k-reducible.
12 * Since the answer may be too large, return it modulo 10^9 + 7.
13 *  
14 * <strong class="example">Example 1:
15 * <div class="example-block">
16 * Input: <span class="example-io">s = "111", k = 1</span>
17 * Output: <span class="example-io">3</span>
18 * Explanation: 
19 * n = 7. The 1-reducible integers less than 7 are 1, 2, and 4.
20 * </div>
21 * <strong class="example">Example 2:
22 * <div class="example-block">
23 * Input: <span class="example-io">s = "1000", k = 2</span>
24 * Output: <span class="example-io">6</span>
25 * Explanation:
26 * n = 8. The 2-reducible integers less than 8 are 1, 2, 3, 4, 5, and 6.
27 * </div>
28 * <strong class="example">Example 3:
29 * <div class="example-block">
30 * Input: <span class="example-io">s = "1", k = 3</span>
31 * Output: <span class="example-io">0</span>
32 * Explanation:
33 * There are no positive integers less than n = 1, so the answer is 0.
34 * </div>
35 *  
36 * Constraints:
37 * 
38 * 	1 <= s.length <= 800
39 * 	s has no leading zeros.
40 * 	s consists only of the characters '0' and '1'.
41 * 	1 <= k <= 5
42 * 
43 */
44pub struct Solution {}
45
46// problem: https://leetcode.com/problems/count-k-reducible-numbers-less-than-n/
47// discuss: https://leetcode.com/problems/count-k-reducible-numbers-less-than-n/discuss/?currentPage=1&orderBy=most_votes&query=
48
49// submission codes start here
50
51impl Solution {
52    pub fn count_k_reducible_numbers(s: String, k: i32) -> i32 {
53        0
54    }
55}
56
57// submission codes end
58
59#[cfg(test)]
60mod tests {
61    use super::*;
62
63    #[test]
64    fn test_3352() {
65    }
66}
67