Find Kth Bit in Nth Binary String

Medium · Bit Manipulation · about 20 minutes

Asked at Google, Amazon, Microsoft, Meta.

S1 = "0" and Si = S(i-1) + "1" + reverse(invert(S(i-1))). Given n and k (1-indexed, k ≤ 2ⁿ − 1), return the k-th bit of Sn as a string "0" or "1".