Find K-th Bit in N-th Binary String in Java

Problem Statement

Given two integers n and k. The problem generates a sequence where each S_n is formed recursively based on the previous string. The transformation follows the following pattern:

• S1 = "0"
• S_n = S_n−1 + "1" + reverse(invert(Sn−1))

where:

• Reverse: Flips the order of characters.
• Invert: Changes '0' to '1' and '1' to '0'.

The task is to find the kth bit in S_n without explicitly constructing the entire string due to its exponential growth.

Example 1:

Input: n = 4, k = 11

Output: 1

Explanation: S₄ = "011100110110001", and the 11th bit is '1'. It maps to position 5 in S₃ and gets inverted.

Example 2:

Input: n = 2, k = 3

Output: 1

Explanation: S₂ = "0110", and the 3rd bit is '1'. Since 3 is the middle position, we return '1'.

Approach 1: Recursive Simulation Approach

The approach recursively without explicitly constructing the entire string S_n. It generates the sequence; we determine the position of k based on the recursive properties of the transformation.

Algorithm

Step 1: If n=1n, return '0', as S1 = "0".

Step 2: The length of S_n is (2ⁿ−1).

Step 3: The middle bit is always at position (length/2) + 1 and is '1'.

Step 4: If k is in the left half (k < mid), it is the same as S_n−1.

Step 5: If k is in the right half (k > mid), it maps to (length – k + 1) in S_n−1 but is inverted.

Step 6: Solve for the new mapped index.

Let’s implement the above steps in a Java program.

Output:

 
1   

Complexity

Time Complexity: The time complexity of a program is O(n). This is because each recursive call reduces n by 1, leading to at most n recursive calls.

Space Complexity: The space complexity of a program is O(n). This is because of recursive function calls stored in the call stack.