Find Kth Bit in Nth Binary String - Bubble Down - O(log k) [JS]
Description Solution: Logic Once we find the count of numbers on the same level as k , we can trace the digit down to the very first level ( S1 = "0" ). On every level, all indices revolve around the middle index, which is always "1" . For every level, reverse the current k into the first half of the sequence. Keep track of how many times we have reversed k , as that determines how many inversions the digit has gone through. Repeat this until we: Reach a middle digit (always guaranteed to be "1" ) or Reach the first level At the end, If the final k is a middle digit, return '0' if it should be inversed, otherwise '1' . If the final k is 1 , return '1' if it should be inversed, otherwise '0' . Example: n = 4 , k = 11 (k = 10 when 0 -indexed) 0123456 7 8901234 0111001 _1_0110001 ( 15 ) 1. | (k = 10 ) 2. | (k = 4 ) 3. | (k = 2 ) 4. | (k = 0 ) ...