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())
s=[int(c) for c in input()]

pc=sum(s)

resm=[0]*n
resp=[0]*n

jm=1
jp=1

totm=0
totp=0
for i in range(n):
    if pc-1>0:
        resm[n-i-1]=jm%(pc-1)
        jm=(2*jm)%(pc-1)
        totm+=resm[n-i-1]*s[n-i-1]
        totm%=pc-1
    
    resp[n-i-1]=jp%(pc+1)
    jp=(2*jp)%(pc+1)
    totp+=resp[n-i-1]*s[n-i-1]
    totp%=pc+1

def popc(x):
    return sum([int(c) for c in format(x,'b')])

for i in range(n):
    if s[i]==1:
        pcc=pc-1
        if pcc==0:
            print(0)
            continue
        cres=(totm+pc-1-resm[i])%(pc-1)
    else:
        pcc=pc+1
        cres=(totp+resp[i])%(pc+1)
    
    if cres==0:
        print(1)
        continue

    cnt=1
    while cres>0:
        cres%=popc(cres)
        cnt+=1
    
    print(cnt)

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

xre = x[::-1]

cou = x.count('1')

if cou == 0:
    for _ in range(n):
        print(1)
    exit()

if cou == 1:
    for i in range(n):
        if i == n-1 and x[i] == '0':
            print(2)
        elif  x[i] == '0' and x[n-1] == '1':
            print(2)
        elif  x[i] == '0' and x[n-1] == '0':
            print(1)
        else:
            print(0)
    exit()

basepl = int(x, 2) % (cou+1)
basemi = int(x, 2) % (cou-1)

li = [0]*n
pl = 1
mi = 1


for i in range(n):
    if xre[i] == '0':
        li[i] = (basepl + pl)  % (cou+1)
    else:
        li[i] = (basemi - mi)  % (cou-1)
    mi = (mi * 2) % (cou-1)
    pl = (pl * 2) % (cou+1)

def f(n):
    m = n
    k = 1
    while m > 0:
        co = str(bin(m)).count('1')
        m = m % co
        k +=1
    return k


for x in li[::-1]:
    print(f(x))

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

def pop(x): 
    ret=0
    while x>0:
        ret+=x%2
        x//=2
    return ret

def solve(x): 
    ret=0
    while x>0:
        pop_c=pop(x)
        x%=pop_c
        ret+=1
    return ret

mod=X.count("1") 
original_plus=0
original_minus=0
for i in range(N):
    if X[N-1-i]=="1":
        if mod>1:
            original_minus+=pow(2,i,mod-1)
        original_plus+=pow(2,i,mod+1)
for i in range(N):
    if X[i]=="0":
        tmp=original_plus+pow(2,N-1-i,mod+1)
        tmp%=mod+1
        print(solve(tmp)+1)
    else:
        if mod==1:
            print(0)
            continue
        tmp=original_minus-pow(2,N-1-i,mod-1)
        tmp%=mod-1
        print(solve(tmp)+1)

Solution (Python):
def main():
    N = int(input())
    S = input()
    X = int(S, 2)
    C = S.count('1')
    xc0 = X % (C + 1)
    xc1 = X % (C - 1) if C > 1 else 0
 
    def f(x):
        c = 0
        while x:
            c += 1
            x = x % bin(x).count('1')
        return c
 
    for i, s in enumerate(S):
        k = N - 1 - i
        if s == '0':
            print(f((xc0 + pow(2, k, C + 1)) % (C + 1)) + 1)
        else:
            if C > 1:
                print(f((xc1 - pow(2, k, C - 1)) % (C - 1)) + 1)
            else:
                print(0)
 
 
main()

Solution (Python):
import sys

input = sys.stdin.readline

n = int(input())
y = str(input())


ones = 0
for i in y:
    if i == '1': ones += 1
x = int(y, 2)

def get(z):
    ret = 0
    while z > 0:
        if z % 2 == 1:
            ret += 1
        z //= 2
    return ret

out = []
rem1 = -1
rem2 = -1
if ones > 1:
    rem1 = x % (ones - 1)
if ones < n:
    rem2 = x % (ones + 1)

def calc(p, m):
    if p <= 2:
        return (1 << p) % m
    a = p // 2
    ret = calc(a, m)
    ret = (ret * ret) % m
    if p % 2 == 1:
        ret = (ret * 2) % m
    return ret



for i in range(n):
    
    o = ones - 1
    if y[n - i - 1] == '0':
        
        o = ones + 1

    
    if o == 0:
        out.append(0)
        continue
    if o == 1:
        out.append(1)
        continue


    if o > ones:
        tmp = (rem2 % o + calc(i, o)) % o
    else:
        tmp = (rem1 % o - calc(i, o) + o) % o


    cnt = 1
    while tmp > 0:
        tmp %= get(tmp)
        cnt += 1

    out.append(cnt)

for i in range(n):
    print(out[n-i-1])

Solution (Python):
import sys, math
import io, os



from collections import defaultdict as dd, deque, Counter

def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var) : sys.stdout.write('\n'.join(map(str, var))+'\n')
def out(var) : sys.stdout.write(str(var)+'\n')




mod = int(1e9)+7

n=int(data())
x=data()
c=x.count('1')
t1,t2=1,1
k1=0
k2=0
for i in range(n-1,-1,-1):
    if x[i]=='1':
        k1=(k1+t1)%(c+1)
        if c==1:
            continue
        k2=(k2+t2)%(c-1)
    t1=(t1*2)%(c+1)
    if c != 1:
        t2=(t2*2)%(c-1)
ans=[]
t1,t2=1,1
for i in range(n-1,-1,-1):
    if x[i]=='1':
        if c==1:
            ans.append(0)
            continue
        k=(k2-t2+c-1)%(c-1)
    else:
        k=(k1+t1)%(c+1)
    cnt=1
    while k:
        k=k%(bin(k)[2:].count('1'))
        cnt+=1
    ans.append(cnt)
    t1 = (t1 * 2) % (c + 1)
    if c!=1:
        t2 = (t2 * 2) % (c - 1)
outl(ans[::-1])

Solution (Python):
'''Author- Akshit Monga'''
n=int(input())
x=input()
x=x[::-1]
ans1=0
ans2=0
c=x.count('1')
for i in range(0,n):
    if x[i]=='1':
        ans1=(ans1+pow(2,i,c+1))%(c+1)
        if c!=1:
            ans2=(ans2+pow(2,i,c-1))%(c-1)
to_print=[]
for i in range(0,n):
    if x[i]=='1':
        if c==1:
            to_print.append(0)
            continue
        var=(ans2%(c-1)-pow(2,i,c-1))%(c-1)
        a = 1
        while var:
            var = var % bin(var).count('1')
            a += 1
        to_print.append(a)
    else:
        
        var = (ans1%(c+1) + pow(2, i, c +1))%(c+1)
        
        
        a = 1
        while var:
            var = var % bin(var).count('1')
            a += 1
        to_print.append(a)
for i in to_print[::-1]:
    print(i)

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()

n= int(input())
a=list(input())

v=a.count('1')

ans=[0]*n
A=[0]*n

for i in range(n):
    x=i
    cnt=0
    while x>0:
        cnt+=1
        r = 0
        for j in range(19):
            if (x>>j)&1:
                r+=1
            if x>>j==0:
                break
        x=x%r
    ans[i]=cnt


q = [0]*n

r = [0]*n
for i in range(n):
    if a[i]=='1':
        if v!=0:
            q[i] = pow(2, n-i-1,v+1) 
        if v!=1:
            r[i] += pow(2, n-i-1,v-1) 
qq=sum(q)
rr=sum(r)

for i in range(n):
    if a[i]=='1':
        if v!=1:
            z = rr - pow(2,n-i-1,v-1)
            cnt = z % (v - 1)
            A[i] = 1 + ans[cnt]
    else:
        z=qq+pow(2,n-i-1,v+1)
        cnt=z%(v+1)
        A[i]=1+ans[cnt]

for i in A:
    print(i)

Solution (Python):
N = int(input())
X = input().strip()
C = X.count("1")
D = int(X, 2)
Mm, Mp = 0, D % (C+1)
if C > 1:
    Mm = D % (C-1)

p = [0]*(2*10**5+2)
for i in range(1, len(p)):
    n = i
    while True:
        b = bin(n).count("1")
        if b <= 0:
            break
        p[i] += 1
        n = n % b

for i in range(1, N+1):
    c = C
    if X[i-1] == "1":
        c -= 1
        if c == 0:
            print(0)
            continue
        m = Mm
        d = pow(2, N-i, c)
        d = (m-d+c) % c
    else:
        c += 1
        m = Mp
        d = pow(2, N-i, c)
        d = (m+d) % c

    print(p[d]+1)

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

dp = [0] * n

for i in range(n):
    num = i
    while num:
        num2 = num
        cnt = 0
        while num2:
            if num2 & 1:
                cnt += 1
            num2 >>= 1

        num %= cnt
        dp[i] += 1

one_cnt = x.count(1)
mod1 = one_cnt - 1
mod2 = one_cnt + 1

sm1 = 0
sm2 = 0
for i, e in enumerate(x):
    if e == 0:
        continue

    if mod1 != 0:
        sm1 += pow(2, n - i - 1, mod1)
        sm1 %= mod1

    sm2 += pow(2, n - i - 1, mod2)
    sm2 %= mod2

for i, e in enumerate(x):
    if mod1 == 0 and e:
        print(0)
        continue

    if e:
        val = sm1 - pow(2, n - i - 1, mod1)
        val %= mod1

    else:
        val = sm2 + pow(2, n - i - 1, mod2)
        val %= mod2

    ans = dp[val] + 1
    print(ans)

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

memo = [0]*n
ans = [-1]*n
popcnt = 0

for i in range(n):
    if x[i] == "1":
        popcnt += 1

amariStaticA = 0
amariStaticB = 0
aaa = -1
if popcnt == 1:
    for i in range(n):
        if x[i] == "1":
            ans[i] = 0
            aaa = i
            amariStaticB += pow(2, n-i-1, popcnt+1)
    amariStaticB %= popcnt+1
else:
    for i in range(n):
        if x[i] == "1":
            amariStaticA += pow(2, n-i-1, max(1, popcnt-1))
            amariStaticB += pow(2, n-i-1, popcnt+1)
    amariStaticA %= max(1, popcnt-1)
    amariStaticB %= popcnt+1

for i in range(n):
    if popcnt == 1 and i == aaa:
        continue
    if x[i] == "0":
        amari = amariStaticB + pow(2, n-i-1, popcnt+1)
        amari %= popcnt+1
    else:
        amari = amariStaticA - pow(2, n-i-1, max(1, popcnt-1))
        amari %= max(1, popcnt-1)
    if amari == 0:
        ans[i] = 1
    else:
        memo[i] = amari

for i in range(len(memo)):
    cnt = 1
    firstMemo = copy.deepcopy(memo[i])
    while memo[i] != 0:
        popcnt = bin(memo[i]).count("1")
        memo[i] %= max(1, popcnt)
        cnt += 1
        if memo[i] == 0:
            ans[i] = cnt
            break


for anss in ans:
    print(anss)

Solution (Python):
import collections
N=int(input())
X=list(input())
X=list(map(int,X))

ans1=0
ans2=0
c=collections.Counter(X)
div=c[1]
for i in range(N):
    ans1=(ans1+X[i]*pow(2,N-i-1,div+1))%(div+1)
    if div-1!=0:
        ans2=(ans2+X[i]*pow(2,N-i-1,div-1))%(div-1)
    else:
        ans2=None
    



for i in range(N):
    cnt = 1
    if (X[i]==0):
        num=(ans1+pow(2,N-i-1,div+1))%(div+1)
        
    else:
        if (div-1)!=0:
            num=(ans2+div-1-pow(2,N-i-1,div-1))%(div-1)
        else:
            cnt=0
            num=0
        
    while num != 0:
        di = 0
        for j in range(18):
            if (num >> j)&1 == 1:
                di = di + 1
        num = num % di
        cnt = cnt + 1
    print(cnt)

Solution (Python):
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n = int(readline())
lst1 = list(readline().rstrip().decode('utf-8'))


res = lst1.copy()
res = "".join(res)
ct = res.count("1")
res = int(res,2)
if ct == 0:
    for i in range(n):
        print(1)
    exit()
if ct == 1:
    amari_of_m = -1
else:
    amari_of_m = res%(ct-1)
amari_of_p = res%(ct+1)

def pow(n,p,mod): 
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod

def func(res):
    ans = 1
    while True:
        ct = 0
        for i in range(len(bin(res))):
            if res>>i&1:
                ct += 1
        if res%ct == 0:
            print(ans+1)
            return
        else:
            res %= ct
            ans += 1

for i in range(n):
    if lst1[i] == "1" and amari_of_m == -1:
        print(0)
        continue
    else:
        resres = pow(2,n-i-1,ct-1) if lst1[i] == "1" else pow(2,n-i-1,ct+1)
    if lst1[i] == "1":
        resres = amari_of_m - resres
        resres %= ct-1
    else:
        resres = amari_of_p + resres
        resres %= ct+1
    if not resres:
        print(1)
    else:
        func(resres)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
x = input()
b = []
c = [0, 1, 1]
for i in range(n+2):
    cnt = 0
    for j in range(101):
        if i >> j & 1:
            cnt += 1
    b.append(cnt)

for i in range(3, n+2):
    c.append(c[i % b[i]]+1)

ans = []
tmp1 = 0
tmp2 = 0
cnt = x.count("1")
if cnt != 1:
    for i in range(n):
        if x[i] == "1":
            tmp1 += pow(2, n-(i+1), cnt+1)
            tmp2 += pow(2, n-(i+1), cnt-1)
    for i in range(n):
        if x[i] == "1":
            ans.append(c[(tmp2 - pow(2, n-(i+1), cnt-1)) % (cnt-1)]+1)
        else:
            ans.append(c[(tmp1 + pow(2, n-(i+1), cnt+1)) % (cnt+1)]+1)

    for i in ans:
        print(i)
else:
    for i in range(n):
        if x[i] == "1":
            tmp1 += pow(2, n-(i+1), cnt+1)
    for i in range(n):
        if x[i] == "1":
            ans.append(0)
        else:
            ans.append(c[(tmp1 + pow(2, n-(i+1), cnt+1)) % (cnt+1)]+1)

    for i in ans:
        print(i)

Solution (Python):
N = int(input())
X = input()
times = {}
times[0] = 0

for i in range(1,200000):
  bi = format(i, 'b')
  arr = list(map(int, bi))
  sbi = sum(arr)
  if i%sbi == 0:
    times[i] = 1
  else:
    times[i] = 1+times[i%sbi]
    
arr = list(map(int, X))
sbX = sum(arr)
X10 = int(X,2)
mo = [1,-1]
if sbX-1 == 0:
  mo2 = [X10%(sbX+1),X10]
else:
  mo2 = [X10%(sbX+1),X10%(sbX-1)]

for i in range(N):
  waru = sbX+mo[int(X[i])]
  if waru == 0:
    print(0)
  else:
    print(times[(mo[int(X[i])]*pow(2,(N-i-1),waru)+mo2[int(X[i])])%waru]+1)

Solution (Python):





import math
import fractions
import sys
import bisect
import heapq  
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr



def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod



def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors


inf = 10 ** 18
mod = 10 ** 9 + 7

n = ir()
x = list(sr())
sum1 = 0
for c in x:
    if c == '1':
        sum1+=1
tmpp = 0
tmpm = 0
for c in x:
    tmpp = tmpp*2
    tmpm = tmpm*2
    if c == '1':
        tmpp+=1
        tmpm+=1
    tmpp%=(sum1+1)
    if sum1 != 1:
        tmpm%=(sum1-1)
    else:
        tmpm = 0
dpp = [0 for i in range(n)]
dpm = [0 for i in range(n)]
mmp = 1
mmm = 0
if sum1 != 1:
    mmm = 1
for i in range(n):
    dpp[n-1-i] = mmp
    dpm[n-1-i] = mmm
    mmp = (mmp*2)%(sum1+1)
    if sum1 != 1:
        mmm = (mmm*2)%(sum1-1)
    else:
        mmm = 0
ansdp = [0 for i in range(n)]
ans = [0 for i in range(n)]

for i,c in enumerate(x):
    if c == '1':
        if sum1 != 1:
            ansdp[i] = (tmpm-dpm[i])%(sum1-1)
            ans[i]+=1
    else:
        ansdp[i] = (tmpp+dpp[i])%(sum1+1)
        ans[i]+=1
while 1:
    end = True
    for c in ansdp:
        if c != 0:
            end = False
    if not end:
        for i in range(n):
            if ansdp[i] != 0:
                tmp = bin(ansdp[i])
                sum11 = 0
                for c in tmp:
                    if c == '1':
                        sum11+=1
                ansdp[i] = ansdp[i]%sum11
                ans[i]+=1
    else:
        for num in ans:
            print(num)
        sys.exit()

Solution (Python):

n = int(input())
x = input()
c = x.count("1")
m = 0
m2 = 0
for i in range(n):
    if x[i] == "1":
        m += pow(2, (n - i - 1), c + 1)
        m %= c + 1
m2 = 0
if c!=1:
    for i in range(n):
        if x[i] == "1":
            m2 += pow(2, (n - i - 1), c - 1)
            m2 %= c - 1

for i in range(n):
    if x[i] == "1":
        if c != 1:
            t = m2 - pow(2, (n - i - 1), c - 1)
            t %= c - 1
            count = 1
        else:
            t = 0
            count = 0
    else:
        t = m + pow(2, (n - i - 1), c + 1)
        t %= c + 1
        count = 1
    while t > 0:
        t %= bin(t).count("1")
        count += 1
    print(count)

Solution (Python):
from functools import lru_cache

N = int(input())
X = input()
x = int(X, 2)
y = X.count('1')
if y == 1:
    x2 = 0
else:
    x2 = x % (y-1)
x1 = x % (y+1)

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

d = [0] * (2*10**5+5)
for i in range(2*10**5+5):
    d[i] = f(i)

for i in range(N):
    if x >>(N - i - 1) & 1:
        
        if y - 1 == 0:
            print(0)
        else:
            print(d[(x2 - pow(2, N - i - 1, y-1)) % (y-1)] + 1)
    else:
        
        print(d[(x1 + pow(2, N - i - 1, y+1)) % (y+1)] + 1)

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

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

lst = [-1] * (4 * N + 10)
lst[0] = 0
lst[1] = 1

def calc(x):
    if lst[x] != -1:
        return lst[x]
    count = 0
    y = x
    while y:
        if y % 2 == 1:
            count += 1
        y //= 2
    lst[x] = calc(x % count) + 1
    return lst[x]



count = X.count('1') 

count1 = count - 1
count2 = count + 1


total1 = 0
total2 = 0

for i in range(N):
    if X[N - 1 - i] == '1':
        if count1 >= 1:
            total1 += pow(2, i, count1)
            total1 %= (count1)

        total2 += pow(2, i, count2)
        total2 %= (count2)


for i in range(N):
    if X[i] == '1':
        if count1 == 0:
            print (0)
            continue
        tmp_total = (total1 - pow(2, N - 1 - i, count1)) % count1
        amari = tmp_total % count1
        ans = calc(amari) + 1
        print (ans)
    else: 
        tmp_total = (total2 + pow(2, N - 1 - i, count2)) % count2
        amari = tmp_total % (count2)
        ans = calc(amari) + 1
        print (ans)

Solution (Python):

def popcnt(x):
    return bin(x).count("1")

def main():
    N = int(input())
    Xs = input()
    X = int(Xs, 2)
    d = popcnt(X)

    lut = [0] * N
    for i in range(1, N):
        Xi = i % popcnt(i)
        lut[i] = lut[Xi] + 1

    dp = d+1
    dm = d-1
    mp = X % dp
    mm = X % dm if dm else 0
    
    
    
    ans = []
    for i in range(N):
        mask = 1 << (N-i-1)
        Xi = X ^ mask
        _ans = 0
        if Xs[i] == '1':
            if dm:
                m = (mm - pow(2, N-i-1, dm)) % dm
                _ans = lut[m] + 1
            
        else:
            
            m = (mp + pow(2, N-i-1, dp)) % dp
            _ans = lut[m] + 1
        ans.append(_ans)
    print(*ans, sep='\n')

if __name__ == '__main__':
    main()

Solution (Python):
def f(n):
    if n in memo:
        return memo[n]
    c=list(str(bin(n)))[2:].count('1')
    r=n%c
    if r>0:
        memo[n]=f(r)+1
    else:
        memo[n]=1
    return memo[n]

memo={0:0}
N=int(input())
X=list(input())
XC=X.count('1')
XN=int('0b'+''.join(X),2)
for i in range(N):
    if X[i]=='1':
        if XC==1:
            print(0)
            continue
        tx=(XN%(XC-1)-pow(2,N-i-1,XC-1))
        if tx<0:
            tx+=XC-1
        tx%=XC-1
    else:
        tx=(XN%(XC+1)+pow(2,N-i-1,XC+1))%(XC+1)
    print(f(tx)+1)

Solution (Python):
def main():
    N = int(input())
    *X, = map(int, input())

    memo = [-1] * 21

    def f(x):
        ret = 0
        while x > 0:
            x = x % bin(x)[2:].count('1')
            ret += 1
        return ret

    for x in range(21):
        memo[x] = f(x)

    cnt = X.count(1)

    if cnt == 1:
        ans = []
        i = 0
        for d in reversed(X):
            if d:
                ans.append(0)
                continue
            if i == 0 or X[-1]:
                ans.append(2)
            else:
                ans.append(1)
            i += 1
            
        ans.reverse()

        print(*ans, sep='\n')
        return

    pow2_0_1 = [1]
    pow2_1_0 = [1]

    t_0_1 = 1
    t_1_0 = 1
    for i in range(N):
        t_0_1 = t_0_1 * 2 % (cnt + 1)
        pow2_0_1.append(t_0_1)

        t_1_0 = t_1_0 * 2 % (cnt - 1)
        pow2_1_0.append(t_1_0)

    chg_0_1 = 0
    chg_1_0 = 0
    i = 0
    for d in reversed(X):
        if d:
            chg_0_1 = (chg_0_1 + pow2_0_1[i]) % (cnt + 1)
            chg_1_0 = (chg_1_0 + pow2_1_0[i]) % (cnt - 1)
        i += 1

    ans = []
    i = 0
    for d in reversed(X):
        if d:
            t = (chg_1_0 - pow2_1_0[i]) % (cnt - 1)
        else:
            t = (chg_0_1 + pow2_0_1[i]) % (cnt + 1)
        i += 1

        add_v = 1
        while t > 20 or memo[t] == -1:
            t = t % bin(t)[2:].count('1')
            add_v += 1
        ans.append(memo[t] + add_v)

    ans.reverse()

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


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
X = input()
cnt = X.count('1')
Y, Z = 0, 0
for i in range(N):
    if cnt > 1:
        Y = (Y + int(X[i])*pow(2, N-i-1, cnt-1))%(cnt-1)
    Z = (Z + int(X[i])*pow(2, N-i-1, cnt+1))%(cnt+1)

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

for i in range(N):
    if X[i] == '1':
        pc = cnt - 1
        if pc <= 0:
            print(0)
            continue
        else:
            Y_i = (Y - pow(2, N-i-1, cnt-1))%(cnt-1)
            ans = 1
            while Y_i > 0:
                Y_i = Y_i % popcount(Y_i)
                ans += 1
            print(ans)
    else:
        Z_i = (Z + pow(2, N-i-1, cnt+1))%(cnt+1)
        ans = 1
        while Z_i > 0:
            Z_i = Z_i % popcount(Z_i)
            ans += 1
        print(ans)

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

pc = 0
d = []
c = x
for i in range(n):
    d.append(c&1)
    if c&1 == 1:
        pc += 1
    c=c>>1

mp =  x%(pc+1)
if pc == 1:
    mm = -1
else:
    mm = x%(pc-1)

for i in range(n):
    if d[-i-1]==0:
        m = 1
        temp = (mp+pow(2,n-i-1,pc+1)) % (pc+1)
        ans = 1
    else:
        if mm == -1:
            temp = 0
            ans = 0
        else:    
            m = -1
            temp = (mm-pow(2,n-i-1,pc-1)) % (pc-1)
            ans = 1
    
    
    
    
    
    while temp:
        
        c = temp
        temppc = 0
        while c:
            if c&1 == 1:
                temppc += 1
            c=c>>1
        
        
        
        
        
        if temppc == 0:
            break
        temp = temp % temppc
        ans += 1
        
        
        
        
        
        
        
        
    
    print(ans)

Solution (Python):
def main():
    n = int(input())
    x = input()
    x = '0b'+x

    x = int(x,0)
    m = bin(x).count('1')

    if m > 1:
        a = x%(m-1)
    b = x%(m+1)
    tmp_a = 1
    tmp_b = 1
    xx = []

    for i in range(n):
        if (x >> i) &1:
            if m == 1:
                xx.append(0)
                continue
            else:
                y = (a - tmp_a)%(m-1)
        else:
            y = (b + tmp_b)%(m+1)
        tmp_a *= 2
        if m > 1:
            tmp_a %= (m-1)
        tmp_b *= 2
        tmp_b %= (m+1)

        cnt = 1
        while y != 0:
            cnt += 1
            y = solve(y)
        xx.append(cnt)
    
    
    for i in range(n-1,-1,-1):
        print(xx[i])

def solve(n):
    m = bin(n).count('1')
    return n%m

main()

Solution (Python):
N=int(input())
X=input()
X10=int(X,2)
one=X.count('1')
def popcount(n):
  c=format(n,'b').count('1')
  if c!=0:
    return n%c
  else:
    return 0
def f(n):
  count=0
  while n>0:
    n=popcount(n)
    count+=1
  return count
if one==1:
  e=X10%2
  for i in range(N):
    if X[i]=='0':
      Y=e+pow(2,N-i-1,2)
      print(f(Y)+1)
     
    elif X[i]=='1':
      print(0)
if one==0:
  for i in range(N):
    print(1)
if one>1:
  a=X10%(one-1)
  b=X10%(one+1)
  c=one-1
  d=one+1
  for i in range(N):
    if X[i]=='1':
      Y=(a-pow(2,N-i-1,c))%c
      print(f(Y)+1)
    if X[i]=='0':
      Y=(b+pow(2,N-i-1,d))%d
      print(f(Y)+1)