1545. Find Kth Bit in Nth Binary String
Problem Description
The problem requires us to generate a binary string Sn
using a specified algorithm and then find the k
th bit in this string for the given n
. The binary string is constructed following these rules:
- Start with
S1
as "0". - For any
i > 1
, the stringSi
is formed by concatenating the previous stringSi-1
with "1" and then adding the reversed and inverted version ofSi-1
.
To clarify, the invert
function flips all bits in a string (0 becomes 1 and 1 becomes 0), and the reverse
function reverses the order of the characters in the string.
A simple illustration shows that the strings grow exponentially as n
increases and the process of creating them is recursive.
The challenge is to find the k
th bit in the constructed string without actually building the entire string, as doing so would be highly inefficient for large n
.
Intuition
The provided solution navigates through the structure of the generated strings using the defined construction algorithm without having to construct the entire string Sn
. Here's how it achieves this:
-
The length of the final string
Sn
is determined by a recursive functioncalcLength
. Since the length is doubled and incremented by 1 with each iteration, this function keeps track and uses a set to record specific positions that would contain the bit "1". -
Base cases are checked: if either
n
is 1 ork
is 1, it's clear from the construction rules that thek
th bit must be "0". -
Knowing that the string is symmetric with a "1" in the middle for any
n > 1
, there are three cases:- If
k
is at the midpoint, return "1". - If
k
is before the midpoint, recursively find thek
th bit inSn-1
. - If
k
is after the midpoint, find the corresponding bit before the midpoint inSn-1
and invert it.
- If
-
A helper function
r
is used to invert a given bit.
The recursive strategy works by leveraging symmetry and the known structure of the string, avoiding unnecessary computation of the full string and thus maintaining efficiency even for large n
.
Learn more about Recursion patterns.
Solution Approach
The solution utilizes a recursive approach, coupled with a set for bookkeeping, to simplify the task of finding the k
th bit in the sequence Sn
. The implementation is structured as follows:
-
The key to the solution lies in understanding the symmetry of the string
Sn
. Each stringSi
fori > 1
is a palindrome with a center bit '1'. This property allows us to only focus on half of the string to find the corresponding value. -
The
calcLength
function calculates the length ofSn
recursively based on the formula that the length ofSi
is twice the length ofSi-1
plus one (len(Si) = 2 * len(Si-1) + 1
). The function also adds the lengthlen(Si)
plus one to the setset
for each iteration, marking positions in the string which result in the bit '1'. -
The
findKthBit
function acts as the primary function to determine thek
th bit:- Base cases check if
k == 1
orn == 1
, and since we know the first character is always '0', it returns '0'. - If the
k
th position has been marked in the set (which was done incalcLength
), it means that thek
th bit is '1'. - Otherwise, the function determines if the
k
th bit is before or after the midpoint ofSn
:-
If
k
is less than the midpoint, recursion is performed to find thek
th bit inSn-1
. -
If
k
is at or beyond the midpoint:- The midpoint bit is always '1', which is directly returned if
k
is exactly the midpoint. - For bits after the midpoint, it must find the corresponding bit before the midpoint in
Sn-1
and invert it using ther
function.
- The midpoint bit is always '1', which is directly returned if
-
- Base cases check if
-
The
r
function is the inverting function, which takes a bit character and returns its inversion.
This implementation forgoes the need to construct the entire Sn
string by smartly exploiting its properties, specifically the palindrome characteristic and marking of certain positions with known bits. The algorithm's efficiency arises from avoiding the explicit generation of the binary string and instead working through recursive calls that "simulate" the construction process minimally to find the required bit.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach using a small example by constructing the string S3
and finding the 5th bit of S3
.
Starting with S1
as "0" and following the problem rules, we can construct the strings S2
and S3
:
S1
is "0"- To get
S2
, we takeS1
, concat a "1", and then add the inverted and reversedS1
: "0 1 1" (where the space indicates the midpoint) - For
S3
, the process is repeated withS2
: "011 1 100" (again, space shows the midpoint)
The length of S3
is 7 bits, and it is a palindrome with the 4th bit being the middle "1". We can visualize it as:
[0] [1] [1] [1] [0] [0] [0]
where brackets show the positions:
1 2 3 4 5 6 7
We want to find the 5th bit:
- As per the rule, the midpoint of
S3
is bit 4 and is "1". So we split the string into two halves around the midpoint:- First half (left of midpoint): [0] [1] [1]
- Second half (right of midpoint): [0] [0] [0]
- We see that the 5th bit is on the right side of the midpoint, which is the reverse and inverted of the first half. So the bit corresponding to the 5th bit is the 3rd bit from the first half (
S2
). - Now we invert that bit. The 3rd bit of
S2
is "1" (sinceS2
is "011"), so its inversion is "0". - We conclude that the 5th bit of
S3
is "0".
This example highlights the application of known symmetry and inversion to determine the value of the k
th bit without constructing the full string Sn
, demonstrating the algorithm's efficiency.
Solution Implementation
1class Solution:
2 def findKthBit(self, n: int, k: int) -> str:
3 if k == 1 or n == 1:
4 # The first bit of any sequence is '0' or the sequence of n=1 is '0'
5 return '0'
6
7 length_set = set()
8 length = self.calculate_length(n, length_set)
9
10 if k in length_set:
11 # All the added lengths in the set represent the middle '1'
12 return '1'
13
14 if k < length // 2:
15 # If k is in the first half, it's the same as the previous sequence
16 return self.findKthBit(n - 1, k)
17 else:
18 # If k is in the second half, invert the (length - k + 1)th bit of the previous sequence
19 return self.invert_bit(self.findKthBit(n - 1, length - k + 1))
20
21 def invert_bit(self, bit: str) -> str:
22 # Inverts the bit '0' to '1' or '1' to '0'
23 return '1' if bit == '0' else '0'
24
25 def calculate_length(self, n: int, length_set: set) -> int:
26 if n == 1:
27 # Base case: the sequence of length 1 has only a single bit '0'
28 return 1
29
30 # Calculate the current length as twice the previous length plus one for the middle '1'
31 current_length = 2 * self.calculate_length(n - 1, length_set) + 1
32 # Add the position of the middle '1' to the length set
33 length_set.add(current_length // 2 + 1)
34 return current_length
35
1class Solution {
2 public char findKthBit(int n, int k) {
3 if (k == 1 || n == 1) {
4 // The first bit of any sequence is '0' or the sequence of n=1 is '0'
5 return '0';
6 }
7 Set<Integer> lengthSet = new HashSet<>();
8 int length = calculateLength(n, lengthSet);
9 if (lengthSet.contains(k)) {
10 // All the added lengths in the set represent the middle '1'
11 return '1';
12 }
13
14 if (k < length / 2) {
15 // If k is in the first half, it's the same as the previous sequence
16 return findKthBit(n - 1, k);
17 } else {
18 // If k is in the second half, invert the (length - k + 1)th bit of the previous sequence
19 return invertBit(findKthBit(n - 1, length - k + 1));
20 }
21 }
22
23 private char invertBit(char bit) {
24 // Inverts the bit '0' to '1' or '1' to '0'
25 return (bit == '0') ? '1' : '0';
26 }
27
28 private int calculateLength(int n, Set<Integer> lengthSet) {
29 if (n == 1) {
30 // Base case: the sequence of length 1 has only a single bit '0'
31 return 1;
32 }
33
34 // Calculate current length as twice the previous length plus one for the middle '1'
35 int currentLength = 2 * calculateLength(n - 1, lengthSet) + 1;
36 // Add the length plus one (position of middle '1') to the set
37 lengthSet.add(currentLength + 1);
38 return currentLength;
39 }
40}
41
1#include <unordered_set>
2using namespace std;
3
4class Solution {
5public:
6 char findKthBit(int n, int k) {
7 // If k is the first bit or n is 1, the k-th bit is always '0'
8 if (k == 1 || n == 1) {
9 return '0';
10 }
11
12 unordered_set<int> lengthSet;
13 int length = calculateLength(n, lengthSet);
14
15 // If k corresponds to the position of the middle '1', return '1'
16 if (lengthSet.count(k)) {
17 return '1';
18 }
19
20 // If k is less than halfway through the string, the k-th bit is the
21 // same as in the sequence for n-1
22 if (k < length / 2) {
23 return findKthBit(n - 1, k);
24 } else {
25 // If k is in the second half, find the bit at the symmetric position
26 // in the sequence for n-1 and invert it
27 return invertBit(findKthBit(n - 1, length - k + 1));
28 }
29 }
30
31private:
32 char invertBit(char bit) {
33 // Inverts the bit: if '0' returns '1', if '1' returns '0'
34 return (bit == '0') ? '1' : '0';
35 }
36
37 int calculateLength(int n, unordered_set<int>& lengthSet) {
38 // Base case for the recursion: the length of the sequence for n=1
39 if (n == 1) {
40 return 1;
41 }
42
43 // Recursive call to calculate the length for n, which is twice the length
44 // of n-1, plus one for the middle '1'
45 int currentLength = 2 * calculateLength(n - 1, lengthSet) + 1;
46
47 // Store current length into the set
48 lengthSet.insert(currentLength);
49
50 return currentLength;
51 }
52};
53
1// Use a global set to store the lengths that have a '1' at the center.
2const lengthSet = new Set<number>();
3
4function findKthBit(n: number, k: number): string {
5 if (k === 1 || n === 1) {
6 // The first bit of any S sequence is '0' or the entire sequence for n=1 is '0'
7 return '0';
8 }
9 const length = calculateLength(n);
10 if (lengthSet.has(k)) {
11 // All the added lengths in the set represent the middle '1'
12 return '1';
13 }
14
15 if (k < length / 2) {
16 // If k is in the first half of the sequence, it's equivalent to the (k)th bit of S_n-1
17 return findKthBit(n - 1, k);
18 } else {
19 // If k is in the second half, invert the (length - k + 1)th bit of S_n-1
20 return invertBit(findKthBit(n - 1, length - k + 1));
21 }
22}
23
24function invertBit(bit: string): string {
25 // Inverts the bit: '0' becomes '1' and '1' becomes '0'
26 return bit === '0' ? '1' : '0';
27}
28
29function calculateLength(n: number): number {
30 if (n === 1) {
31 // Base case: S_1 has a length of 1
32 return 1;
33 }
34
35 // Recursive calculation of the length; length of S_n is twice the length of S_n-1 plus 1 for the '1' in the middle
36 const currentLength = 2 * calculateLength(n - 1) + 1;
37 // Add the position of the '1' in the middle to the set
38 lengthSet.add(currentLength / 2 + 1);
39 return currentLength;
40}
41
Time and Space Complexity
Time Complexity
The time complexity of the findKthBit
function involves multiple recursive calls. The calcLength
function is called recursively to calculate the length of the Sn string. Due to the nature of the construction of Sn, where Sn = Sn-1 + "1" + reverse(invert(Sn-1))
, the length of each subsequent string is double the previous plus one, making it an exponential growth in terms of n.
Let's denote the time complexity of calcLength
as T(n). Therefore, we have:
T(n) = T(n-1) + O(1)
Since this recurses n times, and each recursion is just adding a constant amount of work (besides the recursive call), this simplifies to a linear complexity in terms of n:
T(n) = O(n)
Next, analyzing the recursive calls in the main findKthBit
function, we notice that in the worst case, it can end up recursively calling itself by decreasing n by one each time until n reaches 1. This gives us, in the worst case, a recursion depth of n.
However, we also need to consider that not every recursive call goes all the way down to n=1 due to the early return conditions, so not every call will branch out fully. The recursion only happens to find the kth bit before the midpoint. After the midpoint, the work reduces due to the reuse of the computation as we call findKthBit(n - 1, len - k + 1)
.
As a result, the time complexity is not straightforward to calculate, but we can approximate it by considering that at each level of recursion, the size of the problem is roughly halved (similar to a binary search). The worst-case time complexity thus approximates to:
O(n * log(len))
where len
is the length of the final string Sn which is O(2^n)
.
Combining all the recursive calls and operations within each call, the total time complexity roughly approximates to:
O(n^2)
This is considering that each recursive call to findKthBit
has a cost that doubles each time with a diminishing number of calls due to halving of k as well.
Space Complexity
The space complexity is governed by both the recursive call stack and the space taken by the HashSet to store specific lengths at each level of recursion.
The maximum depth of the recursion stack is n, for the recursive calls to findKthBit
.
The HashSet grows in size linearly with n, since a new length is added for each level of recursion in calcLength
.
Therefore, the space complexity is:
O(n) + O(n) = O(n)
Overall, the space complexity of the function is linear with respect to n due to the recursion stack and the HashSet storage:
O(n)
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?
Recommended Readings
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.