Skip to main content

Find Kth Bit in Nth Binary String

Find Kth Bit in Nth Binary String​

Problem Statement​

Given two positive integers n and k, the binary string S_n is formed as follows:

  • S1 = "0"
  • S_i = S_(i - 1) + "1" + reverse(invert(S_(i - 1))) for i > 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 S_n. 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 <= 20
  • 1 <= k <= 2^n - 1

Intuition​

The goal of the solution is to find the kth bit in the nth binary string S_n generated by specific rules. Here's the step-by-step intuition behind the algorithm:

  1. Base Case: The base case S1 is initialized as "0".
  2. Building Subsequent Strings: For each subsequent S_i where i > 1, the string is constructed by concatenating S_(i-1), "1", and the inverted and reversed S_(i-1).
  3. String Inversion and Reversal: For constructing the inverted and reversed part, iterate through S_(i-1) from end to start, inverting each bit (0 becomes 1 and 1 becomes 0).
  4. Store Intermediate Strings: Use a hash map (mp) to store each S_i to avoid recomputation and facilitate quick access.
  5. Access the k-th Bit: After constructing S_n, access the k-1 index of the string to get the kth bit.

Time Complexity​

The time complexity of the algorithm is O(2n)O(2^n), where nn is the input integer:

  • Constructing Strings: Each S_i is twice the length of S_(i-1), leading to exponential growth. The length of S_n is 2n−12^n - 1.
  • Inversion and Reversal: Inverting and reversing the previous string takes linear time with respect to its length, leading to exponential time overall due to the doubling size at each step.

Space Complexity​

The space complexity of the algorithm is O(2n)O(2^n) in the worst case:

  • Storage in Hash Map: The hash map stores each intermediate string S_i. The total storage needed is the sum of the lengths of all strings up to S_n, which is dominated by the length of S_n.
  • Final String Storage: The final string S_n has length 2n−12^n - 1, contributing to the space complexity.

Overall, both the time and space complexity are exponential in n.

Code​

C++​

class Solution {
public:
    char findKthBit(int n, int k) {
        
        unordered_map<int,string>mp;
        mp[1]="0";
        for(int i=2;i<=n;i++)
        {
            
            int j=mp[i-1].length()-1;
            string s1="";
            while(j>=0){
            if(mp[i-1][j--]=='0')
            s1+='1';
            else s1+='0';
            }
            
            mp[i]+=mp[i-1]+"1"+s1;
        }
        
        string ans=mp[n];
        return ans[k-1];
    }
};