Problem:
 Score : 400 points    Problem Statement Let \mathrm{popcount}(n) be the number of 1 s in the binary representation of n .
For example, \mathrm{popcount}(3) = 2 , \mathrm{popcount}(7) = 3 , and \mathrm{popcount}(0) = 0 .  Let f(n) be the number of times the following operation will be done when we repeat it until n becomes 0 : "replace n with the remainder when n is divided by \mathrm{popcount}(n) ." (It can be proved that, under the constraints of this problem, n always becomes 0 after a finite number of operations.)  For example, when n=7 , it becomes 0 after two operations, as follows:   \mathrm{popcount}(7)=3 , so we divide 7 by 3 and replace it with the remainder, 1 .  \mathrm{popcount}(1)=1 , so we divide 1 by 1 and replace it with the remainder, 0 .   You are given an integer X with N digits in binary.
For each integer i such that 1 \leq i \leq N , let X_i be what X becomes when the i -th bit from the top is inverted.
Find f(X_1), f(X_2), \ldots, f(X_N) .      Constraints  1 \leq N \leq 2 \times 10^5  X is an integer with N digits in binary, possibly with leading zeros.         Input Input is given from Standard Input in the following format:  N  X       Output Print N lines. The i -th line should contain the value f(X_i) .        Sample Input 1 3
011      Sample Output 1 2
1
1   X_1 = 7 , which will change as follows: 7 \rightarrow 1 \rightarrow 0 . Thus, f(7) = 2 .  X_2 = 1 , which will change as follows: 1 \rightarrow 0 . Thus, f(1) = 1 .  X_3 = 2 , which will change as follows: 2 \rightarrow 0 . Thus, f(2) = 1 .        Sample Input 2 23
00110111001011011001110      Sample Output 2 2
1
2
2
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
3

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

dp = [0] * (n+1)

for i in range(1,n+1):
    tmp = bin(i).count("1")
    dp[i] = dp[i%tmp] + 1

t = x.count('1')
po = []

for i in range(n):
    t1 = t
    if x[i] == '1':
        t1 -= 1
    else:
        t1 += 1
    po.append(t1)

t21 = 0
t22 = 0

for i in range(n):
    if x[i] == '1':
        if t > 1:
            t21 += pow(2, (n-i-1), t-1)
            t22 += pow(2, (n-i-1), t+1)
            t21 %= t-1
            t22 %= t+1
        else:
            t22 += pow(2, (n-i-1), t+1)
            t22 %= t+1

for i in range(n):
    if x[i] == '1':
        t3 = t21
    else:
        t3 = t22
    if po[i] == 0:
        print(0)
    else:
        if x[i] == '1':

            t3 -= pow(2, (n-i-1), po[i])
        else:
            t3 += pow(2,(n-i-1), po[i])
        print(dp[t3%po[i]]+1)

Solution (Python):
"""
NTC here
"""



import os
import sys
from io import BytesIO, IOBase

profile = 0
pypy = 1


def iin(): return int(input())


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



def main():
    T = 1
    while T:
        T -= 1
        n = iin()
        a = list(map(int, list(input())))
        ans = []
        def calc(a, md):
            ch = len(a)-1
            rm = 0
            for i in a:
                if i:
                    rm = (rm+ pow(2, ch, md))%md
                ch -= 1
            return rm%md
        
        def bin_calc(a):
            ans = []
            while a:
                ans.append(a&1)
                a >>= 1
            return ans[::-1]
        sm = sum(a)
        dc = {}
        if sm:
            dc[sm] = calc(a, sm)
        if sm-1>0:
            dc[sm-1] = calc(a, sm-1)
        dc[sm+1] = calc(a, sm+1)
        
        for i in range(n):
            sol = 0
            s1 = sm - a[i]
            a[i] = + (not a[i])
            s1 += a[i]
            if s1:
                r1 = dc[s1]
                if a[i]:
                    r1 = (r1 + pow(2, n-i-1, s1))%s1
                else:
                    r1 = (r1 - pow(2, n-i-1, s1))%s1
                sol += 1
                a1 = bin_calc(r1)
                s1 = sum(a1)
                while s1:
                    
                    
                    sol += 1
                    rm = calc(a1, s1)
                    
                    if rm:
                        a1 = bin_calc(rm)
                        s1 = sum(a1)
                    else:
                        break
            a[i] = + (not a[i])
            ans.append(sol)
        print(*ans, sep='\n')





    
        










    




                

        

 
 
 
 
 
 

 
BUFSIZE = 8192
 
 
class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 
if pypy:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
    input = lambda: sys.stdin.readline().rstrip("\r\n")
 

 
if __name__ == "__main__":
    if profile:
        import cProfile
        cProfile.run('main()')
    else:
        main()

Solution (Python):

N = int(input())
X_str = input()

X = int(X_str, 2)

popcount_cache = [0, 1] + [-1] * 3 * 10 ** 5
for x in range(2, 200000+2):
  popcount_cache[x] =  popcount_cache[x // 2] + x % 2












count_cache = [0, 1] + [-1] * 3 * 10 ** 5
for x in range(2, 200000+2):
  count_cache[x] = 1 + count_cache[x % popcount_cache[x]]









  
popcount_N = 0
for s in X_str:
  if s == '1':
    popcount_N += 1

def safemod(x, n):
  if n <= 0:
    return 0
  return x % n

Xmodpp = safemod(X, (popcount_N + 1))
Xmodpn = safemod(X, (popcount_N - 1))

ans = []
for i in range(N):
  if i == 0:
    modpp = 1
    modpn = 1
  else:
    modpp = safemod((modpp * 2) , (popcount_N+1))
    modpn = safemod((modpn * 2) , (popcount_N-1))
  if X_str[N - 1 - i] == '0':
    ans.append(count_cache[  safemod((Xmodpp + modpp), (popcount_N + 1))] + 1)
  else:
    if popcount_N == 1:
      ans.append(0)
    else:
      ans.append(count_cache[  safemod((Xmodpn - modpn), (popcount_N - 1))] + 1)

ans.reverse()
for a in ans:
  print(a)

Solution (Python):
N = int(input())
X = input()
tmp = bin(int(X, 2)).count("1")
big = int(X, 2) % (tmp + 1)
small = int(X, 2) % (tmp - 1) if tmp - 1 else 0

for i in range(N):
    ans = 0
    if X[i] == '1':
        if not tmp - 1:
            print(ans)
            continue

        c = small - pow(2, (N - i - 1), tmp - 1)
        c = c % (tmp - 1)
    else:
        c = big + pow(2, (N - i - 1), tmp + 1)
        c = c % (tmp + 1)
    ans += 1
    while c:
        MOD = bin(int(c)).count("1")
        c %= MOD
        ans += 1
    print(ans)

Solution (Python):
import math

import time
def steps(n,p):
  c = 0
  while n:
    c += 1
    n = n%p
    p = bin(n).count('1')
  return c



n = int(input())
x = input()
p = x.count('1')
ans = []
num = int(x,2)
if p==1:
  for i in range(n-1,-1,-1):
    if x[i]=='1':
      ans.append(0)
    else:
      if i==n-1 or x[n-1]=='1':
        ans.append(2)
      else:
        ans.append(1)
else:
  incs = 1
  decs = 1
  inc = num%(p+1)
  dec = num%(p-1)
  start = time.time()
  k = -1
  for i in range(n-1,-1,-1):
    cp = p
    if x[i] == '0':
      cp += 1
      new = (inc+incs)%cp
    else:
      cp -= 1
      new = (dec-decs)%cp
    k -= 1
    incs = (incs*2)%(p+1)
    decs = (decs*2)%(p-1)
    sol = steps(new,cp)
    if sol==0:
      sol=1
    ans.append(sol)
    
  
ans = ans[::-1]
for x in ans:
  print(x)

Solution (Python):
from sys import stdin
import sys
import itertools
import array
import textwrap
import math

N = int(input())
X = input()
temp = X.count("1")
t = [0, 0, 0]

t[0] = int(X, 2) % (temp-1) if temp != 1 else 0
t[2] = int(X, 2) % (temp+1)
cnt = 0
for i in range(N):
    if X[i] == "1" and temp == 1:
        print(0)
        continue
    if X[i] == "1":
        
        p = pow(2, N-1-i, temp-1)
        a = (t[0]-p) % (temp-1)
    elif X[i] == "0":
        
        m = pow(2, N-1-i, temp+1)
        a = (t[2]+m) % (temp+1)
    cnt = 1
    while a > 0:
        a = a % format(a, 'b').count("1")
        cnt += 1
    print(cnt)

Solution (Python):
N = int(input())
X = input()
temp = X.count("1")
t = [0, 0, 0]

t[0] = int(X, 2) % (temp-1) if temp != 1 else 0
t[2] = int(X, 2) % (temp+1)
cnt = 0
for i in range(N):
    if X[i] == "1" and temp == 1:
        print(0)
        continue
    if X[i] == "1":
        
        p = pow(2, N-1-i, temp-1)
        a = (t[0]-p) % (temp-1)
    elif X[i] == "0":
        
        m = pow(2, N-1-i, temp+1)
        a = (t[2]+m) % (temp+1)
    cnt = 1
    while a > 0:
        a = a % format(a, 'b').count("1")
        cnt += 1
    print(cnt)

Solution (Python):
import numpy as np
from typing import List, Tuple

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


def binary_mod(bits: List[int], div: int) -> int:
    if div == 0:
        return 0

    val = 0
    for b in bits:
        val = (val * 2 + b) % div
    return val


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


popcount = sum(X)
div1 = popcount + 1
div2 = popcount - 1

if popcount == 0:
    print('\n'.join(map(str, [1] * N)))
else:
    rem1 = binary_mod(X, div1)
    rem2 = binary_mod(X, div2)

    for i in range(N):
        if X[i] == 0:
            r = (rem1 + pow(2, N - 1 - i, div1)) % div1
            print(f(r) + 1)
        else:
            if div2 > 0:
                r = (rem2 - pow(2, N - 1 - i, div2) + div2) % div2
                print(f(r) + 1)
            else:
                print(0)

Solution (Python):
def modpow(a, n, p):
  if n == 0:
    return 1
  if n == 1:
    return a % p 
  elif n % 2 == 1:
    return a * modpow(a, n-1, p) % p
  else:
    return modpow(a, n//2, p) **2 % p

l = [-1]*(2*10**5+1)
l[0] = 0
def f(n):
  if l[n] != -1:
    return l[n]
  else:
    b = bin(n)
    k = b.count("1")
    l[n] = f(n%k)+1
    return l[n]

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

k = x.count("1")
x_mod_1 = int(x, 2) % (k+1)
x_mod_0 = int(x, 2) % (k-1) if k > 2 else 0
for i in range(n):
  if x[i] == "0":
    print(f((x_mod_1 + modpow(2, n-1-i, k+1))%(k+1))+1)

  else:
    if k > 2:
      print(f((x_mod_0 - modpow(2, n-1-i, k-1))%(k-1))+1)
    elif k > 1:
      print(1)
    else:
      print(0)

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
from sys import flags
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
x=list(input())
cnt=Counter(x)
x2=int("".join(x),2)
one=cnt["1"]




lst=[0]*(2*10**5+10)

flaglst=[0,0]
if one-1!=0:
    flaglst[0]=x2%(one-1)
flaglst[1]=x2%(one+1)


for i in range(2*10**5):
    now=i+1
    ans=0
    while now:
        cnt2=0
        m=0
        while now>=pow(2,m):
            if now&1<<m:
                cnt2+=1
            m+=1
        now%=cnt2
        ans+=1
    lst[i+1]=ans


for i in range(n):
    tmp=0
    if x[i]=="1":
        tmp=flaglst[0]
        if one-1!=0:
            tmp-=pow(2,n-1-i,one-1)
            tmp%=one-1
        else:
            print(0)
            continue
    else:
        tmp=flaglst[1]
        tmp+=pow(2,n-1-i,one+1)
        tmp%=one+1
    

    print(lst[tmp]+1)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
X = input()

def popcount(n):
    cnt = 0
    while n:
        n %= "{:b}".format(n).count("1")
        cnt += 1
    return cnt

pl = [0]*(N+1)
for i in range(N+1):
    pl[i] = popcount(i)
bn = X.count("1")

modp = [0]*N
modm = [0]*N

for i in range(N):
    if X[i] == "1":
        modp[i] = pow(2, N-1-i, bn+1)
        if not bn == 1:
            modm[i] = pow(2, N-1-i, bn-1)

sp = sum(modp)
sm = sum(modm)
ans = [0]*N
for i in range(N):
    if X[i] == "1":
        if bn == 1:
            ans[i] = 0
            continue
        s = sm
        s -= modm[i]
        s %= bn-1
        ans[i] = pl[s]+1
    else:
        s = sp
        s += pow(2, N-1-i, bn+1)
        s %= bn+1
        ans[i] = pl[s]+1

print(*ans, sep="\n")

Solution (Python):

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

  return cnt

def main():
  n = int(input())
  src = input()
  base = int(src, 2)
  base_cnt = src.count('1')

  basep = base % (base_cnt + 1)
  basem = base % (base_cnt - 1) if base_cnt > 1 else 0

  for i, s in enumerate(src):
    i = n - 1 - i
    num = None

    if s == '0':
      mod = base_cnt + 1
      num = (basep + pow(2, i, mod)) % mod
    elif base_cnt > 1:
      mod = base_cnt - 1
      num = (basem - pow(2, i, mod)) % mod
    else:
      print(0)
      continue

    print(1 + f(num))


main()

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7












N = INT()
X = input()

def popcount(n):
    cnt = 0
    while n:
        n %= "{:b}".format(n).count("1")
        cnt += 1
    return cnt

pl = [0]*(N+1)
for i in range(N+1):
    pl[i] = popcount(i)
bn = X.count("1")

modp = [0]*N
modm = [0]*N

for i in range(N):
    if X[i] == "1":
        modp[i] = pow(2, N-1-i, bn+1)
        if not bn == 1:
            modm[i] = pow(2, N-1-i, bn-1)

sp = sum(modp)
sm = sum(modm)
ans = [0]*N
for i in range(N):
    if X[i] == "1":
        if bn == 1:
            ans[i] = 0
            continue
        s = sm
        s -= modm[i]
        s %= bn-1
        ans[i] = pl[s]+1
    else:
        s = sp
        s += pow(2, N-1-i, bn+1)
        s %= bn+1
        ans[i] = pl[s]+1

print(*ans, sep="\n")

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

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

a=0 
b=0 

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


s=0
t=0
if b>1:
  for i in range(N):
    s=(s+int(X[i])*pow(2, N-1-i, b+1))%(b+1)
    t=(t+int(X[i])*pow(2, N-1-i, b-1))%(b-1)
else:
  for i in range(N):
    s=(s+int(X[i])*pow(2, N-1-i, b+1))%(b+1)
    
"""
(1) X[i]==0の時
Xiは0が(a-1)個、1が(b+1)個となる。ここでXiに対して操作を1度行った後の数tmpは
    tmp={X%(b+1)+2^(N-1-i)%(b+1)}%(b+1)
       ={s+pow(2, N-1, b+1)}%(b+1)
となる。
tmp<(b+1)<Nなので、f(tmp)は冒頭で求めたnums[tmp]が使える。
Xiは1回操作してtmpとなり、nums[tmp]回操作して0になるので、
f(Xi)=1+nums[tmp]
で求められる。

(2) X[i]==1の時
Xiは0が(a+1)個、1が(b-1)個となる。ここでXiに対して操作を1度行った後の数tmpは
    tmp={X%(b-1)+2^(N-1-i)%(b-1)}%(b-1)
       ={t+pow(2, N-1, b-1)}%(b-1)
となる。そのため上記と同様に、
f(Xi)=1+nums[tmp]
で求められる。

ただしb=1の場合には、b-1=0となってしまうため、この場合のみ場合分けする。
具体的にはb=1の場合でX[i]=1の時は、Xi=0なので、問答無用で0を出力する。
"""
if b==1:
  for i in range(N):
    if X[i]=='0':
      tmp=(s+pow(2, N-1-i, b+1))%(b+1)
      print(nums[tmp]+1)
    else:
      print(0)
  exit()

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

Solution (Python):
n = int(input())
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 mp(): return map(int, input().split())
def lmp(): return list(map(int, input().split()))

n = int(input())
x = list(input())
xc = x.count("1")
xu = []
xd = []
if xc == 0:
    for i in range(n):
        print(1)
        exit()

for i in range(n):
    mod = xc+1
    xu.append(pow(2, i, mod))
    
    
    

flag = False
for i in range(n):
    mod = xc-1
    if mod == 0:
        xd.append(0)
        flag = True
    else:
        xd.append(pow(2, i, mod))
        
        
        
xu.reverse()
xd.reverse()
s_xu = 0
s_xd = 0
for i in range(n):
    if x[i] == "1":
        s_xu += xu[i]
        s_xd += xd[i]




for i in range(n):
    cnt = 1
    if x[i] == "0":
        tar = (s_xu+xu[i])%(xc+1)
        
        while tar != 0:
            b_tar = bin(tar)
            tar %= b_tar.count("1")
            cnt += 1
        print(cnt)
    else:
        if flag:
            print(0)
        else:
            tar = (s_xd-xd[i])%(xc-1)
            
            while tar != 0:
                b_tar = bin(tar)
                tar %= b_tar.count("1")
                cnt += 1
            print(cnt)

Solution (Python):
N = int(input())
X = input()
popcount_X = X.count('1')
numX = int(X, 2)
a = numX % (popcount_X + 1)
b = numX % (popcount_X - 1) if popcount_X != 1 else 0
for i, x in enumerate(X, 1): 
    if x == '1' and popcount_X == 1:
        print(0)
        continue
    ans = 1
    if x == '1':
        temp = (b - pow(2, N - i, popcount_X - 1)) % (popcount_X - 1)
    else:
        temp = (a + pow(2, N - i, popcount_X + 1)) % (popcount_X + 1)
    while temp:
        p = format(temp, 'b').count('1') 
        temp %= p
        ans += 1
    print(ans)

Solution (Python):
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def main():
    N = int(readline())
    X = readline().rstrip().decode('utf-8')
    nx = int(X, 2)

    ans = [0] * N

    oc = X.count('1')

    if oc - 1 != 0:
        mx = nx % (oc - 1)
        f = True
    else:
        f = False

    px = nx % (oc + 1)

    for i in range(N):

        if X[i] == '0':
            a = (px + pow(2, N - i - 1, oc + 1)) % (oc + 1)
        elif f:
            a = (mx - pow(2, N - i - 1, oc - 1)) % (oc - 1)
        else:
            ans[i] = 0
            continue

        count = 1
        while a:
            a = a % bin(a).count('1')
            count += 1

        ans[i] = count

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


if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
x=input()
t=int(x,2)
c=x.count('1')
from functools import lru_cache
@lru_cache(None)
def f(x):
  if x==0: return 0
  return f(x%bin(x).count('1'))+1
a=t%-~c
b=0 if c<2 else t%~-c
for i in range(n):
  if int(x[i]):
    d=c-1
    if d<1: print(0)
    else: print(f((b-pow(2,n-i-1,d))%d)+1)
  else:
    d=c+1
    print(f((a+pow(2,n-i-1,d))%d)+1)

Solution (Python):
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def main():
    N = int(readline())
    X = readline().rstrip().decode('utf-8')
    nx = int(X, 2)

    ans = [0] * N

    oc = X.count('1')

    if oc - 1 != 0:
        mx = nx % (oc - 1)
        f = True
    else:
        f = False

    px = nx % (oc + 1)

    for i in range(N):

        if X[i] == '0':
            a = (px + pow(2, N - i - 1, oc + 1)) % (oc + 1)
        elif f:
            a = (mx - pow(2, N - i - 1, oc - 1)) % (oc - 1)
        else:
            ans[i] = 0
            continue

        count = 1
        while a:
            a = a % bin(a).count('1')
            count += 1

        ans[i] = count

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


if __name__ == '__main__':
    main()

Solution (Python):
def popcount(i):
    assert 0 <= i < 0x100000000
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24
memo = [None] * 300000
def do2(x):
    if memo[x] is not None:
        return memo[x]
    cnt = 0
    while x != 0:
        x = x % popcount(x)
        cnt += 1
    memo[x] = cnt
    return cnt

def do():
    ll = int(input())
    s = input()
    n = int(s, 2)

    x = n
    cnt = 0
    ss = bin(x)[2:]
    cnt += 1
    num1 = ss.count("1")
    num1m = num1 - 1
    num1p = num1 + 1
    rs = ss[::-1]
    res1m = 0
    res1p = 0
    for j in range(len(rs)):
        if rs[j] == "1":
            if num1m != 0 and num1m != -1:
                res1m += pow(2, j, num1m)
                res1m %= num1m
            res1p += pow(2, j, num1p)
            res1p %= num1p

    
    for i in range(len(s)):
        
        if s[i] == "1": 
            
            
            if num1m == 0 or num1m == -1:
                print(0)
                continue
            x = res1m - pow(2, ll - i -1, num1m)
            x %= num1m
        elif s[i] == "0": 
            
            
            x = res1p + pow(2, ll - i-1, num1p)
            x %= num1p

        if x == 0:
            print(1)
            continue
        print(do2(x) + 1)
do()

Solution (Python):
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n = int(input())
    x = input()
    k = int(x,2)
    c = x.count('1')
    kp = k%(c+1)
    if c > 1:
        kn = k%(c-1)
    
    for i in range(n):
        cnt = 1
        if x[i] == '1':
            if c == 1:
                print(0)
                continue
            mod = c-1
            tmp = (kn - pow(2,n-i-1,mod))%mod
            while 1:
                if tmp == 0:
                    break
                tmp = tmp%format(tmp, 'b').count('1')
                cnt+=1
        else:
            mod = c+1
            tmp = (kp + pow(2,n-i-1,mod))%mod
            while 1:
                if tmp == 0:
                    break
                tmp = tmp%format(tmp, 'b').count('1')
                cnt+=1
        print(cnt)


if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
x=input()
t=int(x,2)
c=x.count('1')
a=t%-~c
b=0 if c<2 else t%~-c
for i in range(n):
  if int(x[i]):
    if c<2: print(0); continue
    else: t=(b-pow(2,n-i-1,c-1))%~-c
  else: t=(a+pow(2,n-i-1,c+1))%-~c
  z=1
  while t:
    d=bin(t).count('1')
    t%=d
    z+=1
  print(z)

Solution (Python):




import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
n=I()
lis=list(SI())
orig=0
for i in range(n):
    if lis[i]=="0":
        lis[i]=0
    else:
        lis[i]=1
orcount=sum(lis)
m1=0
m3=0
if orcount==1:
    for i in range(n):
        if lis[i]==1:
            m3=(m3+pow(2,n-i-1,orcount+1))
elif orcount>1:
    for i in range(n):
        if lis[i]==1:
            m1=(m1+pow(2,n-i-1,orcount-1))
            m3=(m3+pow(2,n-i-1,orcount+1))
        
        
m1=m1
m3=m3



dp=[0 for i in range(n+1)]
dp[1]=1
for i in range(1,n):
    
    count=0
    j=0
    while pow(2,j)<=i+1:
        if ((i+1)>>j) %2==1:
            count+=1
        j+=1
    z=1
    dp[i+1]=z+dp[(i+1)%count]

for i in range(n):
    if lis[i]==0:
        
        pr=orcount+1
        num=m3+pow(2,n-i-1,pr)
    else:
        
        pr=orcount-1
        if pr!=0:
            num=m1-pow(2,n-i-1,pr)
    
    if pr==0:
        print(0)
    else:
        print(1+dp[num%pr])

Solution (Python):



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

n = int(input())
x = list(input())
xc = x.count("1")
xu = []
xd = []
if xc == 0:
    for i in range(n):
        print(1)
        exit()
t = 1
for i in range(n):
    mod = xc+1
    xu.append(t%mod)
    t *= 2
    t %= mod
t = 1
flag = False
for i in range(n):
    mod = xc-1
    if mod == 0:
        xd.append(0)
        flag = True
    else:
        xd.append(t%mod)
        t *= 2
        t %= mod
xu.reverse()
xd.reverse()
s_xu = 0
s_xd = 0
for i in range(n):
    if x[i] == "1":
        s_xu += xu[i]
        s_xd += xd[i]




for i in range(n):
    cnt = 1
    if x[i] == "0":
        tar = (s_xu+xu[i])%(xc+1)
        
        while tar != 0:
            b_tar = bin(tar)
            tar %= b_tar.count("1")
            cnt += 1
        print(cnt)
    else:
        if flag:
            print(0)
        else:
            tar = (s_xd-xd[i])%(xc-1)
            
            while tar != 0:
                b_tar = bin(tar)
                tar %= b_tar.count("1")
                cnt += 1
            print(cnt)

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

lst = [0 for i in range(n+1)]
for i in range(1, n+1):
    num = i%popcount(i)
    lst[i] = lst[num] + 1

plus = [0 for i in range(n)]
minus = [0 for i in range(n)]
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)
        print(lst[amari] + 1)
    else:
        if cnt != 1:
            amari = (amariminus - minus[n-i-1]) % (cnt-1)
            print(lst[amari] + 1)
        else:
            print(0)

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()
    
    
    
    
    
    @lru_cache(None)
    def r(n):
        if n==0:
            return 0
        bc=0
        for i in range(n.bit_length()):
            if n>>i&1:
                bc+=1
        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()