Find kth bit in nth binary string

String Recursion Simulation

70.2% acceptance

Feb 25, 2026

1520

Given two positive integers n and k, the binary string Sn is formed as follows: S1 = "0" Si = Si-1 + "1" + reverse(invert(Si-1)) for i > 1 Return the kth bit in Sn.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn find_kth_bit(n: i32, k: i32) -> char {
    if n == 1 { return '0'; }
    let mid = 1i32 << (n - 1); // 2^(n-1), middle position (1-indexed)
    if k == mid {
      '1'
    } else if k < mid {
      Self::find_kth_bit(n - 1, k)
    } else {
      // Mirror position in Sn-1, then invert
      let mirror = 2 * mid - k;
      let bit = Self::find_kth_bit(n - 1, mirror);
      if bit == '0' { '1' } else { '0' }
    }
  }
}