You are given a binary string. During one transformation, replace every character simultaneously using the following rules:

• Replace every '0' with "00".
• Replace every '1' with "10".

Apply this transformation exactly n times and return the value at the specified zero-based index in the resulting string.

Class

BinaryStringTransformer

Method

getBit

public int getBit(String binaryString, int n, int index)

• binaryString is the original string containing only '0' and '1'.
• n is the number of times the transformation must be applied.
• index is the zero-based position to inspect after all transformations.
• Returns 0 or 1, representing the character at the specified position.

Rules

• All characters in the same transformation are replaced simultaneously.
• Each transformation doubles the length of the current string.
• If n is 0, inspect the original string without changing it.
• The complete transformed string does not need to be returned.
• The specified index is guaranteed to be valid.

Constraints

• 1 ≤ binaryString.length() ≤ 100,000
• binaryString contains only '0' and '1'.
• 0 ≤ n ≤ 30
• 0 ≤ index ≤ 1,000,000,000
• index < binaryString.length() * 2n

Examples

Example 1

getBit(binaryString = "1101", n = 1, index = 6)

Output: 1

Explanation: One transformation produces "10100010". The character at zero-based index 6 is '1'.

Example 2

getBit(binaryString = "101", n = 2, index = 5)

Output: 0

Explanation: The first transformation produces "100010", and the second transformation produces "100000001000". The character at zero-based index 5 is '0'.

Example 3

getBit(binaryString = "01011", n = 0, index = 3)

Output: 1

Explanation: No transformation is applied. The character at zero-based index 3 in the original string is '1'.

Example 4

getBit(binaryString = "011", n = 3, index = 16)

Output: 1

Explanation: After three transformations, the resulting string is "000000001000000010000000". The character at zero-based index 16 is '1'.