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):
class ModInt:
    def __init__(self, x, MOD):
        self.x = x % MOD
        self.m = MOD

    def __add__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x + other.x, self.m)
        else:
            return ModInt(self.x + other, self.m)

    __radd__ = __add__

    def __sub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x - other.x, self.m)
        else:
            return ModInt(self.x - other, self.m)

    def __rsub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(other.x - self.x, self.m)
        else:
            return ModInt(other - self.x, self.m)

    def __pow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(self.x, other.x, self.m), self.m)
        else:
            ModInt(pow(self.x, other, self.m), self.m)

    def __rpow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(other.x, self.x, self.m), self.m)
        else:
            ModInt(pow(other, self.x, self.m), self.m)

N = int(input())
X = list(map(int, input()))
Xc = sum(X)

if Xc == 0:
    [print(1) for i in range(N)]
elif Xc == 1:
    ans1 = ModInt(0, Xc+1)
    for j in range(N):
        if X[j]:
            ans1 += pow(2,N-1-j,Xc+1)

    for j in range(N):
        if X[j]:
            print(0)
        else:
            print(2) if X[N-1] or j == N-1 else print(1)
else:
    ans1 = ModInt(0, Xc+1)
    ans2 = ModInt(0, Xc-1)
    for j in range(N):
        if X[j]:
            ans1 += pow(2,N-1-j,Xc+1)
            ans2 += pow(2,N-1-j,Xc-1)

    for i in range(N):
        if X[i]:
            ans = ans2 - pow(2,N-1-i,Xc-1)
        else:
            ans = ans1 + pow(2,N-1-i,Xc+1)
        count = 1
        while ans.x > 0:
            tmp = str(bin(ans.x)).count('1')
            ans.x %= tmp
            count += 1
        print(count)

Solution (Python):
N = int(input())
X = input()
c = X.count('1')
if c == 0:
  for i in range(N):
    print(1)
  quit()
if c == 1:
  if int(X[-1]):
    for i in range(N-1):
      print(2)
    print(0)
  else:
    for i in range(N-1):
      if int(X[i]):
        print(0)
      else:
        print(1)
    print(2)
  quit()

memo = {0:0, 1:1, 2:1}
def calc(x):
  global memo
  if x in memo:
    return memo[x]
  c = bin(x).count('1')
  y = x % c
  res = calc(y) + 1
  memo[x] = res

for i in range(3, 2*10**5+1):
  calc(i)

Xmodp = Xmodm = 0
digit_p = digit_m = 1
digit = {}
for i in range(N):
  if int(X[-i-1]):
    Xmodp += digit_p
    Xmodp %= c + 1
    Xmodm += digit_m
    Xmodm %= c - 1
  digit[i] = [digit_p, digit_m]
  digit_p = (digit_p * 2) % (c+1)
  digit_m = (digit_m * 2) % (c-1)

ans = []
for i in range(N):
  x = int(X[-i-1])
  if x:
    ans.append(memo[(Xmodm - digit[i][1]) % (c-1)] + 1)
  else:
    ans.append(memo[(Xmodp + digit[i][0]) % (c+1)] + 1)

ans = ans[::-1]
print(*ans, sep='\n')

Solution (Python):
def resolve():
    
    
    
    

    def popcount(n):
        c=format(n,'b').count('1')
        if c!=0:
            return n%c
        else:
            return 0
    def f(n):
        count=0
        while n>0:
            n=popcount(n)
            count+=1
        return count
        
    n=int(input())    
    x=input()
    cnt=x.count('1')
    x10=int(x,2)
    ans=[]
    a=x10%(cnt+1)
    if cnt==1:
        b=0
    else:
        b=x10%(cnt-1)
    for i in range(n):
        if x[i]=='1' and cnt==1:
            print(0)
            continue
        elif x[i]=='1':
            cal=(b-pow(2,n-1-i,cnt-1))%(cnt-1)
        else:
            cal=(a+pow(2,n-1-i,cnt+1))%(cnt+1)
        print(f(cal)+1)

if __name__ == '__main__':
    resolve()

Solution (Python):


n = int(input())
x = input()
b = [0] * (n+1)
for i in range(1, n+1):
    bit_count = 0
    for j in range(20):
        if i >> j & 1:
            bit_count += 1
    b[i] = bit_count

popcount = [0] * (n+1)
cnt = x.count('1')
for i in range(1, n+1):
    popcount[i] = popcount[i % b[i]] + 1

ans = []
if cnt == 1:
    tmp = 0
    for i in range(n):
        if x[i] == '1':
            tmp += pow(2, n-i-1, 2)
            tmp %= 2
    for i in range(n):
        if x[i] == '1':
            ans.append(0)
        else:
            ans.append(popcount[(tmp - pow(2, n-i-1, 2)) % 2] + 1)
else:
    tmp1 = 0
    tmp2 = 0
    for i in range(n):
        if x[i] == '1':
            tmp1 += pow(2, n-i-1, cnt + 1)
            tmp2 += pow(2, n-i-1, cnt - 1)
    for i in range(n):
        if x[i] == '1':
            ans.append(popcount[(tmp2 - pow(2, n-i-1, cnt - 1)) % (cnt - 1)] + 1)
        else:
            ans.append(popcount[(tmp1 + pow(2, n-i-1, cnt + 1)) % (cnt + 1)] + 1)

for i in ans:
    print(i)

Solution (Python):
def cin():
    return input().split()
def qpow(a,b,p):
    if p == 1 or p == 0:
        return 0
    a = (a%p+p)%p
    ans = 1
    while b!=0:
        if (b&1) != 0:
            ans = (ans * a) % p
        b >>= 1
        a = a * a  % p
    return ans

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

n = int(input())
x = list(input())
x = x[::-1]
cnt = 0;l = len(x)
r1 = 0;r2 = 0
for i in x:
    if i == '1':
        cnt += 1
i = 0
while i < l:
    if x[i] == '1':
        r1 += qpow(2,i,cnt+1)
        r2 += qpow(2,i,cnt-1)
    i += 1
i = 0
a = []
while i < l:
    if x[i] == '0':
        t = f((r1+qpow(2,i,cnt+1))%(cnt+1))+ 1
    else:
        if cnt-1 !=  0:
            t = f((r2-qpow(2,i,cnt-1)+(cnt-1))%(cnt-1)) + 1
        else:
            t = 0
    i += 1
    a.append(t)
a = a[::-1]
for i in a:
    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):
def f(n):
    if n == 0:
        return 0
    return f(n % bin(n).count("1")) + 1


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)

Solution (Python):
def pop_count(n):
    return sum(n >> i & 1 for i in range(n.bit_length()))


def f(n):
    if n == 0:
        return 0
    return f(n % pop_count(n)) + 1


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)

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

n = int(input())
x = list(input())
bit_cnt = x.count('1')


pos = [0] * n
pos_total = 0


neg = [0] * n
neg_total = 0

base = 1
for i in range(n):
    pos[-i-1] = base%(bit_cnt+1)
    if x[-i-1] == '1':
        
        pos_total = (pos_total + base) % (bit_cnt+1)
    base = (base*2) % (bit_cnt+1)

base = 1
if bit_cnt == 1:
    
    pass
else:
    for i in range(n):
        neg[-i-1] = base%(bit_cnt-1)
        if x[-i-1] == '1':
            
            neg_total = (neg_total + base) % (bit_cnt-1)
        base = (base*2) % (bit_cnt-1)

def popcount(n):
    s = list(bin(n)[2:])
    return s.count('1')

memo = {}
memo[0] = 0
def dfs(n, depth=0):
    if n in memo:
        return depth + memo[n]
    else:
        ret = dfs(n%popcount(n), depth+1)
        
        return ret

ans = []
for i in range(n):
    if x[i] == '0':
        st = (pos_total + pos[i]) % (bit_cnt+1)
        print(dfs(st, depth=1))
    elif bit_cnt == 1:
        
        print(0)
    else:
        st = (neg_total - neg[i]) % (bit_cnt-1)
        print(dfs(st, depth=1))

Solution (Python):
N = int(input())
X = str(input())
X10 = int(X,2)

one_num = X.count("1")
X10_pl = X10%(one_num+1)
if one_num>1:
    X10_mi = X10%(one_num-1)
else:
    X10_mi = 0

for i in range(N):
    target = int(X[i])
    
    if target == 0:
        ones = one_num + 1
        plus = pow(2,N-i-1,ones)
        Xnow = (X10_pl + plus)%ones
        
    else:
        if one_num == 1:
            print(0)
            continue
        ones = one_num-1
        plus = -pow(2,N-i-1,ones)
        Xnow = (X10_mi + plus)%ones

    count=1
    
    while Xnow > 0:
        Xnow2 = bin(Xnow)
        ones = Xnow2.count("1")
        Xnow = Xnow%ones
        count+=1
        
    print(count)

Solution (Python):



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


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


def solve(n):
    if n == 0:
        return 0
    c = popcount(n)
    return 1 + solve(n % c)


def main():
    c = X.count("1")
    if c == 0:
        for _ in range(N):
            print(1)
        return
    a, b = 0, 0
    for i in range(N):
        if c == 1 and X[-1 - i] == "1":
            b = (b + pow(2, i, c + 1)) % (c + 1)
        elif X[-1 - i] == "1":
            a = (a + pow(2, i, c - 1)) % (c - 1)
            b = (b + pow(2, i, c + 1)) % (c + 1)
    for i in range(N):
        if c == 1 and X[i] == "1":
            print(0)
            continue
        if X[i] == "1":
            m = c - 1
            w = (a - pow(2, N - 1 - i, m)) % m
        else:
            m = c + 1
            w = (b + pow(2, N - 1 - i, m)) % m
        ans = solve(w) + 1
        print(ans)
            

if __name__ == "__main__":
    main()

Solution (Python):


import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    N = int(input())
    S = input()
    cnt0 = S.count("1")

    if cnt0 == 0:
        print("\n".join(map(str, [1]*N)))
        return

    X = int(S, 2)

    def f2():
        cache = [0] * (cnt0 + 1)
        i = 1
        bi = []
        while i <= cnt0:
            bi.append(i)
            i <<= 1
        from collections import deque
        dq = deque([(0, 0, 0)])
        ls = len(bi) -1
        while dq:
            i, x, cnt = dq.popleft()

            cnt += 1
            for j in range(i, ls):
                y = x | bi[j]

                if y > cnt0: break

                cache[y] = cache[y % cnt] + 1

                j += 1
                dq.append((j, y, cnt))
            else:
                y = x | bi[ls]
                if y > cnt0: continue
                cache[y] = cache[y % cnt] + 1
        return cache


    memo = f2()

    dc = []
    for v in [1, -1]:
        x = cnt0 + v
        y = X % x if x else 0
        dc.append((x, v, y, [1, N-1]))

    ans = [0] * N
    for i in reversed(range(N)):
        cnt, v, n, m1 = dc[0 if S[i] == "0" else 1]

        if cnt == 0:
            ans[i] = 0
            continue

        m2 = (m1[0]<<(m1[1]-i)) % cnt
        n = (n + v*m2) % cnt
        m1[0], m1[1] =  m2, i

        ans[i] = 1 + memo[n]

    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    resolve()

Solution (Python):
N = int(input())
x2 = input()
x10 = int(x2, 2)
popc =  x2.count("1")





if popc <= 1:
    xp = x10%(popc+1)
    xm = 0
else:
    xp = x10%(popc+1)
    xm = x10%(popc-1)




for i in range(N):
    if x2[i] == "1":
        if popc == 1:
            print(0)
            continue
        tmp = (xm - pow(2, N-i-1, popc-1))%(popc-1)
    else:
        tmp = (xp + pow(2, N-i-1, popc+1))%(popc+1)
        
    
    ans = 1
    while tmp > 0:
        tmp %= bin(tmp).count("1")
        ans += 1
    print(ans)

Solution (Python):
def main():
    """
    a % d + c % d = (a + c) % dだ
    整数の余りを取るのと，整数の各桁の余りを取るのが同じを使うこともあった　→　Digits Parade
    """
    N = int(input())
    X = input()
    t = X.count("1")
    v1, v2 = int(X, 2) % (t+1), int(X, 2) % (t-1) if t != 1 else 0
    for i in range(N):
        ans = 1
        x = 0
        if X[i] == "0":
            
            x = v1 + pow(2, N-i-1, t+1)
            x %= t+1
        elif t != 1 and X[i] == "1":
            
            x = v2 - pow(2, N-i-1, t-1)
            x %= t-1
        else:
            
            
            ans = 0
        while x > 0:
            x %= "{:0b}".format(x).count("1")
            ans += 1
        print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    """
    a % d + c % d = (a + c) % dだ
    整数の余りを取るのと，整数の各桁の余りを取るのが同じこともあった　→　Digits Parade
    """
    N = int(input())
    X = input()
    t = X.count("1")
    v1, v2 = int(X, 2) % (t+1), int(X, 2) % (t-1) if t != 1 else 0
    for i in range(N):
        ans = 1
        x = 0
        if X[i] == "0":
            
            x = v1 + pow(2, N-i-1, t+1)
            x %= t+1
        elif t != 1 and X[i] == "1":
            
            x = v2 - pow(2, N-i-1, t-1)
            x %= t-1
        else:
            
            
            ans = 0
        while x > 0:
            x %= "{:0b}".format(x).count("1")
            ans += 1
        print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
X = input()
memo = [-1] * (N+1)
memo[0] = 0

def popcount(k):
    return bin(k).count('1')

def calc(k):
    pop = popcount(k)
    
    key = k
    if memo[key] < 0:
        k %= pop
        if k == 0:
            memo[key] = 1
        else:
            memo[key] = calc(k) + 1
    return memo[key]

K = int(X, 2)
one = popcount(K)
if one == 0:
    K_MOD = K
elif one == 1:
    K_MOD   = 0
    K_MOD_M = K
else:
    K_MOD   = K % one
    K_MOD_M = K % (one-1)
K_MOD_P = K % (one+1)

T_M = [1]*(N+1)
T_P = [1]*(N+1)
for i in range(1,N+1):
    if one > 1:
        T_M[i] = (T_M[i-1]*2) % (one-1)
    T_P[i] = (T_P[i-1]*2) % (one+1)

for i in range(N):
    if X[i] == '1':
        pop = one - 1
        k = K_MOD_M - T_M[N-i-1]
    else:
        pop = one + 1
        k = K_MOD_P + T_P[N-i-1]

    if pop == 0:
        print(0)
    else:
        k %= pop
        print(calc(k)+1)

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

def popcount(n):
    return bin(n).count('1')


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


X_popcount = popcount(X)
X_mod_p = X%(X_popcount+1)
if X_popcount != 1:
    X_mod_m = X%(X_popcount-1)
for i in range(N):
    X_i = X ^ (1<<(N-i-1))
    if X_i == 0:
        ans = 0
    elif X>>(N-i-1)&1 == 1:
        if X_popcount == 1:
            ans = 1
        else:
            ans = f((X_mod_m-pow(2, N-i-1, X_popcount-1))%(X_popcount-1))
    else:
        ans = f((X_mod_p+pow(2, N-i-1, X_popcount+1))%(X_popcount+1))
    print(ans)

Solution (Python):
n = int(input())
x_bin = input()
x = int(x_bin, 2)

pc = x_bin.count('1')
pc_p = pc + 1
pc_m = pc - 1

if pc == 1:
    for i, v in enumerate(x_bin):
        if v == '1':
            print(0)
        else:
            if i != n-1:
                if x_bin[-1] == '0':
                    print(1)
                else:
                    print(2)
            else:
                print(2)
    exit()

p = {0: 1}
m = {0: 1}
for i in range(1, n):
    p[i] = p[i-1]*2 % pc_p
    m[i] = m[i-1]*2 % pc_m

rest = {0: 0}
for i in range(1, pc + 1):
    rest[i] = rest[i % bin(i).count('1')] + 1

x_p = x % pc_p
x_m = x % pc_m

for i in range(n, 0, -1):
    if x_bin[n-i] == '1':
        a = (x_m - m[i-1]) % pc_m
        print(rest[a] + 1)
    else:
        a = (x_p + p[i-1]) % pc_p
        print(rest[a] + 1)

Solution (Python):
N = int(input())
X = input()
memo = {}
X_int = int(X, 2)


def popcount(n: int):
    x = bin(n)[2:]
    return x.count("1")


pcf = popcount(int(X, 2))
pcm = pcf - 1
pcp = pcf + 1
xm = X_int % pcm if pcm != 0 else 0
xp = X_int % pcp


def f(n: int, ops: int):

    while n != 0:
        n %= popcount(n)
        ops += 1
    return ops


def rev(x: str, i: int):
    if x == "1":
        if pcm == 0:
            return -1
        n = (xm - (pow(2, N-i-1, pcm))) % pcm
    else:
        n = (xp + (pow(2, N-i-1, pcp))) % pcp
    return n


if __name__ == "__main__":
    for i, x in enumerate(X):
        n = rev(x, i)
        if n == -1:
            print(0)
        else:
            print(f(n, 1))

Solution (Python):

def f(j):
    cnt = 0
    while j:
        j %= bin(j).count("1")
        cnt += 1
    return cnt

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


X = int(S, 2)


pcx = S.count("1")


pc1 = X % (pcx - 1) if pcx > 1 else 0
pc2 = X % (pcx + 1)

for i, y in enumerate(S):
    k = N - 1 - i
    if y == "0":
        print(f((pc2 + pow(2, k, pcx + 1)) % (pcx + 1)) + 1)
    elif pcx > 1:
        print(f((pc1 - pow(2, k, pcx - 1)) % (pcx - 1)) + 1)
    else:
        print(0)

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

N, X = open(0).read().split()
N = int(N)
XS = list(X)
X = int(X, 2)

p = popcount(X)
xi = X % (p + 1)
if p == 1:
    xd = 0
else:
    xd = X % (p - 1)

for i in range(N):
    if XS[i] == "1":
        if p == 1:
            print(0)
            continue
        else:
            k = pow(2, N - 1 - i, p - 1)
            x = (xd - k) % (p - 1)
    else:
        k = pow(2, N - 1 - i, p + 1)
        x = (xi + k) % (p + 1)
    ans = 1
    while x != 0:
        x %= popcount(x)
        ans += 1
    print(ans)

Solution (Python):
N = int(input())
x2 = input()
x10 = int(x2, 2)
popc =  x2.count("1")





if popc <= 1:
    xp = x10%(popc+1)
    xm = 0
else:
    xp = x10%(popc+1)
    xm = x10%(popc-1)




for i in range(N):
    if x2[i] == "1":
        if popc == 1:
            print(0)
            continue
        tmp = (xm - pow(2, N-i-1, popc-1))%(popc-1)
    else:
        tmp = (xp + pow(2, N-i-1, popc+1))%(popc+1)
        
    
    ans = 1
    while tmp > 0:
        tmp %= bin(tmp).count("1")
        ans += 1
    print(ans)

Solution (Python):
def main():
    """
    a % d + c % d = (a + c) % dだよね
    整数の余りを取るのと，整数の各桁の余りを取るのが同じこともあった　→　Digits Parade
    """
    N = int(input())
    X = input()
    t = X.count("1")
    x1, x2 = int(X, 2) % (t+1), int(X, 2) % (t-1) if t != 1 else 0
    for i in range(N):
        ans = 1
        x = 0
        if X[i] == "0":
            
            p = pow(2, N-i-1, t+1)
            x = x1 + p
            x %= t+1
        elif t != 1 and X[i] == "1":
            p = pow(2, N-i-1, t-1)
            x = x2 - p
            x %= (t-1)
        else:
            
            
            ans = 0
        while x > 0:
            x %= "{:0b}".format(x).count("1")
            ans += 1
        print(ans)


if __name__ == '__main__':
    main()

Solution (Python):


import math

import itertools
from collections import deque
from collections import Counter



import bisect
n=int(input())
x=input()
p=0
for i in x:
    if i=="1":
        p+=1
rp=0
rq=0
for i in range(n):
    if x[i]=="1":
        rp+=pow(2,(n-1-i),p+1)
        rp%=p+1
        if p!=1:
          rq+=pow(2,(n-1-i),p-1)
          rq%=p-1
        else:
          rq=pow(2,(n-1-i))
def popcnt1(n):
    return bin(n).count("1")
res=[0]*n

for i in range(1,n+1):
    res[i-1]=i%popcnt1(i)

for i in range(n):
    ans=0
    if x[i]=="1":
        if p==1:
          print(0)
          continue
        q=rq-pow(2,(n-1-i),p-1)
        q%=p-1
        while True:
            if q==0:
                print(1+ans)
                break
            ans+=1
            q=res[q-1]
    else:
        q=rp+pow(2,(n-1-i),p+1)
        q%=p+1
        while True:
            if q==0:
                print(1+ans)
                break
            ans+=1
            q=res[q-1]

Solution (Python):


import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    N = int(input())
    S = input()
    cnt0 = S.count("1")

    if cnt0 == 0:
        print("\n".join(map(str, [1]*N)))
        return

    X = int(S, 2)

    def f2():
        cache = [-1] * max(9, cnt0+1)
        cache[0] = 0
        for i in range(4): cache[1<<i] = 1
        def f2(x):
            if cache[x] != -1:
                return cache[x]

            y = bin(x).count("1")
            z = 1 + f2(x % y)
            cache[x] = z

            return z
        f2.cache = cache
        return f2
    f2 = f2()

    dc = []
    for v in [1, -1]:
        x = cnt0 + v
        y = X % x if x else 0
        dc.append((x, v, y, [1, N-1]))

    ans = [0] * N
    for i in reversed(range(N)):
        cnt, v, n, m1 = dc[0 if S[i] == "0" else 1]

        if cnt == 0:
            ans[i] = 0
            continue

        m2 = (m1[0]<<(m1[1]-i)) % cnt
        n = (n + v*m2) % cnt
        m1[0], m1[1] =  m2, i

        ans[i] = 1 + f2(n)

    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    resolve()

Solution (Python):
n = int(input())
x = input()
original_pop_cnt = x.count("1")

pop_cnt_add = original_pop_cnt + 1
pop_cnt_sub = original_pop_cnt - 1

n_after_once_popcount_add = 0
n_after_once_popcount_sub = 0

for i in range(n):
    n_after_once_popcount_add = (n_after_once_popcount_add * 2 + int(x[i])) % pop_cnt_add
    if pop_cnt_sub != 0:
        n_after_once_popcount_sub = (n_after_once_popcount_sub * 2 + int(x[i])) % pop_cnt_sub

pow_add = [1] * 250000
pow_sub = [1] * 250000
for i in range(1, n + 100):
    pow_add[i] = (pow_add[i-1]*2) % pop_cnt_add
    if pop_cnt_sub != 0:
        pow_sub[i] = (pow_sub[i-1]*2) % pop_cnt_sub

def f(nex):
    ans = 0
    num = nex
    while num != 0:
        num = num % bin(num).count("1")
        ans += 1
    return ans

for i in range(n-1, -1, -1):
    if x[n - 1 - i] == "0":
        nxt = n_after_once_popcount_add
        nxt = nxt + pow_add[i]
        nxt = nxt % pop_cnt_add
        print(f(nxt) + 1)
    if x[n - 1 - i] == "1":
        if pop_cnt_sub != 0:
            nxt = n_after_once_popcount_sub
            nxt = nxt - pow_sub[i]
            nxt = nxt % pop_cnt_sub
            print(f(nxt) + 1)
        else:
            print(0)

Solution (Python):

n=int(input())
x=input()

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

intx = int( "0b"+x ,0 )
popcount0 = x.count("1")

intx_mod_pp1 = intx %(popcount0+1)
if popcount0!=1:
    intx_mod_pm1 = intx %(popcount0-1)
    
jisho = ["yet"]*n
for i in range(n):
    if x[i]=="1" and popcount0==1:
        print(0)
        continue
    
    pow2ip = pow(2,n-i-1,popcount0+1)
    if popcount0!=1:   pow2im = pow(2,n-i-1,popcount0-1)
    
    intxi=1
    c=0
    while intxi!=0:
        if c==0:
            if x[i]=="0":
                pop = popcount0+1
                intxi = (intx_mod_pp1 + pow2ip%pop )%pop
            else:
                pop = popcount0-1
                intxi = (intx_mod_pm1 - pow2im%pop )%pop        
        else:
            if jisho[intxi]=="yet":
                togo = intxi%popcount(intxi)
                jisho[intxi]= togo
                intxi = togo
            else:
                intxi =jisho[intxi]
        c+=1
    print(c)

Solution (Python):

n=int(input())
x=input()

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

intx = int( "0b"+x ,0 )
popcount0 = x.count("1")

intx_mod_pp1 = intx %(popcount0+1)
if popcount0!=1:
    intx_mod_pm1 = intx %(popcount0-1)
    

jisho = ["yet"]*n



for i in range(n):
    if x[i]=="1" and popcount0==1:
        print(0)
        continue
    
    pow2ip = pow(2,n-i-1,popcount0+1)
    if popcount0!=1:
        pow2im = pow(2,n-i-1,popcount0-1)

    if False:
        pass
    
    
    else:
        intxi=1
        c=0
        while intxi!=0:
            if c==0:
                if x[i]=="0":
                    pop = popcount0+1
                    intxi = (intx_mod_pp1 + pow2ip%pop )%pop
                else:
                    pop = popcount0-1
                    intxi = (intx_mod_pm1 - pow2im%pop )%pop        
            else:
                if jisho[intxi]=="yet":
                    togo = intxi%popcount(intxi)
                    jisho[intxi]= togo
                    intxi = togo
                else:
                    intxi =jisho[intxi]
                
            
            c+=1
        print(c)

Solution (Python):
table = [0 for i in range(2*10**5+5)]
for i in range(2*10**5+5):
    table[i] = "{:0b}".format(i).count("1")


def main():
    """
    a % d + c % d = (a + c) % dだよね
    整数の余りを取るのと，整数の各桁の余りを取るのが同じこともあった　→　Digits Parade
    """
    N = int(input())
    X = input()
    t = X.count("1")
    x1, x2 = int(X, 2) % (t+1), int(X, 2) % (t-1) if t != 1 else 0
    for i in range(N):
        ans = 1
        x = 0
        if X[i] == "0":
            
            p = pow(2, N-i-1, t+1)
            x = x1 + p
            x %= t+1
        elif t != 1 and X[i] == "1":
            p = pow(2, N-i-1, t-1)
            x = x2 - p
            x %= (t-1)
        else:
            
            
            ans = 0
        while x > 0:
            x %= table[x]
            ans += 1
        print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
S = input()
X = int(S, 2)
pcx = S.count('1')

pc1 = X % (pcx - 1) if pcx > 1 else 0

pc2 = X % (pcx + 1)


def f(j):
    cnt = 0
    while j:
        j %= bin(j).count('1')
        cnt += 1
    return cnt


for i, y in enumerate(S):
    k = N - i - 1
    if y == "0":  
        print(f((pc2 + pow(2, k, pcx + 1)) % (pcx + 1)) + 1)
    elif pcx > 1:
        print(f((pc1 - pow(2, k, pcx - 1)) % (pcx - 1)) + 1)
    else:
        print(0)

Solution (Python):
N = int(input())
X = str(input())
F = [0] * N

def calc_f(n:int)->int:
    global F
    x = n
    res = 0
    while 0 < x:
        if F[x] != 0:
            res += F[x]
            break
        pop = bin(n).count('1')
        x %= pop
        res += 1
    F[n] = res


for i in range(1, N):
    calc_f(i)


pop_ini = X.count('1')
pp = pop_ini + 1  
pm = pop_ini - 1  


ap = [0] * N  
am = [0] * N  
for i in range(N):
    ap[i] = pow(2, N-1-i, pp)
    if 0 < pm:
        am[i] = pow(2, N-1-i, pm)


fp = 0  
fm = 0  
for i in range(N):
    if X[i] == '1':
        fp = (fp + ap[i]) % pp
        if 0 < pm:
            fm = (fm + am[i]) % pm


for i in range(N):
    ans = 1
    if X[i] == '1':
        if 0 < pm:
            v = (fm + pm - am[i]) % pm
        else:
            ans = 0
            v = 0
    else:
        v = (fp + ap[i]) % pp
    if 0 < v:
        ans += F[v]
    print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

def p_count(n):
    return bin(n)[2:].count('1')


n = int(input())
x = input().rstrip()
x_dec = int(x,base = 2)

pop_cnt = x.count('1')
pop_cnt_0 = (pop_cnt + 1)
pop_cnt_1 = (pop_cnt - 1)
x_0 = pow(x_dec,1,pop_cnt_0)
x_1 = pow(x_dec,1,pop_cnt_1) if pop_cnt_1 > 0 else 0

x_bit = [0]*n

for i in range(n-1,-1,-1):
    if x[i] == '0':
        x_bit[i] = (x_0 + pow(2,n-1-i,pop_cnt_0))%pop_cnt_0
        
        
    else:
        if pop_cnt_1 > 0:
            x_bit[i] = (x_1 - pow(2,n-1-i,pop_cnt_1))
            x_bit[i] = x_bit[i] if x_bit[i] >= 0 else x_bit[i] + pop_cnt_1
        else:
            x_bit[i] = -1

anslist = []
for i in range(n):
    if x_bit[i] == -1:
        anslist.append(0)
        continue
    ans = 1 
    now = x_bit[i]
    while True:
        if now == 0:
            break
        now = now%p_count(now)
        
        ans += 1
    anslist.append(ans)


for ans in anslist:
    print(ans)

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
 

if one_pop_count == 0:
  one_mod = 0
else:
  one_mod = int(x, 2) % one_pop_count
zero_mod = int(x, 2) % 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):
N = int(input())
X_2 = input()
X_10 = int(X_2, 2)

y = X_2.count('1')

a = X_10%(y+1)
if y==1:
    b = 0
else:
    b = X_10%(y-1)

for i in range(N):
    if X_2[i] == '1' and y == 1:
        print(0)
        continue
    elif X_2[i] == '1':
        x = (b-pow(2, N-1-i, y-1))%(y-1)
    else:
        x = (a+pow(2, N-1-i, y+1))%(y+1)
    count = 1
    while x!=0:
        x %= bin(x)[2:].count('1')
        count += 1
    print(count)