1545. Find Kth Bit in Nth Binary String LeetCode Solution

In this guide, you will get 1545. Find Kth Bit in Nth Binary String LeetCode Solution with the best time and space complexity. The solution to Find Kth Bit in Nth Binary String problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Find Kth Bit in Nth Binary String solution in C++
  4. Find Kth Bit in Nth Binary String solution in Java
  5. Find Kth Bit in Nth Binary String solution in Python
  6. Additional Resources
1545. Find Kth Bit in Nth Binary String LeetCode Solution image

Problem Statement of Find Kth Bit in Nth Binary String

Given two positive integers n and k, the binary string Sn is formed as follows:

S1 = “0”
Si = Si – 1 + “1” + reverse(invert(Si – 1)) for i > 1

Where + denotes the concatenation operation, reverse(x) returns the reversed string x, and invert(x) inverts all the bits in x (0 changes to 1 and 1 changes to 0).
For example, the first four strings in the above sequence are:

S1 = “0”
S2 = “011”
S3 = “0111001”
S4 = “011100110110001”

Return the kth bit in Sn. It is guaranteed that k is valid for the given n.

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”.

Constraints:

1 <= n <= 20
1 <= k <= 2n – 1

Complexity Analysis

  • Time Complexity: O(n^2)
  • Space Complexity: O(n)
See also  584. Find Customer Referee LeetCode Solution

1545. Find Kth Bit in Nth Binary String LeetCode Solution in C++

class Solution {
 public:
  char findKthBit(int n, int k) {
    if (n == 1)
      return '0';
    const int midIndex = pow(2, n - 1);  // 1-indexed
    if (k == midIndex)
      return '1';
    if (k < midIndex)
      return findKthBit(n - 1, k);
    return findKthBit(n - 1, midIndex * 2 - k) == '0' ? '1' : '0';
  }
};
/* code provided by PROGIEZ */

1545. Find Kth Bit in Nth Binary String LeetCode Solution in Java

class Solution {
  public char findKthBit(int n, int k) {
    if (n == 1)
      return '0';
    final int midIndex = (int) Math.pow(2, n - 1); // 1-indexed
    if (k == midIndex)
      return '1';
    if (k < midIndex)
      return findKthBit(n - 1, k);
    return findKthBit(n - 1, midIndex * 2 - k) == '0' ? '1' : '0';
  }
}
// code provided by PROGIEZ

1545. Find Kth Bit in Nth Binary String LeetCode Solution in Python

class Solution:
  def findKthBit(self, n: int, k: int) -> str:
    if n == 1:
      return '0'
    midIndex = pow(2, n - 1)  # 1-indexed
    if k == midIndex:
      return '1'
    if k < midIndex:
      return self.findKthBit(n - 1, k)
    return '1' if self.findKthBit(n - 1, midIndex * 2 - k) == '0' else '0'
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Similar: