Leetcode Problem 1545. Find Kth Bit in Nth Binary String

1545. Find Kth Bit in Nth Binary String

Leetcode Solutions

Recursive Approach with Bit Inversion and Reversal Logic

  1. Define a recursive function findKthBit that takes n and k as arguments.
  2. If n is 1, return '0' as S1 is always '0'.
  3. Calculate the length of Sn which is 2^n - 1.
  4. Find the middle index of Sn which is length / 2 + 1.
  5. If k is equal to the middle index, return '1'.
  6. If k is less than the middle index, recursively call findKthBit with n-1 and k.
  7. If k is greater than the middle index, recursively call findKthBit with n-1 and length - k + 1 to find the corresponding bit in the reversed and inverted Sn-1, and then invert the result before returning it.
UML Thumbnail

Iterative Approach with Bit Manipulation

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...