• Posts

Problem 1545 Find Kth Bit in Nth Binary String

Problem Statement

Link - Problem 1545

Question

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)) 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 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 <= 20
• 1 <= k <= 2n - 1

Solution

class Solution {
public:
    char findKthBit(int n, int k) {
        int invertCount = 0;
        int len = (1 << n) - 1;

        while (k > 1) {
            if (k == len / 2 + 1) {
                return invertCount % 2 == 0 ? '1' : '0';
            }

            if (k > len / 2) {
                k = len + 1 - k;
                invertCount++;
            }

            len /= 2;
        }
        return invertCount % 2 == 0 ? '0' : '1';
    }
};

Complexity Analysis

| Algorithm              | Time Complexity | Space Complexity |
| ---------------------- | --------------- | ---------------- |
| Recursive Construction | O(log n)        | O(1)             |

Explanation

Intial Thoughts

To approach this problem, we should first understand the pattern in the sequence of binary strings. We notice that each string is formed by concatenating the previous string, a ‘1’, and the reverse of the invert of the previous string. We can use this pattern to find the kth bit in the nth string. Initial steps include identifying the length of the string, locating the position of the kth bit, and determining whether the bit is ‘0’ or ‘1’. We need to consider the effect of inverting and reversing on the bits and how it impacts the kth bit. We also need to consider using a while loop to repeatedly divide the length of the string and adjust the position of the kth bit until we can determine its value.

Intuitive Analysis

Intuitively, we can analyze the problem by understanding the properties of the sequence of binary strings. We recognize that the sequence is formed by iterative concatenation and transformation of the previous string. The key insight is to notice that when k is at the midpoint of the current string length, we can determine the bit based on the inversion count. If k is in the second half of the string, we can reflect it to the first half and increment the inversion count. By repeatedly applying this process, we can narrow down the search space and eventually find the kth bit. This approach allows us to avoid constructing the entire string and instead focus on the properties of the sequence to find the desired bit.

1. Intuition

• The problem involves generating a binary string Sn based on a recursive formula, and we need to find the kth bit in this string.
• To approach this problem, we can analyze the pattern of the binary string and how it changes with each iteration.
• The key insight is to recognize that the string can be divided into two parts: the first half and the second half, which is the reverse of the first half with all bits inverted.
• We can use this insight to determine the kth bit without having to generate the entire string.
• By keeping track of the length of the string and the number of inversions, we can efficiently find the kth bit.
• The solution involves using a while loop to iteratively divide the string in half and adjust the kth bit index accordingly.
• The use of the invertCount variable allows us to keep track of the number of inversions and determine the final bit value.

2. Implementation

• The findKthBit function takes two parameters, n and k, which represent the iteration number and the bit index, respectively.
• The invertCount variable is used to keep track of the number of inversions, and the len variable represents the length of the string.
• The while loop continues until k is 1, at which point we can determine the kth bit based on the invertCount and len values.
• Inside the loop, we check if k is equal to len / 2 + 1, in which case we return the bit value based on the invertCount.
• If k is greater than len / 2, we update k to len + 1 - k and increment the invertCount.
• We then divide len by 2 and repeat the process until k is 1.
• The final bit value is determined by the invertCount and returned as a character.

Complexity Analysis

Time Complexity:

• The time complexity is analyzed by the number of while loop iterations. Each iteration reduces the value of len by half, effectively reducing the problem size by half.
• The dominant operation in this algorithm is the while loop condition check and the subsequent update of k and invertCount. This operation is performed log(n) times, where n is the input size.
• Justification of the Big O classification as O(log n) comes from the mathematical reasoning that the number of iterations of the while loop is proportional to the logarithm of the input size n, since len is reduced by half in each iteration.

Space Complexity:

• The space complexity analysis focuses on the memory usage of the algorithm. The algorithm uses a constant amount of space to store the variables invertCount, len, and k.
• The data structure used in the algorithm is minimal, with only a few primitive type variables. There are no data structures that scale with the input size, such as arrays or linked lists.
• Justification of the space complexity as O(1) comes from the fact that the memory usage does not grow with the input size, and only a constant amount of space is used throughout the execution of the algorithm.

Footnote

This question is rated as Medium difficulty.

Hints

Since n is small, we can simply simulate the process of constructing S1 to Sn.