Find Kth Bit in Nth Binary String
MedPrompt
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))fori > 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 <= 201 <= k <= 2n - 1
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly simulates the process described in the problem. It builds the binary string S_n iteratively, starting from S_1 and applying the given formation rule n-1 times. Once the full string S_n is constructed, it simply retrieves the character at the k-th position.
Algorithm
- Initialize a string
sto"0". - Loop from
i = 2ton. - Inside the loop, construct the string for
S_ibased onS_{i-1}: a. Create an inverted version of the current strings. b. Reverse the inverted string. c. Concatenate the currents, the character"1", and the reversed-inverted string to form the news. - After the loop finishes, the string
swill hold the value ofS_n. - Return the character at index
k-1from the final strings.
Walkthrough
The brute-force method involves generating the entire binary string S_n as defined by the recurrence relation. We start with S_1 = "0". Then, we loop from i = 2 to n, each time generating S_i from S_{i-1} using the formula S_i = S_{i-1} + "1" + reverse(invert(S_{i-1})). This requires helper functions to perform the invert and reverse operations. After n-1 iterations, we will have the complete string S_n. The final step is to return the character at the k-1 index (since k is 1-based). Given the constraint n <= 20, the maximum length of the string is 2^20 - 1, which is just over a million characters. Building and storing this string is feasible but computationally expensive.
class Solution { public char findKthBit(int n, int k) { if (n == 1) { return '0'; } StringBuilder s = new StringBuilder("0"); for (int i = 2; i <= n; i++) { StringBuilder inverted = new StringBuilder(); for (int j = 0; j < s.length(); j++) { inverted.append(s.charAt(j) == '0' ? '1' : '0'); } s.append('1').append(inverted.reverse()); } return s.charAt(k - 1); }}Complexity
Time
O(2^n) - The time taken is dominated by the construction of the final string. The total number of characters generated across all steps is proportional to the sum of lengths of `S_1, S_2, ..., S_n`, which is `O(2^n)`.
Space
O(2^n) - We need to store the entire string `S_n`, which has a length of `2^n - 1`.
Trade-offs
Pros
Simple to understand and implement as it directly follows the problem definition.
Cons
Highly inefficient in terms of both time and space complexity.
Not feasible for larger values of
n(e.g., n > 25) due to exponential growth of the string length.
Instead of constructing the entire string, this approach uses a divide-and-conquer strategy based on the recursive definition of S_n. We can determine the k-th bit by figuring out which of the three parts of S_n (S_{n-1}, the middle '1', or reverse(invert(S_{n-1}))) it falls into, and then recursively solving for the smaller subproblem.
Algorithm
- Define a recursive function, let's call it
solve(n, k). - Base Case: If
n == 1, the string is"0", so return'0'. - Calculate the middle position
mid = 2^(n-1). - Recursive Step:
a. If
k == mid, the character is the central'1'. Return'1'. b. Ifk < mid, the character is in the first part (S_{n-1}). Recursively callsolve(n - 1, k). c. Ifk > mid, the character is in thereverse(invert(S_{n-1}))part. The corresponding position inS_{n-1}is2*mid - k. The bit is the inverse of the bit at that position. Return the result of!solve(n - 1, 2 * mid - k).
Walkthrough
The key observation is that the string S_n has a well-defined structure based on S_{n-1}. The length of S_n is 2^n - 1, and its midpoint is at index mid = 2^(n-1). We can find the k-th bit without building the string:
- If
kis exactlymid, the bit is'1'. - If
kis less thanmid, thek-th bit ofS_nis the same as thek-th bit ofS_{n-1}. We can make a recursive call forS_{n-1}with the samek. - If
kis greater thanmid, it falls into thereverse(invert(S_{n-1}))part. We can find its corresponding position inS_{n-1}, which turns out to be2^n - k. The bit at this new position inS_{n-1}must be inverted. So, we make a recursive call forS_{n-1}with the newkand flip the result. The recursion stops when we reach the base case ofn=1, where the string is simply"0".
class Solution { public char findKthBit(int n, int k) { return solve(n, k); } private char solve(int n, int k) { // Base case if (n == 1) { return '0'; } int mid = 1 << (n - 1); // 2^(n-1) if (k == mid) { return '1'; } else if (k < mid) { return solve(n - 1, k); } else { // k > mid char bit = solve(n - 1, 2 * mid - k); return (bit == '0') ? '1' : '0'; } }}Complexity
Time
O(n) - Each recursive call reduces `n` by 1, and the operations within each call are constant time. The total time is proportional to the recursion depth.
Space
O(n) - Due to the recursion call stack depth, which can go up to `n`.
Trade-offs
Pros
Extremely efficient time complexity compared to the brute-force approach.
Avoids the large memory footprint of generating the full string.
Cons
Uses recursion, which can lead to stack overflow for very large
n(though not an issue for the given constraints).Incurs function call overhead, which can be slightly slower than an equivalent iterative solution.
This approach optimizes the recursive solution by converting it into an iterative process. It eliminates the recursion stack, reducing space complexity to constant. The logic remains the same: we trace the position k down from S_n to S_1, keeping track of how many times an inversion is needed.
Algorithm
- Initialize a variable
flips = 0to count the number of inversions. - Start a loop that continues as long as
n > 1. - In each iteration, calculate the middle position
mid = 2^(n-1). - If
k == mid, the original bit is'1'. We can stop and determine the final bit based on theflipscount. - If
k > mid, it means we are crossing over to the inverted part. We updatekto its mirrored positionk = 2 * mid - kand incrementflips. - If
k < mid, we do nothing tokorflips. - Decrement
nto move to the next smaller string. - After the loop, the base bit is determined. If the loop was exited because
k == mid, the base bit is'1'. Otherwise, the loop finished,nis 1, and the base bit is'0'. - The final result is the base bit if
flipsis even, and the inverted base bit ifflipsis odd.
Walkthrough
We can simulate the recursive calls iteratively. We start with the given n and k and loop downwards. In each step, we check k against the midpoint of the current string S_n. If k is in the right half, we update k to its mirrored position in the left half and increment a flips counter. This counter tracks how many times the bit should be inverted. The loop continues until n becomes 1 or k lands on a midpoint. The final bit is determined by the base bit ('0' for S_1 or '1' for a midpoint) and the parity of the flips counter.
class Solution { public char findKthBit(int n, int k) { int flips = 0; while (n > 1) { int mid = 1 << (n - 1); if (k == mid) { // The original bit is '1'. Apply the flips and return. return (flips % 2 == 0) ? '1' : '0'; } if (k > mid) { // Mirrored position, requires a flip. k = 2 * mid - k; flips++; } // If k < mid, we just move to the next level. n--; } // Base case: n=1, original bit is '0'. Apply flips. return (flips % 2 == 0) ? '0' : '1'; }}Complexity
Time
O(n) - The loop runs at most `n-1` times, and each iteration performs constant time operations.
Space
O(1) - Only a few variables are used to keep track of the state, regardless of the size of `n`.
Trade-offs
Pros
The most efficient solution with optimal time and space complexity.
Avoids recursion overhead and any risk of stack overflow.
Cons
The logic can be slightly less intuitive to derive compared to the direct recursive solution.
Solutions
Solution
class Solution {public char findKthBit(int n, int k) { return (char)('0' + dfs(n, k)); }private int dfs(int n, int k) { if (k == 1) { return 0; } if ((k & (k - 1)) == 0) { return 1; } int m = 1 << n; if (k * 2 < m - 1) { return dfs(n - 1, k); } return dfs(n - 1, m - k) ^ 1; }}class Solution {public: char findKthBit(int n, int k) { function<int(int, int)> dfs = [&](int n, int k) { if (k == 1) { return 0; } if ((k & (k - 1)) == 0) { return 1; } int m = 1 << n; if (k * 2 < m - 1) { return dfs(n - 1, k); } return dfs(n - 1, m - k) ^ 1; }; return '0' + dfs(n, k); }};class Solution: def findKthBit(self, n: int, k: int) -> str: def dfs(n: int, k: int) -> int: if k == 1: return 0 if (k & (k - 1)) == 0: return 1 m = 1 << n if k * 2 < m - 1: return dfs(n - 1, k) return dfs(n - 1, m - k) ^ 1 return str(dfs(n, k))Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.