Given a decimal number m. Convert it into a binary string and apply n iterations, in each iteration 0 becomes 01, and 1 becomes 10. Find the kth (1-indexing) character in the string after the nth iteration.
Example 1:
Input: m = 5, n = 2, k = 5
output: 0
Explanation: Binary representation of m 
is "101", after one iteration binary 
representation will be "100110", and after 
second iteration binary representation 
will be "100101101001". 
Example 1:
Input: m = 5, n = 2, k = 1
output: 1
Explanation: Binary representation of m 
is "101", after one iteration binary 
representation will be "100110", and after 
second iteration binary representation
will be "100101101001". 
Your task:
You do not need to read any input or print anything. The task is to complete the function kthCharacter(), which takes 3 integers m, n, and k as input and returns a character. 
Expected Time Complexity: O(2^{n})
Expected Auxiliary Space: O(2^{n})
Constraints:
0 ≤ m ≤ 50
0 ≤ n ≤ 10
K is a valid index

Difficulty: EASY
Tags: String algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(2^{n})
Expected Auxiliary Space: O(2^{n})

Starter code:
#User function Template for python3

class Solution:

	def kthCharacter(self, m, n, k):

		# code here

Solutions:
class Solution:

	def kthCharacter(self, m, n, k):
		bstr = self.d2b(m)
		s = ''
		for i in range(n):
			for j in range(len(bstr)):
				if bstr[j] == '1':
					s += '10'
				else:
					s += '01'
			bstr = s
			s = ''
		return bstr[k - 1]

	def d2b(self, m):
		if m == 0:
			return '0'
		c = 1
		n = 2
		while m - n > 1:
			n *= 2
			c += 1
		if m - n < 0:
			c -= 1
		r = [0] * (c + 1)
		if m % 2 != 0:
			r[len(r) - 1] = 1
			m -= 1
		for i in range(c, 0, -1):
			t = 2 ** i
			if m - t >= 0:
				r[c - i] = 1
				m -= t
		return ''.join((str(e) for e in r))


class Solution:

	def kthCharacter(self, m, n, k):
		b = bin(m)[2:]
		l = len(b)
		for i in range(n):
			s = ''
			for j in range(len(b)):
				if b[j] == '0':
					s += '01'
				else:
					s += '10'
			b = s
		return b[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		bin_num = bin(m)[2:]
		for i in range(n):
			new_num = []
			for j in bin_num:
				if j == '1':
					new_num.append('10')
				else:
					new_num.append('01')
			bin_num = ''.join(new_num)
		return bin_num[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		num = bin(m)
		index = num.index('b')
		num = num[index + 1:]
		res = 0
		for i in range(n):
			j = 0
			while j < len(num):
				if num[j] == '0':
					num = num[:j + 1] + '1' + num[j + 1:]
					j += 1
				else:
					num = num[:j + 1] + '0' + num[j + 1:]
					j += 1
				j += 1
		return num[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		bun_str = bin(m).replace('0b', '')
		for i in range(n):
			bun_str = bun_str.replace('0', '%temp%').replace('1', '10').replace('%temp%', '01')
		return bun_str[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		l = list(bin(m).replace('0b', ''))
		for j in range(n):
			for i in range(len(l)):
				if l[i] == '1':
					l[i] = '10'
				else:
					l[i] = '01'
			l = list(''.join(l))
		return int(l[k - 1])


class Solution:

	def kthCharacter(self, m, n, k):
		b = bin(m)
		b = b[2:]
		for i in range(n):
			res = ''
			for i in b:
				if i == '1':
					res += '10'
				else:
					res += '01'
			b = res
		return b[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		l = ''
		l += bin(m)
		l = l[2:]
		for i in range(n):
			l = l.replace('1', 'a')
			l = l.replace('0', 'b')
			l = l.replace('a', '10')
			l = l.replace('b', '01')
		return l[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		bin = ''
		while m >= 2:
			bin += str(m % 2)
			m = m // 2
		bin += str(m)
		bin = bin[::-1]
		ans = ''
		for i in range(n):
			for j in bin:
				if j == '0':
					ans += '01'
				else:
					ans += '10'
			bin = ans
			ans = ''
		return bin[k - 1]


class Solution:

	def solve(self, dec, n, ans):
		if n - 1 < 0:
			ans += dec
			return
		lis = []
		for i in range(len(dec)):
			if dec[i] == '0':
				lis += ['0', '1']
			if dec[i] == '1':
				lis += ['1', '0']
		self.solve(lis, n - 1, ans)

	def kthCharacter(self, m, n, k):
		dec = bin(m)
		dec = dec.replace('0b', '')
		dec = list(dec)
		ans = []
		self.solve(dec, n, ans)
		return ans[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		b = bin(m)[2:]
		t = len(b)
		for _ in range(n):
			temp = ''
			for i in range(len(b)):
				if b[i] == '0':
					temp += '01'
				else:
					temp += '10'
			b = temp
		return b[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		if m == 0 and n == 0:
			return 0
		li = []
		while m != 0:
			di = m % 2
			li.append(str(di))
			m //= 2
		li = li[::-1]
		if len(li) == 0:
			li.append('0')
		while n != 0:
			le = len(li)
			for i in range(le):
				a = li.pop(0)
				if a == '1':
					li.append('1')
					li.append('0')
				else:
					li.append('0')
					li.append('1')
			n -= 1
		if k <= len(li):
			return li[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		m = format(m, 'b')
		ans = ''
		res = m
		for i in range(n):
			ans = res
			res = ''
			for i in ans:
				if i == '1':
					res += '10'
				else:
					res += '01'
		return res[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		binVal = ''.join(bin(m))[2:]
		temp = ''
		for i in range(0, n):
			for num in binVal:
				if num == '0':
					temp += '01'
				else:
					temp += '10'
			binVal = temp
			temp = ''
		return binVal[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		k1 = str(bin(m)[2:])
		k1 = list(k1)
		while n > 0:
			for index in range(len(k1)):
				if k1[index] == '1':
					k1.pop(index)
					k1.insert(index, '10')
				else:
					k1.pop(index)
					k1.insert(index, '01')
				s = ''.join(k1)
			k1 = list(s)
			n -= 1
		return k1[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		num = bin(m)
		num = num[2:]
		count = 1
		str_num = ''
		while count <= n:
			for i in num:
				if i == '1':
					str_num += '10'
				else:
					str_num += '01'
			num = str_num
			str_num = ''
			count += 1
		return num[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		a = bin(m)[2:]
		w = list(a)
		for i in range(n):
			x = ''
			for j in w:
				if j == '1':
					x += '10'
				else:
					x += '01'
			w = list(x)
		return w[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		s = ''
		if m == 0:
			s = '0'
		while m:
			temp = m % 2
			s += str(temp)
			m = m >> 1
		s = s[::-1]
		s1 = ''
		for x in range(n):
			for j in range(len(s)):
				if s[j] == '0':
					s1 += '01'
				else:
					s1 += '10'
			s = s1
			s1 = ''
		return s[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		b = bin(m).replace('0b', '')
		c = list(b)
		for i in range(n):
			for j in range(len(c)):
				if c[j] == '1':
					c[j] = '10'
				else:
					c[j] = '01'
			b = ''.join((str(i) for i in c))
			c = list(b)
		return c[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		binary = str(bin(m).replace('0b', ''))
		for i in range(n):
			binary = binary.replace('0', 'z')
			binary = binary.replace('1', 'o')
			binary = binary.replace('z', '01')
			binary = binary.replace('o', '10')
		return binary[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		binary_str = bin(m)[2:]
		for i in range(n):
			new_str = ''
			for ch in binary_str:
				if ch == '0':
					new_str += '01'
				else:
					new_str += '10'
			binary_str = new_str
		return binary_str[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		binary = bin(m).replace('0b', '')
		new_binary = ''
		for count in range(n):
			for char in binary:
				if char == '0':
					new_binary = new_binary + '01'
				else:
					new_binary = new_binary + '10'
			binary = new_binary
			new_binary = ''
		return binary[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		x = bin(m)[2:]
		s = ''
		while n > 0:
			n = n - 1
			s = ''
			for i in range(len(x)):
				if x[i] == '0':
					s = s + '01'
				else:
					s = s + '10'
			x = s
			i = 0
		if s != '':
			return s[k - 1]
		else:
			return x[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		temp = bin(m)
		temp = temp[2:]
		ans = ''
		while n > 0:
			for i in temp:
				if i == '1':
					ans = ans + '10'
				else:
					ans = ans + '01'
			temp = ans
			ans = ''
			n = n - 1
		return temp[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		l = bin(m)[2:]
		for i in range(n):
			t = ''
			for i in l[:k]:
				if i == '0':
					t += '01'
				else:
					t += '10'
			l = t
		return l[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		s = str(bin(m)[2:])
		for i in range(n):
			s1 = ''
			for i in s:
				if i == '1':
					s1 += '10'
				else:
					s1 += '01'
			s = s1
		return s[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		j = 0
		str1 = ''
		str2 = str(bin(m).replace('0b', ''))
		while j < n:
			for i in str2:
				if i == '0':
					str1 += '01'
				else:
					str1 += '10'
			j += 1
			str2 = str1
			str1 = ''
		return int(str2[k - 1])


class Solution:

	def kthCharacter(self, m, n, k):
		m = bin(m)[2:]
		if n == 0:
			return m[k - 1]
		for i in range(n):
			x = ''
			for j in m:
				if j == '1':
					x += '10'
				else:
					x += '01'
			m = x
		return x[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		num = '{0:b}'.format(int(m))
		for i in range(n):
			mod = ''
			for j in range(len(num)):
				if num[j] == '0':
					mod = mod + '01'
				else:
					mod = mod + '10'
			num = mod
		return num[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		string = '{0:b}'.format(m)
		modified = string
		for _ in range(n):
			modified = ''
			for ch in string:
				if ch == '0':
					modified += '01'
				else:
					modified += '10'
			string = modified
		return modified[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		binary = []
		if m == 0:
			binary.append('0')
		while m != 0:
			rem = str(m % 2)
			m = m // 2
			binary.append(rem)
		binary = binary[::-1]
		for iter in range(n):
			for i in range(len(binary)):
				if binary[i] == '0':
					binary[i] = '01'
				if binary[i] == '1':
					binary[i] = '10'
			str1 = ''.join(binary)
			binary = list(str1)
		if len(binary) == 1:
			if binary[0] == '0':
				binary[0] = '01'
			else:
				binary[0] = '10'
			str1 = ''.join(binary)
			binary = list(str1)
		return binary[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		num = ''
		binary = str(bin(m)[2:])
		counter = 0
		while counter < n:
			for j in binary:
				if j == '0':
					num += '01'
				elif j == '1':
					num += '10'
			binary = num
			num = ''
			counter += 1
		return binary[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		b = bin(m)[2:]
		for i in range(n):
			b = self.helper(b)
		return b[k - 1]

	def helper(self, s):
		l = list(s)
		for i in range(len(l)):
			if l[i] == '1':
				l[i] = '10'
			else:
				l[i] = '01'
		return ''.join(l)


class Solution:

	def kthCharacter(self, m, n, k):
		char = bin(m)[2:]
		temp = ''
		for _ in range(n):
			for item in char:
				if item == '1':
					temp += '10'
				else:
					temp += '01'
			char = temp
			temp = ''
		return char[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		s = bin(m)[2:]
		temp = ''
		for i in range(n):
			for element in s:
				if element == '0':
					temp += '01'
				elif element == '1':
					temp += '10'
			s = temp
			temp = ''
		return s[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		d1 = {'1': '10', '0': '01'}
		res = str(bin(m).replace('0b', ''))
		while n:
			res = ''.join([d1[i] for i in res])
			n -= 1
		return res[k - 1]


import re

class Solution:

	def kthCharacter(self, m, n, k):
		binary = format(m, 'b')
		result = ''
		for i in range(n):
			for j in binary:
				if j == '0':
					result += '01'
				else:
					result += '10'
			binary = result
			result = ''
		return binary[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		ans = ''.join(bin(m)[2:])
		temp = ''
		for i in range(n):
			for j in range(len(ans)):
				if ans[j] == '0':
					temp = temp + '01'
				elif ans[j] == '1':
					temp = temp + '10'
			ans = temp
			temp = ''
		return ans[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		x = ''.join(bin(m)[2:])
		c = 0
		temp = ''
		for c in range(n):
			for i in x:
				if i == '1':
					temp += '10'
				elif i == '0':
					temp += '01'
			x = temp
			temp = ''
		return x[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		a = bin(m).replace('0b', '')
		temp = ''
		for i in range(0, n):
			for num in a:
				if num == '0':
					temp += '01'
				elif num == '1':
					temp += '10'
			a = temp
			temp = ''
		return a[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		bv = ''.join(bin(m))[2:]
		ans = ''
		for _ in range(0, n):
			for i in bv:
				if i == '0':
					ans += '01'
				else:
					ans += '10'
			bv = ans
			ans = ''
		return bv[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):

		def converter(strg):
			news = ''
			for i in strg:
				if i == '1':
					news += '10'
				else:
					news += '01'
			return news
		binary = bin(m)[2:]
		for i in range(n):
			binary = converter(binary)
		return binary[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		if n == 0:
			ans = format(m, 'b')
			return int(ans[k - 1])
		q = (k + 1) // 2
		r = (k + 1) % 2
		if r == 0:
			return self.kthCharacter(m, n - 1, q)
		else:
			return 1 ^ self.kthCharacter(m, n - 1, q)


class Solution:

	def kthCharacter(self, m, n, k):
		binary = bin(m)[2:]
		res = ''
		z = 1
		while z <= n:
			for i in binary:
				if i == '1':
					res += '10'
				else:
					res += '01'
			binary = res
			res = ''
			z += 1
		return binary[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		res = str(bin(m)[2:])
		for j in range(n):
			temp = res
			res = ''
			for i in temp:
				if i == '1':
					res += '10'
				else:
					res += '01'
		return res[k - 1]


class Solution:

	def kthCharacter(self, m, n, f):
		m = list(bin(m)[2:])
		for i in range(n):
			for (k, j) in enumerate(m):
				if j == '0':
					m[k] = '01'
				else:
					m[k] = '10'
			m = list(''.join(m))
		return m[f - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		binaryStr = bin(m)[2:]
		temp = ''
		for i in range(0, n):
			for char in binaryStr:
				if char == '0':
					temp += '01'
				else:
					temp += '10'
			binaryStr = temp
			temp = ''
		return binaryStr[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		j = 0
		a = bin(m).replace('0b', '')
		temp = ''
		while j < int(n):
			for i in a:
				if i == '0':
					temp += '01'
				if i == '1':
					temp += '10'
			j += 1
			a = temp
			temp = ''
		c = list(a)
		return c[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		bindata = str(format(m, 'b'))
		i = 0
		res = ''
		while i < n:
			for j in bindata:
				if j == '1':
					res += '10'
				else:
					res += '01'
			i += 1
			bindata = res
			res = ''
		return bindata[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		mbin = str(bin(m)[2:])
		for _ in range(n):
			new = ''
			for j in mbin:
				if j == '1':
					new += '10'
				else:
					new += '01'
			mbin = new
		return mbin[k - 1]


def binn(num):
	res = ''
	num = str(num)
	for x in range(len(num)):
		if num[x] == '0':
			res += '01'
		else:
			res += '10'
	return res

class Solution:

	def kthCharacter(self, m, n, k):
		b = bin(m)[2:]
		for x in range(n):
			b = binn(b)
		return b[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		binstr = bin(m).replace('0b', '')
		temp = ''
		for j in range(n):
			for char in binstr:
				if char == '0':
					temp += '01'
				else:
					temp += '10'
			binstr = temp
			temp = ''
		return binstr[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		temp = bin(m).replace('0b', '')
		ans = ''
		for i in range(n):
			s = ''
			for i in temp:
				if i == '0':
					s += '01'
				else:
					s += '10'
			temp = s
		ans = temp
		if len(ans) > 0 and k - 1 < len(ans):
			return ans[k - 1]
		else:
			return ''


class Solution:

	def kthCharacter(self, m, n, k):

		def decimalToBinary(n):
			return bin(n).replace('0b', '')
		row = decimalToBinary(m)
		for i in range(n):
			temp = ''
			for j in row:
				if j == '0':
					temp += '01'
				else:
					temp += '10'
			row = temp
		return row[k - 1]


class Solution:

	def kthCharacter(self, m, n, k):
		m = bin(m)[2:]
		if n == 0:
			return m[k - 1]
		for i in range(n):
			a = ''
			for i in m:
				if i == '0':
					a += '01'
				elif i == '1':
					a += '10'
			m = a
		return a[k - 1]