Find Kth Bit in Nth Binary String
MediumAsked by:
+1
More companies
20 views
Topics:
RecursionBit Manipulation
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
Solution
Clarifying Questions
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
- What are the constraints on N and K? Specifically, what are the maximum possible values for N and K?
- Is N guaranteed to be a positive integer? What about K?
- If K is greater than the length of the Nth binary string, what should I return?
- Could you please provide an example of the expected output for a small N and K, like N=3 and K=2?
- By 'Nth Binary String', do you mean the Nth string generated in the sequence S1 = '0', S(i) = S(i-1) + '1' + invert(reverse(S(i-1)))?
Brute Force Solution
Approach
The brute force method involves generating each binary string one by one until we reach the Nth string. Once we have the Nth binary string, we simply find the Kth bit in that string. This means we build everything out step-by-step until we have our answer.
Here's how the algorithm would work step-by-step:
- Start by building the first string according to the problem's rule.
- Use the first string to build the second string, again following the problem's rule.
- Repeat this process, using the previous string to generate the next string, until you have built the Nth string.
- Once the Nth string is created, simply look at the Kth position in the string to find the Kth bit.
Code Implementation
def find_kth_bit_in_nth_binary_string_brute_force(n, k):
current_string = "0"
for i in range(1, n):
# Build up the binary strings iteratively until we reach the nth string.
inverted_string = ''.join(['1' if bit == '0' else '0' for bit in current_string])
reversed_inverted_string = inverted_string[::-1]
current_string = current_string + "1" + reversed_inverted_string
# After reaching nth string, break since no more computation is required.
# After generating the nth binary string, retrieve the kth bit.
return current_string[k - 1]Big(O) Analysis
Time Complexity
O(2^N) – The brute force solution constructs each binary string from 1 to N. The length of the Nth string is 2^N - 1. Constructing each string involves creating the previous string's inverse and concatenating it. Therefore, the cost of building the Nth string is proportional to its length, which is O(2^N). The cost of building all strings from 1 to N sums to approximately 2^1 + 2^2 + ... + 2^N, which is dominated by the last term, making the total time complexity O(2^N).
Space Complexity
O(2^N) – The brute force solution explicitly builds each binary string from the 1st to the Nth. In the worst-case scenario, the Nth binary string will have a length of approximately 2^N. Therefore, the space complexity is dominated by the storage required for this largest string, leading to O(2^N) auxiliary space.
Optimal Solution
Approach
Instead of generating all the binary strings up to the Nth one, which would take a very long time, we can cleverly figure out the Kth bit by working backwards. We use the properties of how the binary strings are built to efficiently determine the bit without ever constructing the strings themselves.
Here's how the algorithm would work step-by-step:
- Start by understanding that each binary string is built from the previous one using a pattern of inverting and adding a '0' or '1'.
- Instead of building the string from the beginning, start with the bit position we're interested in (K) and work backwards to the first string.
- At each step, determine if the Kth bit was originally from a previous string or if it's new (the '0' or '1' added during the inversion process).
- If the Kth bit was created by inverting a previous string, invert the bit's value and adjust the position to reflect where it came from in the previous string.
- Repeat the process of determining origin and potentially inverting until you reach the very first string (which is simply '0').
- The final bit value you have after tracing back to the first string is your answer.
Code Implementation
def find_kth_bit_in_nth_binary_string(nth_string, kth_bit):
inverted = False
while nth_string > 1:
length_of_previous_string = (1 << nth_string) - 1
# If kth_bit is the last bit, we know its value
if kth_bit == (length_of_previous_string + 1) // 2:
return int(inverted)
# If kth_bit is in the second half, it was generated
if kth_bit > (length_of_previous_string + 1) // 2:
kth_bit = length_of_previous_string - kth_bit + 1
inverted = not inverted
nth_string -= 1
# Return the value after potential inversions.
return int(not inverted)Big(O) Analysis
Time Complexity
O(n) – The algorithm works backward from the nth binary string towards the first. In the worst case, we iterate 'n' times, each time determining whether the kth bit was inherited or inverted from a previous string. Each iteration involves a constant amount of work (inversion and position adjustment). Therefore, the time complexity is directly proportional to 'n', the input number representing the nth string we start from. Since the work done in each step is constant, the overall time complexity simplifies to O(n).
Space Complexity
O(N) – The algorithm works backward from the Nth binary string to the first. The primary space usage comes from the recursive calls, as described in the steps 'Repeat the process of determining origin and potentially inverting until you reach the very first string'. The maximum depth of the recursion stack will be proportional to N, because, in the worst case, it may have to recurse up to the first string. Therefore, the space complexity is O(N).
Edge Cases
| Case | How to Handle |
|---|---|
| n = 0 or k <= 0 | Return an error or throw an exception as the binary string sequence starts from n=1 and k must be positive. |
| n = very large number causing stack overflow with recursive calls | Iterative approach can be used or recursion with memoization to handle large n values to prevent exceeding call stack limit. |
| k exceeds the length of the string generated for nth binary string | Return an error or throw an exception as k cannot be greater than the string length. |
| n = 1, k = 1 | Should return '0' as per the base case S1 = '0'. |
| n is reasonably large (e.g., 20), k is close to the string's maximum length | The algorithm should calculate efficiently and not timeout, testing time complexity is important. |
| k is 1 and n is large | The first bit can be calculated relatively fast as it depends on recursive calls with smaller n. |
| Integer overflow during length calculation of the nth string | Use appropriate data types (long) to prevent integer overflow when computing length of string. |
| If the resulting bit is not '0' or '1' | Return an error or throw an exception indicating the produced result is invalid, which would happen with a bug in the algorithm. |
n = 0 or k <= 0
How to Handle:
Return an error or throw an exception as the binary string sequence starts from n=1 and k must be positive.
n = very large number causing stack overflow with recursive calls
How to Handle:
Iterative approach can be used or recursion with memoization to handle large n values to prevent exceeding call stack limit.
k exceeds the length of the string generated for nth binary string
How to Handle:
Return an error or throw an exception as k cannot be greater than the string length.
n = 1, k = 1
How to Handle:
Should return '0' as per the base case S1 = '0'.
n is reasonably large (e.g., 20), k is close to the string's maximum length
How to Handle:
The algorithm should calculate efficiently and not timeout, testing time complexity is important.
k is 1 and n is large
How to Handle:
The first bit can be calculated relatively fast as it depends on recursive calls with smaller n.
Integer overflow during length calculation of the nth string
How to Handle:
Use appropriate data types (long) to prevent integer overflow when computing length of string.
If the resulting bit is not '0' or '1'
How to Handle:
Return an error or throw an exception indicating the produced result is invalid, which would happen with a bug in the algorithm.
Explore Interview QuestionsTaro 75Google Interview QuestionsMeta Interview QuestionsAmazon Interview QuestionsApple Interview QuestionsNetflix Interview Questions
Explore Interview ExperiencesOpenAI Interview ExperiencesAnthropic Interview ExperiencesPerplexity Interview ExperiencesWindsurf Interview ExperiencesMistral AI Interview Experiences
