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
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

N = int(input())
Xb = input().rstrip()
p = Xb.count('1')
def popcount(x):
    return bin(x).count('1')
def calc(X):
    ans = 0
    while X!=0:
        X %= popcount(X)
        ans += 1
    return ans
Xp = 0
Xm = 0
tp = 1
tm = 1
b = 0
if p>1:
    flag = True
else:
    flag = False

for i in reversed(range(N)):
    if Xb[i]=='1':
        Xp += tp
        Xp %= (p+1)
        if flag:
            Xm += tm
            Xm %= (p-1)
    tp *= 2
    tp %= (p+1)
    if flag:
        tm *= 2
        tm %= (p-1)

for i in range(N):
    if Xb[i]=='1' and p==1:
        print(0)
        continue
    elif Xb[i]=='1':
        X = (Xm - pow(2,N-1-i,p-1)+p-1)%(p-1)
    else:
        X = (Xp + pow(2,N-1-i,p+1))%(p+1)
    print(calc(X)+1)

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



N = I()
X = list(input())


def calc(x):
    n = len(x)
    c = x.count('1')
    now = 0
    for i in range(n):
        if x[i] == '1':
            now += 2**(n-1-i)
            now %= c
    if now == 0:
        return 1
    else:
        return calc(list(format(now,'b')))+1

count = X.count('1')

a = [1]*(N+1)
if count >= 2:
    a[0] = 1%(count-1)
    for i in range(1,N+1):
        a[i] = a[i-1]*2
        a[i] %= count-1

b = [1]*(N+1)
b[0] = 1%(count+1)
for i in range(1,N+1):
    b[i] = b[i-1]*2
    b[i] %= count+1

suma = 0
sumb = 0
for i in range(N):
    if X[i] == '1':
        suma += a[N-i-1]
        sumb += b[N-i-1]
        sumb %= (count+1)
        if count >= 2:
            suma %= (count-1)

ans = [0]*N
for i in range(N):
    if X[i] == '1':
        if count == 1:
            ans[i] = 0
            continue
        val = (suma-a[N-i-1])%(count-1)
        if val == 0:
            ans[i] = 1
        else:
            ans[i] = calc(list(format(val,'b')))+1
    else:
        val = (sumb+b[N-i-1])%(count+1)
        if val == 0:
            ans[i] = 1
        else:
            ans[i] = calc(list(format(val,'b')))+1

for a in ans:
    print(a)

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



s = input()
x = int(s, base=2)
popcount = s.count('1')
y_zero = x % (popcount + 1)
if popcount > 1:
    y_one = x % (popcount - 1)
dp = [-1] * n
dp[0] = 0


def calc(y):
    if dp[y] != -1:
        return dp[y]
    dp[y] = 1 + calc(y % bin(y).count('1'))
    return dp[y]


ans = [0] * n
rem_zero = 1
if popcount > 1:
    rem_one = popcount - 2
for i in range(n):
    if s[n - 1 - i] == '0':
        ans[n - 1 - i] = 1 + calc((y_zero + rem_zero) % (popcount + 1))
    elif popcount > 1:
        ans[n - 1 - i] = 1 + calc((y_one + rem_one) % (popcount - 1))
    else:
        ans[n - 1 - i] = 0
    rem_zero = rem_zero * 2 % (popcount + 1)
    if popcount > 1:
        rem_one = rem_one * 2 % (popcount - 1)
for i in range(n):
    print(ans[i])

Solution (Python):


n = int(input())
X = input()
c = 0
cnt = 0
for i,x in enumerate(X):
    c += (1<<(n-i-1))*int(x)
    cnt += int(x)

amari_cnt_p = c % (cnt+1)
if cnt != 1:
    amari_cnt_m = c % (cnt-1)

dp = []
for d in range(n):
    if cnt == 1 and X[d] == '1':
      dp.append(-1)
      continue

    if X[d] == "0":
        amari = (amari_cnt_p + pow(2,n-d-1,cnt+1))%(cnt+1)
    else:
        if cnt != 1:
            amari = (amari_cnt_m - pow(2,n-d-1,cnt-1))%(cnt-1)
        else:
            amari = 0
    dp.append(amari)

memo = [-1]*(2*10**5+10)
memo[0] = 1
def calc(n):
    if n == -1:
        return 0
    if n == 0:
        return 1
    if memo[n] != -1:
        return memo[n]
    cnt = 1
    while n > 0:
        c = bin(n).count("1")
        n %= c
        cnt += 1
    memo[n] = cnt
    return cnt

for d in dp:
    ans = calc(d)
    print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

from functools import lru_cache,reduce
@lru_cache()
def dfs(n):
    if n == 0:
        return 0
    popcnt = bin(n).count('1')
    if n%popcnt == 0:
        return 1
    return dfs(n%popcnt) + 1

def main():
    N = int(input())
    X = input()
    cnt = 0
    for i in range(N):
        if X[i] == '1':
            cnt += 1
    
    if cnt == 0:
        for i in range(N):
            print(1)
        return 
    
    power1 = [0] * N
    power2 = [0] * N
    for i in range(N):
        if cnt > 1:
            power1[i] = pow(2,i,cnt - 1)
        power2[i] = pow(2,i,cnt + 1)
    
    modu1 = 0
    modu2 = 0
    ans = [0] * N
    for i in range(N):
        if X[N - i - 1] == '1':
            if cnt > 1:
                modu1 += power1[i]
                modu1 %= (cnt - 1)
            modu2 += power2[i]
            modu2 %= (cnt + 1)
    
    for i in range(N):
        if X[i] == '1':
            if cnt == 1:
                ans[i] = 0
                continue
            now = modu1
            now -= power1[N - i - 1]
            now %= (cnt - 1)
            ans[i] = dfs(now) + 1
        else:
            now = modu2
            now += power2[N - i - 1]
            now %= (cnt + 1)
            ans[i] = dfs(now) + 1
    print('\n'.join(map(str,ans)))
if __name__ == '__main__':
    main()

Solution (Python):

n = int(input())
x = input()
cnt = x.count("1")
x_cnt_plus = 0
x_cnt_minus = 0
for i in range(n):
    if x[i] == "1":
        x_cnt_plus += pow(2, n - i - 1, cnt + 1)
        x_cnt_plus %= cnt + 1
        if cnt > 1:
            x_cnt_minus += pow(2, n - i - 1, cnt - 1)
            x_cnt_minus %= cnt - 1
for i in range(n):  
    if x[i] == "0":
        f = x_cnt_plus + pow(2, n - i - 1, cnt + 1)
        f %= cnt + 1
    else:
        if cnt == 1:
            print(0)
            continue
        f = x_cnt_minus + cnt - 1 - pow(2, n - i - 1, cnt - 1)
        f %= cnt - 1
    ans = 1
    while f != 0:
        cnt_f_1 = 0
        k = f
        while k:
            if k % 2:
                cnt_f_1 += 1
            k //= 2
        f = f % cnt_f_1
        ans += 1
    print(ans)
"""
step1; 1を数える cnt_1 
step2 : 全体の計算をする cnt1 + 1 とcnt1 -1 それぞれ
step3 : それぞれの桁に対して0 なら cnt+ 1 を適用 + 2**k mod cnt + 1
            1ならcnt - 1　を適用 - 2**k mod (cnt-1)
step4 : その中でf(x)を0になるまで計算
"""

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

c1 = x.count('1')
if c1 > 1:
    cc1 = int('0b' + x, 0) % (c1 - 1)
cc2 = int('0b' + x, 0) % (c1 + 1)

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

if c1 == 1:
    for i in range(n):
        if x[i] == '1':
            print(0)
        else:
            print(f((pow(2, n-i-1, c1+1) + cc2) % (c1 + 1)) + 1)
    exit()

for i in range(n):
    if x[i] == '1':
        print(f((-pow(2, n-i-1, c1-1) + cc1) % (c1 - 1)) + 1)
    else:
        print(f((pow(2, n-i-1, c1+1) + cc2) % (c1 + 1)) + 1)

Solution (Python):
def solve(N, strX):
    def getNum1s(numD):
        num1s = [0] * (1<<numD)
        for S in range(1, 1<<numD):
            num1s[S] = num1s[S ^ (S & -S)] + 1
        return num1s
    num1s = getNum1s(20)

    fs = [0] * (N+1)
    for x in range(1, N+1):
        fs[x] = fs[x%num1s[x]] + 1

    M = strX.count('1')
    M1, M9 = M+1, M-1

    XmodM1 = 0
    for X in strX:
        XmodM1 *= 2
        XmodM1 += int(X)
        XmodM1 %= M1
    XmodM9 = 0
    for X in strX:
        XmodM9 *= 2
        XmodM9 += int(X)
        XmodM9 %= M9

    modM1s = []
    modM1 = 1
    for d in range(N+2):
        modM1s.append(modM1)
        modM1 *= 2
        modM1 %= M1

    modM9s = []
    modM9 = 1
    for d in range(N+2):
        modM9s.append(modM9)
        modM9 *= 2
        modM9 %= M9

    anss = []
    for X, modM1, modM9 in zip(strX[::-1], modM1s, modM9s):
        if X == '0':
            Y2 = (XmodM1 + modM1) % M1
        else:
            Y2 = (XmodM9 - modM9) % M9
        ans = fs[Y2] + 1
        anss.append(ans)

    return anss[::-1]


def solve2(N, strX):
    def getNum1s(numD):
        num1s = [0] * (1<<numD)
        for S in range(1, 1<<numD):
            num1s[S] = num1s[S ^ (S & -S)] + 1
        return num1s
    num1s = getNum1s(20)

    fs = [0] * (N+1)
    for x in range(1, N+1):
        fs[x] = fs[x%num1s[x]] + 1

    M = strX.count('1')
    M1, M9 = M+1, M-1

    XmodM1 = 0
    for X in strX:
        XmodM1 *= 2
        XmodM1 += int(X)
        XmodM1 %= M1

    modM1s = []
    modM1 = 1
    for d in range(N+2):
        modM1s.append(modM1)
        modM1 *= 2
        modM1 %= M1

    anss = []
    for X, modM1 in zip(strX[::-1], modM1s):
        if X == '0':
            Y2 = (XmodM1 + modM1) % M1
            ans = fs[Y2] + 1
        else:
            ans = 0
        anss.append(ans)

    return anss[::-1]


N = int(input())
strX = input().rstrip()

num1 = strX.count('1')

if num1 == 0:
    anss = [1] * N
elif num1 == 1:
    anss = solve2(N, strX)
else:
    anss = solve(N, strX)

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

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

ans_reduce,ans_add = 0,0
for i in range(n):
    if(one_num>1):
        ans_reduce = (ans_reduce+pow(2,n-i-1,one_num-1)*(1 if x[i] == '1' else 0))%(one_num-1)
    ans_add = (ans_add+pow(2,n-i-1,one_num+1)*(1 if x[i] == '1' else 0))%(1+one_num)

for i in range(n):
    now_one = one_num + (-1 if x[i] == '1' else 1)
    if(now_one == 0):
        print(0)
        continue
    num = ((ans_reduce if x[i] == '1' else ans_add) + pow(2,n-i-1,now_one)*(-1 if x[i] == '1' else 1))%now_one
    ans = 1
    while(num!=0):
        ans += 1
        num = num % bin(num).count('1')
    print(ans)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7




popc = [0] * ((1 << 18) + 1)
for bit in range(1, 1 << 18):
    opt = bin(bit).count('1')
    popc[bit] = bit % opt

f_list = [0] * ((1 << 18) + 1)
for i in range(1, 1 << 18):
    now = popc[i]
    cnt = 1
    while True:
        if now == 0:
            f_list[i] = cnt
            break
        now = popc[now]
        cnt += 1

N = getN()
X = input()
NX = len(X)
time = X.count('1')
t1 = time + 1
t2 = time - 1

lis_left_1 = [0] * NX

now = 1 % t1
lis_left_1[0] = now
for i in range(1, NX):
    now = (2 * now) % t1
    lis_left_1[i] = now

lis_left_2 = [0] * NX

if t2 > 0:
    now = 1 % t2
    lis_left_2[0] = now
    for i in range(1, NX):
        now = (2 * now) % t2
        lis_left_2[i] = now

left_mother_1 = 0
for i in range(NX):
    if int(X[i]) == 1:
        left_mother_1 += lis_left_1[NX - i - 1]

left_mother_2 = 0
for i in range(NX):
    if int(X[i]) == 1:
        left_mother_2 += lis_left_2[NX - i - 1]

for i in range(N):
    
    if int(X[i]) == 1:
        if t2 == 0:
            print(0)
            continue
        opt_mom = left_mother_2
        opt_mom -= lis_left_2[NX - i - 1]
        opt_mom %= t2
        print(f_list[opt_mom] + 1)
    
    else:
        opt_mom = left_mother_1
        opt_mom += lis_left_1[NX - i - 1]
        opt_mom %= t1
        print(f_list[opt_mom] + 1)

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque, defaultdict


from collections import Counter

from itertools import accumulate,combinations,permutations,product

from heapq import heapify,heappop,heappush


from functools import reduce,lru_cache

from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    

    N = int(input())
    s = input()
    
    
    
    
    def bin(x): return format(x, 'b')
    def bitcount(x): return bin(x).count("1")
    
    @lru_cache(None)
    def r(n):
        if n==0:
            return 0
        bc=bitcount(n)
        return r(n%bc)+1

    mod=s.count("1")
    c1=0
    c2=0
    cur1=1%(mod+1)
    
    if mod>1:
        cur2=1%(mod-1)
        for i in range(N):
            if s[-1-i]=="1":
                c1+=cur1
                c1%=(mod+1)
                c2+=cur2
                c2%=(mod-1)

            cur1=cur1*2%(mod+1)
            cur2=cur2*2%(mod-1)
    else:
        for i in range(N):
            if s[-1-i]=="1":
                c1+=cur1
                c1%=(mod+1)
            cur1=cur1*2%(mod+1)



    for i in range(N):
        if s[i]=="1":
            f=-1
            cmod=mod-1
        else:
            f=1
            cmod=mod+1

        if cmod==0:
            print(0)
            continue
        
        if f==1:
            n=c1+pow(2,N-1-i,cmod)
            n%=cmod
        else:
            n=c2-pow(2,N-1-i,cmod)
            n%=cmod

        print(1+r(n))
    





if __name__ == "__main__":
    main()

Solution (Python):


def main():
    N = int(input())
    X = [None] * N
    l = list(input())
    Xc = 0
    for i in range(N):
        X[i] = int(l[i])
        Xc += X[i]

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

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

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

if __name__ == "__main__":
    main()

Solution (Python):
def popcnt(n):
    return bin(n).count("1")
N = int(input())
L = [0]*(N+1)
for i in range(1,N+1):
    L[i] = L[i%popcnt(i)]+1
L[N] = -1
X = input()
M = X.count("1")+1
m = max(1,M-2)
X = list(X)
XM = int(X[-1])
Xm = int(X[-1])
tM = 1
tm = 1
X.reverse()
for i in range(1,N):
    tM = tM*2%M
    tm = tm*2%m
    if X[i] == "1":
        XM = (XM + tM)%M
        Xm = (Xm + tm)%m
ans = []
tM = 1
tm = 1
for i in range(N):
    A = 0
    if X[i] == "0":
        A = (XM + tM)%M
    else:
        A = (Xm + m - tm)%m
        if M == 2:
            A = N
    ans.append(A)
    tM = (tM*2)%M
    tm = (tm*2)%m
ans.reverse()
for a in ans:
    print(L[a]+1)

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

cnt = 0
for i in range(N):
    if X[i] == "1":
        cnt += 1
    
down = [0] * N
up = [0] * N
ald = 0
alu = 0
for i in range(N):
    up[i] = pow(2, N-1-i, cnt+1)
    if X[i] == "1":
        alu += up[i]
        alu %= cnt+1
    if cnt <= 1:
        continue
    down[i] = pow(2, N-1-i, cnt-1)
    if X[i] == "1":
        ald += down[i]
        ald %= cnt-1

for i in range(N):    
    if X[i] == "1":
        if cnt == 1:
            print(0)
            continue
        n = (ald - down[i]) % (cnt-1)
    else:
        n = (alu + up[i]) % (cnt+1)
    ans = 1
    while n != 0:
        c = 0
        for j in range(20):
            if (n >> j) % 2 == 1:
                c += 1
        n %= c
        ans += 1
    print(ans)

Solution (Python):


import sys
import numpy as np
from functools import lru_cache
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)


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


N = int(readline())
X = readline().decode().rstrip()
X_ = int(X, 2)
X_cnt = X.count('1')
p1 = X_ % (X_cnt + 1)
m1 = X_ % (X_cnt - 1) if X_cnt > 1 else 0

for i in range(N):
    if X[i] == '0':
        cnt = X_cnt + 1
        acc = (p1 + pow(2, N - i - 1, cnt)) % cnt

    else:
        cnt = X_cnt - 1
        if cnt == 0:
            print(0)
            continue
        acc = (m1 - pow(2, N - i - 1, cnt)) % cnt
    print(f(acc) + 1)

Solution (Python):

from collections import defaultdict, deque, Counter, OrderedDict
from functools import reduce, lru_cache
import collections, heapq, itertools, bisect
import math, fractions
import sys, copy

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline().rstrip())
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline().rstrip())
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

def main():
    N = I()
    X = S()
    original_popcount = X.count("1")

    upper_popcount = original_popcount + 1
    lower_popcount = original_popcount - 1

    if original_popcount == 0:
        for i in range(N):
            print(1)
        return

    if original_popcount == 1:
        for i in range(N):
            if X[-1] == "1":
                if i != N-1:
                    print(2)
                else:
                    print(0)
            else:
                if X[i] == "1":
                    print(0)
                elif i == N-1:
                    print(2)
                else:
                    print(1)
        return

    
    upper = [0] * N
    lower = [0] * N
    upper[-1] = 1 % upper_popcount
    lower[-1] = 1 % lower_popcount

    for i in range(1, N)[::-1]:
        upper[i-1] = (2 * upper[i]) % upper_popcount
        lower[i-1] = (2 * lower[i]) % lower_popcount

    mu = 0
    ml = 0
    for i in range(N):
        if X[i] == "1":
            mu = (mu + upper[i]) % upper_popcount
            ml = (ml + lower[i]) % lower_popcount

    for i in range(N):
        if X[i] == "0":
            m = (mu + upper[i]) % upper_popcount
        else:
            m = (ml - lower[i]) % lower_popcount

        ans = 1
        while m:
            tmp = m
            ones = 0
            while tmp:
                if tmp & 1 == 1:
                    ones += 1
                tmp //= 2
            m %= ones
            ans += 1

        print(ans)



if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n_ansl = [0]*(2*(10**5))
    for i in range(1,2*(10**5)):
    
        cnt = 0
        one_cnt = bin(i).count("1")
        rem = i
        while rem != 0:
            one_cnt = bin(rem).count("1")
            rem = rem%one_cnt   
            cnt += 1
        n_ansl[i] = cnt
 
    n = int(input())
    x = list(input())
    one_cnt = x.count('1')

    if one_cnt == 0:
        for i in range(n):
            print(1)
        exit()
    
    curr_2b_p = 1
    curr_2b_m = 1
    curr_sum_p1 = 0
    curr_sum_m1 = 0
    for i in range(n-1, -1, -1):
        if x[i] == '1':
            curr_sum_p1 += curr_2b_p
            curr_sum_m1 += curr_2b_m
            curr_sum_p1%=(one_cnt+1)
            if one_cnt > 1:
                curr_sum_m1%=(one_cnt-1)
        curr_2b_p*=2
        curr_2b_m*=2
        curr_2b_p%=(one_cnt+1)
        if one_cnt > 1:
            curr_2b_m%=(one_cnt-1)
 
        
 
    curr_2b_p = 1
    curr_2b_m = 1
    ansl = [0]*(n)
    for i in range(n-1, -1, -1):
        if x[i] == '1':
            diff = (-1)*curr_2b_m
            if one_cnt > 1:
                ans = (curr_sum_m1 + diff)%(one_cnt-1)
                ansl[i] = n_ansl[ans]+1
            else:
                ansl[i] = 0
        else:
            diff = curr_2b_p
            ans = (curr_sum_p1 + diff)%(one_cnt+1)
            ansl[i] = (n_ansl[ans]+1)
        curr_2b_p*=2
        curr_2b_m*=2
        curr_2b_p%=(one_cnt+1)
        if one_cnt > 1:
            curr_2b_m%=(one_cnt-1)
 
 
    
    for a in ansl:
        print(a)
 
if __name__ == "__main__":
    main()

Solution (Python):
import copy
n=int(input())
x=list(input())
b=[]
for i in range(2**18):
  b.append(format(i,'0'+str(18)+'b'))
  if i>n+1:
    break
ct=[0]*(n+1)
for i in range(1,n):
  ct1=0
  for j in range(len(b[i])):
    if b[i][j]=='1':
      ct1+=1
  ct[i]=i%ct1

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

moda=[1]
modb=[1]
modc=[1]
for i in range(n-1):
  if CT>=2:
    moda.append(moda[-1]*2%(CT-1))
  if CT>=1:
    modb.append(modb[-1]*2%CT)
  modc.append(modc[-1]*2%(CT+1))


x.reverse()
za=0
zb=0
zc=0
for i in range(n):
  if x[i]=='1':
    if CT>=2:
      za+=moda[i]
      za%=(CT-1)
    if CT>=1:
      zb+=modb[i]
      zb%=CT
    zc+=modc[i]
    zc%=(CT+1)
x.reverse()
moda.reverse()
modc.reverse()

for i in range(n):
  y2=x[i]
  if y2=='1':
    ct1=CT-1
  else:
    ct1=CT+1
  if ct1==0:
    print(0)
  else:
    if y2=='1':
      z=za
      z-=moda[i]
      z%=ct1
    else:
      z=zc
      z+=modc[i]
      z%=ct1
    
    ans=1
    while z!=0:
      z=ct[z]
      ans+=1
    print(ans)

Solution (Python):
n=int(input())
x=input()
p=x.count("1")
Ma=[1]+[0]*(n-1)
Mb=[1]+[0]*(n-1)
for i in range(1,n):
  if p>1:
    Ma[i]=Ma[i-1]*2%(p-1)
  else:
    Ma[i]=0
    Ma[0]=0
  Mb[i]=Mb[i-1]*2%(p+1)
Sa=Sb=0
for i in range(n):
  if x[i]=="1":
    Sa+=Ma[n-1-i]
    Sb+=Mb[n-1-i]
for i in range(n):
  a=0
  if x[i]=="1":
    if p==1:
      s=0
    else:
      s=(Sa-Ma[n-1-i])%(p-1)
      a+=1
  else:
    s=(Sb+Mb[n-1-i])%(p+1)
    a+=1
  while(s>0):
    t=0
    r=s
    while(r>0):
      t+=r&1
      r//=2
    s%=t
    a+=1
  print(a)

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    
    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 main():
    N = int(input())
    X = input()
    d = {}
    dd = {}
    x1 = X.count('1')
    xn = int(X, 2)
    def hoge(i):
        if i in dd:
            return dd[i]
        if i not in d:
            j = popcount(i)
            d[i] = i % j
            if d[i] == 0:
                dd[i] = 1
            else:
                dd[i] = 1 + hoge(d[i])
        return dd[i]
    if N == 1:
        if X == '1':
            print(0)
            return 0
        else:
            print(1)
            return 1
    if x1 == 1:
        xn1 = 0
    else:
        xn1 = xn % (x1-1)
    xn2 = xn % (x1 + 1)
    for i in range(N):
        if X[i] == '1':
            t = xn1
            if x1-1 == 0:
                print(0)
                continue
            t -= pow(2, N-1-i, x1-1)
            t %= (x1-1)
        else:
            t = xn2
            t += pow(2, N-1-i, x1+1)
            t %= (x1 + 1)
        if t == 0:
            print(1)
        else:
            print(1 + hoge(t))
main()

Solution (Python):
def get_popcount(n):
    ret = 0
    while n > 0:
        if n & 1 == 1:
            ret += 1
        n >>= 1
    return ret


def main():
    N = int(input())
    X = input()
    ans = [0] * N
    
    X_popcount = len([x for x in X if x == '1'])
    popcounts = [X_popcount] * N
    for i, x in enumerate(X):
        if x == '1':
            popcounts[i] -= 1
        else:
            popcounts[i] += 1
    
    X_nexts = [0, 0]  
    pows = [1, 1]
    for x in X[::-1]:
        if x == '1':
            if X_popcount - 1 > 0:
                X_nexts[0] += pows[0]
                X_nexts[0] %= X_popcount - 1
            X_nexts[1] += pows[1]
            X_nexts[1] %= X_popcount + 1
        if X_popcount - 1 > 0:
            pows[0] *= 2
            pows[0] %= X_popcount - 1
        pows[1] *= 2
        pows[1] %= X_popcount + 1
    
    xs = [0] * N
    pows = [1, 1]
    for j, x in enumerate(X[::-1]):
        i = N - 1 - j
        if x == '1':
            if X_popcount - 1 > 0:
                xs[i] = X_nexts[0] - pows[0]
                xs[i] %= X_popcount - 1
                ans[i] += 1
        else:
            xs[i] = X_nexts[1] + pows[1]
            xs[i] %= X_popcount + 1
            ans[i] += 1
        if X_popcount - 1 > 0:
            pows[0] *= 2
            pows[0] %= X_popcount - 1
        pows[1] *= 2
        pows[1] %= X_popcount + 1
    
    while sum(xs) > 0:
        for i, x in enumerate(xs):
            if x == 0:
                continue
            xs[i] = x % get_popcount(x)
            ans[i] += 1
    
    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

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


n=int(input())
X=str(input())

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



def culc(x):
    bin_x=str(bin(x)[2:])
    one=0
    for i in range(len(bin_x)):
        if bin_x[i]=='1':
            one+=1
    return x%one
        




dp=[-1]*(number+1)
dp[0]=0
def rec(x):
    if dp[x]>=0:
        return dp[x]
    else:
        dp[x]=rec(culc(x))+1
        return dp[x]



if number==0:
    for i in range(n):
        print(1)
    sys.exit()



base1=0
for i in range(n):
    if X[i]=='1':
        base1=(base1+pow(2,n-i-1,number+1))%(number+1)

if number==1:
    for i in range(n):
        if X[i]=='1':
            print(0)
        else:
            temp=(base1+pow(2,n-i-1,number+1))%(number+1)
            ans=rec(temp)+1
            print(ans)
    sys.exit()



base2=0
for i in range(n):
    if X[i]=='1':
        base2=(base2+pow(2,n-i-1,number-1))%(number-1)






for i in range(n):
    
    if X[i]=='0':
        temp=(base1+pow(2,n-i-1,number+1))%(number+1)
        ans=rec(temp)+1
        print(ans)
    
    if X[i]=='1':
        temp=(base2-pow(2,n-i-1,number-1))%(number-1)
        ans=rec(temp)+1
        print(ans)

Solution (Python):
def fast_powmod(n, m):
    pow2 = 2
    result = 1
    while n > 0:
        if n % 2 == 1:
            result = (result * pow2) % m
        pow2 = (pow2 * pow2) % m
        n >>= 1

    return result

def popcnt3(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()

res = dict()
res[1] = 1
res[2] = 1
for i in range(3, 2 * 10**5 + 1):
    val = i % popcnt3(i)
    if val == 0:
        res[i] = 1
    else:
        res[i] = res[val] + 1

count = 0
for i in x:
    if i == "1":
        count += 1

x = x[::-1]
small = 0
big = 0
for i in range(len(x)):
    if x[i] == "1":
        if count - 1 != 0:
            small += fast_powmod(i, count - 1)
        big += fast_powmod(i, count + 1)

try:
    small %= count - 1
except:
    small = 0
big %= count + 1

anse = []
for i in range(len(x)):
    if x[i] == "1":
        done = False
        ans = 0
        if count - 1 == 0:
            anse.append(0)
        else:
            cur = small - fast_powmod(i, count - 1)
            cur %= count - 1
            if cur == 0:
                anse.append(1)
            else:
                anse.append(res[cur] + 1)
    else:
        done = False
        ans = 0
        cur = big + fast_powmod(i, count + 1)
        cur %= count + 1
        if cur == 0:
            anse.append(1)
        else:
            anse.append(res[cur] + 1)


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