Leetcode 1545: Find Kth Bit in Nth Binary String

Input: The input consists of two integers n and k. The integer n represents the index of the string Sn and k represents the position of the bit we need to return.

Example: n = 3, k = 2

Constraints:

• 1 <= n <= 20

• 1 <= k <= 2^n - 1

Output: Return the kth bit of the string Sn.

Example: Output: 1

Constraints:

• The string Sn is formed recursively, and the kth bit must be accessed in constant time.

Goal: The goal is to find an efficient way to compute the kth bit of the string Sn without constructing the entire string.

Steps:

• 1. The recursive construction of the string leads to exponential growth in length. Instead of constructing the full string, we need to deduce the position of the kth bit.

• 2. Utilize the recursive structure of the string to find a method that tracks the bit without constructing the entire string.

Goal: The input size should not exceed the bounds given by the constraints. The length of Sn grows exponentially, so direct construction of Sn is inefficient.

Steps:

• 1 <= n <= 20

• 1 <= k <= 2^n - 1

Assumptions:

• The problem guarantees that k will be a valid index for the given n.

• Input: n = 3, k = 2

• Explanation: For n = 3, we know S3 = '0111001'. The 2nd bit is '1'.

• Input: n = 4, k = 7

• Explanation: For n = 4, we know S4 = '011100110110001'. The 7th bit is '0'.

Approach: We need to leverage the recursive nature of the sequence to compute the kth bit without constructing the full sequence.

Observations:

• The length of Sn grows exponentially with n. Thus, constructing the entire string is inefficient.

• We can trace the position of k within the recursive structure of Sn.

• We will work backwards to deduce the bit's value using the recursive properties of the sequence.

Steps:

• 1. Start by checking if the kth bit lies in the first part (Si-1) of the recursive construction.

• 2. If k is in the middle (the added '1'), return '1'.

• 3. If k is in the third part (reverse(invert(Si-1))), adjust k and repeat the process recursively.

Empty Inputs:

• The string Sn is never empty, as n >= 1.

Large Inputs:

• For large values of n (close to 20), ensure the solution efficiently handles the exponential growth of the string.

Special Values:

• When k equals the maximum possible value (2^n - 1), ensure the solution handles boundary conditions correctly.

Constraints:

• Ensure the solution runs within time limits for all values of n and k.

char findKthBit(int n, int k) {

    string s = "0";
    
    for(int i = 2; i <= n; i++) {
        string tmp = s;
        s += '1';
        for(int j = tmp.size() - 1; j >= 0; j--) {
            
            s += (tmp[j] == '0') ? '1':'0';
            
        }
    }

    return s[k-1];
}

1 : Function Declaration

char findKthBit(int n, int k) {

This line declares the function `findKthBit`, which takes two integers `n` and `k` as input and returns a character (either '0' or '1') representing the k-th bit of the binary string for the given value of n.

2 : String Initialization

    string s = "0";

The string `s` is initialized to "0". This will be used to store the binary sequence that will be modified iteratively.

3 : Loop

    for(int i = 2; i <= n; i++) {

A for loop starts from i = 2 and runs until i = n, progressively building the binary string `s` by following the given pattern.

4 : String Copy

        string tmp = s;

Create a copy of the current string `s` into the variable `tmp`, which will be used for further manipulation.

5 : String Update

        s += '1';

Add a '1' to the string `s`. This is part of the pattern where each iteration appends a '1' to the string.

6 : Inner Loop

        for(int j = tmp.size() - 1; j >= 0; j--) {

A for loop starts from the last character of `tmp` and iterates backward, flipping the bits of the string to form the new pattern.

7 : Bit Flipping

            s += (tmp[j] == '0') ? '1' : '0';

For each character in `tmp`, append the flipped bit to `s`. If the character is '0', append '1', otherwise append '0'.

8 : Return Statement

    return s[k-1];

Return the k-th character from the string `s`. Since indexing starts at 0, we subtract 1 from `k` to get the correct index.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: Since we work recursively with the structure of Sn, the time complexity depends on the recursion depth, which is O(n).

Best Case: O(1)

Worst Case: O(1)

Description: We only store a few variables to track the recursive steps, so the space complexity is O(1).

Leetcode 1545: Find Kth Bit in Nth Binary String

Explore →