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

sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read


sys.setrecursionlimit(10**7)







def sum_count(arr):
    mem = arr[:]
    while True:
        if len(mem) == 1:break
        tmp = []
        while True:
            if len(mem) == 1:
                tmp.append(mem[-1])
                mem = tmp[:]
                break
            if len(mem) == 0:
                mem = tmp[:]
                break
            x1, x2 = mem.pop(), mem.pop()
            tmp.append(int(x1) + int(x2))

    return int(mem[0])

def run():
    N = int(input())
    X = list(input())[::-1]
    lis_bf = []
    lis_af = []
    count1 = sum_count(X)
    sum_val_bf, sum_val_af = 0, 0
    if count1 <= 1:
        for i in range(N):
            tmp_af = 0
            if int(X[i]):
                tmp_af = pow(2, i, count1 + 1)
            lis_af.append(tmp_af)
            sum_val_af += tmp_af
            sum_val_af %= count1 + 1

        for i in list(range(N))[::-1]:
            ans = 0
            if X[i] == '1':
                print(0)
                continue
            else:
                next_val = (sum_val_af + pow(2, i, count1 + 1)) % (count1 + 1)
            
            ans += 1
            
            while True:
                if next_val == 0: break
                val = next_val
                count_n = sum_count(list(bin(val)[2:]))
                next_val = val % count_n
                ans += 1
                
            print(ans)
        return None

    for i in range(N):
        tmp_bf, tmp_af = 0,0
        if int(X[i]):
            tmp_bf = pow(2, i , count1-1)
            tmp_af = pow(2, i, count1+1)
        lis_bf.append(tmp_bf)
        lis_af.append(tmp_af)
        sum_val_bf += tmp_bf
        sum_val_bf %= count1-1
        sum_val_af += tmp_af
        sum_val_af %= count1 + 1

    for i in list(range(N))[::-1]:
        ans = 0
        if X[i] == '1':
            next_val = (sum_val_bf - lis_bf[i]) % (count1-1)
        else:
            next_val = (sum_val_af + pow(2, i, count1+1)) % (count1+1)
        
        ans += 1
        
        while True:
            if next_val == 0:break
            val = next_val
            count_n = sum_count(list(bin(val)[2:]))
            next_val = val % count_n
            ans += 1
            
        print(ans)


if __name__ == "__main__":
    run()

Solution (Python):
from sys import stdin

def mpow(n, p, mod):
    if mod == 0:
        return 0
    r = 1
    while p > 0:
        if p & 1 == 1:
            r = r * n % mod
        n = n * n % mod
        p >>= 1
    return r
def popcount(u):
    if u == 0:
        return 0
    a = u % bin(u).count('1')
    return 1 + popcount(a)
def main():
    input = stdin.readline
    n = int(input())
    x = '0b' + input()
    xs = int(x, 0)
    xc = x.count('1')
    xsp = mpow(xs, 1, xc + 1)
    xsm = mpow(xs, 1, xc - 1)
    for i in range(2, n + 2):
        if x[i] == '0':
            y = xsp + mpow(2, n - i + 1, xc + 1)
            y = mpow(y, 1, xc + 1)
        elif xc == 1:
            print(0)
            continue
        else:
            y = xsm - mpow(2, n - i + 1, xc - 1)
            y = mpow(y, 1, xc - 1)
        print(popcount(y) + 1)
main()

Solution (Python):
from sys import stdin

def mpow(n, p, mod):
    if mod == 0:
        return 0
    r = 1
    while p > 0:
        if p & 1 == 1:
            r = r * n % mod
        n = n * n % mod
        p >>= 1
    return r
def popcount(u):
    if u == 0:
        return 0
    a = u % bin(u).count('1')
    return 1 + popcount(a)
def main():
    input = stdin.readline
    n = int(input())
    x = '0b' + input()
    xs = int(x, 0)
    xc = x.count('1')
    xsp = mpow(xs, 1, xc + 1)
    xsm = mpow(xs, 1, xc - 1)
    for i in range(2, n + 2):
        if x[i] == '0':
            y = xsp + mpow(2, n - i + 1, xc + 1)
            y = mpow(y, 1, xc + 1)
            print(popcount(y) + 1)
        elif xc == 1:
            print(0)
        else:
            y = xsm - mpow(2, n - i + 1, xc - 1)
            y = mpow(y, 1, xc - 1)
            print(popcount(y) + 1)
main()

Solution (Python):
n, X = open(0).read().split()
n = int(n)
x = int(X, 2)
X = list(map(int, X))

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

ma = 2 * 10**5 + 1
dp = [0] * ma
for i in range(1, ma):
    dp[i] = dp[i % popcount(i)] + 1

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

Solution (Python):
def solve(N,X):
    ans = []
    cnt = X.count("1")
    rem_ori = [0,0]
    for i in range(N):
        if X[i] == "1":
            if cnt != 1:
                rem_ori[0] += pow(2,N-i-1,cnt-1)
                rem_ori[0] %= (cnt-1)
            else:
                rem_ori[0] = 0
            rem_ori[1] += pow(2,N-i-1,cnt+1)
            rem_ori[1] %= (cnt+1)

    rem = [(rem_ori[0] if X[i] == "1" else rem_ori[1]) for i in range(N)]
    for i in range(N):
        if X[i] == "1":
            if cnt != 1:
                rem[i] -= pow(2,N-i-1,cnt-1)
                rem[i] %= (cnt-1)
                ans.append(cal(rem[i],1))
            else:
                ans.append(0)
        else:
            rem[i] += pow(2,N-i-1,cnt+1)
            rem[i] %= (cnt+1)
            ans.append(cal(rem[i],1))

    return ans

def cal(rem,rec):
    if rem == 0:
        return rec
    else:
        b = bin(rem)[2:]
        cnt = b.count("1")
        rem %= cnt
        return cal(rem,rec+1)

def main():
    N = int(input())
    X = input()

    ans = solve(N,X)
    for i in range(N):
        print(ans[i])

if __name__ == "__main__":
    main()

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

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

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

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

one_pow2 = [1]*220001
zero_pow2 = [1]*220001
for i in range(1, 220001):
    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):
def solve(N,X):
    ans = []
    cnt = X.count("1")
    rem_ori = [0,0]
    for i in range(N):
        if X[i] == "1":
            if cnt != 1:
                rem_ori[0] += pow(2,N-i-1,cnt-1)
                rem_ori[0] %= (cnt-1)
            else:
                rem_ori[0] = 0
            rem_ori[1] += pow(2,N-i-1,cnt+1)
            rem_ori[1] %= (cnt+1)

    rem = [(rem_ori[0] if X[i] == "1" else rem_ori[1]) for i in range(N)]
    for i in range(N):
        if X[i] == "1":
            if cnt != 1:
                rem[i] -= pow(2,N-i-1,cnt-1)
                rem[i] %= (cnt-1)
                ans.append(cal(rem[i],1))
            else:
                ans.append(0)
        else:
            rem[i] += pow(2,N-i-1,cnt+1)
            rem[i] %= (cnt+1)
            ans.append(cal(rem[i],1))

    return ans

def cal(rem,rec):
    if rem == 0:
        return rec
    else:
        b = bin(rem)[2:]
        cnt = b.count("1")
        rem %= cnt
        return cal(rem,rec+1)

def main():
    N = int(input())
    X = input()

    ans = solve(N,X)
    for i in range(N):
        print(ans[i])

if __name__ == "__main__":
    main()

Solution (Python):
import math


def f(n):
    pop = 0
    ntemp = n
    for i in range(int(math.log2(n)) + 1):
        pop += ntemp % 2
        ntemp //= 2
    return n % pop


n = int(input())
S = input()
popcount = 0
for i in range(n):
    popcount += int(S[i])


if popcount == 1:
    if S[-1] == 1:
        ans = [2] * n
        ans[-1] = 0
    else:
        ans = [1] * n
        ans[-1] = 2
        for i in range(n):
            if S[i] == '1':
                ans[i] = 0
    for i in range(n):
        print(ans[i])
    exit()


Sint = int(S, 2)
remminus = Sint % (popcount - 1)
remplus = Sint % (popcount + 1)


remlistminus = []
remlistplus = []
temp = 1
for i in range(n):
    remlistminus.append(temp)
    temp = (temp * 2) % (popcount - 1)
temp = 1
for i in range(n):
    remlistplus.append(temp)
    temp = (temp * 2) % (popcount + 1)
remlistminus.reverse()
remlistplus.reverse()

ans = []
for i in range(n):
    count = 1
    if S[i] == '0':
        rem = (remplus + remlistplus[i]) % (popcount + 1)
        while rem > 0:
            rem = f(rem)
            count += 1
    else:
        rem = (remminus - remlistminus[i]) % (popcount - 1)
        while rem > 0:
            rem = f(rem)
            count += 1
    ans.append(count)
for i in range(n):
    print(ans[i])

Solution (Python):
N=int(input())
X=input()
c=X.count('1')
r1=int(X,2)%(c-1) if c>1 else 0
r2=int(X,2)%(c+1)
d=[0]*(N+1)
for i in range(N):
    d[i+1]=d[(i+1)%bin(i+1).count('1')]+1
for i in range(N):
    if X[i]=='0':
        n=(r2+pow(2,N-i-1,c+1))%(c+1)
    else:
        if c==1:
            print(0)
            continue
        n=(r1-pow(2,N-i-1,c-1))%(c-1)
    print(d[n]+1)

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

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


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


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

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

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

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

x = int(X, 2)
pcx = X.count("1")
pc1 = x % (pcx - 1) if pcx > 1 else 0
pc2 = x % (pcx + 1)


for i in range(N):
    if X[i] == '0':
        X_next = pc2 + pow(2,N-1-i,pcx+1)
        X_pop_next = pcx + 1
    elif X[i] == '1' and pcx - 1 != 0:
        X_next = pc1 - pow(2,N-1-i,pcx-1)
        X_pop_next = pcx - 1
    else :
        print(0)
        continue
    
        
    if X_pop_next == 0:
        print(0)
        continue
        
    X_next = X_next % X_pop_next
    ans = 1
    
    while X_next != 0:
        X_next = X_next % popcount(X_next)
        ans += 1
    
    print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
N = int(input())
X = input()
zero_pop = X.count('1') + 1
one_pop = X.count('1') - 1
one_mod, zero_mod = 0, 0

for b in X:
    if one_pop != 0:
        one_mod = (one_mod * 2 + int(b)) % one_pop
    zero_mod = (zero_mod * 2 + int(b)) % zero_pop

pop = {0:0}
def popcount(n):
    if n in pop:
        return pop[n]
    pop[n] = popcount(n // 2) + n % 2
    return pop[n]
memo = {0:0}
def f_count(n):
    if n in memo:
        return memo[n]
    memo[n] = f_count(n % popcount(n)) + 1
    return memo[n]
one_p = {0:1}
def one_pow(n):
    if n in one_p:
        return one_p[n]
    one_p[n] = one_pow(n - 1) * 2 % one_pop
    return one_p[n]
zero_p = {0:1}
def zero_pow(n):
    if n in zero_p:
        return zero_p[n]
    zero_p[n] = zero_pow(n - 1) * 2 % zero_pop
    return zero_p[n]
for i in range(N):
    if X[i] == '1' and one_pop == 0:
        print(0)
        continue
    if X[i] == '1':
        x = one_mod
        x -= one_pow(N-1-i)
        x %= one_pop
    elif X[i] == '0':
        x = zero_mod
        x += zero_pow(N-1-i)
        x %= zero_pop
    
    print(f_count(x) + 1)

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

def powmod(lst,mod):
    if not mod: return
    d = 1
    for i in range(n)[::-1]:
        d %= mod
        lst[i] = d
        d *= 2

def xmod(mod):
    if not mod: return 
    res = 0
    d = 1
    for i in range(n)[::-1]:
        d %= mod
        if int(x[i]):
            res += d
            res %= mod
        d *= 2
    return res

def solve(x):
    res = 1
    while x != 0:
        popcnt = 0
        for i in range(20):
            if x>>i & 1: popcnt += 1
        x %= popcnt
        res += 1
    return res
    
powlst0 = [0]*n
powlst1 = [0]*n
powmod(powlst0,popcnt+1)
x0 = xmod(popcnt+1)
powmod(powlst1,popcnt-1)
x1 = xmod(popcnt-1)

for i in range(n):
    if int(x[i]):
        if popcnt == 1: print(0)
        else: print(solve((x1-powlst1[i])%(popcnt-1)))
    else: print(solve((x0+powlst0[i])%(popcnt+1)))

Solution (Python):



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



dic={}
bn00 = X.count('1')
x00 = int(''.join(X),2)
aa = x00 % (bn00+1)
if bn00-1==0:
    bb = 0
else:
    bb = x00 % (bn00-1)
for i in range(N):
    
    b = int(X[i]) & 1
    bn = b ^ 1
    if bn:
        bn0 = bn00 + 1
        x0 = aa
    else:
        bn0 = bn00 - 1
        x0 = bb
    if bn0==0: 
        print(0)
        continue
    if b: 
        xi = x0 - b * pow(2,N-1-i,bn0)
    if bn:
        xi = x0 + bn * pow(2, N - 1 - i, bn0)
    xi %= bn0
    num = xi
    count = 1
    while num > 0:
        p = format(num,'b').count('1') 
        num = num % p
        count += 1
    print(count)

Solution (Python):
import sys
input=sys.stdin.readline
n=int(input())
x=input().rstrip()
x10=int(x,2)
pcx=x.count("1")

plus=x10%(pcx+1)
if pcx>=2:
    minus=x10%(pcx-1)

def popcnt(x):
    cnt=1
    while x>=1:
        x%=(bin(x).count("1"))
        cnt+=1
    return cnt

for i in range(n):
    if x[i]=="0":
        amari=(plus+pow(2,n-i-1,pcx+1))%(pcx+1)
        print(popcnt(amari))
    else:
        if pcx==1:
            print(0)
        else:
            amari=(minus-pow(2,n-i-1,pcx-1))%(pcx-1)
            print(popcnt(amari))

Solution (Python):
import sys


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


def main():
    N = int(sys.stdin.readline().rstrip())
    X = sys.stdin.readline().rstrip()

    Xdec = int(X, 2)

    
    md = popcount(Xdec)
    md_p, md_m = md + 1, md - 1

    tmp_p = Xdec % md_p
    if md_m > 0:
        tmp_m = Xdec % md_m

    for i in range(0, N, 1):
        if X[i] == "1":  
            if md_m == 0:
                print(0)
                continue
            x_m = pow(2, (N - 1 - i), md_m)
            tmp = (tmp_m - x_m) % md_m

        if X[i] == "0":  
            x_p = pow(2, (N - 1 - i), md_p)
            tmp = (tmp_p + x_p) % md_p

        cnt = 1
        while tmp:

            tmp = tmp % popcount(tmp)
            cnt += 1

        print(cnt)


main()

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

poptbl=[0]*(2*10**5+1)
def popcount(x):
    global poptbl
    
    
    
    poptbl[x]=bin(x).count('1')
    return poptbl[x]

ftbl=[0]*(2*10**5+1)
def f(x):
    global ftbl

    
    
    
    
    if x==0:
        return 0
    else:
        ans=f(x%popcount(x))+1
        
        ftbl[x]=ans
        return ans    

def main():
    n=int(input())
    x=input()
    m=x.count('1')
    
    xint=int(x,2)
    
    if m!=1:
        xmodm1=xint%(m-1)
    else:
        xmodm1=1
    xmodp1=xint%(m+1)
    pow2mod1=[0]*n
    pow2mod2=[0]*n
    pow2mod1[0]=1
    pow2mod2[0]=1
    for i in range(1,n):
        if m!=1:
            pow2mod1[i]=pow2mod1[i-1]*2 % (m-1)
        pow2mod2[i]=pow2mod2[i-1]*2 % (m+1)

    ans=[]
    
    for i in range(n):
        if x[i]=='1':
            if m==1:
                a=0
                ans.append(a)
            else:
                xx=( xmodm1 + (m-1) -pow2mod1[n-i-1] )%(m-1)
                
                a=f(xx)+1
                ans.append(a)
        else:
            xx=( xmodp1 + pow2mod2[n-i-1] )%(m+1)
            
            a=f(xx)+1
            ans.append(a)
        
        print(a)
    return ans

if __name__=='__main__':
    
    ans=main()

Solution (Python):
def readinput():
    n=int(input())
    x=input()
    return n,x

poptbl=[0]*(2*10**5+1)
def popcount(x):
    global poptbl
    if poptbl[x]!=0:
        return poptbl[x]
    
    poptbl[x]=bin(x).count('1')
    return poptbl[x]

ftbl=[0]*(2*10**5+1)
def f(x):
    global ftbl

    
    
    
    
    if x==0:
        return 0
    else:
        ans=f(x%popcount(x))+1
        
        ftbl[x]=ans
        return ans    

def main():
    n=int(input())
    x=input()
    m=x.count('1')
    
    xint=int(x,2)
    
    if m!=1:
        xmodm1=xint%(m-1)
    else:
        xmodm1=1
    xmodp1=xint%(m+1)
    pow2mod1=[0]*n
    pow2mod2=[0]*n
    pow2mod1[0]=1
    pow2mod2[0]=1
    for i in range(1,n):
        if m!=1:
            pow2mod1[i]=pow2mod1[i-1]*2 % (m-1)
        pow2mod2[i]=pow2mod2[i-1]*2 % (m+1)

    ans=[]
    
    for i in range(n):
        if x[i]=='1':
            if m==1:
                a=0
                ans.append(a)
            else:
                xx=( xmodm1 + (m-1) -pow2mod1[n-i-1] )%(m-1)
                
                a=f(xx)+1
                ans.append(a)
        else:
            xx=( xmodp1 + pow2mod2[n-i-1] )%(m+1)
            
            a=f(xx)+1
            ans.append(a)
        
        print(a)
    return ans

if __name__=='__main__':
    
    ans=main()

Solution (Python):
def readinput():
    n=int(input())
    x=input()
    return n,x

poptbl=[0]*(2*10**5+1)
def popcount(x):
    global poptbl
    if poptbl[x]!=0:
        return poptbl[x]
    
    poptbl[x]=bin(x).count('1')
    return poptbl[x]

ftbl=[0]*(2*10**5+1)
def f(x):
    global ftbl

    if ftbl[x]!=0:
        return ftbl[x]
    
    
    if x==0:
        return 0
    else:
        ans=f(x%popcount(x))+1
        
        ftbl[x]=ans
        return ans    

def main():
    n=int(input())
    x=input()
    m=x.count('1')
    
    xint=int(x,2)
    
    if m!=1:
        xmodm1=xint%(m-1)
    else:
        xmodm1=1
    xmodp1=xint%(m+1)
    pow2mod1=[0]*n
    pow2mod2=[0]*n
    pow2mod1[0]=1
    pow2mod2[0]=1
    for i in range(1,n):
        if m!=1:
            pow2mod1[i]=pow2mod1[i-1]*2 % (m-1)
        pow2mod2[i]=pow2mod2[i-1]*2 % (m+1)

    ans=[]
    
    for i in range(n):
        if x[i]=='1':
            if m==1:
                a=0
                ans.append(a)
            else:
                xx=( xmodm1 + (m-1) -pow2mod1[n-i-1] )%(m-1)
                
                a=f(xx)+1
                ans.append(a)
        else:
            xx=( xmodp1 + pow2mod2[n-i-1] )%(m+1)
            
            a=f(xx)+1
            ans.append(a)
        
        print(a)
    return ans

if __name__=='__main__':
    
    ans=main()

Solution (Python):
def readinput():
    n=int(input())
    x=input()
    return n,x

poptbl=[0]*(2*10**5+1)
def popcount(x):
    global poptbl
    if poptbl[x]!=0:
        return poptbl[x]
    
    poptbl[x]=bin(x).count('1')
    return poptbl[x]

ftbl=[0]*(2*10**5+1)
def f(x):
    global ftbl

    if ftbl[x]!=0:
        return ftbl[x]
    
    
    if x==0:
        return 0
    else:
        ans=f(x%popcount(x))+1
        
        ftbl[x]=ans
        return ans    

def main():
    n=int(input())
    x=input()
    m=x.count('1')
    
    xint=int(x,2)
    
    if m!=1:
        xmodm1=xint%(m-1)
    else:
        xmodm1=1
    xmodp1=xint%(m+1)
    pow2mod1=[0]*n
    pow2mod2=[0]*n
    pow2mod1[0]=1
    pow2mod2[0]=1
    for i in range(1,n):
        if m!=1:
            pow2mod1[i]=pow2mod1[i-1]*2 % (m-1)
        pow2mod2[i]=pow2mod2[i-1]*2 % (m+1)

    ans=[]
    
    for i in range(n):
        if x[i]=='1':
            if m==1:
                a=0
                ans.append(a)
            else:
                xx=( xmodm1 + (m-1) -pow2mod1[n-i-1] )%(m-1)
                
                a=f(xx)+1
                ans.append(a)
        else:
            xx=( xmodp1 + pow2mod2[n-i-1] )%(m+1)
            
            a=f(xx)+1
            ans.append(a)
        
        print(a)
    return ans

if __name__=='__main__':
    
    ans=main()

Solution (Python):
n = int(input())
x = input()
x_popcnt = x.count('1')
one_popcnt = x_popcnt - 1
zero_popcnt = x_popcnt + 1

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

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

onepow2 = [1]*220000
if one_popcnt != 0:
    for i in range(1, 220000):
        onepow2[i] = 2*onepow2[i-1] % one_popcnt
zeropow2 = [1]*220000
for i in range(1, 220000):
    zeropow2[i] = 2*zeropow2[i-1] % zero_popcnt
for i in range(n-1, -1, -1):
    if x[n-1-i] == '1':
        if one_popcnt != 0:
            nxt = one_mod
            nxt -= onepow2[i]
            nxt %= one_popcnt
            print(f[nxt]+1)
        else:
            print(0)
    if x[n-1-i] == '0':
        nxt = zero_mod
        nxt += zeropow2[i]
        nxt %= zero_popcnt
        print(f[nxt]+1)

Solution (Python):
n = int(input())
x = input()
x_popcnt = x.count('1')
one_popcnt = x_popcnt - 1
zero_popcnt = x_popcnt + 1

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

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

for i in range(n-1, -1, -1):
    if x[n-1-i] == '1':
        if one_popcnt != 0:
            nxt = one_mod
            nxt -= pow(2, i, one_popcnt)
            nxt %= one_popcnt
            print(f[nxt]+1)
        else:
            print(0)
    if x[n-1-i] == '0':
        nxt = zero_mod
        nxt += pow(2, i, zero_popcnt)
        nxt %= zero_popcnt
        print(f[nxt]+1)

Solution (Python):
n = int(input())
x = list(map(int, input()))

one_cnt = x.count(1)
mods = [one_cnt - 1, one_cnt + 1]
sms = [0, 0]

for i in range(2):
    if mods[i] == 0:
        continue

    for j, e in enumerate(x):
        sms[i] += pow(2, n - j - 1, mods[i]) * e
        sms[i] %= mods[i]

for i, e in enumerate(x):
    idx = 1 - e
    mod = mods[idx]
    sm = sms[idx]

    if mod == 0:
        print(0)
        continue

    sm_changed = sm + pow(2, n - i - 1, mod) * (-1) ** e
    sm_changed %= mod
    ans = 1
    while sm_changed:
        tmp = sm_changed
        cnt = 0
        while tmp:
            cnt += tmp & 1
            tmp >>= 1

        sm_changed %= cnt
        ans += 1

    print(ans)

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

def popcount(n):
    bin_n = bin(n)[2:]
    count = 0
    for i in bin_n:
        count += int(i)
    return count

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

plus = [0 for i in range(n)] 
minus = [0 for i in range(n)] 
if cnt == 0:
    plus[0] = 0
else:
    plus[0] = 1
if cnt != 1:
    minus[0] = 1
for i in range(1, n):
    plus[i] = (plus[i-1]*2) % (cnt+1)
    if cnt != 1:
        minus[i] = (minus[i-1]*2) % (cnt-1)

origin = int(''.join(x), base=2)
amariplus = origin % (cnt+1)
if cnt != 1:
    amariminus = origin % (cnt-1)

for i in range(n):
    if x[i] == '0':
        amari = (amariplus + plus[n-i-1]) % (cnt+1)
    else:
        if cnt != 1:
            amari = (amariminus - minus[n-i-1]) % (cnt-1)
        else:
            print(0)
            continue
    ans = 1
    while amari != 0:
        ans += 1
        amari = amari % popcount(amari)
    print(ans)

Solution (Python):
N = 2 * 10 ** 5
n = int(input())
x = input()

def popcount(n):
    res = 0
    while n > 0:
        res += n & 1
        n >>= 1
    return res

f = [0] * (N + 1)
for i in range(1, N + 1):
    m = i
    while True:
        f[i] += 1
        p = popcount(m)
        m %= popcount(m)
        if m == 0:
            break

px = x.count('1')
m01 = 0
m10 = 0
for c in x:
    b = int(c)
    m01 = (2 * m01 + b) % (px + 1)
    if px - 1 != 0:
        m10 = (2 * m10 + b) % (px - 1)

for i, c in enumerate(x):
    if c == '0':
        m = m01 + pow(2, n - i - 1, px + 1)
        m %= px + 1
        print(f[m] + 1)
    elif px - 1 == 0:
        print(0)
    else:
        m = m10 - pow(2, n - i - 1, px - 1)
        m %= px - 1
        print(f[m] + 1)

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

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

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


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


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

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

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

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


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


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

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

Solution (Python):

 
def f(n):
        cnt = 0
        while n:
            cnt+= 1
            n = n%bin(n).count('1')
        return cnt
 
def main():
    N = int(input())
    X = input()
    X10 = int(X,2)
    X10_num1 = X.count('1')
    X10_pulse = X10%(X10_num1+1)
    X10_ninus = X10%(X10_num1-1) if X10_num1 >1 else 0
 
 
    for i in range(N,0,-1):
        if (X10>>(i-1) & 1) and X10_num1 >1:
            mod = X10_num1-1
            amari = (X10_ninus - pow(2,i-1,mod))%(mod) 
        elif (X10>>(i-1) & 1) and X10_num1 ==1:
            print(0)
            continue
        else:
            mod = X10_num1+1
            amari = (X10_pulse + pow(2,i-1,mod))%(mod) 
 
        print(1+f(amari))
 
 
main()

Solution (Python):


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

def main():
    N = int(input())
    X = input()
    X10 = int(X,2)
    X10_num1 = X.count('1')
    X10_pulse = X10%(X10_num1+1)
    X10_ninus = X10%(X10_num1-1) if X10_num1 >1 else 0


    for i in range(N,0,-1):
        j = N-i
        if (X[j] == '1') and X10_num1 >1:
            mod = X10_num1-1
            amari = (X10_ninus - pow(2,i-1,mod))%(mod) 
        elif (X[j] == '1') and X10_num1 ==1:
            print(0)
            continue
        else:
            mod = X10_num1+1
            amari = (X10_pulse + pow(2,i-1,mod))%(mod)

        print(1+f(amari))


main()