Given a binary number (of $N$ bits) $X$. Find the highest power of 2 that divides this number.
Note: If the binary number is "100" then the highest power of 2 that divides it is 2 (as $2^{2}$ = 4)

------ Input: ------ 

The first line contains N the number of bits in the number
The next line contains a binary number of N bits

------ Output: ------ 

The first and only line contains the max power of 2 that divides the given number

------ Constraints: ------ 

$ $1 ≤ N ≤10^{5}$$
$ $1≤ X$$

----- Sample Input 1 ------ 
5
10100
----- Sample Output 1 ------ 
2

Source: codechef | Difficulty: EASY
Tags: String algorithms

Bit manipulation

Data structures

Mathematics


Solutions:
n = int(input())
t = int(input())
c = 0
for i in range(1, n + 1):
	if t % 2 ** i == 0:
		c = i
	if t % 2 ** (i + 1) != 0:
		break
print(c)


n = int(input())
s = int(input())
c = 1
a = 0
while n > 0:
	if s % 2 ** c == 0:
		a = c
	if s % 2 ** (c + 1) != 0:
		break
	c = c + 1
	n = n - 1
print(a)


import math
n = int(input())
l = list(input())
v = 0
for i in range(n):
	if l[n - i - 1] == '1':
		v = v + pow(2, i)
c = 0
while v & 1 == 0:
	v = v // 2
	c = c + 1
print(c)


N = int(input())
s = input()
for i in range(N - 1, -1, -1):
	if s[i] == '1':
		print(N - 1 - i)
		break


n = int(input())
s = int(input())
i = 0
while s % 2 ** i == 0:
	i = i + 1
print(i - 1)


n = int(input())
k = int(input())
i = 0
while k % 2 ** i == 0:
	j = i
	i = i + 1
print(j)


n = int(input())
s = input()
s = s[::-1]
c = 0
for i in s:
	if i == '0':
		c += 1
	else:
		break
print(c)


N = int(input())
s = list(input()[::-1])
print(s.index('1'))


N = int(input())
S = input()
P = S.rstrip('0')
print(N - len(P))


n = int(input())
s = input()
r = s.rstrip('0')
print(len(s) - len(r))


n = int(input())
s = input()
s = s[::-1]
x = s.find('1')
print(x)


a = int(input())
b = input()
nb = int('0b' + b, base=2)
p2 = 1
while nb % 2 ** p2 == 0:
	p2 += 1
print(p2 - 1)


n = int(input())
b = input().split('1')[-1]
print(len(b))


a = input()
print(len(input().split('1')[-1]))


n = int(input())
b = input()
c = 0
for i in range(n - 1, 0, -1):
	if b[i] == '1':
		break
	else:
		c += 1
print(c)


v = input()
b = input()[::-1]
i = b.find('1')
print(i)


p = input()
b = input()[::-1]
i = b.find('1')
print(i)


n = input()
b = input()[::-1]
i = b.find('1')
print(i)


from collections import Counter
t = int(input())
s = input()
s = s[::-1]
c = 0
for i in s:
	if i == '0':
		c += 1
	else:
		break
print(c)


n = int(input())
l = input()[::-1]
print(l.index('1'))


n = int(input())
s = input()
count = 0
for i in range(len(s) - 1, -1, -1):
	if s[i] == '0':
		count += 1
	else:
		break
print(count)


n = int(input())
s = input()
s = int(s, 2)
m = 1
while True:
	c = 2 ** m
	if s % c == 0:
		m += 1
	else:
		print(m - 1)
		break


n = int(input())
b = input()
c = int(b, 2)
i = 2
j = 0
while True:
	if c % i != 0:
		print(j)
		break
	j = j + 1
	i = i * 2


n = int(input())
s = input()
m = 0
for i in range(n - 1, -1, -1):
	if s[i] == '0':
		m = m + 1
	else:
		break
print(m)


n = int(input())
m = int(input())
k = 0
while m % 2 ** k == 0:
	k += 1
print(k - 1)


n = int(input())
s = input()
a = int(s, 2)
l = []
for i in range(1, 9):
	m = 2 ** i
	if a % m == 0:
		l.append(i)
print(max(l))


n = int(input())
a = input()
b = a[::-1]
c = 0
for t in b:
	if t == '0':
		c += 1
	else:
		break
print(c)


n = int(input())
c = int(input())
k = 1
m = 1
a = []
for i in range(1, 9):
	k = m * 2
	m = k
	if c % k == 0:
		a.append(i)
print(max(a))


n = int(input())
s = input()
s1 = s[::-1]
print(s1.index('1'))


n = int(input())
s = input()
x = s.split('1')
print(len(x[len(x) - 1]))


n = int(input())
s = input()
lis = []
x = s.split('1')
for i in range(len(x)):
	print(len(x[len(x) - 1]))
	break


n = int(input())
bina = [int(i) for i in str(input())]
c = 0
for i in bina[::-1]:
	if i == 1:
		break
	c = c + 1
print(c)


n = input()
a = input()
a = a[::-1]
count = 0
for char in a:
	if char == '0':
		count += 1
	else:
		break
print(count)


a = int(input())
b = input()
c = b[::-1]
print(c.find('1'))


a = int(input())
b = input()
c = b.strip('0')
print(a - len(c))


N = int(input())
Binary = input()
Binary = Binary.rstrip('0')
print(N - len(Binary))


n = int(input())
a = input()
a = a[::-1]
print(a.find('1'))


n = int(input())
b = input()
b = b[::-1]
print(b.find('1'))


n = int(input())
s = input().strip()
ans = 0
for i in range(1, n):
	if s[i] == '1':
		ans = n - i - 1
print(ans)


a = int(input(''))
x = input('')
k = str(x)
c = 0
for j in k[::-1]:
	if j == '0':
		c = c + 1
	else:
		break
print(c)


t = int(input())
fin = 0
str1 = str(input())
for i in str1[::-1]:
	if i == '0':
		fin += 1
	else:
		break
print(fin)


p = int(input())
a = input()
a = a[::-1]
b = 0
for i in a:
	if i == '0':
		b += 1
	else:
		break
print(b)


t = int(input())
s = input()
s = int(s, 2)
ans = 2
pows = 1
while s & ans == 0 and s >= ans:
	ans <<= 1
	pows += 1
print(pows)


t = int(input())
s = [int(i) for i in str(input())]
s = s[::-1]
c = 0
flag = 0
for i in range(t):
	if s[i] == 1:
		print(c)
		flag = 1
		break
	else:
		c += 1
if flag == 0:
	print(0)


n = int(input())
num = input()
c = 0
for j in range(-1, -n, -1):
	if num[j] == '1':
		print(c)
		break
	else:
		c = c + 1


bit = int(input(''))
num = input('')
sum = 0
a = bit - 1
for i in range(bit):
	if num[i] == '1':
		sum = sum + 2 ** a
		a -= 1
	else:
		a -= 1
a = -1
while 1:
	a += 1
	if sum % 2 ** a != 0:
		a -= 1
		break
print(a)


n = int(input())
x = input()
if int(x, 2) % 2 != 0:
	print('0')
else:
	y = x[::-1]
	print(list(y).index('1'))


N = int(input())
X = input()
A = 0
b = []
for i in range(N):
	if X[i] == '1':
		b.append(N - 1 - i)
print(min(b))


n = int(input())
a = input()
a = a.rstrip('0')
print(n - len(a))


N = int(input())
string = str(input())
count = 0
for i in range(N - 1, 0, -1):
	if string[i] == '0':
		count += 1
	else:
		break
print(count)


n = int(input())
k = input()
k = k[::-1]
c = 0
flag = 0
for i in k:
	if i == '0':
		c = c + 1
	else:
		print(c)
		flag = 1
		break
if flag == 0:
	print('0')


n = int(input())
x = str(input())
count_of_0s_from_last = 0
for i in reversed(range(len(x))):
	if x[i] == '1':
		break
	else:
		count_of_0s_from_last += 1
print(count_of_0s_from_last)


n = int(input())
x = input()
x = int(x, 2)
k = []
i = 0
while True:
	if x % pow(2, i) == 0:
		k.append(i)
	i += 1
	if i == 5:
		break
print(max(k))


N = int(input())
n = input()
b = n[::-1]
for i in range(N):
	if b[i] == '1':
		print(i)
		break


n = int(input())
binary = [*input()]
binary.reverse()
for i in range(1, n + 1):
	if binary[i] == '1':
		print(i)
		break


def binaryToDecimal(n):
	return int(n, 2)
n = int(input())
s = input()
a = binaryToDecimal(s)
i = 0
x = 2
while a % x == 0:
	x = x * 2
	i += 1
print(i)


a = int(input())
b = input()
for i in range(1, len(b) + 1):
	if b[-i] == '1':
		print(i - 1)
		break


n = int(input())
b = input()
a = int(b, 2)
s = a & ~a + 1
for i in range(s):
	if 2 ** i == s:
		print(i)
		break


t = int(input())
z = list(input())
z = z[::-1]
pos = z.index('1')
print(pos)


lent = int(input())
x = list(input())
x = x[::-1]
pos = x.index('1')
print(pos)


def bin_to_dec(n):
	(s, b) = (0, 1)
	while n > 0:
		r = n % 10
		s = s + r * b
		n = n // 10
		b = b * 2
	return s
n = int(input())
num = int(input())
x = bin_to_dec(num)
big = 0
for i in range(5):
	if x % pow(2, i) == 0:
		big = i
print(big)


n = int(input())
s = input()
lst = []
for i in s:
	lst.append(int(i))
lst.reverse()
print(lst.index(1))