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):
n = int(input())
x = input()

dp = [0] * n
for i in range(1, n-1):
    tmp = i
    cnt = 0
    while tmp > 0:
        cnt += tmp % 2
        tmp //= 2
    dp[i] = dp[i%cnt] + 1

c = x.count('1')

if c == 1:
    dp_2 = [0] * n
    dp_2[0] = 1 % (c + 1)
    for i in range(1, n):
        dp_2[i] = (2 * dp_2[i-1]) % (c + 1)

    mod_2 = 0
    for i in range(n):
        if x[i] == '1':
            mod_2 = (mod_2 + dp_2[n-i-1]) % (c + 1)

    for i in range(n):
        if x[i] == '1':
            print(0)
        else:
            mod = (mod_2 + dp_2[n-i-1]) % (c + 1)
            print(dp[mod] + 1)
else:
    dp_1 = [0] * n
    dp_2 = [0] * n
    dp_1[0] = 1 % (c - 1)
    dp_2[0] = 1 % (c + 1)
    for i in range(1, n):
        dp_1[i] = (2 * dp_1[i-1]) % (c - 1)
        dp_2[i] = (2 * dp_2[i-1]) % (c + 1)

    mod_1 = 0
    mod_2 = 0
    for i in range(n):
        if x[i] == '1':
            mod_1 = (mod_1 + dp_1[n-i-1]) % (c - 1)
            mod_2 = (mod_2 + dp_2[n-i-1]) % (c + 1)

    for i in range(n):
        if x[i] == '1':
            mod = (mod_1 - dp_1[n-i-1]) % (c - 1)
            print(dp[mod] + 1)
        else:
            mod = (mod_2 + dp_2[n-i-1]) % (c + 1)
            print(dp[mod] + 1)

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

def main():
    n = int(input())
    x = list(input())
    for i in range(n):
        x[i] = int(x[i])
    A0 = 0
    A1 = 0
    B = sum(x)
    for i in range(n):
        if B+1 != 0:
            A0 += x[i]*pow(2,n-i-1,B+1)
            A0 %= B+1
        if B-1 != 0:
            A1 += x[i]*pow(2,n-i-1,B-1)
            A1 %= B-1
    for i in range(n):
        if x[i] == 0:
            BB = B + 1
            AA = A0 + pow(2,n-i-1,BB)
        else:
            BB = B - 1
            if BB == 0:
                AA = 0
            else:
                AA = A1 - pow(2,n-i-1,BB)
        ans = 1
        if BB == 0:
            print(0)
            continue
        while AA%BB != 0:
            AA = AA%BB
            AAA = AA
            BB = 0
            while AAA != 0:
                BB += AAA%2
                AAA //= 2
            ans += 1
        print(ans)
    
if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
x = input()
remain = [None]*(n)
ans = [1]*(n)
one = x.count("1")+1
if one == 2:
    for i in range(n):
        if x[i] == "1":
            ans[i] = 0
            remain[i] = 0

num = 0
for i in range(n-1, -1, -1):
    if x[i] == "1":
        num += pow(2, n-1-i, one)

for i in range(n):
    if x[i] == "0":
        num_temp = num+pow(2, n-1-i, one)
        num_temp %= one
        remain[i] = num_temp


one -= 2
if one == 0:
    pass

else:
    num = 0
    for i in range(n-1, -1, -1):
        if x[i] == "1":
            num += pow(2, n-1-i, one)

    for i in range(n):
        if x[i] == "1":
            num_temp = num-pow(2, n-1-i, one)
            num_temp %= one
            remain[i] = num_temp

for i in range(n):
    if remain[i] != 0:
        rem = remain[i]
        while rem != 0:
            ans[i] += 1
            popcount = format(rem, "b").count("1")
            rem %= popcount

for i in ans:
    print(i)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = input()
d = {}
def sub(val):
    if val in d:
        return d[val]
    pc = 0
    for i in range(val.bit_length()):
        if val>>i&1:
            pc += 1
    if pc==0:
        ans = 0
    else:
        tmp = val % pc
        if tmp==0:
            ans = 1
        else:
            ans = sub(tmp) + 1
    d[val] = ans
    return ans

pc = sum(item=="1" for item in a)
val0 = 0 
val1 = 0 
for i in range(n):
    if a[i]=="1":
        if pc>1:
            val0 += pow(2,n-1-i,pc-1)
        val1 += pow(2,n-1-i,pc+1)
        
ans = [None]*n

for i in range(n):
    if a[i]=="1":
        if pc==1:
            val = 0
            ans[i] = 0
        else:
            val = (val0 - pow(2,n-1-i,pc-1))%(pc-1) 
            ans[i] = sub(val) + 1

    else:
        val = (val1 + pow(2,n-1-i,pc+1))%(pc+1) 
        ans[i] = sub(val) + 1

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

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

nxt = [0]*n
zero2one = 0
one2zero = 0

cnt = 0
for i in range(n):
    if x[i]=='1':
        cnt += 1

zero2one = 0
for i in range(n):
    zero2one += int(x[i])*pow(2,n-i-1,cnt+1)
zero2one %= cnt+1

one2zero = 0
if cnt>1:
    for i in range(n):
        one2zero += int(x[i])*pow(2,n-i-1,cnt-1)
    one2zero %= cnt-1

for i in range(n):
    if x[i]=='0':
        nxt[i] = (zero2one + pow(2,n-i-1,cnt+1))%(cnt+1)
    else:
        if cnt>1:
            nxt[i] = (one2zero - pow(2,n-i-1,cnt-1))%(cnt-1)
        else:
            nxt[i] = -1

MX = 2*10**5+5
ans = [0]*MX
for i in range(MX):
    xn = bin(i)[2:]
    res = 0
    while(xn != '0'):
        l = len(xn)
        res += 1
        cnt = 0
        for j in range(l):
            if xn[j]=='1':
                cnt += 1
        after = 0
        for j in range(l):
            after += int(xn[j])*pow(2,l-j-1,cnt)
            after %= cnt
        xn = bin(after)[2:]
    ans[i]=res

for i in range(n):
    if nxt[i]==-1:
        print(0)
    else:
        print(ans[nxt[i]]+1)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def all_bit_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8) 
    x = x + (x >> 16) 
    x = x + (x >> 32) 
    return x & 0x0000007f
  
n = int(readline())
d = [0]*(n+1)
d[1] = 1
for i in range(2,n+1):
  q = all_bit_count(i)
  p = i%q
  d[i] = d[p]+1
  
x = input()
c = x.count('1')

a1 = 0
a0 = 0
C = max(1,c-1)
for i,xi in enumerate(x[::-1]):
  if xi == '1':
    a1 += pow(2,i,C)
    a1 %= C
    a0 += pow(2,i,c+1)
    a0 %= (c+1)
    
for i,xi in enumerate(x):
  if xi == '1':
    if c > 1:
      cc = (a1 - pow(2,n-1-i,C))%C
      print(d[cc]+1)
    else:
      print(0)
  else:
    cc = (a0 + pow(2,n-1-i,c+1))%(c+1)
    print(d[cc]+1)

Solution (Python):
n = int(input())
x = input()
ones = 0
for i in x:
    if i=='1':
        ones += 1
mods = [0, 0]
for i in range(n):
    if x[n-i-1]=='1':
        if ones>1:
            mods[0] += pow(2, i, ones-1)
        mods[1] += pow(2, i, ones+1)
if ones>1:
    mods[0] %= ones-1
mods[1] %= ones+1
def f(x):
    if x==0:
        return 1
    cnt = 1
    while x>0:
        p = bin(x).count('1')
        x %= p
        cnt += 1
    return cnt
for i in range(n-1, -1, -1):
    if x[n-i-1]=='1' and ones==1:
        print(0)
        continue
    if x[n-i-1]=='1':
        init = (mods[0] - pow(2, i, ones-1))%(ones-1)
    else:
        init = (mods[1] + pow(2, i, ones+1))%(ones+1)
    print(f(init))

Solution (Python):
n = int(input())
x = input()
flg = [0] * n
for i in range(n):
    if x[i] == '1':
        flg[i] = 1
x = int(x, 2)
cnt = sum(flg)
if cnt == 1:
    x_a = 0
else:
    x_a = x % (cnt - 1)
x_b = x % (cnt + 1)


for i in range(n):
    if flg[i] == 1:
        if cnt == 1:
            print(0)
            continue
        t = (x_a - pow(2, n-i-1, cnt-1)) % (cnt - 1)
    else:
        t = (x_b + pow(2, n-i-1, cnt+1)) % (cnt + 1)

    if t == 0:
        print(1)
    else:
        tmp = 1
        while t > 0:
            pop = bin(t).count('1')
            t = t % pop
            tmp += 1

        print(tmp)

Solution (Python):
def rem(n, a):
    if a == 0:
        return 0
    ans=0
    for i in n:
        ans*=2
        ans+=i
        ans%=a
    return ans
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, x = int(input()), list(map(int,input()))

p = x.count(1)
m = [0] * n
q = p - 1
if q!=0:
    m[0] = 1
    for i in range(1, n):
        m[i] = 2 * m[i - 1] % q

w = p + 1
k = [0] * n
k[0] = 1
for i in range(1, n):
    k[i] = 2 * k[i - 1] % w

s = rem(x, q)
t = rem(x, w)
for i in range(n):
    if x[i] == 0:
        a = (t + k[n - i - 1]) % w
        
    else:
        if q == 0:
            print(0)
            continue
        
        
        a = (s - m[n - i - 1]) % q

    cnt = 1
    b = popcnt(a)
    
    
    while b:
        a %= b
        b = popcnt(a)
        cnt += 1
    print(cnt)

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]
def NSTR(n): return [input() for _ in range(n)]


import time


INF = float("inf")
MOD = 10**9 + 7


def bit_sum(n):
    wa = 0
    while n > 0:
        wa += n & 1
        n >>= 1
    return wa

def bit(n, k):
    return (n >> k) & 1

def main():
    start = time.time()
    N = INT()
    X = input()
    origX = X
    wa = X.count("1")
    x = 0
    px = 0
    nx = 0
    start = time.time()
    for c in X:
        x <<= 1
        px <<= 1
        nx <<= 1
        if c == "1":
            x |= 1
            px |= 1
            nx |= 1
        px %= (wa+1)
        if wa != 1:
            nx %= (wa-1)
        else:
            nx %= wa
    if wa == 1:
        nx = None
    
    
    X = x
    table = [None]*(N+1)
    table[0] = 0
    table[1] = 1
    for i in range(1, N+1):
        table[i] = table[i % bit_sum(i)] + 1
    
    

    for i, c in enumerate(origX):
        count = 0
        if c == "1":
            if wa == 1:
                print(0)
                continue
            x = (nx-pow(2, N-i-1, wa-1)) % (wa-1)
            print(table[x]+1)
        else:
            x = (px+pow(2, N-i-1, wa+1)) % (wa+1)
            print(table[x]+1)
    
    return


if __name__ == '__main__':
    main()

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

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))



n = readint()
x = readstr()

a = int(x,2)

bit = x.count('1')

z = [0]*(n+1)
for i in range(1,n+1):
    b = i
    while b>0:
        c = 0
        for j in range(b.bit_length()):
            if b&(1<<j):
                c += 1
        b%=c
        z[i]+=1

if bit!=1:
    p = a%(bit-1)
q = a%(bit+1)

ans = [1]*n
for i in range(n):
    if x[i]=='1':
        if bit==1:
            b = 0
            ans[i]-=1
        else:
            b = p-pow(2,n-i-1,bit-1)+bit-1
            b%=bit-1
    else:
        b = q+pow(2,n-i-1,bit+1)
        b%=bit+1
    ans[i]+=z[b]

printrows(ans)

Solution (Python):
import math

import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def popcorn(i,k):
    num = 0
    ii = i
    while ii > 0:
        if ii&1:
            num += 1
        ii //= 2
    if i%num:
        return popcorn(i%num,k+1)
    else:
        return k+1

def main():
    n = int(ipt())
    x = list(map(int,list(input())))
    si = sum(x)
    su = si+1
    sd = max(1,si-1)
    amu = 0
    amd = 0
    n2u = [1]
    if si == 2:
        n2d = [0]
    else:
        n2d = [1]
    for i in x[::-1]:
        if i:
            amu = (amu+n2u[-1])%su
            amd = (amd+n2d[-1])%sd
        n2u.append((n2u[-1]*2)%su)
        n2d.append((n2d[-1]*2)%sd)
    for i,xi in enumerate(x):
        if xi:
            ni = (amd-n2d[-2-i])%sd
            if si == 1:
                print(0)
            elif ni == 0:
                print(1)
            else:
                print(popcorn(ni,1))
        else:
            ni = (amu+n2u[-2-i])%su
            if ni == 0:
                print(1)
            else:
                print(popcorn(ni,1))


    return None

if __name__ == '__main__':
    main()

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

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

M = X.count("1")
a = -1
if M==1:
    a = X.index("1")

def f0(X,M):
    if M<=0: return 0
    ret = 0
    for i,x in enumerate(X[::-1]):
        if x=="1" :
            ret += pow(2,i,M)
            ret %= M
    return ret

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

n0 = f0(X,M+1)
n1 = f0(X,M-1)

for i in range(N):
    if M==1 and a==i:
        print(0)
    else:
        if X[i] == "0":
            n = (n0 + pow(2,N-1-i,M+1))%(M+1)
        else:
            n = (n1 - pow(2,N-1-i,M-1))%(M-1)
        print(f(n)+1)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
from functools import lru_cache

n = int(input())
x = input()
mod = x.count("1")
flag = (mod == 1)
if mod == 0:
    for i in range(n):
        print(1)
    exit()
@lru_cache(maxsize = n+1)
def f(x):
    if x==0:return 0
    y = x
    cnt = 0
    while y>0:
        cnt += y&1
        y >>= 1
    x %= cnt
    return f(x) + 1
if mod == 1:mod += 2
powmod = [[1%(mod-1)]*n,[1%(mod+1)]*n]

for i in range(n-1):
    powmod[0][i+1] = powmod[0][i]*2%(mod-1)
    powmod[1][i+1] = powmod[1][i]*2%(mod+1)

X = [0,0]
for i,b in enumerate(x[::-1]):
    X[0] += powmod[0][i]*int(b)
    X[1] += powmod[1][i]*int(b)
    X[0] %= mod-1
    X[1] %= mod+1
ans = [0]*n
for i in range(n):
    if flag:
        if x[n-1-i] == "1":
            ans[n-1-i] = 0
        else:
            now = (X[0] + powmod[0][i])%(mod-1)
            ans[n-i-1] = f(now) + 1
        continue
    if x[n-1-i] == "1":
        now = (X[0] - powmod[0][i])%(mod-1)
    else:
        now = (X[1] + powmod[1][i])%(mod+1)
    ans[n-i-1] = f(now) + 1
print("\n".join(str(i) for i in ans))

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

def f(n):
    if n == 0:
        return 0
    pc = 0
    k = n
    while k:
        pc += k & 1
        k >>= 1
    
    return 1 + f(n % pc)

def solve():
    N = int(readline())
    X = readline().rstrip()
    X = list(map(int, X))

    N1 = sum(X) - 1
    N0 = N1 + 2












    a0 = 0
    a1 = 0
    for i in range(N):
        a0 = (a0 * 2 + X[i]) % N0
        a1 = (a1 * 2 + X[i]) % N1 if N1 != 0 else 0
    
    anses = [0] * N
    b0 = 1
    b1 = 1
    for i in range(N):
        if X[N - 1 - i] == 0:
            k = (a0 + b0) % N0
        else:
            k = (a1 - b1) % N1 if N1 != 0 else 0
        
        if N1 == 0 and X[N - 1 - i] == 1:
            anses[N - 1 - i] = 0
        else:
            anses[N - 1 - i] = 1 + f(k)

        b0 = b0 * 2 % N0
        b1 = b1 * 2 % N1 if N1 != 0 else 0

    for a in anses:
        print(a)

solve()

Solution (Python):


from collections import Counter
def func(x):
    cnt = 0
    y = x
    while x > 0:
        if x%2 == 1:
            cnt += 1
        x //= 2
    return y%cnt
        
def main():
    N = int( input())
    X = list( map( int, list( input())))
    base_plus = 0
    base_minus = 0
    r = 1
    one = Counter(X)[1]
    for x in X[::-1]:
        base_plus += r*x
        base_plus %= one+1
        r *= 2
        r %= one+1
    r = 1
    if one > 1:
        for x in X[::-1]:
            base_minus += r*x
            base_minus %= one-1
            r *= 2
            r %= one-1

    ANS = [0]*N
    
    
    for i in range(N):
        if one == 1:
            if X[i] == 1:
                ANS[i] = 0
                continue
        if X[i] == 1:
            xi = (base_minus -  pow(2,N-1-i,one-1))%(one-1)
            
        else:
            xi = (base_plus +  pow(2,N-1-i,one+1))%(one+1)
            
        
        if xi == 0:
            ANS[i] = 1
            continue
        ans = 1
        while xi > 0:
            ans += 1
            xi = func(xi)
        ANS[i] = ans
    print("\n".join( map( str, ANS)))
    
    
if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
x = list(input())
p_origin = x.count('1')

def bit_count(x):
    count = 0
    while x > 0:
        if x & 1:
            count += 1
        x = x >> 1
    return count


def get_ans(i):
    ans = 1
    if x[i] == '0':
        p_first = (sum_plus + p_plus[i]) % (p_origin+1)
    else:
        if p_origin-1 == 0:
            return 0
        p_first = (sum_minus - p_minus[i]) % (p_origin-1)
    while p_first != 0:
        p_first = p_first % bit_count(p_first)
        ans += 1
    return ans

p_minus = [0]*n 
p_plus = [0]*n 

t1 = 1
t2 = 1
for i in range(n):
    p_minus[n-1-i] = t1
    p_plus[n-1-i] = t2
    t1 *= 2
    t2 *= 2
    if p_origin == 1:
        t1 = 0
    else:
        t1 %= p_origin-1
    t2 %= p_origin+1

sum_plus = 0
sum_minus = 0
for i in range(n):
    if x[i] == '1':
        sum_plus += p_plus[i]
        sum_minus += p_minus[i]

for i in range(n):
    print(get_ans(i))

Solution (Python):
def count(n):
    k = n.bit_length()
    res = 0
    for i in range(k):
        if (n >> i) & 1:
            res += 1
    return res

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

p = 0
for i in range(N):
    if X[i] == '1':
        p += 1


r1 = 0
for i in range(N):
    if X[~i] == '1':
        r1 += pow(2, i, p + 1)
        r1 %= p + 1

if p > 1:
    
    r2 = 0
    for i in range(N):
        if X[~i] == '1':
            r2 += pow(2, i, p - 1)
            r2 %= p - 1
else:
    r2 = -1

rem = [0 for _ in range(N)]

for i in range(N):
    if X[i] == '1': 
        if r2 == -1:
            r = -1
        else:
            r = r2 - pow(2, N - 1 - i, p - 1)
            r %= p - 1
    else:
        r = r1 + pow(2, N - 1 - i, p + 1)
        r %= p + 1
    rem[i] = r

res = [0 for _ in range(N)]

for i in range(N):
    k = rem[i]
    if k == -1:
        res[i] = 0
    else:
        j = 1
        while k:
            k %= count(k)
            j += 1
        res[i] = j

print('\n'.join(map(str, res)))

Solution (Python):
def popcount(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())
x = input()
mod = x.count("1")
U = 2**20
C = [0]*U
for i in range(1, U):
  q = popcount(i)
  C[i] = C[i%q] + 1
t_1 = 0
t_2 = 0
for j, s in enumerate(x):
  if s == "1":
    if mod > 1:
      t_1 += pow(2, n-1-j, mod-1)
      t_1 %= mod-1
    t_2 += pow(2, n-1-j, mod+1)
    t_2 %= mod+1
for i in range(n):
  if x[i] == "1":
    if mod == 1:
      print(0)
      continue
    temp = t_1
    temp -= pow(2, n-1-i, mod-1)
    temp %= mod-1
  else:
    temp = t_2
    temp += pow(2, n-1-i, mod+1)
    temp %= mod+1
  res = C[temp] + 1
  print(res)

Solution (Python):
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

n = n_in()
x = s_in()

popcnt = sum(i == '1' for i in x)

def mod_add(a, b):
  return (a+b)%MOD

def mod_sub(a, b):
  return (a+MOD-b)%MOD

def mod_mul(a, b):
  return a*b%MOD


def extgcd(a,b):
    r = (1,0,a)
    w = (0,1,b)
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return (w[0],w[1])

def mod_inv(a):
    x,_  = extgcd(a, MOD)
    return (MOD+x%MOD)%MOD

def mod_div(a, b):
    return a*mod_inv(b)%MOD

def mod_pow(a, b):
    res = 1
    while b > 0:
        if b & 1:
            res = res * a % MOD
        a = a * a % MOD
        b >>= 1
    return res

memo = {}

MOD = popcnt+1
memo[MOD] = []
for i in range(n):
    memo[MOD].append(mod_pow(2, i))
    

if popcnt-1 > 0:
    MOD = popcnt-1
    memo[MOD] = []
    for i in range(n):
        memo[MOD].append(mod_pow(2, i))

base_1 = 0
base_2 = 0
for i in range(n):
    if x[i] == '1':
        MOD = popcnt+1
        base_1 = mod_add(base_1, memo[MOD][n-i-1])

    
        if popcnt-1 > 0:
            MOD = popcnt-1
            base_2 = mod_add(base_2, memo[MOD][n-i-1])


for i in range(n):
    cnt = 0
    if x[i] == '0':        
        MOD = popcnt + 1
        current = mod_add(base_1, memo[MOD][n-i-1])
        cnt += 1
        while current > 0:
            MOD = sum(c=='1' for c in bin(current)[2:])
            current = current%MOD
            cnt += 1
    else:
        MOD = popcnt - 1
        if MOD == 0:
            print(0)
            continue
        current = mod_sub(base_2, memo[MOD][n-i-1])
        cnt += 1
        while current > 0:
            MOD = sum(c=='1' for c in bin(current)[2:])
            current = current%MOD
            cnt += 1

    print(cnt)

Solution (Python):
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

INF = 10**18
eps = 10**-7

N = int(readline())
X = readline().rstrip()
X = X[::-1]

C = X.count("1")

if C == 0:
    for i in range(N):
        print(1)
    exit()

if C == 1:
    
    Cp = [0]*(N+1)

    Cp[0] = 1
    for i in range(N):
        Cp[i+1] = Cp[i]*2%(C+1)
    sumcp = 0

    for i in range(N):
        if X[i] == "1":
            sumcp = (sumcp+Cp[i])%(C+1)


    

    List = [0]*(N+1)

    for i in range(1,N+1):
        
        cnt = 0
        for j in range(20):
            if i>>j&1:
                cnt += 1
        List[i] = List[i%cnt]+1

    ans = [0]*N

    for i in range(N):
        if X[i] == "1":
            ans[N-1-i] = 0
        else:
            a = (sumcp + Cp[i])%(C+1)
            ans[N-1-i] = List[a]+1
    for anss in ans:
        print(anss)

    exit()





Cp = [0]*(N+1)
Cm = [0]*(N+1)

Cp[0] = 1
Cm[0] = 1

if C == 2:
    Cm[0] = 0

for i in range(N):
    Cp[i+1] = Cp[i]*2%(C+1)
    Cm[i+1] = Cm[i]*2%(C-1)
sumcp = 0
sumcm = 0

for i in range(N):
    if X[i] == "1":
        sumcp = (sumcp+Cp[i])%(C+1)
        sumcm = (sumcm+Cm[i])%(C-1)




List = [0]*(N+1)

for i in range(1,N+1):
    
    cnt = 0
    for j in range(20):
        if i>>j&1:
            cnt += 1
    List[i] = List[i%cnt]+1

ans = [0]*N

for i in range(N):
    if X[i] == "1":
        a = (sumcm - Cm[i])%(C-1)
        ans[N-1-i] = List[a]+1
    else:
        a = (sumcp + Cp[i])%(C+1)
        ans[N-1-i] = List[a]+1
for anss in ans:
    print(anss)

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

l = [0] * (2*10**5+1)
ans = [0] * (2*10**5+1)
for i in range(2*10**5+1):
  l[i] = bin(i).count('1')
  
for i in range(2*10**5+1):
  x = i
  y = 0
  while x!=0:
    y += 1
    x %= l[x]
    
  ans[i] = y
  
X_count = X.count('1')
plu = X_count + 1
mi = X_count - 1
plu_res = 0
mi_res = 0
X_int = int(X,2)

for i in range(N):
  if X[i]=='0':
    continue
  else:
    plu_res += pow(2,N-i-1,plu)
    plu_res %= plu
    if mi>0:
      mi_res += pow(2,N-i-1,mi)
      mi_res %= mi
      
for i in range(N):
  if X[i]=='0':
    x = (plu_res + pow(2,N-i-1,plu)) % plu
    print(1 + ans[x])
  else:
    if mi!=0:
      x = (mi_res - pow(2,N-i-1,mi)) % mi
      print(1 + ans[x])
    else:
      print(0)

Solution (Python):
N = int(input())
X = list(map(int, input().strip()))

count_j = X.count(1)

def calc_table(m):
	if m == 1:
		return [0] * N
	elif m == 0:
		return None
	table = []
	x = 1
	for i in range(N):
		table.append(x)
		x = (x * 2) % m
	table.reverse()
	return table

count_m = count_j - 1
count_p = count_j + 1

mod_m = calc_table(count_m)
mod_j = calc_table(count_j)
mod_p = calc_table(count_p)

original_j = 0
original_m = 0
original_p = 0
if count_m > 0:
	for i, b in enumerate(X):
		if b == 1:
			original_j = (original_j + mod_j[i]) % count_j
			original_m = (original_m + mod_m[i]) % count_m
			original_p = (original_p + mod_p[i]) % count_p
else:
	for i, b in enumerate(X):
		if b == 1:
			original_j = (original_j + mod_j[i]) % count_j
			original_p = (original_p + mod_p[i]) % count_p



f_cache = [None] * N
def calc_f(x):
	if x == 0:
		return 0
	f = f_cache[x]
	if f != None:
		return f
	count = 0
	i = x
	while i > 0:
		if i % 2 == 1:
			count += 1
		i //= 2
	f = calc_f(x % count) + 1
	f_cache[x] = f
	return f

for i, b in enumerate(X):
	if b == 0:
		x = (original_p + mod_p[i]) % count_p
		print(calc_f(x) + 1)
	else:
		if count_m > 0:
			x = (original_m - mod_m[i]) % count_m
			print(calc_f(x) + 1)
		else:
			print(0)

Solution (Python):
def f(n):
  c=0
  while n>0:
    n%=format(n, 'b').count('1')
    c+=1
  return c

N=int(input())
X=input()
nums=[0]+[f(i) for i in range(1, N+1)]

a=0
b=0
for i in range(N):
  if X[i]=='0':
    a+=1
  else:
    b+=1

s=0
t=0
if b>1:
  for i in range(N):
    s=(s+int(X[i])*pow(2, N-1-i, b+1))%(b+1)
    t=(t+int(X[i])*pow(2, N-1-i, b-1))%(b-1)
else:
  for i in range(N):
    s=(s+int(X[i])*pow(2, N-1-i, b+1))%(b+1)
    
if b==1:
  for i in range(N):
    if X[i]=='0':
      tmp=(s+pow(2, N-1-i, b+1))%(b+1)
      print(nums[tmp]+1)
    else:
      print(0)
  exit()

for i in range(N):
  if X[i]=='0':
    tmp=(s+pow(2, N-1-i, b+1))%(b+1)
    print(nums[tmp]+1)
  else:
    tmp=(t-pow(2, N-1-i, b-1))%(b-1)
    print(nums[tmp]+1)

Solution (Python):
N = int(input())
ans_list = [0] * (N+1)
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
for i in range(N):
    if i == 0:
        continue
    else:
        if i %popcnt(i) == 0 :
            ans_list[i] = 1
        else:
            ans_list[i] = ans_list[i%popcnt(i)] + 1
S = input()
count = 0
for i in range(N):
    if S[i] == "1":
        count += 1
if count == 1:
    high_total = 0
    low_total = 0
    for i in range(N):
        if S[i] == "1":
            high_total += pow(2,N-1-i,count+1)
            high_total %= (count+1)
    for i in range(N):
        if S[i] == "1":
            print(0)
        if S[i] == "0":
            total = (high_total + pow(2,N-1-i,count+1)) % (count+1)
            print(ans_list[total]+1)
else:
    high_total = 0
    low_total = 0
    for i in range(N):
        if S[i] == "1":
            high_total += pow(2,N-1-i,count+1)
            high_total %= (count+1)
            low_total +=  pow(2,N-1-i,count-1)
            low_total %= (count-1)
    for i in range(N):
        if S[i] == "1":
            total = (low_total - pow(2,N-1-i,count-1)) % (count-1)
            print(ans_list[total]+1)
        if S[i] == "0":
            total = (high_total + pow(2,N-1-i,count+1)) % (count+1)
            print(ans_list[total]+1)

Solution (Python):
import math

mod = 1000000007
dp = [0, 1]
num = [0, 1]
for i in range(2, 200000):
    if i % 2 == 0:
        num.append(num[i//2])
    else:
        num.append(num[i//2]+1)
    dp.append(dp[i % num[i]]+1)
N = int(input())
x = input()
ones = 0
for c in x:
    if c == '1':
        ones += 1
powlow = [1]
powhigh = [1]
modlow = ones - 1
modhigh = ones + 1
for i in range(200000):
    if modlow != 0:
        powlow.append((powlow[i]*2) % modlow)
    powhigh.append((powhigh[i]*2) % modhigh)
reslow = 0
reshigh = 0
for i in range(N):
    if x[i] == '1':
        if modlow != 0:
            reslow = (reslow + powlow[N - i - 1]) % modlow
        reshigh = (reshigh + powhigh[N - i - 1]) % modhigh
for i in range(N):
    if x[i] == '1':
        if modlow != 0:
            temp = (modlow + reslow - powlow[N - i - 1]) % modlow
            print(dp[temp] + 1)
        else:
            print(0)
    if x[i] == '0':
        temp = (reshigh + powhigh[N - i - 1]) % modhigh
        print(dp[temp] + 1)

Solution (Python):
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
import copy


MOD = 10 ** 9 + 7




n = int(input())
x = input()
nx = int(x, 2)
c = x.count("1")

numa = 0
numb = 0
p = 0
for i in reversed(range(len(x))):
    if x[i] == "1":
        if c > 1:
            numa += pow(2, p, c - 1)
        numb += pow(2, p, c + 1)
    p += 1



for i in range(n):
    if x[i] == "0":
        val = (numb + pow(2, n-i-1, c + 1)) % (c+1)
        
        if val == 0:
            print(1)
            continue
        count = 1
        while val > 0:
            val = val % bin(val).count("1")
            count += 1
        print(count)
    else:
        if c == 1:
            print(0)
            continue
        val = (numa - pow(2, n - i - 1, c - 1)) % (c - 1)
        
        if val == 0:
            print(1)
            continue
        count = 1
        while val > 0:
            val = val % bin(val).count("1")
            count += 1
        print(count)