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):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    def solve(p):
        cur = p
        cnt = 1
        while cur > 0:
            pop = f'{cur:b}'.count("1")
            cur = cur % pop
            cnt += 1

        return cnt

    n = int(readline())
    s = input()

    c = s.count("1")
    cp = c + 1
    cm = c - 1

    fp = 0
    fm = 0

    for i, x in enumerate(s[::-1]):
        if x == "1":
            if cp <= n:
                fp += pow(2, i, cp)
                fp %= cp
            if cm > 0:
                fm += pow(2, i, cm)
                fm %= cm

    for i in range(n):
        if s[i] == "0":
            a = pow(2, n - (i + 1), cp)
            cur = (fp + a) % cp
            print(solve(cur))
        else:
            if cm > 0:
                a = pow(2, n - (i + 1), cm)
                cur = (fm - a) % cm
                print(solve(cur))
            else:
                print(0)


if __name__ == '__main__':
    main()

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random,resource

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    s = S()

    m = {}
    m[0] = 0
    def f(i):
        if i in m:
            return m[i]

        c = 0
        ii = i
        while ii > 0:
            c += ii % 2
            ii //= 2

        t = i % c
        m[i] = f(t) + 1
        return m[i]

    c = len([_ for _ in s if _ == '1'])
    t = int(s, 2)
    cm = (c+1) * c * (c-1)
    if c > 1:
        t %= cm

    r = []
    k = 1
    for i in range(n-1,-1,-1):
        if t == k:
            r.append(0)
        elif s[i] == '1':
            r.append(f((t - k) % (c-1)) + 1)
        else:
            r.append(f((t + k) % (c+1)) + 1)
        k *= 2
        if c > 1:
            k %= cm

    return JA(r[::-1], "\n")


print(main())

Solution (Python):
def resolve():
    N = int(input())
    X = input()
    Xint = int(X,2)
    popX = X.count("1")
    if popX == 1:
        idx = X.find("1")
        for i in range(N):
            if i == idx:
                print(0)
            else: 
                if i != N-1:
                    if X[-1] == "0":
                        print(1)
                    else:
                        print(2)
                else:
                    print(2)
        return

    Xmod_plus =  Xint % (popX+1)
    Xmod_minus = Xint % (popX-1)

    pop_2expi_p = {0:1}
    pop_2expi_m = {0:1}
    for i in range(1,N):
        pop_2expi_p[i] = pop_2expi_p[i-1] * 2 % (popX+1)
        pop_2expi_m[i] = pop_2expi_m[i-1] * 2 % (popX-1)

    for i in range(N):
        count = 1
        if X[i] == "1":
            nX = (Xmod_minus - pop_2expi_m[N-1-i] ) % (popX-1) 
        if X[i] == "0":
            nX = (Xmod_plus + pop_2expi_p[N-1-i] ) % (popX+1) 
        for j in range(N):
            if nX == 0:
                break
            else:
                nX %= bin(nX).count("1")              
                count += 1
        print(count)
resolve()

Solution (Python):



def pc(x):
    return format(x, 'b').count('1')

N = int(input())
X = input()
Xn = int(X,2)
p = pc(Xn)
X = list(X)

Xp = Xn%(p+1)
if p==1:
    Xm = 0
else:
    Xm = Xn%(p-1)

def f(i):
    if p==1 and X[i]=='1':
        
        return 0
    else:
        if X[i]=='1':
            
            ret = Xm - pow(2, N-1-i, p-1)
            ret %= p-1
        else:
            
            ret = Xp + pow(2, N-1-i, p+1)
            ret %= p+1
        cnt = 1
        while ret > 0:
            ret %= pc(ret)
            cnt += 1
        return cnt

def main():
    for i in range(N):
        ret = f(i)
        print(ret)

if __name__ == '__main__':
    main()

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

n = int(input())
s = input()

def pcnt(x):
    return bin(x).count('1')

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

x = [0]*n

for i in range(n):
    x[i] = int(s[i])


pc = sum([x[i] for i in range(n)])

ans = [0]*n


for b in range(2):
    npc = pc
    if b == 0: npc += 1
    else: npc -= 1
        
    if npc <= 0: continue 
    
    
    
    r0 = 0
    for i in range(n):
        r0 = (r0*2)%npc
        r0 += x[i]
    
    
    
    
    k = 1
    for i in range(n-1, -1, -1):
        if x[i] == b:
            r = r0
            if b == 0: r = (r+k)%npc
            else: r = (r-k+npc)%npc 
            ans[i] = f(r)+1
        k = (k*2)%npc

print(*ans)

Solution (Python):
import sys
import math
import heapq
from collections import defaultdict, deque
from decimal import *
def r():
    return int(input())
def rm():
    return map(int,input().split())
def rl():
    return list(map(int,input().split()))

'''D Anything Goes to zero'''
twoPowM1=[0]*(300000)
twoPowM2=[0]*(300000)
stepsSmall=[0]*(300000)

n=r()
s=input()
bitcount=0
for i in range(n):
    if s[i]=='1':
        bitcount+=1

mod=bitcount-1
if mod>0:
    twoPowM1[0]=1
    for i in range(1,len(twoPowM1)):
        twoPowM1[i]=(twoPowM1[i-1]+twoPowM1[i-1])%mod

mod=bitcount+1
twoPowM2[0]=1
for i in range(1,len(twoPowM2)):
    twoPowM2[i]=(twoPowM2[i-1]+twoPowM2[i-1])%mod

for i in range(1,len(stepsSmall)):
    stepsSmall[i]=1+stepsSmall[i%bin(i).count('1')]

valM1=0;valM2=0
for i in range(n):
    mod=bitcount-1
    if mod>0:
        valM1=((valM1*2)%mod+int(s[i]))%mod
    mod=bitcount+1
    valM2=((valM2*2)%mod+int(s[i]))%mod

for i in range(n):
    pow=n-1-i
    if s[i]=='0':
        mod=bitcount+1
        newVal=(valM2+twoPowM2[pow])%mod
        print(stepsSmall[newVal]+1)
    else:
        mod=bitcount-1
        if mod==0:
            print(0)
        else:
            newVal=(valM1-twoPowM1[pow])%mod
            print(stepsSmall[newVal]+1)

Solution (Python):



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

ones=x.count("1")

a=ones+1
b=ones-1

xda=0
xdb=0
for i in range(n):
    if x[-1-i]=="1":
        xda+=pow(2,i,a)
        xda%=a
        if b==0:
            continue
        xdb+=pow(2,i,b)
        xdb%=b

xds=[-1]*n

for i in range(n):
    if x[-1-i]=="0":
        xds[-1-i]=(xda+pow(2,i,a))%a
    else:
        if b==0:
            continue
        xds[-1-i]=(xdb-pow(2,i,b))%b

    
def popcount(x):
    return bin(x).count("1")
    
def solve(x):
    if x<0:
        return -1
    if x==0:
        return 0
    cnt=0
    while x>0:
        cnt+=1
        x=x%popcount(x)
    return cnt

for xd in xds:
    print(1+solve(xd))

Solution (Python):



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

ones=x.count("1")

a=ones+1
b=ones-1

xda=0
xdb=0
for i in range(n):
    if x[-1-i]=="1":
        xda+=pow(2,i,a)
        xda%=a
        if b==0:
            continue
        xdb+=pow(2,i,b)
        xdb%=b

xds=[-1]*n

for i in range(n):
    if x[-1-i]=="0":
        xds[-1-i]=(xda+pow(2,i,a))%a
    else:
        if b==0:
            continue
        xds[-1-i]=(xdb-pow(2,i,b))%b

    
def popcount(x):
    return bin(x).count("1")
    
def solve(x):
    if x<0:
        return -1
    if x==0:
        return 0
    cnt=0
    while x>0:
        cnt+=1
        x=x%popcount(x)
    return cnt

for xd in xds:
    print(1+solve(xd))

Solution (Python):

import math
def popcount(x):
    s=0
    y=int(math.log2(x))+2
    for i in range(y):
        if(x>>i)&1:
            s+=1
    return x%s
n=int(input())
x=input()[::-1]

c=x.count("1")



if c!=1:
    m=[[1%(c-1),1%(c+1)]]
    for i in range(n-1):
        m.append([(2*m[-1][0])%(c-1),(2*m[-1][1])%(c+1)])
    l=[0,0]
    for i in range(n):
        if x[i]=="1":
            l[0]+=m[i][0]
            l[1]+=m[i][1]
            l[0]%=(c-1)
            l[1]%=(c+1)
else:
    m=[[1%(c+1),1%(c+1)]]
    for i in range(n-1):
        m.append([(2*m[-1][0])%(c+1),(2*m[-1][1])%(c+1)])
    l=[0,0]
    for i in range(n):
        if x[i]=="1":
            l[0]+=m[i][0]
            l[1]+=m[i][1]
            l[0]%=(c+1)
            l[1]%=(c+1)



ans=[0]*n
for i in range(n):
    if x[i]=="1":
        if c-1==0:
            ans[i]=0
            continue
        p=(l[0]+(c-1)-m[i][0])%(c-1)
        ans[i]+=1
        while p!=0:
            p=popcount(p)
            ans[i]+=1
    else:
        p=(l[1]+m[i][1])%(c+1)
        ans[i]+=1
        while p!=0:
            p=popcount(p)
            ans[i]+=1
ans=ans[::-1]
for i in range(n):
    print(ans[i])

Solution (Python):
def main():
    def f(n):
        if n == 0: return 0
        return f(n % bin(n).count('1')) + 1
    n = int(input())
    X = list(input())
    c = sum(list(map(int, X)))
    m = int(''.join(X), 2)
    mp, mm = m % (c + 1), m % (c - 1) if c - 1 != 0 else 0
    jp, jm = 1, 1
    ans = [0] * n
    for i in range(n - 1, -1, -1):
        if X[i] == '0':
            mod = c + 1
            ans[i] = f((mp + jp) % mod) + 1
        else:
            ans[i] = f((mm - jm + mod) % mod) + 1 if (mod := c - 1) != 0 else 0
        jp, jm = (jp << 1) % (c + 1), (jm << 1) % (c - 1) if c - 1 != 0 else 0
    [print(a) for a in ans]
if __name__ == '__main__':
    main()

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

memo = {}


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


def f(n):
    if n == 0:
        return 0
    if n in memo:
        return memo[n]
    memo[n] = 1 + f(n % popcount(n))
    return memo[n]


def solve(N, X):
    Xint = int(X, 2)
    p = popcount(Xint)
    if 1 < p:
        x1 = Xint % (p - 1)
    x2 = Xint % (p + 1)
    ans = []
    b = 1
    if 1 < p:
        bmod1 = b % (p - 1)
    bmod2 = b % (p + 1)
    for i in range(N):
        if X[-1 - i] == '1':
            if 1 < p:
                ans.append(1 + f((x1 - bmod1) % (p - 1)))
            else:
                ans.append(0)
        else:
            ans.append(1 + f((x2 + bmod2) % (p + 1)))
        b <<= 1
        if 1 < p:
            bmod1 = bmod1 * 2 % (p - 1)
        bmod2 = bmod2 * 2 % (p + 1)

    return list(reversed(ans))


for x in solve(N, X):
    print(x)

Solution (Python):

def bitsoncount(x):
    return bin(x).count('1')

def solve(x):
    global ans
    bx = bitsoncount(x)
    if bx == 0:
        return ans
    else:
        ans += 1
        x = x % bx
        solve(x)


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

Xb = bitsoncount(int(X, 2))
if (Xb - 1) != 0:
    X0 = int(X, 2) % (Xb-1)
X1 = int(X, 2) % (Xb+1)

for x, i in zip(X, reversed(range(N))):
    x = int(x)
    if x == 0:
        temp = (X1 + pow(2, i, Xb+1)) % (Xb+1)
        ans = 1
    else:
        if Xb - 1 == 0:
            print(0)
            continue
        temp = (X0 - pow(2, i, Xb-1)) % (Xb-1)
        ans = 1
    
    solve(temp)
    print(ans)

Solution (Python):
from sys import stdin,stdout
def INPUT():return list(int(i) for i in stdin.readline().split())
def inp():return stdin.readline()
def out(x):return stdout.write(x)
import math

def power(a,p,m):
    if m==0:
        return 0
    res=1
    while(p>0):
        if p&1:
            res=(res*a)%m
        a=(a*a)%m
        p//=2
    return res%m
n=int(input())
s=input()
A=list(int(i) for i in s)
R=[]
for i in range(n-1,-1,-1):
    R.append(A[i])
one=0
for e in A:
    if e==1:
        one+=1
max=one+1
min=one-1
ansmax=0
ansmin=0

for i in range(n):
    ansmax=(ansmax+power(2,i,max)*(R[i]))%max
    if min!=0:
        ansmin=(ansmin+power(2,i,min)*R[i])%min
def popcount(z):
    ans=0
    while(z!=0):
        if z%2==1:
            ans+=1
        z//=2
    return ans

B=[]
for i in range(n):
    if R[i]==1:
        if min!=0:
            r=(ansmin-power(2,i,min))%min
            count=1
            while(r!=0):
                count+=1
                r=r%popcount(r)
        else:
            count=0
        B.append(count)
    else:
        r=(ansmax+power(2,i,max))%max
        count=1
        while(r!=0):
            count+=1
            r=r%popcount(r)
        B.append(count)
B.reverse()
for ele in B:
    print(ele)

Solution (Python):
import sys

N = int(sys.stdin.readline().strip())
X = sys.stdin.readline().strip()

def popcount(n):
    cnt = 0
    while n > 0:
        cnt += n & 1
        n //= 2
    return cnt

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


pcnt = X.count('1')
MOD1 = pcnt + 1
MOD2 = pcnt - 1

nXp = 0
nXm = 0

pow1 = [1] * N
pow2 = [0] * N
for i in range(1, N):
    pow1[i] = (pow1[i-1] * 2) % MOD1
if MOD2 != 0:
    pow2[0] = 1
    for i in range(1, N):
        pow2[i] = (pow2[i-1] * 2) % MOD2

for i in range(N):
    if X[i] == '1':
        nXp += pow1[N-1-i]
nXp %= MOD1

if MOD2 != 0:
    for i in range(N):
        if X[i] == '1':
            nXm += pow2[N-1-i]

    nXm %= MOD2
    

for i in range(0, N):
    if X[i] == '0':
        k = (nXp + pow1[N-1-i]) % MOD1
        print(f(k) + 1)
    else:
        if MOD2 == 0:
            print(0)
        else:
            k = (nXm - pow2[N-1-i]) % MOD2
            print(f(k) + 1)

Solution (Python):
import sys
import itertools

import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines



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

N = int(input())
X = input()
ones = X.count('1')
MOD1 = ones + 1
MOD2 = ones - 1
pow1 = [1] * (len(X) + 1)
pow2 = [1] * (len(X) + 1)
if MOD2 != 0:
    for i in range(1, len(X) + 1):
        pow1[i] = (pow1[i - 1] * 2) % MOD1
        pow2[i] = (pow2[i - 1] * 2) % MOD2
else:
    for i in range(1, len(X) + 1):
        pow1[i] = (pow1[i - 1] * 2) % MOD1

X1, X2 = 0, 0
for i in range(N):
    if X[i] == '1':
        X1 += pow1[N - i - 1]
        X2 += pow2[N - i - 1]
X1 %= MOD1
if MOD2 != 0:
    X2 %= MOD2

for i in range(N):
    d = N - i - 1
    if X[i] == '0':
        x = (X1 + pow1[d]) % MOD1
        print(f(x) + 1)
    else:
        if MOD2 != 0:
            x = (X2 - pow2[d]) % MOD2
            print(f(x) + 1)
        else:
            print(0)

Solution (Python):
import sys
import itertools

import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines



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

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

ones = X.count('1')
MOD1 = ones + 1
MOD2 = ones - 1
pow1 = [1] * (len(X) + 1)
pow2 = [0] * (len(X) + 1)
if MOD2 != 0:
    pow1[0] = 1
    pow2[0] = 1
    for i in range(1, len(X) + 1):
        pow1[i] = (pow1[i - 1] * 2) % MOD1
        pow2[i] = (pow2[i - 1] * 2) % MOD2
else:
    for i in range(1, len(X) + 1):
        pow1[i] = (pow1[i - 1] * 2) % MOD1

X1 = 0
X2 = 0
for i in range(N):
    if X[i] == '1':
        X1 += pow1[N - i - 1]
        X2 += pow2[N - i - 1]
X1 %= MOD1
if MOD2 != 0:
    X2 %= MOD2

for i in range(N):
    d = N - i - 1
    if X[i] == '0':
        x = (X1 + pow1[d]) % MOD1
        print(f(x) + 1)
    else:
        if MOD2 != 0:
            x = (X2 - pow2[d]) % MOD2
            print(f(x) + 1)
        else:
            print(0)

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

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

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

Solution (Python):
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby
from heapq import heapify, heappush, heappop



n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return map(lambda x: x + d, A)
def ldec(A, d=1): return map(lambda x: x - d, A)

popcount = lambda x: bin(x).count("1")
bitflip = lambda x, n: x ^ (1 << n)
bitflip2 = lambda x, n: x ^ (1 << (len(bin(x))-2 - (n+1)))
bits = lambda x, n = 0: bin(x)[2:].zfill(n)

N = n1()
X = list(map(int, list(s1())))

rt = [0, 0]
t1 = 1
t2 = 1
p = X.count(1)

for i in range(N-1, -1, -1):    
    if X[i] == 1:
        if p > 1: rt[0] = (rt[0] + t1) % (p - 1)
        rt[1] = (rt[1] + t2) % (p + 1)
    if p > 1: t1 = t1 * 2 % (p - 1)
    t2 = t2 * 2 % (p + 1)

for i in range(N):
    if X[i] == 1 and p == 1:
        print(0)
        continue

    if X[i] == 0:
        t = (rt[1] + pow(2, N-i-1, p+1)) % (p + 1)
    else:
        t = (rt[0] - pow(2, N-i-1, p-1)) % (p - 1)

    ans = 1
    while t > 0:
        t %= popcount(t)
        ans += 1
    
    print(ans)

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

n=int(input())
s=input()
X=int(s,2)

one_cnt=popcount(X)

modp=X%(one_cnt+1)
modm=X%(one_cnt-1) if one_cnt-1!=0 else 0

for i in range(n):
    if s[i]=="1":
        if one_cnt-1==0:
            print(0)
            continue
        else:
            num=(modm-pow(2,n-i-1,one_cnt-1))%(one_cnt-1)
    else:
        num=(modp+pow(2,n-i-1,one_cnt+1))%(one_cnt+1)

    
    cnt=1
    while num!=0:
        num=num%popcount(num)
        cnt+=1
    print(cnt)

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


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


if p==0:
    for i in range(n):
        print(1)
    exit()
elif p==1:
    z=x.index('1')
    t=pow(2,n-z-1,p+1)
    for i in range(n):
        if i==z:
            print(0)
        else:
            tmp=(t+pow(2,n-i-1,p+1))%(p+1)
            print(solve(tmp))
    exit()



a,b=[],[]
for i in range(n):
    a.append(pow(2,i,p+1))
    b.append(pow(2,i,p-1))


a1,b1=0,0
for i in range(n):
    if x[-1-i]=='1':
        a1+=a[i]
        b1+=b[i]


for i in range(n):
    if x[i]=='1':
        tmp=(b1-b[-1-i])%(p-1)
    else:
        tmp=(a1+a[-1-i])%(p+1)
    print(solve(tmp))

Solution (Python):
N = int(input())
X = input()
X_arr = list(X)
N, X = int(N), int(X, 2)
MAX_N = 2 * 10 ** 5


def popcount(x):
    cnt = 0
    for i in range(x.bit_length()):
        if x & 1 << i:
            cnt += 1
    return cnt


memo = [0] * (MAX_N + 1)
for i, n in enumerate(range(1, MAX_N + 1), start=1):
    cnt = 0
    while n:
        p = popcount(n)
        n = n % p
        cnt += 1
    memo[i] = cnt


x_popcount = popcount(X)
p_upper, p_downer = x_popcount + 1, x_popcount - 1
y_upper = X % p_upper
y_downer = X % p_downer if p_downer else None

for i in range(N):
    if X_arr[i] == '0':
        z = (y_upper + pow(2, (N - i - 1), p_upper)) % p_upper
    else:
        if not p_downer:
            print(0)
            continue
        z = (y_downer - pow(2, (N - i - 1), p_downer)) % p_downer

    print(memo[z] + 1)

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

num_of_one = x.count("1")


if num_of_one == 0:
    for i in range(n):
        print(1)

elif num_of_one == 1:
    for i in range(n):
        if x[i] == "1":
            print(0)
        else:
            
            if x[-1] == "0" and i != n-1:
                print(1)
            
            else:
                print(2)
else:
    dic = collections.defaultdict(int)
    
    for i in range(n):
        tmp_p = i

        cnt = 0
        while tmp_p:
            tmp_p %= bin(tmp_p).count("1")
            cnt += 1
        dic[i] = cnt


    
    bi_mod_p = [1 % (num_of_one+1)]
    bi_mod_m = [1 % (num_of_one-1)]
    for i in range(1,n):
        bi_mod_p.append((bi_mod_p[-1] * 2) % (num_of_one+1))
        bi_mod_m.append((bi_mod_m[-1] * 2) % (num_of_one-1))

    
    bi_mod_p.reverse()
    bi_mod_m.reverse()

    
    sum_p = 0
    sum_m = 0
    for i in range(n):
        if x[i] == "1":
            sum_p += bi_mod_p[i]
            sum_p %= (num_of_one+1)
            sum_m += bi_mod_m[i]
            sum_m %= (num_of_one-1)
    tmp = 0
    for i in range(n):
        
        if x[i] == "0":
            tmp = sum_p + bi_mod_p[i]
            tmp %= (num_of_one+1)

        
        else:
            tmp = sum_m - bi_mod_m[i]
            if tmp < 0:
                tmp += (num_of_one-1)
            tmp %= (num_of_one-1)
        print(dic[tmp]+1)

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

pcn=x.count('1')
px=int(x,2)%(pcn+1)
mx=int(x,2)%(pcn-1) if pcn>1 else 0
p2=[0]*n
m2=[0]*n

for i in range(n):
    p2[i]=pow(2,n-1-i,pcn+1)
    m2[i]=pow(2,n-1-i,pcn-1) if pcn>1 else 0

for i in range(n):
    p=False if int(x[i])&1 else True
    if pcn==1 and not p:
        print(0)
        continue
    ans=0
    tmp=0
    if(p):
        tmp=(px+p2[i])%(pcn+1)
    else:
        tmp=(mx-m2[i])%(pcn-1)
    ans+=1
    while tmp!=0:
        ipcn=str(bin(tmp)).count('1')
        tmp%=ipcn
        ans+=1
    print(ans)

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

pop_X = sum(map(int,list(X)))
X_10 = int('0b'+X,2)

r_0 = X_10%(pop_X+1)
diff_0 = 1%(pop_X+1)

zero_flag = False
if pop_X == 1:
    zero_flag = True
else:
    r_1 = X_10%(pop_X-1)
    diff_1 = 1%(pop_X-1)

answer = []


for i in range(N)[::-1]:
    if X[i]=='0':
        r = (r_0+diff_0)%(pop_X+1)
    else:
        if zero_flag:
            answer.append(0)
            diff_0 = (diff_0*2)%(pop_X+1)
            continue
        else:
            r = (r_1-diff_1)%(pop_X-1)
    count = 1
    while True:
        if r == 0:
            break
        pop = sum(map(int,list(bin(r)[2:])))
        r = r % pop
        count += 1
        
    answer.append(count)
    diff_0 = (diff_0*2)%(pop_X+1)
    if zero_flag:
        continue
    diff_1 = (diff_1*2)%(pop_X-1)

for i in answer[::-1]:
    print(i)

Solution (Python):
n = int(input())
x = input()[::-1]

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

p = x.count("1")
p1, p2 = p + 1, p - 1

if p == 1:
    ii = x.index("1")
    x1 = pow(2, ii, p1)
    for i in range(n)[::-1]:
        if i == ii:
            print(0)
        else:
            r = (x1 + pow(2, i, p1)) % p1
            print(f[r] + 1)
    exit()

x1 = x2 = 0
for i in range(n):
    if x[i] == "1":
        x1 += pow(2, i, p1); x2 += pow(2, i, p2)
        x1 %= p1; x2 %= p2

for i in range(n)[::-1]:
    if x[i] == "0":
        r = (x1 + pow(2, i, p1)) % p1
    else:
        r = (x2 - pow(2, i, p2)) % p2
    print(f[r] + 1)

Solution (Python):
N=int(input())
X=input()
Y=int(X,2)
Z=Y
C=X.count('1')
if C==1:
  for i in range(N):
    if X[i]=='1':
      print(0)
    elif i==N-1:
      print(2)
    else:
      print(1)
  exit()
Y,Z=Y%(C+1),Z%(C-1)

def f(x):
  if x==0:
    return 0
  return 1+f(x%bin(x).count('1'))

for i in range(N):
  if X[i]=='1':
    print(1+f((Z-pow(2,N-i-1,C-1))%(C-1)))
  else:
    print(1+f((Y+pow(2,N-i-1,C+1))%(C+1)))

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

def pop_cnt(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

pop_S = 0
for s in S:
    if s == "1":
        pop_S += 1

p1 = pop_S + 1
p2 = pop_S - 1


mod_sum1 = 0
mod_sum2 = 0
for i, s in enumerate(S):
    if s == "1":
        mod_sum1 = (mod_sum1 + pow(2, N - i - 1, p1)) % p1
        if p2:
            mod_sum2 = (mod_sum2 + pow(2, N - i - 1, p2)) % p2


cnt = [0] * (p1 + 2)

for i in range(1, p1 + 1):
    cnt[i] = cnt[i % pop_cnt(i)] + 1


for i, s in enumerate(S):
    if s == "0":
        mod_sum = (mod_sum1 + pow(2, N - i - 1, p1)) % p1
        
        print(cnt[mod_sum] + 1)
    else:
        if pop_S == 1:
            print(0)
        else:
            mod_sum = (mod_sum2 - pow(2, N - i - 1, p2)) % p2
            
            print(cnt[mod_sum] + 1)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    X = input()
    cnt_init = X.count("1")
    x = int(X, 2)
    a = x % (cnt_init + 1)
    if cnt_init - 1 != 0:
        b = x % (cnt_init - 1)

    for i in range(n):
        if X[i] == "0":
            cnt = cnt_init + 1
            y = (a + pow(2, n - i - 1, cnt)) % cnt
        else:
            cnt = cnt_init - 1
            if cnt == 0:
                print(0)
                continue
            y = (b - pow(2, n - i - 1, cnt)) % cnt

        res = 1
        while y:
            cnt = bin(y).count("1")
            y %= cnt
            res += 1
        print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):
N=int(input())
X=input()
def popcount(n):
    s=str(bin(n))
    return len([i for i in s if i=='1'])
def f(n):
    c=1
    while n!=0:
        n=n%popcount(n)
        c=c+1
    return c
x=int(X,2)
P=popcount(x)
F=list(X)
L=[1,2]
M=[1,2]
if P!=1:
    for i in range(1,N):
        L.append((L[i]*2)%(P+1))
        M.append((M[i]*2)%(P-1))
    s=x%(P+1)
    t=x%(P-1)
    for i in range(N):
        if F[i] == '1':
            q = (t - M[N-i-1])%(P-1)
            print(f(q))
        else:
            Q = P + 1
            q = (s + L[N-i-1])%(P+1)
            print(f(q))
else:
    for i in range(1,N):
        L.append(0)
    s=x%2
    for i in range(N):
        if F[i] == '1':
            print(0)
        else:
            q = (s + L[N - i - 1])%2
            print(f(q))

Solution (Python):
def p(x):
  return bin(x).count('1')

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

N = int(input())
X = input()
cnt = X.count('1')
x = int(X,2)
a = x % (cnt + 1)
if cnt != 1:
  b = x % (cnt - 1)

for i in range(N):
  if X[i] == '0':
    k = (a + pow(2,N-i-1,cnt+1))%(cnt+1)
  else:
    if cnt == 1:
      print(0)
      continue
    k = (b-pow(2,N-i-1,cnt-1))%(cnt-1)
  print(f(k)+1)

Solution (Python):

import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import copy
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


def pop_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


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


def solve():
    N = Scanner.int()
    S = Scanner.string()
    pc = sum([s == '1' for s in S])
    ans = [0 for _ in range(N)]
    for b in range(2):
        npc = pc
        if b == 0:
            npc += 1
        else:
            npc -= 1
        if npc <= 0:
            continue
        r0 = 0
        for i in range(N):
            r0 = ((r0 * 2) + int(S[i])) % npc
        k = 1
        for i in reversed(range(N)):
            if int(S[i]) == b:
                r = r0
                if b == 0:
                    r = (r + k) % npc
                else:
                    r = (r - k + npc) % npc
                ans[i] = f(r) + 1
            k = (k * 2) % npc
    print(*ans, sep='\n')


def main():
    sys.setrecursionlimit(1000000)
    
    
    
    
    
    solve()


if __name__ == "__main__":
    main()