[알고리즘문제] 릿코드 Find Kth Bit in Nth Binary String

https://leetcode.com/problems/find-kth-bit-in-nth-binary-string/

Find Kth Bit in Nth Binary String - LeetCode

 

input으로 n, k를 준다.

n을 이용하여 binary string을 만든다.

string이 만들어지는 규칙은

S1 = "0";

S2 = S1 + "1" + reverse(invert(S1));

...

 

Si = Si-1 + "1" + reverse(invert(Si-1));

 

만약 i가 4라고 한다면 

S1 = "0"

S2 = "010"

S3 = "0111001"

S4 = "011100110110001"

이 된다.

여기서 k + 1번째 문자를 반환한다.

n이 4이고, k가 11이라면

"011100110110001" => 1을 반환한다.

 

impl Solution {
    pub fn find_kth_bit(n: i32, k: i32) -> char {
        if k == 0 { return '0';}
        let mut bit = String::from("0");

        Solution::recursion(&mut bit, 0, n);

        let mut answer: Vec<char> = bit.chars().collect();
        
        answer[k as usize - 1]
    }

    fn recursion(prev: &mut String, idx: i32, n: i32) {
        if idx == n - 1 {
            return;
        }
        let mut bit = Solution::reverse(prev.clone());
        bit = Solution::invert(bit);

        prev.push_str("1");
        prev.push_str(&*bit);

        Solution::recursion(prev, idx + 1, n);
    }

    fn reverse(bit: String) -> String {
        bit.chars().rev().collect::<String>()
    }

    fn invert(bit: String) -> String {
        let mut value = String::from("");
        for c in bit.chars() {
            if c == '0' { value.push('1'); }
            else { value.push('0'); }
        }
        value
    }
}

 

time complexity : O(n²)

space complexity : O(n)