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 math
from collections import defaultdict,deque
ml=lambda:map(int,input().split())
ll=lambda:list(map(int,input().split()))
ii=lambda:int(input())
ip=lambda:list(input())
ips=lambda:input().split()

"""========main code==============="""

def fast_expo(x,y,m):
    res=1
    while(y):
        if(y&1):
            res*=x
            res%=m
        x*=x
        x%=m
        y>>=1
    return res    

dp=defaultdict(int)
dp[1]=1
dp[2]=1
for i in range(3,200001):
    k=i
    cnt=0
    while(k):
        if(k%2): cnt+=1
        k>>=1
    dp[i]=dp[i%cnt]+1
n=ii()
a=ip()
a=a[::-1]
c=a.count('1')

min_1=0
max_1=0

for i in range(n):
    if(a[i]=='1'):
        if(c-1!=0):
            min_1+=fast_expo(2,i,c-1)
            min_1%=(c-1)
        max_1+=fast_expo(2,i,c+1)
        
        max_1%=(c+1)
    
ans=[]    

for i in range(n):
    if(a[i]=='1'):
        if(c-1==0):
            ans.append(0)
        else:    
            ans.append(dp[(min_1-fast_expo(2,i,c-1)+(c-1))%(c-1)]+1)
    else:
        ans.append(dp[(max_1+fast_expo(2,i,c+1))%(c+1)]+1)
ans=ans[::-1]
for i in ans:
    print(i)

Solution (Python):
import sys


def popcount(n):
    c = 0
    while n:
        if n & 1:
            c += 1
        n >>= 1

    return c


def f(n, c=0):
    while pc := popcount(n):
        n %= pc
        c += 1

    return c


def _resolve(n, x_bytes):
    one_i = b'1'[0]
    pc_x = x_bytes.count(b'1')

    i2_mod_pc_x_p1 = [0] * n
    i2_mod_pc_x_m1 = [0] * n
    x_mod_pc_x_p1 = 0
    x_mod_pc_x_m1 = 0

    i2 = 1
    x = 0
    mod = pc_x + 1
    for a in range(n):
        i2_mod_pc_x_p1[- 1 - a] = i2
        i2 *= 2
        i2 %= mod

        x *= 2
        x %= mod
        if (x_bytes[a] == one_i):
            x += 1
    x_mod_pc_x_p1 = x % mod

    if pc_x > 1:
        i2 = 1
        x = 0
        mod = pc_x - 1
        for a in range(n):
            i2_mod_pc_x_m1[- 1 - a] = i2
            i2 *= 2
            i2 %= mod

            x *= 2
            x %= mod
            if (x_bytes[a] == one_i):
                x += 1
        x_mod_pc_x_m1 = x % mod

    
    
    

    
    

    for a in range(n):
        if x_bytes[a] == one_i:
            mod = pc_x - 1
            if mod == 0:
                yield 0
                continue
            b = x_mod_pc_x_m1 - i2_mod_pc_x_m1[a]
        else:
            mod = pc_x + 1
            b = x_mod_pc_x_p1 + i2_mod_pc_x_p1[a]
        b %= mod

        yield f(b, 1)

def resolve(in_, out):
    n = int(in_.readline())
    x_bytes = in_.readline()
    for ret in _resolve(n, x_bytes):
        print(ret, file=out)


def main():
    resolve(sys.stdin.buffer, sys.stdout)


if __name__ == '__main__':
    main()

Solution (Python):
def popcount(x):
    return bin(x).count("1")
def solve(n):
    if n == 0:
        return 0
    return 1+solve(n % popcount(n))

N = int(input())
X = input()
num_x = int(X, 2)
p_cnt = X.count('1')
if p_cnt == 1:
    for i in range(N):
        if X[i] == '1':
            print(0)
        elif i == N-1:
            print(2)
        else:
            print(1)
    exit()
r0_p = num_x % (p_cnt+1)
r0_m = num_x % (p_cnt-1)
for i in range(N):
    if X[i] == '0':
        c_p_cnt = p_cnt+1
        r = (r0_p + pow(2, (N - 1 - i), c_p_cnt)) % c_p_cnt
    else:
        c_p_cnt = p_cnt-1
        if c_p_cnt == 0:
            print(0)
            continue
        r = (r0_m- pow(2, (N - 1 - i), c_p_cnt)) % c_p_cnt
    print(1 + solve(r % c_p_cnt))

Solution (Python):

N=int(input())
X=str(input())
   
CNT=0
for i in range(N):
    if X[i]=="1":
        CNT+=1
NUM=int(X,2)

to0_cnt=[0 for i in range(N)]
for i in range(1,N):
    ans=0
    num=i
    while True:
        cnt=0
        for j in bin(num)[2:]:
            if j=="1":
                cnt+=1
        if cnt==0:
            break
        r=num%cnt
        ans+=1
        if r==0:
            break
        num=r
    to0_cnt[i]=ans
                
R=[NUM%(CNT+1),NUM%(CNT-1) if CNT!=1 else 0]
for i in range(N):
    if X[i]=="0":
        cnt=CNT+1
        r=(R[0]+pow(2,N-i-1,cnt))%cnt
    else:
        cnt=CNT-1
        if NUM-pow(2,N-i-1)==0:
            print(0)
            continue
        r=(R[1]-pow(2,N-i-1,cnt))%cnt
    
    ans=1+to0_cnt[r]
    print(ans)

Solution (Python):
N = int(input())
num = input()
X = int(num,2)
c = num.count('1')
def A(s):
    if s == 0:
        return 1
    return A(s%(bin(s).count('1'))) + 1
if c==1:
  for i in range(N):
    if num[i] == '1':
      print(0)
    elif i == N-1:
      print(2)
    else:
      print(1)
  exit()
amari1 = X%(c+1)
amari2 = X%(c-1)
for i in range(N):
    if num[i] == '1':
        print(A((amari2-pow(2,N-1-i,c-1))%(c-1)))
    else:
        print(A((amari1+pow(2,N-1-i,c+1))%(c+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):
def popcount_int(n):
    return bin(n).count('1')

def popcount_bin(s):
    return s.count('1')

def poptimes(n,cnt=1):
    if n==0:
        return cnt
    else:
        n%=popcount_int(n)
        cnt+=1
        return poptimes(n,cnt)

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

S_int=int(S,2)
pc=popcount_bin(S)
pc_plus=S_int%(pc+1)
if pc!=1:
    pc_minus=S_int%(pc-1)

for i in range(N):
    if S[i]=='1':
        if pc!=1:
            tmp=pc_minus-pow(2,N-i-1,pc-1)
            print(poptimes(tmp%(pc-1)))
        else:
            print(0)
            continue
    else:
        tmp=pc_plus+pow(2,N-i-1,pc+1)
        print(poptimes(tmp%(pc+1)))

Solution (Python):
numBits = int(input())
bitString = input()

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

count1 = bitString.count('1')
x = int(bitString,2)
xPlus = x % (count1 + 1)
if (count1 - 1) == 0:
  xMinus = 0
else:
  xMinus = x % (count1 - 1)

for i in range(numBits)  :
  if bitString[i] == '0':
    print(calculateAndPrintPopcount( (xPlus + pow(2,numBits-1-i,(count1+1))) % (count1+1) ) + 1)
  else:
    if (count1-1) == 0:
      print(0)
    else:
      print(calculateAndPrintPopcount( (xMinus - pow(2,numBits-1-i,(count1-1)) ) % (count1-1) ) +1)

Solution (Python):
N=int(input())
x=input()
num=0
n=0
def twice(a):
    ans=0
    while a:
        ans+=a%2
        a//=2
    return ans

ma=5*10**5
dp=[0]*ma
for i in range(1,ma):
    dp[i]=dp[i%twice(i)]+1
c=x.count("1")
a=int(x,2)%(c+1)
if c==1:
    for i in range(N):
        if x[i]=="0":
            print(dp[(a+pow(2,N-i-1,2))%2]+1)
        else:
            print(0)
    exit()
b=int(x,2)%(c-1)
for i in range(N):
    if x[i]=="0":
        print(dp[(a+pow(2,N-i-1,c+1))%(c+1)]+1)
    else:
        print(dp[(b-pow(2,N-i-1,c-1))%(c-1)]+1)

Solution (Python):
def popcnt_int(n): 
    return bin(n).count('1')

def popcnt_bin(s): 
    return s.count('1')

def poptimes(n, cnt=1): 
    if n==0:
        return cnt
    else:
        n %= popcnt_int(n)
        cnt += 1
        return poptimes(n, cnt)

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


s_int = int(s,2) 
pc = popcnt_bin(s)
pc_plus = s_int % (pc+1) 
if  pc != 1: 
    pc_minus = s_int % (pc-1)



for i in range(n):
    if s[i] == '1': 
        if pc != 1: 
            tmp = pc_minus - pow(2, n-i-1, pc-1) 
            print(poptimes(tmp % (pc-1))) 
        else: 
            print(0)
            continue
    
    else: 
        tmp = pc_plus + pow(2, n-i-1, pc+1)
        print(poptimes(tmp % (pc+1)))

Solution (Python):
def popcnt_int(n): 
    return bin(n).count('1')

def popcnt_bin(s): 
    return s.count('1')

def poptimes(n, cnt=1): 
    if n==0:
        return cnt
    else:
        n %= popcnt_int(n)
        cnt += 1
        return poptimes(n, cnt)

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

s_int = int(s,2)
pc = popcnt_bin(s)
pc_plus = s_int % (pc+1)
if  pc != 1:
    pc_minus = s_int % (pc-1)


for i in range(n):
    if s[i] == '1':
        if pc != 1:
            tmp = pc_minus - pow(2, n-i-1, pc-1)
            print(poptimes(tmp % (pc-1)))
        else:
            print(0)
            continue
    
    else:
        tmp = pc_plus + pow(2, n-i-1, pc+1)
        print(poptimes(tmp % (pc+1)))

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

def goes_to_zero(n):
  cnt = 0
  while(n > 0):
    n %= bin(n).count('1')
    cnt += 1
  return cnt
  
c1 = X.count('1')
xint = int(X,2)
xtp = xint % (c1 + 1)
if (c1 - 1) == 0:  
  xtm = 0
else:
  xtm = xint % (c1 - 1)
  
for i in range(n)  :
  if X[i] == '0':
    print(goes_to_zero( (xtp + pow(2,n-1-i,(c1+1))) % (c1+1) ) + 1)
  else:
    if (c1-1) == 0:
      print(0)
    else:
      print(goes_to_zero( (xtm - pow(2,n-1-i,(c1-1)) ) % (c1-1) ) +1)

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):
def query(x):
    cnt=0
    while(x>0):
        x=x%bin(x).count('1')
        cnt+=1
    return cnt

N=int(input())
X=input()[::-1]
c=X.count('1')

sump,summ=0,0
for i in range(N):
    if X[i]=='1':
        sump=(sump+pow(2,i,c+1))%(c+1)
        if c>1:
            summ=(summ+pow(2,i,c-1))%(c-1)
ans=[]
for i in range(N):
    if X[i]=='0':
        x=(sump+pow(2,i,c+1))%(c+1)
        ans.append(query(x)+1)
    else:
        if c==1:
            ans.append(0)
        else:
            x=(summ-pow(2,i,c-1)+c-1)%(c-1)
            ans.append(query(x)+1)
print(*ans[::-1],sep='\n')

Solution (Python):
def popcount(x):
    if x in memo:
        return memo[x]
    res=0
    while(x>0):
        if x&1:
            res+=1
        x//=2
    memo[x]=res
    return res
memo={}

N=int(input())
X=input()[::-1]
c=X.count('1')
count=[0]*(c+2)
for i in range(c+2):
    x=i
    cnt=0
    while(x>0):
        x=x%popcount(x)
        cnt+=1
    count[i]=cnt

if X[0]=='0':
    summ,sumn,sump=0,0,0
else:
    summ,sumn,sump=1,1,1
bitm,bitn,bitp=[0]*N,[0]*N,[0]*N
bitm[0],bitn[0],bitp[0]=1,1,1
for i in range(1,N):
    if c>1:
        bitm[i]=bitm[i-1]*2%(c-1)
    bitn[i]=bitn[i-1]*2%c
    bitp[i]=bitp[i-1]*2%(c+1)
    if X[i]=='1':
        if c>1:
            summ=(summ+bitm[i])%(c-1)
        sumn=(sumn+bitn[i])%c
        sump=(sump+bitp[i])%(c+1)
ans=[]
for i in range(N):
    if X[i]=='0':
        x=(sump+bitp[i])%(c+1)
        ans.append(count[x]+1)
    else:
        if c==1:
            ans.append(0)
        else:
            x=(summ-bitm[i]+c-1)%(c-1)
            ans.append(count[x]+1)
print(*ans[::-1],sep='\n')

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

    c1 = x.count('1')
    c1p, c1m = c1 + 1, c1 - 1
    sp = sum(pow(2, n - i - 1, c1p) for i, c in enumerate(x) if c == '1')
    sm = None
    if c1m > 0:
        sm = sum(pow(2, n - i - 1, c1m) for i, c in enumerate(x) if c == '1')

    A = [0] * n
    for i in range(n):
        nx = None
        if x[i] == '0':
            nx = (sp + pow(2, n - i - 1, c1p)) % c1p
        else:
            if sm is None:
                continue

            nx = (sm - pow(2, n - i - 1, c1m)) % c1m

        A[i] += 1

        while nx > 0:
            nx %= format(nx, 'b').count('1')
            A[i] += 1

    for a in A:
        print(a)


if __name__ == '__main__':
    main()

Solution (Python):
n = int( input() )
x = input()
x_pop = x.count( "1" )
x_pls = x_pop + 1
x_mns = x_pop - 1


rp = [ pow( 2, i, x_pls ) for i in range( n + 1 ) ]
if x_mns > 0:
    rm = [ pow( 2, i, x_mns ) for i in range( n + 1 ) ]
else:
    rm = [ 0 ] * ( n + 1 )

x = x[ : : -1 ]
rem_p = 0
rem_m = 0
for i in range( n ):
    if x[ i ] == "1":
        rem_p += rp[ i ]
        rem_m += rm[ i ]

for i in range( n - 1, -1, -1 ):
    if x[ i ] == "0":
        tmp = ( rem_p + rp[ i ] ) % x_pls
    elif x_mns > 0:
        tmp = ( rem_m - rm[ i ] ) % x_mns
    else: 
        print( 0 )
        continue
    ans = 1
    while tmp > 0:
        tmp = tmp % bin( tmp ).count( "1" )
        ans += 1
    print( ans )

Solution (Python):
from collections import deque
N = int(input())
X = str(input())
X = list(X)

motokosu = 0
only = float("inf")
for i in range(N):
  if X[i] == "1":
    motokosu += 1
    only = i
if motokosu != 1:
  only = float("inf")

MAX = 2*pow(10,5)+10
base = [0 for _ in range(MAX)] 
for i in range(MAX):
  now = i
  temp = 0
  while now != 0:
    ones = 0
    tnow = now*1
    for t in range(len(bin(now))-2):
      if (now>>t)&1 == 1:
        ones += 1
    
    now = now%ones
    
    base[i] = base[now] + 1
    break
    
  

A = []
pkosu = motokosu+1
mkosu = motokosu-1
P = deque([])
M = deque([])
ptemp = 1; mtemp = 1
for i in range(N):
  P.appendleft(ptemp%pkosu)
  ptemp = ptemp*2%pkosu
  if mkosu < 1:
    M.appendleft(0)
  else:
    M.appendleft(mtemp%mkosu)
    mtemp = mtemp*2%mkosu

pmotosuji = 0; mmotosuji = 0
for i in range(N):
  if X[i] == "1":
    pmotosuji = (pmotosuji+P[i])%pkosu
    if mkosu >= 1:
      mmotosuji = (mmotosuji+M[i])%mkosu


for i in range(N): 
  if only == i:
    print(0)
    continue
  if X[i] == "0": 
    kosu = motokosu + 1
    suji = (pmotosuji + P[i])%kosu
  else: 
    kosu = motokosu - 1
    if kosu == 0:
      suji = -1
    else:
      suji = (mmotosuji - M[i])%kosu
    
  
  
  
  if suji == -1:
    ans = 1
  else:
    nxt = suji%kosu
    ans = 1+base[nxt]
  
  print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain, product
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp



class UnionFindEx:
    def __init__(self, size):
        
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    N = ii()
    X = input()
    X_POP = X.count('1')
    X_POP_P = X_POP + 1
    X_POP_N = X_POP - 1
    FX_P = 0
    FX_N = 0
    for i, b in enumerate(X):
        FX_P <<= 1
        FX_N <<= 1
        if b=='1':
            FX_P += 1
            FX_N += 1
        FX_P %= X_POP_P
        FX_N %= X_POP_N or 1
    
    def popcount(n):
        return bin(n).count('1')
    @lru_cache(None)
    def f(n):
        if n==0:
            return 0
        else:
            return f(n % popcount(n)) + 1
    ans = []
    for i, b in enumerate(reversed(X)):
        if b=='0':
            fx = f((FX_P + pow(2, i, X_POP_P)) % X_POP_P)+1
        else:
            if X_POP_N==0:
                fx = 0
            else:
                fx = f((FX_N - pow(2, i, X_POP_N)) % X_POP_N)+1
        ans.append(fx)
    print(*reversed(ans))



main()

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain, product
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp



class UnionFindEx:
    def __init__(self, size):
        
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    N = ii()
    X = input()
    X_POP = X.count('1')
    X_POP_P = X_POP + 1
    X_POP_N = X_POP - 1
    FX_P = 0
    FX_N = 0
    for i, b in enumerate(X):
        FX_P <<= 1
        FX_N <<= 1
        if b=='1':
            FX_P += 1
            FX_N += 1
        FX_P %= X_POP_P
        FX_N %= X_POP_N or 1
    
    def popcount(n):
        return bin(n).count('1')
    def f(n):
        if n==0:
            return 0
        else:
            return f(n % popcount(n)) + 1
    ans = []
    for i, b in enumerate(reversed(X)):
        if b=='0':
            fx = f((FX_P + pow(2, i, X_POP_P)) % X_POP_P)+1
        else:
            if X_POP_N==0:
                fx = 0
            else:
                fx = f((FX_N - pow(2, i, X_POP_N)) % X_POP_N)+1
        ans.append(fx)
    print(*reversed(ans))



main()

Solution (Python):
it = lambda: list(map(int, input().strip().split()))


def count(num):
    cnt = 0
    while num > 0:
        if num & 1:
            cnt += 1
        num = num >> 1
    return cnt

def find(num):
    ans = 0
    while num > 0:
        ans += 1
        cnt = count(num)
        num = num % cnt
    return ans

def create(N, cnt):
    cur = 1
    two = [0] * N
    for i in range(N):
        two[i] = cur % cnt
        cur = (cur << 1) % cnt
    return two

def getRem(N, A, cnt, two):
    rem = 0
    for i in range(N):
        if A[i] == '1':
            rem = (rem + two[N - i - 1]) % cnt
    return rem

def solve():
    N = int(input())
    A = list(input().strip())

    popcount = 0
    for i in range(N):
        if A[i] == '1':
            popcount += 1
    
    more = popcount + 1
    less = popcount - 1

    if less != 0:
        less_two = create(N, less)
        rem_less = getRem(N, A, less, less_two)
    more_two = create(N, more)
    rem_more = getRem(N, A, more, more_two)
    
    nums = []
    for i in range(N):
        if A[i] == '1':
            if less == 0:
                nums.append(-1)
            else:
                nums.append((rem_less - less_two[N - i - 1]) % less)
        else:
            nums.append((rem_more + more_two[N - i - 1]) % more)
    

    for num in nums:
        if num == -1:
            print(0)
        else:
            print(find(num) + 1)


solve()

Solution (Python):
from sys import stdin,stdout                           
import math                                            
import heapq                                           
                                                       
t = 1                                                  
def aint():                                            
	return int(input().strip())                        
def lint():                                            
	return list(map(int,input().split()))              
def fint():                                            
	return list(map(int,stdin.readline().split()))     
                                                       

def f(n):
	if n==0:
		return 0

	N=n
	cnt=0
	while(N):
		cnt+=N&1
		N>>=1
	return f(n%cnt)+1

def main():
	n=aint()
	x=input()
	c=x.count("1")
	if(c==0):
		for i in range(n):
			print("1")
		return
	elif(c==1):
		for i in range(n):
			if(x[i]=="1"):
				print(0)
			elif x[i]=="0":
				if x[n-1]=="1"or i==(n-1):
					print("2")
				else:
					print(1)
		return
	mod1=c+1
	mod2=c-1
	mul1=1
	mul2=1
	rem1=0
	rem2=0
	for i in range(n-1,-1,-1):
		if(x[i]=='1'):
			rem1=(rem1+mul1)%mod1
			rem2=(rem2+mul2)%mod2
		mul1=(2*mul1)%mod1
		mul2=(2*mul2)%mod2
	ans=[]
	mul1=1
	mul2=1


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

			ans.append(f((rem1+mul1)%mod1)+1)
		else:

			ans.append(f((rem2-mul2)%mod2)+1)
		mul1=(2*mul1)%mod1
		mul2=(2*mul2)%mod2

	for i in range(n-1,-1,-1):
		print(ans[i])
	return




for i in range(t):                                     
	
	main()

Solution (Python):
def main():
    n=int(input())
    X=input().strip()
    cnt_1=X.count('1')
    k1,k2=int(X,2)%(cnt_1-1) if cnt_1!=1 else 0,int(X,2)%(cnt_1+1)
    for i,x in enumerate(X):
        ans=0
        if x=='0':
            k=k2+pow(2,n-i-1,cnt_1+1)
            k%=cnt_1+1
            ans+=1
            while k:
                num=bin(k).count('1')
                k%=num
                ans+=1
        elif x=='1' and cnt_1!=1:
            k=k1-pow(2,n-i-1,cnt_1-1)
            k%=cnt_1-1
            ans+=1
            while k:
                num=bin(k).count('1')
                k%=num
                ans+=1
        else:
            ans=0
        print(ans)
    
if __name__=='__main__':
    main()

Solution (Python):
def main():
    N = int(input())
    X = input()
    t = X.count("1")
    x1, x2 = int(X, 2) % (t-1) if t != 1 else 0, int(X, 2) % (t+1)
    for i in range(N):
        ans = 0
        if X[i] == "0":
            
            x = x2 + pow(2, N-i-1, t+1)
            x %= t+1
            ans += 1
            while x > 0:
                b = "{:0b}".format(x).count("1")
                x %= b
                ans += 1
        elif X[i] == "1" and t != 1:
            
            x = x1 - pow(2, N-i-1, t-1)
            x %= t-1
            ans += 1
            while x > 0:
                b = "{:0b}".format(x).count("1")
                x %= b
                ans += 1
        else:
            
            ans = 0
        print(ans)


if __name__ == '__main__':
    main()

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

cnt = [0]*(200001)
for i in range(1,200001):
    pc = bin(i).count('1')
    cnt[i] = cnt[i%pc] + 1
    
plus = X.count("1")+1
minus = X.count("1")-1

defp = int(X, 2)%plus
if minus:
    defm = int(X, 2)%minus
else:
    defm = None

pl = 1
mi = 1
ans = []
for i, x in enumerate(X[::-1]):
    if x == "0":
        ans.append(cnt[(defp+pl)%plus]+1)
    else:
        if minus:
            ans.append(cnt[(defm-mi)%minus]+1)
        else:
            ans.append(0)
    pl = 2*pl%plus
    if minus:
        mi = 2*mi%minus

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

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


N = int(input())
X = input()
Xo = int(X, 2)

count = 0
ans = 0
ori = pc(Xo)
X = list(X)

Xp = Xo%(ori + 1)
if ori == 1:
    Xm = 0
else:
    Xm = Xo % (ori - 1)


for i in range(N):
    if ori == 1 and X[i] == '1':
        print(0)
        continue
    else:
        if X[i] == '1':
            
            ans = Xm - pow(2, N-1-i, ori - 1)
            ans %= ori - 1
        else:
            
            ans = Xp + pow(2, N-1-i, ori + 1)
            ans %= ori + 1
    count = 1
    while ans > 0:
        
        
        
        ans %= pc(ans)
        count += 1

   
    print(count)
    count = 1

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

cnt_x = x.count("1")
px10 = 0
nx10 = 0
ans = [0] * (N+1)

for i in range(1, N+1): 
    popcnt = format(i,"b").count("1")
    fx = i % popcnt
    ans[i] = ans[fx] + 1

for i in range(N):
    px10 += (int(x[i]) * pow(2,N-1-i, cnt_x+1)) % (cnt_x+1)
    if cnt_x != 0 and cnt_x != 1:
        nx10 += int(x[i])*pow(2,N-1-i,cnt_x-1) % (cnt_x-1)


for i in range(N):
    if x[i] == "0":
        xi10 = (px10+pow(2,N-1-i,cnt_x+1))%(cnt_x+1)
        print(ans[xi10]+1)
    else:
        if cnt_x != 1:
            xi10 = (nx10-pow(2,N-1-i,cnt_x-1))%(cnt_x-1)
            print(ans[xi10]+1)
        else:
            print(0)

Solution (Python):
def f(n):
  ans=1
  while n!=0:
    ans+=1
    n%=bin(n).count("1")
  return ans
n=int(input())
x=input()
o=x.count("1")
if o==0:exit(print(*[1]*n))
if o==1:
  if x[-1]=="1":
    ans=[2]*n
    ans[-1]=0
  else:
    ans=[1]*n
    ans[-1]=2
    ans[x.index("1")]=0
  exit(print(*ans))
mo=0
mz=0
for i in range(n):
  if x[n-i-1]=="1":
    mo=(pow(2,i,o+1)+mo)%(o+1)
    mz=(pow(2,i,o-1)+mz)%(o-1)
for i in range(n):
  if x[i]=="1":
    m=(mz-pow(2,n-i-1,o-1))%(o-1)
  else:
    m=(mo+pow(2,n-i-1,o+1))%(o+1)
  print(f(m))

Solution (Python):
n=int(input())
x=input()
count_x=x.count("1")
px10=0
nx10=0
xi=[0]*n
ans=[0]*(n+1)
for i in range(1,n+1):
    popcount=format(i,"b").count("1")
    fx=i%popcount
    ans[i]=ans[fx]+1
for i in range(n):
    px10+=(int(x[i])*pow(2,n-1-i,count_x+1))%(count_x+1)
    if count_x!=0 and count_x!=1:
        nx10+=int(x[i])*pow(2,n-1-i,count_x-1)%(count_x-1)
for i in range(n):
    if x[i]=="0":
        xi10=(px10+pow(2,n-1-i,count_x+1))%(count_x+1)
        print(ans[xi10]+1)
    else:
        if count_x!=1:
            xi10=(nx10-pow(2,n-1-i,count_x-1))%(count_x-1)
            print(ans[xi10]+1)
        else:
            print(0)

Solution (Python):
def main():
    N = int(input())
    X = input()
    
    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

    ans = []
   
    f = [0] * N
    
    for i in range(1, N):
        pc = popcount(i)
        j =  i % pc
        f[i] = f[j] + 1
    
    
    X_COUNT = X.count("1")
    X = tuple(map(int, tuple(X)))
    rem_plus = [0] * N
    rem_minus = [0] * N
    two_factor = 1
    for i in range(N):
        rem_plus[i] = two_factor
        two_factor *= 2
        two_factor %= (X_COUNT+1)

    if X_COUNT > 1:
        two_factor = 1
        for i in range(N):
            rem_minus[i] = two_factor
            two_factor *= 2
            two_factor %= (X_COUNT-1)


    X_rem_plus = 0
    X_rem_minus = 0
    two_factor = 1
    for c in X[::-1]:
        X_rem_plus += two_factor*c
        X_rem_plus %= (X_COUNT+1)
        two_factor *= 2
        two_factor %= (X_COUNT+1)
    
    if X_COUNT > 1:
        two_factor = 1
        for c in X[::-1]:
            X_rem_minus += two_factor*c
            X_rem_minus %= (X_COUNT-1)
            two_factor *= 2
            two_factor %= (X_COUNT-1)
    
    for i, c in enumerate(X):
        if c:
            if X_COUNT > 1:
                rem = X_rem_minus - rem_minus[N-1-i]
                rem %= (X_COUNT-1)
                ans.append(f[rem]+1)
            elif X_COUNT == 1:
                ans.append(0)
            else:
                ans.append(0)
        else:
            rem = X_rem_plus + rem_plus[N-1-i]
            rem %= (X_COUNT+1)
            ans.append(f[rem]+1)
   
    print(*ans, sep="\n")

if __name__ == "__main__":
    main()

Solution (Python):

def popcount(X):
  pc = 0
  while X>0:
    pc += X%2
    X = X//2
  return pc

N = int(input())
B = input()
X = int(B, 2)

pcx = popcount(X)
pc0to1 = pcx + 1
pc1to0 = pcx - 1
if pc0to1 > 0:
  r0to1 = X%pc0to1
  r20to1 = [1]
  for i in range(1,N):
    r20to1.append((r20to1[-1]*2)%pc0to1)
if pc1to0 > 0:
  r1to0 = X%pc1to0
  r21to0 = [1]
  for i in range(1,N):
    r21to0.append((r21to0[-1]*2)%pc1to0)

for i in range(N):
  b = B[i]
  if b == "0":
    pc = pc0to1
  else:
    pc = pc1to0
  if pc == 0:
    print(0)
    continue

  if b == "0":
    x = r0to1 + r20to1[-(i+1)]
  else:
    x = r1to0 - r21to0[-(i+1)]
  x = x%pc

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