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.
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; }}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.