#1545
Find Kth Bit in Nth Binary String
pupil · 515 · lc medium +28 · verified · 73.7% accepted · 1,849 likes · top 84%
Description
A sequence of binary strings is defined as: S1 = "0", and for i > 1, Si = S(i-1) + "1" + reverse(invert(S(i-1))). Given integers n and k, return the kth bit (1-indexed) in string Sn. It is guaranteed k is valid.
Example 1:
Input: n = 3, k = 1
Output: "0"
Explanation: S3 is "0111001".
The 1st bit is "0".
Example 2:
Input: n = 4, k = 11
Output: "1"
Explanation: S4 is "011100110110001".
The 11th bit is "1".
Code
1
2
3