Find Kth Bit in Nth Binary String

MEDIUM

Description

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

S₁ = "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:

S₁= "0"
S₂= "011"
S₃= "0111001"
S₄ = "011100110110001"

Return the k^th 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: S₃ is "0111001".
The 1^st bit is "0".

Example 2:

Input: n = 4, k = 11
Output: "1"
Explanation: S₄ is "011100110110001".
The 11^th bit is "1".

Constraints:

1 <= n <= 20
1 <= k <= 2ⁿ - 1

Approaches

Checkout 3 different approaches to solve Find Kth Bit in Nth Binary String. Click on different approaches to view the approach and algorithm in detail.

Brute-force String Construction

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 s to "0".
Loop from i = 2 to n.
Inside the loop, construct the string for S_i based on S_{i-1}: a. Create an inverted version of the current string s. b. Reverse the inverted string. c. Concatenate the current s, the character "1", and the reversed-inverted string to form the new s.
After the loop finishes, the string s will hold the value of S_n.
Return the character at index k-1 from the final string s.

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 Analysis

Time Complexity: 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 Complexity: O(2^n) - We need to store the entire string `S_n`, which has a length of `2^n - 1`.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Find Kth Bit in Nth Binary String. Click on different languages to view the code.

Video Solution

Watch the video walkthrough for Find Kth Bit in Nth Binary String

Patterns:

Recursion

Data Structures:

String