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 > 1Where + 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 <= 201 <= k <= 2n - 1This approach involves directly simulating the sequence construction up to the desired nth binary string and retrieving the k-th bit from it. Since the problem ensures n and k are constrained, this method remains efficient enough.
The solution constructs each sequence iteratively using the relationship: Si = Si-1 + '1' + reverse(invert(Si-1)). We manage a buffer array S that stores each sequence step-by-step until Sn is reached, whereupon we simply return the k-th position.
C++
Java
Python
C#
JavaScript
Time Complexity: O(2^n), as each step fully constructs the sequence of size approximately 2^n.
Space Complexity: O(2^n), owing to storing the full sequence.
This approach leverages the recursive nature and mathematical properties of the sequence to find the k-th bit without constructing the entire string. By recognizing the symmetry and structure, we use recursive calculations to directly determine the desired bit.
The recursive approach utilizes the breakdown of the sequence into its two halves with a central break. We trace the k-th bit's location through recursion: if it's in the right half, consider the transformed position in the left. This efficient strategy provides a path to directly compute the k-th bit without constructing full strings.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), limited by the recursion depth of n.
Space Complexity: O(n), due to recursive call stack.
| Approach | Complexity |
|---|---|
| Iterative Construction | Time Complexity: O(2^n), as each step fully constructs the sequence of size approximately 2^n. |
| Recursive Mathematical Approach | Time Complexity: O(n), limited by the recursion depth of |
Find Kth Bit in Nth Binary String - Leetcode 1545 - Python • NeetCodeIO • 8,620 views views
Watch 9 more video solutions →Practice Find Kth Bit in Nth Binary String with our built-in code editor and test cases.
Practice on FleetCode