Given a binary string S . Perform R iterations on string S, where in each iteration 0 becomes 01 and 1 becomes 10. Find the Nth character (considering 0 based indexing) of the string after performing these R iterations. (See Examples for better understanding)
Example 1:
Input:
S = 101
R = 2 
N = 3
Output:
1
Explanation : 
After 1st iteration S becomes 100110.
After 2nd iteration, S = 100101101001
Now, we can clearly see that the character
at 3rd index is 1, and so the output.
Example
Input:
S = 11
R = 1 
N = 3
Output:
0
Explanation: 
After 1st iteration S becomes 1010.
Now, we can clearly see that the character
at 3rd index is 0, and so the output.
Your task:
You don't need to read input or print anything. Your task is to complete the function nthCharacter() which takes the string S and integers R and N as input parameters and returns the N-th character of the string after performing R operations on S.
 
Expected Time Complexity: O(r*len(s))
Expected Auxilary Space: O(len(s))
Constraints: 
1 ≤ String length ≤ 10^{3}
1 ≤ R ≤ 20
0 ≤ N < Length of final string

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: #User function Template for python3

class Solution:
    def nthCharacter(self, S, R, N):
        # code here

Solutions:
class Solution:

	def nthCharacter(self, S, R, N):
		f = N // 2 ** R
		k = N % 2 ** R
		x = S[f]

		def manu(N, k):
			if N == 0:
				return x
			parent = manu(N - 1, k // 2)
			if parent == '1' and k % 2 == 0 or (parent == '0' and k % 2 == 1):
				return '1'
			else:
				return '0'
		return manu(R, k)


class Solution:

	def nthCharacter(self, S, R, N):
		f = 1
		fl = 0
		while R:
			fl = N >> 1
			if 2 * fl == N:
				f = int(not f ^ 1)
			else:
				f = int(not f ^ 0)
			N >>= 1
			R -= 1
		if f == 0:
			return str(int(not int(S[fl])))
		else:
			return S[fl]


class Solution:

	def nthCharacter(self, s, r, n):
		f = ''
		it = 0
		l = 0
		while l <= n:
			it += 1
			l = it * pow(2, r)
		p = pow(2, r)
		n %= p
		if it == 0:
			it += 1
		f += s[it - 1]
		for i in range(r):
			s = ''
			for j in range(len(f)):
				if f[j] == '1':
					s += '10'
				else:
					s += '01'
			f = s
		return f[n]


class Solution:

	def nthCharacter(self, S, R, N):
		x = 0
		y = 0
		while x < N + 1:
			y += 1
			x = y * 2 ** R
		power = 2 ** R
		N %= power
		if y == 0:
			y += 1
		r = S[y - 1]
		for i in range(R):
			s = ''
			for i in r:
				if i == '1':
					s += '10'
				else:
					s += '01'
			r = s
		return r[N]


import math

class Solution:

	def nthCharacter(self, S, R, N):
		char = N + 1
		sqr = 1
		i = 0
		while i < R:
			sqr *= 2
			char /= 2
			i += 1
		find = math.ceil(char)
		get = int(char % 1 * sqr)
		i = 0
		value = S[find - 1]
		while i < R:
			res = ''
			j = 0
			while j < len(value):
				if value[j] == '1':
					res += '10'
				else:
					res += '01'
				j += 1
			value = res
			i += 1
		return value[get - 1]


class Solution:

	def nthCharacter(self, S, R, N):
		N = N + 1
		f = ''
		l = 0
		it = 0
		while l < N:
			it += 1
			l = it * pow(2, R)
		p = pow(2, R)
		N -= 1
		N %= p
		if it == 0:
			it += 1
		f = S[it - 1]
		for j in range(R):
			temp = ''
			for i in f:
				if i == '0':
					temp += '01'
				else:
					temp += '10'
			f = temp
		return f[N]


class Solution:

	def nthCharacter(self, S, R, N):
		if R == 0:
			return int(S[N])
		if N % 2 == 0:
			return self.nthCharacter(S, R - 1, N // 2)
		if N % 2 == 1:
			p = self.nthCharacter(S, R - 1, (N - 1) // 2)
			if p == 0:
				return 1
			else:
				return 0
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		snr = input().split()
		(S, R, N) = (snr[0], int(snr[1]), int(snr[2]))
		ob = Solution()
		print(ob.nthCharacter(S, R, N))


class Solution:

	def nthCharacter(self, s, r, n):
		n += 1
		f = ''
		it = 0
		l = 0
		while l < n:
			it += 1
			l = it * pow(2, r)
		p = pow(2, r)
		n -= 1
		n %= p
		if it == 0:
			it += 1
		f += s[it - 1]
		for i in range(r):
			s = ''
			for j in range(len(f)):
				if f[j] == '1':
					s += '10'
				else:
					s += '01'
			f = s
		return f[n]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		snr = input().split()
		(S, R, N) = (snr[0], int(snr[1]), int(snr[2]))
		ob = Solution()
		print(ob.nthCharacter(S, R, N))


class Solution:

	def nthCharacter(self, s, r, n):
		f = False
		while r:
			r -= 1
			f ^= n & 1
			n >>= 1
		return int(s[n]) ^ f
		s = s[int(n / 2 ** r)]
		for i in range(r):
			s = s.replace('1', 't').replace('0', '01').replace('t', '10')
		return s[n % 2 ** r]


class Solution:

	def nthCharacter(self, s, r, n):
		d = {'0': '01', '1': '10'}
		s = s[int(n / 2 ** r)]
		for i in range(r):
			s = ''.join([d[i] for i in s])
		return s[n % 2 ** r]


class Solution:

	def nthCharacter(self, S, R, N):
		flips = 0
		p = 2 ** R
		i = N % p
		N = N // p
		while i > 0:
			if i % 2:
				flips += 1
			i = i // 2
		if S[N] == '0':
			if flips % 2 == 1:
				return 1
			else:
				return 0
		elif flips % 2 == 1:
			return 0
		else:
			return 1


class Solution:

	def nthCharacter(self, s, R, N):
		char_map = {'0': '01', '1': '10'}
		S = s[int(N / 2 ** R)]
		for i in range(R):
			S = ''.join([char_map[c] for c in S])
		return S[N % 2 ** R]


class Solution:

	def nthCharacter(self, S, R, N):
		char_map = {'0': '01', '1': '10'}
		S = S[int(N / 2 ** R)]
		for i in range(R):
			S = ''.join([char_map[c] for c in S])
		return S[N % 2 ** R]
		s = ''
		while R > 0:
			for i in range(len(S)):
				if S[i] == '1':
					s += '10'
				else:
					s += '01'
			R -= 1
		S = s
		e = S[N]
		return e


class Solution:

	def nthCharacter(self, S, R, N):

		def helper(s, r, n):
			if r == 0:
				return s[n]
			idx = n // 2 ** r
			if s[idx] == '1':
				return helper('10', r - 1, n - idx * 2 ** r)
			else:
				return helper('01', r - 1, n - idx * 2 ** r)
		return helper(S, R, N)


class Solution:

	def nthCharacter(self, S, R, N):
		d = {'0': '01', '1': '10'}
		i = N + 1
		for s in range(R, -1, -1):
			k = 2 ** s
			q = i // k
			r = i % k
			if r == 0:
				S = d[S[q - 1]]
				i -= k * (q - 1)
			else:
				S = d[S[q]]
				i -= k * q
		return S[i - 1]


import math

class Solution:

	def nthCharacter(self, S, R, N):
		x = int(pow(2, R))
		c = S[N // x]
		i = N % x
		for j in range(R):
			s = str()
			for k in c:
				s += '10' if k == '1' else '01'
			c = s
		return c[i]


class Solution:
	table = [['', ''] for i in range(21)]
	table[0] = ['0', '1']

	def nthCharacter(self, S, R, N):

		def lookup(ch, r):
			if self.table[r][int(ch)]:
				return self.table[r][int(ch)]
			else:
				last = lookup(ch, r - 1)
				new = ''
				for ch in last:
					if ch == '0':
						new += '01'
					else:
						new += '10'
				self.table[r][int(ch)] = new
				return new
		block = N // 2 ** R
		N = N % 2 ** R
		root = int(S[block])
		if N == 0:
			return root
		flip = True
		while N > 1:
			if N & 1:
				flip = not flip
			N = N >> 1
		return int(not root) if flip else root
		return s[N]


class Solution:

	def nthCharacter(self, S, R, N):
		flip = False
		while R:
			R -= 1
			flip ^= N & 1
			N >>= 1
		return int(S[N]) ^ flip


class Solution:

	def nthCharacter(self, S, R, N):
		a = [N]
		for i in range(R):
			a.append(int(N / 2))
			N = int(N / 2)
		j = len(a) - 1
		x = int(S[a[j]])
		while j > 0:
			if x == 0 and a[j - 1] % 2 == 0 or (x == 1 and a[j - 1] % 2 == 1):
				x = 0
			else:
				x = 1
			j -= 1
		return x


class Solution:

	def nthCharacter(self, S, R, N):
		dic = {'1': '10', '0': '01'}
		i = N // 2 ** R
		d = S[i]
		s = d
		rem = N % 2 ** R
		for j in range(R):
			k = 0
			s = ''
			while k < len(d):
				s += dic[d[k]]
				k += 1
			d = s
		return d[rem]


class Solution:

	def nthCharacter(self, S, R, N):
		(one, zero) = ('1', '0')
		for i in range(R):
			s = ''
			for i in one:
				if i == '1':
					s += '10'
				else:
					s += '01'
			one = s
			s = ''
			for i in zero:
				if i == '1':
					s += '10'
				else:
					s += '01'
			zero = s
		n = N // len(one)
		r = N % len(one)
		if S[n] == '1':
			return one[r]
		else:
			return zero[r]


import math

class Solution:

	def nthCharacter(self, S, R, N):
		prev_index = -1
		tmp_str = S
		mul = int(math.pow(2, R))
		for r in range(R + 1):
			n = len(tmp_str)
			j = 0
			while j < n:
				start = prev_index + 1
				end = start + mul - 1
				if start == end and N == start:
					return tmp_str[j]
				if N >= start and N <= end:
					if tmp_str[j] == '1':
						tmp_str = '10'
					else:
						tmp_str = '01'
					break
				else:
					prev_index = end
				j += 1
			mul = mul // 2
		return '-1'


class Solution:

	def nthCharacter(self, S, R, N):
		length = len(S) * 2 ** R
		sub_length = (N + 1) // 2 ** R
		ind = N - sub_length * 2 ** R
		if ind >= 0:
			if sub_length < len(S):
				sub_string = S[sub_length]
			else:
				sub_string = S[-1]
		elif sub_length < len(S):
			sub_string = S[sub_length - 1]
		else:
			sub_string = S[-1]
		j = R
		while j > 0:
			sub_string = list(sub_string)
			for i in range(len(sub_string)):
				if sub_string[i] == '1':
					sub_string[i] = '10'
				else:
					sub_string[i] = '01'
			sub_string = ''.join(sub_string)
			j -= 1
		return sub_string[ind]


class Solution:
	transCache = None

	def nthCharacter(self, S, R, N):
		characterNum = 1 << R
		originalCharacter = N // characterNum
		characterIndex = N % characterNum
		lastIterationCharacters = self.transform(S[originalCharacter], R)
		return lastIterationCharacters[characterIndex]

	def transform(self, S, R):
		if self.transCache:
			return self.transCache[S, R]
		self.transCache = {}
		self.transCache['1', 0] = '1'
		self.transCache['0', 0] = '0'
		r = 1
		while r <= 20:
			self.transCache['1', r] = self.transCache['1', r - 1] + self.transCache['0', r - 1]
			self.transCache['0', r] = self.transCache['0', r - 1] + self.transCache['1', r - 1]
			r += 1
		return self.transCache[S, R]


class Solution:

	def nthCharacter(self, S, R, N):
		f = False
		for _ in range(R):
			f ^= N & 1
			N >>= 1
		return int(S[N]) ^ f


import math

class Solution:

	def comp(self, table):
		output = ''
		tab = ['1', '0']
		for i in table:
			output += tab[int(i)]
		return output

	def nthCharacter(self, S, R, N):
		if N < 0:
			return -1
		if R == 0:
			return S[N]
		index = math.floor(N / 2 ** R)
		bit_index = N % 2 ** R
		word = S[index]
		for i in range(R):
			word += self.comp(word)
			if bit_index < len(word):
				return word[bit_index]


class Solution:

	def nthCharacter(self, S, R, N):
		if R == 0:
			return S[N]
		mul = 2 ** R
		i = N // mul
		Nnext = N % mul
		snext = '01'
		if S[i] == '1':
			snext = '10'
		return self.nthCharacter(snext, R - 1, Nnext)


class Solution:

	def generate(self, str_):
		op = ''
		for char in str_:
			if char == '0':
				op += '01'
			else:
				op += '10'
		return op

	def nthCharacter(self, S, R, N):
		rem = N % 2 ** R
		idx = int(N / 2 ** R)
		char = S[idx]
		for i in range(R):
			char = self.generate(char)
		return char[rem]


class Solution:

	def nthCharacter(self, S, R, N):
		c = 0
		s1 = ''
		x = 0
		n = len(S)
		for i in range(n + 1):
			c = i * 2 ** R
			if c == N:
				x = i
				break
			elif c > N:
				x = i - 1
				break
		s1 = S[x]
		c = x * 2 ** R
		N = N - c
		x = 0
		S = ''
		for i in range(R):
			if x == 0:
				for i in range(len(s1)):
					if s1[i] == '0':
						S += '01'
					else:
						S += '10'
				x = 1
				s1 = ''
			else:
				for i in range(len(S)):
					if S[i] == '0':
						s1 += '01'
					else:
						s1 += '10'
				x = 0
				S = ''
		S = S + s1
		return S[N]


class Solution:

	def operation(self, S):
		re_str = []
		for l in S:
			if l == '0':
				re_str.append('01')
			else:
				re_str.append('10')
		return ''.join(re_str)

	def nthCharacter(self, S, R, N):
		ret = ''
		if (R == 0) & (N >= len(S)):
			return 0
		if R == 1:
			for c in S:
				if c == '0':
					ret += '01'
				else:
					ret += '10'
			return ret[N]
		for i in range(len(S)):
			temp = ''
			if S[i] == '0':
				temp = '0110'
			else:
				temp = '1001'
			t = R - 2
			while t > 0:
				temp1 = temp[0:int(len(temp) / 2)]
				temp2 = temp[int(len(temp) / 2):int(len(temp))]
				temp2 += temp1
				temp += temp2
				t -= 1
			ret += temp
			if len(ret) > N:
				return ret[N]
			else:
				N -= len(temp)
				ret = ''
		return 0


class Solution:

	def nthCharacter(self, S, R, N):
		j = N % 2 ** R
		si = S[N // 2 ** R]
		for k in range(R):
			st = ''
			for v in si:
				if v == '0':
					st += '01'
				else:
					st += '10'
			si = st
		return si[j]


class Solution:

	def nthCharacter(self, S, R, N):
		k = 0
		while R > 0:
			k ^= N & 1
			N >>= 1
			R -= 1
		return int(S[N]) ^ k