You are given a binary string s of length n. You have to perform binary addition of the string with '1'.
 
Example 1:
Input: 
n = 4
s = 1010
Output: 1011
Explaination: 
The decimal equivalent of given s is 10, 
Adding 1 gives 11, its binary representation
is 1011.
 
Example 2:
Input: 
n = 3
s = 111
Output: 1000
Explaination: The given number is 7. 
Now 7+1 = 8, whose binary representation 
is 1000.
 
Your Task:
You do not need to read input or print anyhthing. Your task is to complete the function binaryAdd() which takes n and s as input parameters and returns the resultant binary string after adding 1 with s.
 
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)
 
Constraints:
1 ≤ n ≤ 10000

Difficulty: EASY
Tags: String algorithms

Data structures

Mathematics
Skill types: Data structures
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3



class Solution:

    def binaryAdd(self, n, s):

        # code here

Solutions:
class Solution:

	def binaryAdd(self, n, s):
		s = s[::-1]
		val = 0
		for i in range(len(s)):
			val += 2 ** i * int(s[i])
		val += 1
		binn = bin(val)[2:]
		diff = len(s) - len(binn)
		binn = '0' * diff + binn
		return binn


class Solution:

	def binaryAdd(self, n, s):
		new = ''
		cnt = 0
		if s[-1] == '0':
			new = s[0:n - 1] + str(1)
			return new
		else:
			for i in range(len(s)):
				if s[-i - 1] == '0':
					break
				cnt += 1
			if '0' not in s:
				new = '1' + '0' * cnt
				return new
			new = s[0:n - cnt - 1] + '1' + '0' * cnt
			return new


class Solution:

	def binaryAdd(self, n, s):
		count = 0
		news = ''
		if s[-1] == '0':
			news = news + s[0:n - 1] + '1'
			return news
		else:
			for x in range(1, n + 1):
				if s[-x] == '1':
					news = news + '0'
					if x == n:
						news = '1' + news
						return news
				else:
					news = '1' + news
					count = 1
				if count == 1:
					news = s[0:-x] + news
					return news


class Solution:

	def binaryAdd(self, n, s):
		ans = bin(int(s, 2) + 1)[2:]
		return '0' * (n - len(ans)) + str(ans)


class Solution:

	def binaryAdd(self, n, s):
		k = int(s, 2)
		s = n - len(bin(k + 1)[2:])
		return s * '0' + bin(k + 1)[2:]


class Solution:

	def binaryAdd(self, n, s):
		num = bin(int(s, 2) + 1)[2:]
		m = len(num)
		zeros = '0' * n
		output = (zeros + num)[-n:]
		return num if m >= n else output


class Solution:

	def binaryAdd(self, n, s):
		ans = bin(int(s, 2) + 1).replace('0b', '').zfill(n)
		return ans


class Solution:

	def binaryAdd(self, n, s):
		count = 0
		m = 0
		for i in range(len(s) - 1, -1, -1):
			count += int(s[i]) * pow(2, m)
			m = m + 1
		count += 1
		p = []
		p.extend(bin(count))
		k = ''.join(p[2:])
		h = ''
		if len(s) != len(k):
			for i in range(len(s) - len(k)):
				h += '0'
		h += k[:]
		return str(h)


from numpy import binary_repr

class Solution:

	def binaryAdd(self, n, s):
		carry = 1
		result = []
		for i in range(len(s) - 1, -1, -1):
			if s[i] == '0' and carry == 1:
				result.append('1')
				carry = 0
			elif s[i] == '1' and carry == 1:
				result.append('0')
				carry = 1
			else:
				result.append(s[i])
		if carry == 1:
			result.append('1')
		result.reverse()
		return ''.join(result)


class Solution:

	def binaryAdd(self, n, s):
		l = len(s)
		x = int(s, 2) + 1
		ans = bin(x)[2:]
		if len(ans) < l:
			ans = (l - len(ans)) * '0' + ans
		return ans


class Solution:

	def binaryAdd(self, n, s):
		ans = ''
		add = '1'
		for i in range(len(s) - 1, -1, -1):
			if s[i] == add:
				ans += '0'
			else:
				ans += '1'
				add = '0'
		else:
			if add == '1':
				ans += add
		return ''.join((ans[i] for i in range(len(ans) - 1, -1, -1)))


class Solution:

	def binaryAdd(self, n, s):
		return format(int(s, 2) + 1, '0' + str(len(s)) + 'b')


class Solution:

	def binaryAdd(self, n, s):
		for t in range(n):
			ans = bin(int(s, 2) + 1).replace('0b', '')
		return '0' * (n - len(ans)) + str(ans)


class Solution:

	def binaryAdd(self, n, s):
		s1 = '0' * n
		s3 = ''
		t = int(s, 2)
		s2 = bin(t + 1).replace('0b', '')
		j = 0
		if len(s2) > n:
			return s2
		else:
			for i in range(n):
				if i < n - len(s2):
					s3 += s1[i]
				else:
					s3 += s2[j]
					j += 1
		return s3


class Solution:

	def binaryAdd(self, n, s):
		binary = list(s)
		carry = '1'
		for i in range(n):
			if binary[n - i - 1] == '1' and carry == '1':
				binary[n - i - 1] = '0'
			elif binary[n - i - 1] == '0' and carry == '1':
				binary[n - i - 1] = '1'
				carry = '0'
		if carry == '1':
			binary.insert(0, '1')
		return ''.join(binary)


class Solution:

	def binaryAdd(self, n, b):
		ans = bin(int(b, 2) + 1).replace('0b', '')
		return '0' * (n - len(ans)) + str(ans)


class Solution:

	def binaryAdd(self, n, s):
		p = bin(int(s, 2) + 1).replace('0b', '')
		return '0' * (n - len(p)) + str(p)


class Solution:

	def binaryAdd(self, n, s):
		b = ''
		carry = 1
		for i in reversed(s):
			if i == '1' and carry:
				carry = 1
				a = '0'
			elif i == '1' and (not carry):
				carry = 0
				a = '1'
			elif i == '0' and carry:
				carry = 0
				a = '1'
			elif i == '0' and (not carry):
				carry = 0
				a = '0'
			b += a
		if carry:
			b += '1'
		return ''.join(reversed(b))


class Solution:

	def binaryAdd(self, n, s):
		j = n
		n = eval('0b' + s)
		n += 1
		n = bin(n)[2:]
		while len(n) < j:
			n = '0' + n
		return n


class Solution:

	def binaryAdd(self, n, s):
		zeros = 0
		try:
			zeros = str(s).index('1')
		except:
			pass
		iv = int(str(s), 2)
		bv = bin(iv + 1)[2:]
		return '0' * (n - len(bv)) + bv


class Solution:

	def binaryAdd(self, n, s):
		ls = []
		for x in s:
			ls.append(x)
		for i in range(n - 1, -1, -1):
			if ls[i] == '0':
				ls[i] = '1'
				return ''.join(ls)
			elif ls[i] == '1':
				ls[i] = '0'
		return '1' + ''.join(ls)


class Solution:

	def binaryAdd(self, n, s):
		dec = int(s, 2)
		res = dec + 1
		ans = bin(res).replace('0b', '')
		return str(ans).zfill(n)


class Solution:

	def binaryAdd(self, n, s):
		ans = ''
		c = 1
		for i in range(n - 1, -1, -1):
			if int(s[i]) + c == 2:
				ans = '0' + ans
			elif int(s[i]) + c == 1:
				ans = '1' + ans
				c = 0
			else:
				ans = s[i] + ans
				c = 0
		if c:
			ans = '1' + '0' * n
		return ans


class Solution:

	def getDecimal(self, binary):
		decimal = 0
		i = 0
		while binary != 0:
			rem = binary % 10
			decimal += rem * 2 ** i
			i += 1
			binary //= 10
		return decimal

	def getBinary(self, decimal):
		binary = ''
		while decimal != 0:
			rem = decimal % 2
			binary = str(rem) + binary
			decimal //= 2
		return binary

	def binaryAdd(self, n, s):
		bi = ''
		decimal = self.getDecimal(int(s))
		binary = self.getBinary(decimal + 1)
		if len(binary) < n:
			size = n - len(binary)
			return '0' * size + binary
		return binary
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		s = input()
		ob = Solution()
		print(ob.binaryAdd(n, s))


class Solution:

	def binaryAdd(self, n, s):
		count = ''
		res = str(bin(int(s, 2) + 1))[2:]
		if n > len(res):
			for itr in range(n - len(res)):
				count += '0'
		return count + res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		s = input()
		ob = Solution()
		print(ob.binaryAdd(n, s))


class Solution:

	def binaryAdd(self, n, s):
		j = n
		n = n - 1
		c = 0
		for i in s:
			if i == '1':
				c += 2 ** n
			n -= 1
		c += 1
		d = bin(c)
		d = d[2:]
		if len(d) < j:
			d = (j - len(d)) * '0' + d
		return d
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		s = input()
		ob = Solution()
		print(ob.binaryAdd(n, s))


class Solution:

	def binaryAdd(self, n, s):
		ans = ''
		carry = 1
		for i in range(n - 1, -1, -1):
			if s[i] == '1' and carry == 1:
				ans += '0'
				carry = 1
			elif s[i] == '1' and carry == 0:
				ans += '1'
				carry = 0
			elif s[i] == '0' and carry == 1:
				ans += '1'
				carry = 0
			else:
				ans += '0'
				carry = 0
		ans += str(carry) if carry == 1 else ''
		ans = ans[::-1]
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		s = input()
		ob = Solution()
		print(ob.binaryAdd(n, s))


class Solution:

	def binaryAdd(self, n, s):
		flag = 0
		S = ''
		if s.count('0') == 0:
			S = '1' + '0' * len(s)
			return S
		for i in s[::-1]:
			if i == '1' and flag == 0:
				S = S + '0'
			elif i == '0' and flag == 0:
				S = S + '1'
				flag = 1
			else:
				S = S + i
		S = S[::-1]
		return S


class Solution:

	def binaryAdd(self, n, s):
		a = 1
		f = ''
		for i in range(n - 1, -1, -1):
			j = int(s[i]) + a
			if j == 1 or j == 0:
				f = f + str(j)
				a = 0
			elif j == 2:
				f = f + '0'
				a = 1
		if a == 1:
			f = f + '1'
		return f[::-1]


class Solution:

	def binaryAdd(self, n, s):
		decimal = int(s, 2)
		decimal += 1
		binary = bin(decimal)[2:]
		ans = binary.zfill(n)
		return ans


class Solution:

	def binaryAdd(self, n, s):
		a = int(s, 2) + 1
		d = bin(a)[2:]
		e = '0' * (n - len(d)) + d
		return e


class Solution:

	def binaryAdd(self, n, s):
		s = s[::-1]
		dec = 0
		for i in range(0, n):
			dec = dec + int(s[i]) * pow(2, i)
		dec += 1
		binnum = str(bin(dec))[2:]
		if len(binnum) < n:
			return '0' * (n - len(binnum)) + binnum
		return str(bin(dec))[2:]


class Solution:

	def binaryAdd(self, n, s):
		z = int(s, 2)
		x = z + 1
		k = bin(x)[2:]
		l = '0' * (n - len(k)) + k
		return l


class Solution:

	def binaryAdd(self, n, s):
		return str(bin(int(s, 2) + 1))[2:].zfill(len(s))


class Solution:

	def binaryAdd(self, n, s):
		a = int('0b' + s, 2)
		a += 1
		b = bin(a)[2:]
		return '0' * (n - len(b)) + b


class Solution:

	def binaryAdd(self, n, s):
		l = []
		add = 1
		carry = 0
		while n - 1 >= 0:
			if add == 1:
				if int(s[n - 1]) + add > 1:
					l.append('0')
					carry = 1
					add = 0
				else:
					l.append('1')
					carry = 0
					add = 0
			elif int(s[n - 1]) + carry > 1:
				carry = 1
				l.append('0')
			else:
				l.append(carry + int(s[n - 1]))
				carry = 0
			n -= 1
		if carry != 0:
			l.append(carry)
		out = ''
		a = len(l) - 1
		while a >= 0:
			out += str(l[a])
			a -= 1
		return out