1545. Find Kth Bit in Nth Binary String Medium

1/**
2 * [1545] Find Kth Bit in Nth Binary String
3 *
4 * Given two positive integers n and k, the binary string Sn is formed as follows:
5 *
6 * S1 = "0"
7 * Si = Si - 1 + "1" + reverse(invert(Si - 1)) for i > 1
8 *
9 * Where + denotes the concatenation operation, reverse(x) returns the reversed string x, and invert(x) inverts all the bits in x (0 changes to 1 and 1 changes to 0).
10 * For example, the first four strings in the above sequence are:
11 *
12 * S1 = "0"
13 * S2 = "011"
14 * S3 = "0111001"
15 * S4 = "011100110110001"
16 *
17 * Return the k^th bit in Sn. It is guaranteed that k is valid for the given n.
18 *  
19 * Example 1:
20 *
21 * Input: n = 3, k = 1
22 * Output: "0"
23 * Explanation: S3 is "<u>0</u>111001".
24 * The 1^st bit is "0".
25 *
26 * Example 2:
27 *
28 * Input: n = 4, k = 11
29 * Output: "1"
30 * Explanation: S4 is "0111001101<u>1</u>0001".
31 * The 11^th bit is "1".
32 *
33 *  
34 * Constraints:
35 *
36 * 1 <= n <= 20
37 * 1 <= k <= 2^n - 1
38 *
39 */
40pub struct Solution {}
41
42// problem: https://leetcode.com/problems/find-kth-bit-in-nth-binary-string/
43// discuss: https://leetcode.com/problems/find-kth-bit-in-nth-binary-string/discuss/?currentPage=1&orderBy=most_votes&query=
44
45// submission codes start here
46
47impl Solution {
48    pub fn find_kth_bit(n: i32, k: i32) -> char {
49        if k == 1 || n == 1 {
50            return '0';
51        }
52        // total 2&n - 1
53        let half = ((1 << n) - 1) / 2 + 1;
54        if half == k {
55            return '1';
56        } else if k > half {
57            return if Self::find_kth_bit(n - 1, 2 * half - k) == '0' {
58                '1'
59            } else {
60                '0'
61            };
62        } else {
63            Self::find_kth_bit(n - 1, k)
64        }
65    }
66}
67
68// submission codes end
69
70#[cfg(test)]
71mod tests {
72    use super::*;
73
74    #[test]
75    fn test_1545() {
76        assert_eq!(Solution::find_kth_bit(4, 11), '1');
77    }
78}
79