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 - 1Problem Overview: The binary string S_n is built recursively. S_1 = "0". For every next step: S_n = S_{n-1} + "1" + reverse(invert(S_{n-1})). The task is to return the kth bit (1-indexed) in S_n without necessarily constructing the entire string.
Approach 1: Iterative Construction (O(2^n) time, O(2^n) space)
This method directly simulates the definition of the sequence. Start from S_1 = "0". For each step, generate the next string by appending "1" and then the reversed inverted version of the current string. Inversion flips every bit (0 → 1, 1 → 0) and reversing changes the order. Once the string for n is built, return the character at index k - 1. The approach uses basic string operations and straightforward simulation. The downside is exponential growth: the string length becomes 2^n - 1, which quickly becomes impractical for larger n.
Approach 2: Recursive Mathematical Insight (O(n) time, O(n) space)
The recursive structure of the string reveals a pattern that avoids building it. The total length of S_n is 2^n - 1, and the middle element is always '1'. If k equals the middle index, the answer is immediately '1'. If k is in the left half, the problem reduces to finding the kth bit of S_{n-1}. If k lies in the right half, map it to the mirrored position in the left half using k' = length - k + 1, then invert the result. This works because the right half is exactly reverse(invert(S_{n-1})). The recursion depth is at most n, so the time complexity becomes O(n) with O(n) stack space. This technique leverages properties of recursion and symmetry in the string construction.
Recommended for interviews: Interviewers typically expect the recursive mathematical approach. The brute-force construction shows you understand how the sequence is generated, but recognizing the symmetry and middle pivot demonstrates stronger problem-solving skills. The optimal approach reduces exponential work to a simple recursive reduction based on position.
This 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.
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.
Time Complexity: O(n), limited by the recursion depth of n.
Space Complexity: O(n), due to recursive call stack.
We can observe that for S_n, the first half is the same as S_{n-1}, and the second half is the reverse and negation of S_{n-1}. Therefore, we can design a function dfs(n, k), which represents the k-th character of the n-th string. The answer is dfs(n, k).
The calculation process of the function dfs(n, k) is as follows:
k = 1, then the answer is 0;k is a power of 2, then the answer is 1;k times 2 < 2^n - 1, it means that k is in the first half, and the answer is dfs(n - 1, k);dfs(n - 1, 2^n - k) \oplus 1, where \oplus represents the XOR operation.The time complexity is O(n), and the space complexity is O(n). Here, n is the given n in the problem.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| 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 |
| Case Analysis + Recursion | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Construction | O(2^n) | O(2^n) | Good for understanding the definition and for very small n where full simulation is feasible. |
| Recursive Mathematical Approach | O(n) | O(n) | Best choice for interviews and large n. Avoids constructing the full string using symmetry and recursion. |
Find Kth Bit in Nth Binary String | Detailed Recursion | Dry Run | Leetcode 1545 | codestorywithMIK • codestorywithMIK • 13,911 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