Find Kth Bit in Nth Binary String

Given two positive integers n and k, you are asked to find the kth bit in the binary string Sn, where:
• S1 = "0"
• Si = Si−1 + "1" + reverse(invert(Si−1)) for i > 1
Where:
• + denotes concatenation,
• reverse(x) means the string reversed,
• invert(x) changes 0 → 1 and 1 → 0.
You must return the kth bit (1-indexed) in Sn.
________________________________________
🧠 Intuition
Instead of constructing the entire string (which grows exponentially), we can use recursion and observe the pattern:
• The middle element of Sn is always "1".
• The first half is Sn-1.
• The second half is the reversed and inverted version of Sn-1.
If k equals the middle position → return "1".
If k is in the first half → same as findKthBit(n-1, k).
If k is in the second half → inverted result of findKthBit(n-1, length - k + 1).