You are given a binary string s, an integer k, and a 0-based position index.
One expansion step rewrites the string by replacing every 0 with 00 and every 1 with 10, so the string doubles in length. After k expansion steps the string has length s.length * 2^k, far too long to build.
Return the bit (0 or 1) at position index of the string after k expansion steps.
Examples
Example 1
Input: s = "01", k = 1, index = 2
Output: 1
Explanation: One step turns "01" into "0010"; position 2 holds 1.
Example 2
Input: s = "1", k = 2, index = 1
Output: 0
Explanation: "1" -> "10" -> "1000"; position 1 holds 0.
Example 3
Input: s = "101", k = 0, index = 2
Output: 1
Explanation: With no steps the string is unchanged.
Constraints
1≤s.length≤1000
s consists only of 0 and 1
0≤k≤50
0≤index<s.length⋅2k and index≤253−1
Loading editor...
Log in to run your code. Your draft is saved in this browser.Log inSign up