Problem:
 Score : 400 points    Problem Statement Let \mathrm{popcount}(n) be the number of 1 s in the binary representation of n .
For example, \mathrm{popcount}(3) = 2 , \mathrm{popcount}(7) = 3 , and \mathrm{popcount}(0) = 0 .  Let f(n) be the number of times the following operation will be done when we repeat it until n becomes 0 : "replace n with the remainder when n is divided by \mathrm{popcount}(n) ." (It can be proved that, under the constraints of this problem, n always becomes 0 after a finite number of operations.)  For example, when n=7 , it becomes 0 after two operations, as follows:   \mathrm{popcount}(7)=3 , so we divide 7 by 3 and replace it with the remainder, 1 .  \mathrm{popcount}(1)=1 , so we divide 1 by 1 and replace it with the remainder, 0 .   You are given an integer X with N digits in binary.
For each integer i such that 1 \leq i \leq N , let X_i be what X becomes when the i -th bit from the top is inverted.
Find f(X_1), f(X_2), \ldots, f(X_N) .      Constraints  1 \leq N \leq 2 \times 10^5  X is an integer with N digits in binary, possibly with leading zeros.         Input Input is given from Standard Input in the following format:  N  X       Output Print N lines. The i -th line should contain the value f(X_i) .        Sample Input 1 3
011      Sample Output 1 2
1
1   X_1 = 7 , which will change as follows: 7 \rightarrow 1 \rightarrow 0 . Thus, f(7) = 2 .  X_2 = 1 , which will change as follows: 1 \rightarrow 0 . Thus, f(1) = 1 .  X_3 = 2 , which will change as follows: 2 \rightarrow 0 . Thus, f(2) = 1 .        Sample Input 2 23
00110111001011011001110      Sample Output 2 2
1
2
2
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
3

Solution (Python):
from copy import copy

def popcount(x):
    return bin(x).count("1")

def f(x):
    if x == 0:
        return 0
    return f(x%popcount(x))+1

n = int(input())
x = input()
xx = int(x,2)
p = x.count("1")
stand1 = xx%(p+1)
if p != 1:
    stand2 = xx%(p-1)
for i in range(n):
    if x[i] == "1":
        if p != 1:
            k = copy(stand2)
            k -= pow(2,n-i-1,p-1) 
            k %= p-1
        else:
            print(0)
            continue
    else:
        k = copy(stand1)
        k += pow(2,n-i-1,p+1)
        k %= p+1
    print(1+f(k))

Solution (Python):
def f(n):
    cnt = 1
    while n > 0:
        n  %= bin(n).count('1')
        cnt += 1
    return cnt

if __name__ == "__main__":
    n = int(input())
    x = input()
    d = x.count('1')
    if d == 1:
        for i in x[:-1]:
            if i == '0':
                print(1)
            else:
                print(0)
        if x[-1] == '1':
            print(0)
        else:
            print(2)
        exit()

    ans = []
    M = 0
    for i in x:
        M <<= 1
        if i == '1':
            M += 1
    p = M % (d + 1)
    m = M % (d - 1)
    for i in range(n):
        if x[i] == '0':
            ans.append(f((p + pow(2, n - i - 1, d + 1)) % (d + 1)))
        else:
            ans.append(f((m - pow(2, n - i - 1, d - 1)) % (d - 1)))
    print(*ans, sep='\n')

Solution (Python):
def popcount(x):
    c = 0
    while x > 0:
        if x & 1: c += 1
        x //= 2
    return c

def f(x):
    if x==0: return 0
    return f(x % popcount(x)) + 1

n = int(input())
X = input()
po = X.count('1')
pp = po + 1
pm = max(1, po - 1)
rp = rm = 0
for x in X:
    rp = (rp*2 + int(x)) % pp
    rm = (rm*2 + int(x)) % pm
bp = [0]*(n) 
bm = [0]*(n) 
bp[n-1] = 1 % pp
bm[n-1] = 1 % pm
for i in range(n-1, 0, -1):
    bp[i-1] = bp[i]*2 % pp
    bm[i-1] = bm[i]*2 % pm
for i in range(n):
    if X[i] == '0': ri = (rp + bp[i]) % pp
    else:
        if po-1 != 0: ri = (rm - bm[i]) % pm
        else:
            print(0)
            continue
    print(f(ri) + 1)

Solution (Python):
from logging import *
basicConfig(level=DEBUG, format='%(levelname)s: %(message)s')
disable(CRITICAL)

n = int(input())
X = input()
debug('n {}'.format(n))
debug('X {}'.format(X))
po = X.count('1')





pp = po + 1
pm = max(1, po - 1)

rp = 0
rm = 0
for x in X:
    rp = (rp*2 + int(x)) % pp
    rm = (rm*2 + int(x)) % pm

bp = [0]*(n) 
bm = [0]*(n) 
bp[n-1] = 1 % pp
bm[n-1] = 1 % pm
for i in range(n-1,0,-1):
    bp[i-1] = bp[i]*2 % pp
    bm[i-1] = bm[i]*2 % pm

debug('po {}'.format(po))
debug('pp {}'.format(pp))
debug('pm {}'.format(pm))
debug('rp {}'.format(rp))
debug('rm {}'.format(rm))
debug('bp {}'.format(bp))
debug('bm {}'.format(bm))
debug('===')

def popcount(x):
    c = 0
    while x > 0:
        if x & 1: c += 1
        x //= 2
    return c

def f(x):
    if x==0: return 0
    return f(x % popcount(x)) + 1

for i in range(n):
    if X[i] == '0':
        ri = (rp + bp[i]) % pp
    else: 
        if po-1 != 0: ri = (rm - bm[i]) % pm
        else:
            print(0)
            continue
    debug('i {} ri {}'.format(i,ri))
    c = f(ri) + 1
    debug('c {}'.format(c))
    print(c)

Solution (Python):


from pprint import pprint
import sys

sys.setrecursionlimit(10 ** 6)
INF = float('inf')


n = int(input())
x = input()
x_pc = x.count('1')
x_pc_plus = x_pc + 1
x_pc_minus = x_pc - 1


r_plus_list = [pow(2, i, x_pc_plus) for i in range(n+1)]
r_minus_list = [0] * (n+1)
if x_pc_minus > 0:
    r_minus_list = [pow(2, i, x_pc_minus) for i in range(n+1)]

x = x[::-1]
r_plus = 0
r_minus = 0
for i in range(n):
    if x[i] == '1':
        r_plus += r_plus_list[i]
        r_minus += r_minus_list[i]

for i in range(n-1, -1, -1):
    if x[i] == '0':
        diff = (r_plus + r_plus_list[i]) % x_pc_plus
    elif x_pc_minus >= 1:
        diff = (r_minus - r_minus_list[i]) % x_pc_minus
    else:
        print(0)
        continue
    ans = 1
    while diff > 0:
        diff = diff % bin(diff).count('1')
        ans += 1
    print(ans)

Solution (Python):
def popcount(n):
    return bin(n).count("1")

def f(n):
    cnt = 0
    while n != 0:
        n %= popcount(n)
        cnt += 1
    return cnt

N = int(input())
S = input()

pcnt_X = S.count("1")
X = int(S, 2)

Xm = X % (pcnt_X - 1) if pcnt_X - 1 > 0 else float("inf")
Xp = X % (pcnt_X + 1)

for i, s in enumerate(S):
    if s == "0":
        x = (Xp + pow(2, N - 1 - i, pcnt_X + 1)) % (pcnt_X + 1)
        print(1 + f(x))
    elif pcnt_X - 1 > 0:
        x = (Xm - pow(2, N - 1 - i, pcnt_X - 1)) % (pcnt_X - 1)
        print(1 + f(x))
    else:
        print(0)

Solution (Python):
N = int(input())
X = input()

n1 = X.count("1")
Xn = int(X, 2)

Xms = (Xn % (n1 - 1)) if n1 > 1 else 0
Xml = Xn % (n1 + 1)


def f(n):
    if n == 0:
        return 0
    return f(n % bin(n).count("1")) + 1


dp = [0] * ((10 ** 5) * 2 + 1)
for i in range(1, len(dp)):
    dp[i] = f(i)


for i in range(N):
    cnt = 0
    Xim = 0

    if X[i] == "1" and n1 == 1:
        print(cnt)
    elif X[i] == "1":
        print(dp[(Xms - pow(2, N - i - 1, n1 - 1)) % (n1 - 1)] + 1)
    else:
        print(dp[(Xml + pow(2, N - i - 1, n1 + 1)) % (n1 + 1)] + 1)

Solution (Python):
def popcount(n):
    return bin(n).count('1')
    
N=int(input())
X=input()
xl=list(X)
X=int(X,2)
a=popcount(X)

if a==1:
    xd=0
else:
    xd=X%(a-1)

xi=X%(a+1)

for i in range(N):
    if xl[i]=='1':
        if a==1:
            print(0)
            continue
        else:
            k=pow(2,N-1-i,a-1)
            x=(xd-k)%(a-1)
    else:
        k=pow(2,N-1-i,a+1)
        x=(xi+k)%(a+1)
    count=1
    while x!=0:
        x%=popcount(x)
        count+=1
    print(count)

Solution (Python):
N = int(input())
X = input()

n1 = X.count("1")
Xn = int(X, 2)

Xms = (Xn % (n1 - 1)) if n1 > 1 else 0
Xml = Xn % (n1 + 1)













for i in range(N):
    cnt = 0
    xi = 0
    if X[i] == "1" and n1 == 1:
        print(cnt)
        continue
    elif X[i] == "1":
        xi = (Xms - pow(2, N - i - 1, n1 - 1)) % (n1 - 1)
    else:
        xi = (Xml + pow(2, N - i - 1, n1 + 1)) % (n1 + 1)
    cnt = 1
    while xi != 0:
        xi %= bin(xi).count("1")
        cnt += 1
    print(cnt)

Solution (Python):
N = int(input())
X = input()

n1 = X.count("1")
Xn = int(X, 2)

Xms = (Xn % (n1 - 1)) if n1 > 1 else 0
Xml = Xn % (n1 + 1)

p2s = [1]
p2l = [1]
s2 = 1
l2 = 1
for i in range(N - 1):
    s2 = (s2 * 2) % (n1 - 1) if n1 > 1 else 0
    l2 = (l2 * 2) % (n1 + 1)
    p2s.append(s2)
    p2l.append(l2)


def f(n):
    if n == 0:
        return 0
    return f(n % bin(n).count("1")) + 1


dp = [0] * ((10 ** 5) * 2 + 1)
for i in range(1, len(dp)):
    dp[i] = f(i)


for i in range(N):
    cnt = 0
    p2 = 2 ** (N - i - 1)
    Xim = 0

    if X[i] == "1" and n1 == 1:
        print(cnt)
    elif X[i] == "1":
        print(dp[(Xms - p2s[-i - 1]) % (n1 - 1)] + 1)
    else:
        print(dp[(Xml + p2l[-i - 1]) % (n1 + 1)] + 1)

Solution (Python):
n = int(input())
x = input()

popcount = x.count('1')
p = int(x, 2) % (popcount + 1)
q = int(x, 2) % (popcount - 1) if popcount != 1 else 0
for i in range(n):
    if x[i] == '0':
        y = (p + pow(2, n-i-1, popcount+1)) % (popcount + 1)
    else:
        if popcount != 1:
            y = (q - pow(2, n-i-1, popcount-1)) % (popcount - 1)
        else:
            print(0)
            continue
    cnt = 1
    while y != 0:
        y %= bin(y).count('1')
        cnt += 1
    print(cnt)

Solution (Python):
N = int(input())
X = input()

n1 = X.count("1")
Xn = int(X, 2)

Xms = (Xn % (n1 - 1)) if n1 > 1 else 0
Xml = Xn % (n1 + 1)

p2s = [1]
p2l = [1]
s2 = 1
l2 = 1
for i in range(N - 1):
    s2 = (s2 * 2) % (n1 - 1) if n1 > 1 else 0
    l2 = (l2 * 2) % (n1 + 1)
    p2s.append(s2)
    p2l.append(l2)


def f(n):
    if n == 0:
        return 0
    return f(n % bin(n).count("1")) + 1


for i in range(N):
    cnt = 0
    p2 = 2 ** (N - i - 1)
    Xim = 0

    if X[i] == "1" and n1 == 1:
        print(cnt)
    elif X[i] == "1":
        print(f((Xms - p2s[-i - 1]) % (n1 - 1)) + 1)
    else:
        print(f((Xml + p2l[-i - 1]) % (n1 + 1)) + 1)

Solution (Python):
def count_pop(y):
  count = 0
  while y != 0:
    if y & 1 == 1:count+=1
    y = y >> 1
  return count
  
def main():
  N = int(input())
  X = input()
  X_val=int(X,2)
  X_pc=X.count('1')
  x_mod_pc_x_plus_1 = X_val % (X_pc + 1)
  x_mod_pc_x_minus_1 = X_val % max(X_pc - 1, 1)
  for i in range(N):
    if X[i] == '1':
      pc = X_pc - 1
      if pc == 0:
        print(0)
        continue
      val = (x_mod_pc_x_minus_1 - pow(2, N-i-1, pc)) % pc
    else:     
      pc = X_pc + 1
      val = (x_mod_pc_x_plus_1 + pow(2, N-i-1, pc)) % pc
    ans = 1   
    while val > 0:
      val %= bin(val).count('1')
      ans += 1
    print(ans)
  pass       
if __name__=='__main__':
  main()

Solution (Python):
n = int(input())
s = input()
x = int(s, 2)
p = s.count("1")
if p > 1:
	pre0 = x%(p-1)
pre1 = x%(p+1)

nxt = [i for i in range(n+10)]
for i in range(1, n+10):
	nxt[i] %= bin(i).count("1")

for i in range(n):
	if x == 1<<(n-1-i):
		print(0)
		continue
	if s[i] == "0":
		tmp = (pre1 + pow(2, n-1-i, p+1)) % (p+1)
	else:
		tmp = (pre0 - pow(2, n-1-i, p-1)) % (p-1)
	ans = 1
	while tmp > 0:
		ans += 1
		tmp = nxt[tmp]
	print(ans)

Solution (Python):
N = int(input())
X = input()

n1 = X.count("1")
Xn = int(X, 2)

Xms = (Xn % (n1 - 1)) if n1 > 1 else 0
Xml = Xn % (n1 + 1)

p2s = [1]
p2l = [1]
s2 = 1
l2 = 1
for i in range(N - 1):
    s2 = (s2 * 2) % (n1 - 1) if n1 > 1 else 0
    l2 = (l2 * 2) % (n1 + 1)
    p2s.append(s2)
    p2l.append(l2)


def f(n):
    if n == 0:
        return 0
    return f(n % bin(n).count("1")) + 1


for i in range(N):
    cnt = 0
    p2 = 2 ** (N - i - 1)
    Xim = 0

    if X[i] == "1" and n1 == 1:
        print(cnt)
        continue
    elif X[i] == "1":
        Xim = (
            Xms - p2s[-i - 1]
            if Xms - p2s[-i - 1] >= 0
            else ((n1 - 1) + (Xms - p2s[-i - 1]))
        )
    else:
        Xim = (
            Xml + p2l[-i - 1]
            if Xml + p2l[-i - 1] < (n1 + 1)
            else (Xml + p2l[-i - 1] - (n1 + 1))
        )
    print(f(Xim) + 1)

Solution (Python):
N = int(input())
X = input()

n1 = X.count("1")
Xn = int(X, 2)

Xms = (Xn % (n1 - 1)) if n1 > 1 else 0
Xml = Xn % (n1 + 1)

p2s = [1]
p2l = [1]
s2 = 1
l2 = 1
for i in range(N - 1):
    s2 = (s2 * 2) % (n1 - 1) if n1 > 1 else 0
    l2 = (l2 * 2) % (n1 + 1)
    p2s.append(s2)
    p2l.append(l2)

for i in range(N):
    cnt = 0
    p2 = 2 ** (N - i - 1)
    Xim = 0

    if X[i] == "1" and n1 == 1:
        print(cnt)
        continue
    elif X[i] == "1":
        Xim = (
            Xms - p2s[-i - 1]
            if Xms - p2s[-i - 1] >= 0
            else ((n1 - 1) + (Xms - p2s[-i - 1]))
        )
    else:
        Xim = (
            Xml + p2l[-i - 1]
            if Xml + p2l[-i - 1] < (n1 + 1)
            else (Xml + p2l[-i - 1] - (n1 + 1))
        )

    cnt += 1
    while Xim > 0:
        Xim %= bin(Xim).count("1")
        cnt += 1
    print(cnt)

Solution (Python):
n = int(input())
x = input()

def count(n):
    cnt = 0
    while n:
        cnt += n % 2
        n //= 2
    return cnt

LIMIT = 5*10**5
dp = [0] * LIMIT
for i in range(1, LIMIT):
    dp[i] = dp[i % count(i)]+1

c = x.count("1")
a = int(x,2) % (c+1)

if c == 1:
    for i in range(n):
        if x[i] == "0":
            print(dp[(a + pow(2, n-i-1, c+1)) % (c+1)] + 1)
        else:
            print(0)
    exit()

b = int(x,2) % (c-1)
for i in range(n):
    if x[i] == "0":
        print(dp[(a + pow(2, n-i-1, c + 1)) % (c + 1)] + 1)
    else:
        print(dp[(b - pow(2, n-i-1, c - 1)) % (c - 1)] + 1)

Solution (Python):
def popcnt(n):
   c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
   c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
   c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
   c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
   c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
   c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
   return c
n = int(input())
s = input()
f = []
f.append(0)
M = 200000
for i in range(1,M+1):
    x = i
    cnt = 0
    while x > 0:
        x = x % popcnt(x)
        cnt += 1
    f.append(cnt)

    
buf = s.count('1')
if buf == 0:
    for i in range(n):
        if s[i] == '1':
            print(0)
        else:
            print(1)
else:
    a = buf + 1
    pow2a = []
    pow2a.append(1)
    for i in range(M):
        pow2a.append((pow2a[i]*2) % a)
    b = buf - 1
    pow2b = []
    pow2b.append(1)
    if buf != 1:
        for i in range(M):
            pow2b.append((pow2b[i]*2) % b)
    asum = 0
    for i in range(n):
        if s[i] == '1':
            asum = (asum + pow2a[n - 1 - i]) % a
    bsum = 0
    if buf != 1:    
        for i in range(n):
            if s[i] == '1':            
                bsum = (bsum + pow2b[n - 1 - i]) % b
    if buf == 1:
        for i in range(n):
            if s[i] == '1':
                print(0)
            else:
                x = (asum + pow2a[n - 1 - i]) % a
                print(f[x] + 1)
    else:
        for i in range(n):
            if s[i] == '1':
                x = (bsum - pow2b[n - 1 - i] + b) % b
                print(f[x] + 1)
            else:
                x = (asum + pow2a[n - 1 - i]) % a
                print(f[x] + 1)

Solution (Python):
from functools import lru_cache

N = int(input())
X = input()


@lru_cache(maxsize=None)
def popcount(x):
    return x % bin(x).count('1')


def f(x):
    cnt = 1
    while x > 0:
        x = popcount(x)
        cnt += 1

    return cnt


count = X.count('1')
mod_one = count - 1
if mod_one == 0:
    mod_one = 1
mod_zero = count + 1
ones = [1 % mod_one]
zeros = [1 % mod_zero]
x_mod_one = 0 if X[-1] == '0' else 1 % mod_one
x_mod_zero = 0 if X[-1] == '0' else 1 % mod_zero

for xi in reversed(X[:-1]):
    ones.append(ones[-1] * 2 % mod_one)
    zeros.append(zeros[-1] * 2 % mod_zero)
    if xi == '1':
        x_mod_one += ones[-1]
        x_mod_one %= mod_one
        x_mod_zero += zeros[-1]
        x_mod_zero %= mod_zero

ones = list(reversed(ones))
zeros = list(reversed(zeros))

for i in range(N):
    if count == 1 and X[i] == '1':
        print(0)
    elif X[i] == '1':
        x = (x_mod_one - ones[i]) % mod_one
        print(f(x))
    else:
        x = (x_mod_zero + zeros[i]) % mod_zero
        print(f(x))

Solution (Python):
import sys
sys.setrecursionlimit(10**8)

N = int(input())
X = str(input())
ones = X.count('1')
intX = int(X, 2)
def check(n, r):
    if n == 0:
        return print(r)
    d = str(bin(n)).count('1')
    check(n%d, r+1)

if ones > 1:
    Xplus = intX % (ones + 1)
    Xminus = intX % (ones - 1)
else:
    Xplus = intX % (ones + 1)
    Xminus = intX

for i in range(N):
    e = 1
    if X[i] == '0':
        num = (Xplus + pow(2, N-1-i, ones + 1)) % (ones + 1)
    elif X[i] == '1' and ones > 1:
        num = (Xminus - pow(2, N-1-i, ones - 1)) % (ones - 1)
    else:
        num = (Xminus - pow(2, N-1-i))
        e = 0
    check(num, e)

Solution (Python):
N = int(input())
S = input()

def pcnt(x):
    return str(bin(x)).count("1")

dpl = 5*10**5
dp = [0] * dpl
for i in range(1, dpl):
    dp[i] = dp[i % pcnt(i)]+1

c = S.count("1")
a = int(S, 2) % (c+1)
 
def f():
    if c == 1:
        for i in range(N):
            if S[i] == "0":
                print(dp[(a + pow(2, N-i-1, c+1)) % (c+1)] + 1)
            else:
                print(0)
        return
    
    b = int(S, 2) % (c-1)
    for i in range(N):
        if S[i] == "0":
            print(dp[(a+pow(2, N-i-1, c+1))%(c+1)]+1)
        else:
            print(dp[(b-pow(2, N-i-1, c-1))%(c-1)]+1)

f()

Solution (Python):
n=int(input())
x_=input()
px=x_.count("1")
if not px:
    for i in range(n):
        print(1)
    exit()
if px==1:

    for i in range(n):
        if int(x_[i]):
            print(0)
        else:
            if i==n-1 or int(x_[-1])==1:
                print(2)
            else:
                print(1)
    exit()
x=int(x_,2)

pow2=[1]

for i in range(n):
    tmp=pow2[-1]
    tmp*=2
    tmp%=px+1
    pow2.append(tmp)
pow22=[1]
for i in range(n):
    tmp=pow22[-1]
    tmp*=2
    tmp%=px-1
    pow22.append(tmp)
x1=x%(px+1)
x2=x%(px-1)
ans=[]
for i in range(n):
    tmp=0;dv=0
    if int(x_[-i-1]):
        tmp=x2-pow22[i]
        tmp%=(px-1)
        dv=px-1
    else:
        tmp=x1+pow2[i]
        tmp%=(px+1)
        dv=px+1
    
    cnt=1
    while tmp:
        
        dv=bin(tmp).count("1")
        if not dv or not tmp:
            break
        
        tmp%=dv
        cnt+=1
    ans.append(cnt)
for i in ans[::-1]:
    print(i)

Solution (Python):
import sys
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(sys.stdin.readline())
def ria(): return list(map(int, sys.stdin.readline().split()))
def ws(s): sys.stdout.write(s); sys.stdout.write('\n')
def wi(n): sys.stdout.write(str(n)); sys.stdout.write('\n')
def wia(a, sep=' '): sys.stdout.write(sep.join([str(x) for x in a])); sys.stdout.write('\n')


def main():
    n = ri()
    x = rs()

    k = int(x, 2)
    d = x.count('1')
    
    if d > 1:
        k0 = k % (d-1)
    k1 = k % (d+1)

    f = [0] * (n + 1)
    for i in range(1, n+1):
        f[i] = f[i % bin(i).count('1')] + 1

    for i in range(n):
        cnt = 0
        if x[i] == '1' and d - 1 > 0:
            cnt += f[(k0 - pow(2, n - i - 1, d - 1)) % (d - 1)] + 1
        elif x[i] == '0':
            cnt += f[(k1 + pow(2, n - i - 1, d + 1)) % (d + 1)] + 1
        wi(cnt)


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
X = input()

cnt = X.count('1')
if cnt == 1:
    for x in X[:-1]:
        if x == '0':
            print(1)
        else:
            print(0)
    if X[-1] == '1':
        print(0)
    else:
        print(2)
    exit()

M = 0
for x in X:
    M <<= 1
    if x == '1':
        M += 1

def solve(n):
    ret = 1
    while n > 0:
        ret += 1
        n %= bin(n).count('1')
    return ret

ans = []
p = M % (cnt + 1)
m = M % (cnt - 1)

for i in range(N):
    if X[i] == '0':
        ans.append(solve((p + pow(2, N - i - 1, cnt + 1)) % (cnt + 1)))
    else:
        ans.append(solve((m - pow(2, N - i - 1, cnt - 1)) % (cnt - 1)))
print(*ans, sep='\n')

Solution (Python):
from functools import lru_cache


a = int(input())
b = input()
X = b.count("1")
ans1 = []
ans2 = []

@lru_cache(maxsize=None)
def func1(c):
    x = X + 1
    n = 1
    nsum = 0
    for i in reversed(range(len(c))):
        ans1.append(n)
        nsum += n * int(c[i])
        n = n % x if n > x else n
        n *= 2
    return nsum
    
@lru_cache(maxsize=None)
def func2(c):
    x = X - 1
    if x == 0:
        return 0
    n = 1
    nsum = 0
    for i in reversed(range(len(c))):
        ans2.append(n)
        nsum += n * int(c[i])
        n = n % x if n > x else n
        n *= 2
    return nsum    

def func(c):
    x = c.count("1")
    if x == 0:
        return 0
    n = 1
    nsum = 0
    for i in reversed(range(len(c))):
        nsum += n * int(c[i])
        n = n % x if n > x else n
        if n == 0:
            break
        n *= 2
    nsum %= x
    cans = bin(nsum).count("1")
    if cans == 0:
        return 1
    else:
        return 1 + func(bin(nsum)[2:])
    
allans1 = func1(b)
allans2 = func2(b)
ans1 = ans1[::-1]
if allans2 == 0:
    ans2 = [0] * a
else:
    ans2 = ans2[::-1]

c = list(b)
for i in range(a):
    if c[i] == "0":
        ans = (allans1 + ans1[i]) % (X + 1)
        ans = func(bin(ans)[2:]) + 1
        print(str(ans))
    else:
        if allans2 - ans2[i] == 0 and X - 1 == 0:
            print("0")
        else:
            ans = (allans2 - ans2[i]) % (X - 1)
            ans = func(bin(ans)[2:]) + 1
            print(str(ans))

Solution (Python):
def search(n):
    res = 0
    while n:
        n %= bin(n).count("1")
        res += 1
    return res


def main():
    n = int(input())
    x = list(input())
    x_decimal = int("".join(map(str, x)), 2)
    first_mod = sum(map(int, list(x)))
    increase_mod = first_mod + 1
    increase_base = x_decimal % increase_mod  
    decrease_mod = first_mod - 1
    if decrease_mod:
        decrease_base = x_decimal % decrease_mod  
    for i in range(n):
        cnt = 0
        if x[i] == "1" and decrease_mod:
            cnt = 1 + search((decrease_base - pow(2, n - i - 1, decrease_mod)) % decrease_mod)
        elif x[i] == "0":
            cnt = 1 + search((increase_base + pow(2, n - i - 1, increase_mod)) % increase_mod)
        print(cnt)


if __name__ == '__main__':
    main()

Solution (Python):


import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**6)
INF = float("inf")

def popcount(n):
    ret = 0
    for i in range(18):
        if n>>i & 1:
            ret += 1
    return ret

def main():
    N = int(input())
    X = input().decode().rstrip()

    
    x_cnt = X.count("1")

    
    
    
    x_mod_pl,x_mod_mi = 0,0
    d_pl,d_mi = 1,1
    mod_pl,mod_mi = x_cnt+1,max(1,x_cnt-1)
    for i in range(N-1,-1,-1):
        if X[i]=="1":
            x_mod_pl = (x_mod_pl + d_pl) % mod_pl
            x_mod_mi = (x_mod_mi + d_mi) % mod_mi
        d_pl = (d_pl*2) % mod_pl
        d_mi = (d_mi*2) % mod_mi
    
    for i in range(N):
        ans = 1
        if X[i] == "1":
            
            if x_cnt == 1:
                print(0)
                continue
            a = (x_mod_mi - pow(2,(N-1-i), mod_mi)) % mod_mi
        else:
            a = (x_mod_pl + pow(2,(N-1-i), mod_pl)) % mod_pl

        while a > 0:
            pop_cnt = popcount(a)
            a %= pop_cnt
            ans += 1

        print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
n=int(input())
x=input()
chk0=chk1=chk2=0
b=x.count("1")
if b==1 and x=="1":
    print(0)
    exit()
elif b==1:
    for i in range(n):
        if i==n-1: print(2)
        elif x[i]=="0": print(1)
        else: print(0)
    exit()
for i,j in enumerate(x[::-1]):
    if j=="1":
        chk1+=pow(2,i,b+1)
        if b>1: chk2+=pow(2,i,b-1)
        else: chk2=0
l=[]
for i,j in enumerate(x[::-1]):
    if b: a1=pow(2,i,b+1)
    else: a1=1
    if b>1: a2=pow(2,i,b-1)
    else: a2=1
    if j=="0":
        t=chk1+a1
    else:
        if b>1: t=chk2+b-1-a2
        else: t=0
    ans,f=0,1
    while t:
        if f:
            if j=="0": t%=(b+1)
            else: t%=(b-1)
            f=0
        else:
            t%=bin(t).count("1")
        ans+=1
    l.append(ans)
for i in l[::-1]:
    print(i)

Solution (Python):
def f(n):
    if n == 0:
        return 0
    return f(n % bin(n).count("1")) + 1


def solve():
    N = int(input())
    X = input()
    p = X.count("1")
    rem_plus = 0
    rem_minus = 0
    for i in range(N):
        k = N - i - 1
        if X[i] == "0":
            continue
        elif p > 1:
            rem_minus = (rem_minus + pow(2, k, p - 1)) % (p - 1)
        rem_plus = (rem_plus + pow(2, k, p + 1)) % (p + 1)
    for i in range(N):
        k = N - i - 1
        if X[i] == "0":
            print(f((rem_plus + pow(2, k, p + 1)) % (p + 1)) + 1)
        elif p > 1:
            print(f((rem_minus - pow(2, k, p - 1)) % (p - 1)) + 1)
        else:
            print(0)


if __name__ == "__main__":
    solve()

Solution (Python):
N = int(input())
X = input()

arr = [0 for _ in range(N+1)]
for i in range(1, N+1):
    cnt = bin(i).count('1')
    arr[i] = arr[i%cnt] + 1

x = int(X, 2)
pop = X.count('1')
plu = x % (pop+1)
mai = x % (pop-1) if pop>1 else 0


for i in range(N):
    
    if X[i] == '0':
        
        res = (plu + pow(2, N-1-i, pop+1)) % (pop+1)
    else:
        if pop == 1:
            print(0)
            continue
        
        res = (mai - pow(2, N-1-i, pop-1)) % (pop-1)
    print(arr[res] + 1)

Solution (Python):
n = int(input())
x = input()

original_pop_count = x.count('1')
one_pop_count = original_pop_count - 1
zero_pop_count = original_pop_count + 1

one_mod = 0
zero_mod = 0

for b in x:
    
    if one_pop_count != 0:
        one_mod = (one_mod*2 + int(b) ) % one_pop_count
    zero_mod = (zero_mod*2 + int(b) ) % zero_pop_count


f = [0]*220000
pop_count = [0]*220000
for i in range(1,220000):
    pop_count[i] = pop_count[i//2] + i%2 
    f[i] = f[i % pop_count[i]] + 1


one_pow2 = [1]*220000
zero_pow2 = [1]*220000
for i in range(1, 220000): 
    if one_pop_count != 0:
        one_pow2[i] = one_pow2[i-1] * 2 % one_pop_count
    zero_pow2[i] = zero_pow2[i-1] * 2 % zero_pop_count


for i  in range(n-1, -1, -1):
    if x[n-1-i] == '1':
        if one_pop_count != 0:
            nxt = one_mod
            nxt -= one_pow2[i]
            nxt %= one_pop_count 
            print(f[nxt]+1)
        else:
            print(0)
        
    if x[n-1-i] == '0':
        nxt = zero_mod
        nxt += zero_pow2[i]
        nxt %= zero_pop_count
        print(f[nxt]+1)

Solution (Python):
from collections import Counter
import sys
sys.setrecursionlimit(10 ** 6)



def dfs(n):
    if memo[n] >= 0:
        rst = memo[n]
    else:
        tmp = n
        one = 0
        while tmp > 0:
            one += tmp & 1
            tmp >>= 1
        m = n % one
        rst = 1 if m == 0 else 1 + dfs(m)
        memo[n] = rst
    return rst


N = int(input())
X = list(map(int, list(input())))
one = Counter(X)[1]



if one > 1:
    Sm = 0
    mm = one - 1
    tm = 1
    for i in range(N - 1, -1, -1):
        tm %= mm
        if X[i] == 1:
            Sm += tm
            Sm %= mm
        tm *= 2

Sp = 0
mp = one + 1
tp = 1
for i in range(N - 1, -1, -1):
    tp %= mp
    if X[i] == 1:
        Sp += tp
        Sp %= mp
    tp *= 2


memo = [-1] * (2 * (10 ** 5) + 10)
memo[0] = 0

for i in range(N):
    
    if X[i] == 0:
        m = (Sp + pow(2, N - 1 - i, mp)) % mp
    elif one > 1:
        m = (Sm - pow(2, N - 1 - i, mm)) % mm
    else:  
        print(0)
        continue
    cnt = 1

    
    cnt += dfs(m)
    print(cnt)

Solution (Python):
import math
N = int(input())
S = input()

lst0 = [0]*N
lst1 = [0]*N
lst0[0] = 1
lst1[0] = 1
c = S.count('1')
m0 = int(S[-1])
m1 = int(S[-1])
for i in range(1, N):
    lst0[i] += (lst0[i-1]*2)%(c+1)
    if c == 1:lst1[i] = 0
    else: lst1[i] += (lst1[i-1]*2)%(c-1)
    m0 += lst0[i] * int(S[N - 1- i])
    m0 %= c+1
    m1 += (lst1[i] * int(S[N - 1 - i]))
    if c == 1: m1 = 0
    else: m1 %= c-1

memo = [0]*(N+1)

def calc(a):
    global ans, memo
    if a == 0: return ans
    ans += 1
    if memo[a] != 0:
        b = memo[a]
    else:
        b = bin(a).count('1')
        memo[a] = b
    return calc(a%b)
    
for i in range(N):
    if S[i] == '1':
        b = c - 1
        if b == 0: a = 0
        else: a = max((m1 - lst1[N - 1 - i])%b, (m1 - lst1[N - 1 - i]+ b)%b)
    else:
        b = c + 1
        a = (m0 + lst0[N - 1 - i])%b
    if b == 0: print(0)
    elif a == 0:print(1)
    else:
        ans = 1
        print(calc(a))

Solution (Python):
from collections import Counter
import sys
sys.setrecursionlimit(10 ** 6)


def dfs(n):
    if memo[n] >= 0:
        rst = memo[n]
    else:
        tmp = n
        one = 0
        while tmp > 0:
            one += tmp & 1
            tmp >>= 1
        m = n % one
        rst = 1 if m == 0 else 1 + dfs(m)
        memo[n] = rst
    return rst


N = int(input())
X = list(map(int, list(input())))
one = Counter(X)[1]


if one > 1:
    Sm = 0
    mm = one - 1
    tm = 1
    for i in range(N - 1, -1, -1):
        tm %= mm
        if X[i] == 1:
            Sm += tm
            Sm %= mm
        tm *= 2

Sp = 0
mp = one + 1
tp = 1
for i in range(N - 1, -1, -1):
    tp %= mp
    if X[i] == 1:
        Sp += tp
        Sp %= mp
    tp *= 2


memo = [-1] * (2 * (10 ** 5) + 10)
memo[0] = 0

for i in range(N):
    if X[i] == 0:
        m = (Sp + pow(2, N - 1 - i, mp)) % mp
    elif one > 1:
        m = (Sm - pow(2, N - 1 - i, mm)) % mm
    else:
        print(0)
        continue
    print(1 + dfs(m))

Solution (Python):
def modpow(a, n, m):
    r = 1
    while n > 0:
        if n & 1:
            r = r*a % m
        a = a*a % m
        n >>= 1
    return r

N = int(input())
X = input()
d = sum([y == '1' for y in X])
A,B = 0,0
f = list([0 for _ in range(N+1)])

for i in range(N):
	if X[i] == '1':
		if not d==1:
			A += modpow(2, N-i-1, d-1)
		B += modpow(2, N-i-1, d+1)
	t,c = i+1,0
	for j in range(18):
		if t & 1<<j:
			c += 1
	f[t] = f[t%c]+1

for i in range(N):
	c = 0
	if X[i]=='1' and not d==1:
		c = f[(A-modpow(2,N-i-1,d-1))%(d-1)]+1
	elif X[i] == '0':
		c = f[(B+modpow(2,N-i-1,d+1))%(d+1)]+1
	print(c)