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 = list(input())
P = X.count("1")
if P != 1:
    P1 = 0
    P2 = 0
    for i in range(N):
        if X[i] == "1":
            P1 += pow(2,N-i-1,P-1)
            P1 %= P-1
            P2 += pow(2,N-i-1,P+1)
            P2 %= P+1
    for i in range(N):
        count = 1
        if X[i] == "0":
            cur = P2+pow(2,N-i-1,P+1)
            cur %= P+1
        else:
            cur = P1-pow(2,N-1-i,P-1)
            cur %= P-1
        while cur > 0:
            mod = bin(cur).count("1")
            cur %= mod
            count += 1
        print(count)
else:
    P2 = 0
    for i in range(N):
        if X[i] == "1":
            P2 += pow(2,N-i-1,P+1)
    for i in range(N):
        count = 1
        if X[i] =="1":
            print(0)
        else:
            cur = P2+pow(2,N-i-1,P+1)
            cur %= P+1
            while cur > 0:
                mod = bin(cur).count("1")
                cur %= mod
                count += 1
            print(count)

Solution (Python):

import sys
input = sys.stdin.readline

n = int(input())
x = [int(item) for item in list(input().rstrip())]
x.reverse()

ones = x.count(1)
aug = ones + 1
dim = ones - 1

modaug = 0
moddim = 0
for i, item in enumerate(x):
    if item == 1:
        modaug += pow(2, i, aug)
        modaug %= aug
        if dim != 0:
            moddim += pow(2, i, dim)
            moddim %= dim

cnt = [-1] * (2*10**5 + 10)
cnt[0] = 0; cnt[1] = 1
for i in range(1, 2*10**5 + 10):
    val = i
    num = bin(val).count("1")
    cnt[i] = cnt[val % num] + 1

ans = []
for i, item in enumerate(x):
    if item == 0:
        tmp = modaug + pow(2, i, aug)
        tmp %= aug
    else:
        if dim == 0:
            ans.append(0)
            continue
        else:
            tmp = moddim - pow(2, i, dim)
            tmp %= dim
    ans.append(cnt[tmp] + 1)

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

Solution (Python):
N = int(input())
X = input()
X = X[::-1]

def count(n):
    if n==0:
        return 0
    m = 0
    for i in range(18):
        if n&2**i:
            m += 1
    n %= m
    return 1+count(n)



p1 = [1]*(N+1)
p2 = [1]*(N+1)
m = 0
for i in range(N):
    if X[i]=='1':
        m += 1

for n in range(N):
    p1[n+1] = 2*p1[n]%(m+1)
    if m!=1:
        p2[n+1] = 2*p2[n]%(m-1)

num = [0]*N
base1 = 0
base2 = 0
for i in range(N):
    if X[i]=='1':
        base1 += p1[i]
        base2 += p2[i]

ans = [0]*N
for i in range(N):
    if X[i]=='0':
        num[i] = (base1+p1[i])%(m+1)
        ans[i] += 1
    else:
        if m!=1:
            num[i] = (base2-p2[i])%(m-1)
            ans[i] += 1
        else:
            num[i] = 0



for i in range(N-1,-1,-1):
    ans[i] += count(num[i])
    print(ans[i])

Solution (Python):
N = int(input())
X = input()
Xi = int(X, 2)

c0 = X.count('1')
Xp = Xi % (c0 + 1)

if c0 != 1:
    Xm = Xi % (c0 - 1)

for i, x in enumerate(X):
    if x == '1':
        if c0 == 1:
            print(0)
            continue
        y = (Xm - pow(2, N - 1 - i, c0 - 1)) % (c0 - 1)
    else:
        y = (Xp + pow(2, N - 1 - i, c0 + 1)) % (c0 + 1)

    ans = 1
    while y:
        y %= bin(y).count('1')
        ans += 1
    print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(200000)
n=int(input())
x=input()

tab=[0]+[i%bin(i).count('1') for i in range(1,200001)]

xcnt=x.count("1")
staxp=0
staxm=0
pl=xcnt+1
mi=xcnt-1
if mi==0:
    mi=1
for i in range(n):
    if x[n-i-1]=="1":
        staxp=(staxp+pow(2,i,pl))%pl
        staxm=(staxm+pow(2,i,mi))%mi
    
def calc(x,now):
    if x==0:
        return now
    else:
        return calc(tab[x],now+1)

for i in range(n):
    if x[i]=="1":
        if xcnt==1:
            print(0)
        else:
            sta=(staxm-pow(2,n-i-1,mi))%mi
            print(1+calc(sta,0))
    else:
        sta=(staxp+pow(2,n-i-1,pl))%pl
        print(1+calc(sta,0))

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




l = 2*10**5 + 5
A = [0] * l
for i in range(1,l):
    ab = format(i, "b")
    abo = ab.count("1")
    A[i] = i % abo

B = [-1] * l
B[0] = 0


def dd(y):
    
    if B[y] == -1:
        return dd(A[y])+1
    else:
        return B[y]

for i in range(1, l):
    
    B[i] = dd(i)



m = x.count("1")
m0 = m-1
m00 = m0
if m0 == 0:
    m0 = 1

m1 = m+1
M0 = [1]
M1 = [1]
for i in range(l):
    M0.append((M0[-1]*2) % m0)
    M1.append((M1[-1]*2) % m1)

n0 = 0
n1 = 0
for i in range(n):
    if x[n-1-i] == "1":
        n0 = (n0 + M0[i]) % m0
        n1 = (n1 + M1[i]) % m1

for i in range(n):
    nn = 0
    if x[i] == "1":
        nn = (n0 - M0[n-i-1]) % m0
    else:
        nn = (n1 + M1[n-i-1]) % m1
    print(B[nn]+1 if (m00!=0 or x[i]!="1") else 0)

Solution (Python):
import sys
N = int(input())

X = input()

o = 0
cnt = 0
for i in X:
    o *= 2
    if i == "1":
        o += 1
        cnt += 1

if cnt == 0:
    for i in range(N):
        print (1)
    sys.exit()
elif cnt == 1:
    orev = [o % (cnt+1) , None]
else:
    orev = [o % (cnt+1) , o % (cnt-1)]

for i in range(N):

    nb = int(X[i])

    if nb == 0:
        mod = cnt+1
        now = (orev[0] + pow(2,N-1-i,mod)) % mod

        ans = 1
        while now != 0:
            s = format( now , 'b' )
            one = 0
            for j in s:
                if j == "1":
                    one += 1
            now %= one
            ans += 1

        print (ans)

    else:
        if cnt == 1:
            print (0)
            continue
        
        mod = cnt-1
        now = (orev[1] - pow(2,N-1-i,mod)) % mod

        ans = 1
        while now != 0:
            s = format( now , 'b' )
            one = 0
            for j in s:
                if j == "1":
                    one += 1
            now %= one
            ans += 1

        print (ans)

Solution (Python):
from functools import lru_cache
N = int(input())
S = input()
X = int(S, 2)

P = S.count('1')
if P == 0:
    for i in range(N):
        print(1)
    exit()

Rp = X % (P+1)
if P != 1:
    Rn = X % (P-1)

@lru_cache(None)
def popcnt(x):
    return bin(x).count('1')

for i in range(N):
    if S[i] == '1':
        if P == 1:
            print(0)
            continue
        p = P-1
        x = (Rn - pow(2, N-1-i, p)) % p
    else:
        p = P+1
        x = (Rp + pow(2, N-1-i, p)) % p

    cnt = 1
    while x:
        x %= popcnt(x)
        cnt += 1
    print(cnt)

Solution (Python):
def calc(x):
    if x == 0:
        return 0
    cnt = 0
    for i in range(25):
        if x >> i & 1:
            cnt += 1
    return 1 + calc(x % cnt)

N = int(input())
X = list(map(int, input().rstrip()))
count = sum(X)
mod1 = [0] * N
mod2 = [0] * N
sum1 = sum2 = 0
for i, d in enumerate(X):
    if count > 1:
        mod1[i] = pow(2, N - i - 1, count-1)
    mod2[i] = pow(2, N - i - 1, count+1)
    if d:
        if count > 1:
            sum1 = (sum1 + mod1[i]) % (count - 1)
        sum2 = (sum2 + mod2[i]) % (count + 1)
for i, d in enumerate(X):
    ans = 0
    if d:
        if count > 1:
            ans = 1 + calc((sum1 - mod1[i]) % (count - 1))
    else:
        ans = 1 + calc((sum2 + mod2[i]) % (count + 1))
    print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
S = list(map(int, list(input())[: -1]))
pp = sum(S)
Xp = 0
Xm = 0
S.reverse()
for i in range(N):
  Xp += pow(2, i, pp + 1) * S[i]
  Xp %= pp + 1
  Xm += pow(2, i, max(1, pp - 1)) * S[i]
  Xm %= max(1, pp - 1)

rres = [0] * N
for i in range(N):
  res = 1
  if S[i]:
    if pp == 1: res = 0
    else:
      X = (Xm - pow(2, i, max(1, pp - 1))) % max(1, pp - 1)
      while X:
        c = bin(X).count("1")
        X %= c
        res += 1
  else:
    X = (Xp + pow(2, i, pp + 1)) % (pp + 1)
    while X:
      c = bin(X).count("1")
      X %= c
      res += 1
  rres[i] = res
rres.reverse()
for r in rres: print(r)

Solution (Python):
def popc(x):
    acc = 0
    while x > 0:
        acc += x&1
        x >>= 1
    return acc

def fn(x):
    if x == 0:
        return 0
    return fn(x % popc(x)) + 1

n = int(input())
s = input()
o = s.count("1")
x = int(s, 2)
mp = x % (o+1)
mn = 0
if o > 1:
    mn = x % (o-1)
for i in range(n-1, -1, -1):
    if s[n-i-1] == "1":
        if o == 1:
            print(0)
            continue
        print(fn((mn - pow(2, i, o-1)) % (o-1)) + 1)
    else:
        print(fn((mp + pow(2, i, o+1)) % (o+1)) + 1)

Solution (Python):
import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def popcount(x):
    x = x - ((x >> 1) & 0x55555555)
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    return x & 0x0000007f

def solve():
    n = ni()
    X = list(map(int, list(ns())))
    p = sum(X)
    pl, ps = p+1, p-1

    g = [-1] * (n+5)
    g[0] = 0
    for i in range(1, n+5):
        g[i] = g[i % popcount(i)] + 1
    ql = qs = 0
    for x in X:
        ql = (ql * 2 + x) % pl
        if ps > 0:
            qs = (qs * 2 + x) % ps
    vl = vs = 1
    ans = [0]*n
    for i in range(n-1, -1, -1):
        if X[i]:
            if ps > 0:
                ans[i] = g[(qs-vs)%ps] + 1
        else:
            ans[i] = g[(ql+vl)%pl] + 1
        if ps > 0:
            vs = vs * 2 % ps
        vl = vl * 2 % pl
    prn(ans)
    return

solve()

Solution (Python):
import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
X=input()
def popcount(x):
  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

F=[0]*(n+1)
F[1]=1
for i in range(2,n+1):
  F[i]=1+F[i%popcount(i)]

ct=X.count("1")
if ct==0:
  for _ in range(n):
    print(1)
elif ct==1:
  for i in range(n):
    if X[i]=="1":
      cur=i
      break
  for i in range(n):
    if i==cur:
      print(0)
    else:
      if i==n-1 or cur==n-1:
        print(2)
      else:
        print(1)

else:
  a,b=0,0
  for i in range(n):
    if X[n-1-i]=="1":
      a=(a+pow(2,i,ct-1))%(ct-1)
      b=(b+pow(2,i,ct+1))%(ct+1)
  for i in range(n):
    if X[i]=="0":
      print(F[(b+pow(2,n-1-i,ct+1))%(ct+1)]+1)
    else:
      print(F[(a-pow(2,n-1-i,ct-1))%(ct-1)]+1)

Solution (Python):
def main():
    n = int(input())
    bit = input()[::-1]
    count = bit.count("1")
    count_plus = count+1
    count_minus = count-1
    pow_plus = [1 % count_plus]
    for i in range(n):
        pow_plus.append(pow_plus[-1]*2 % count_plus)
    if count_minus != 0:
        pow_minus = [1 % count_minus]
        for i in range(n):
            pow_minus.append(pow_minus[-1]*2 % count_minus)
    else:
        pow_minus = []

    bit_plus = 0
    bit_minus = 0

    for i in range(n):
        if bit[i] == "1":
            bit_plus = (bit_plus+pow_plus[i]) % count_plus
    if count_minus != 0:
        for i in range(n):
            if bit[i] == "1":
                bit_minus = (bit_minus+pow_minus[i]) % count_minus
    ans = []
    for i in range(n):
        if bit[i] == "1":
            if count_minus == 0:
                ans.append(0)
                continue
            bit_ans = (bit_minus-pow_minus[i]) % count_minus
            count = count_minus
        else:
            bit_ans = (bit_plus+pow_plus[i]) % count_plus
            count = count_plus
        cnt = 1
        while bit_ans:
            b = str(bin(bit_ans)).count("1")
            bit_ans = bit_ans % b
            cnt += 1
        ans.append(cnt)
    for i in ans[::-1]:
        print(i)


main()

Solution (Python):
n = int(input())
x = input()
popcount_x = x.count("1")
popcount_x1 = popcount_x + 1
popcount_x2 = popcount_x - 1

if popcount_x2 == 0: popcount_x2 = -1

div1 = [0]*n
div2 = [0]*n
cur1 = 1
cur2 = 1
for i in range(n):
    cur1 %= popcount_x1
    cur2 %= popcount_x2
    div1[i] = cur1
    div2[i] = cur2
    cur1 *= 2
    cur2 *= 2


fn = [0]*n
for i in range(1,n):
    popcount = bin(i)[2:].count("1")
    fn[i] = fn[(i)%popcount] + 1

    
x_div1 = sum(int(x[i]) * div1[-i-1] for i in range(n)) % popcount_x1
x_div2 = sum(int(x[i]) * div2[-i-1] for i in range(n)) % popcount_x2

for i in range(n):
    if x[i] == "0": 
        xi_div = (x_div1 + div1[-i-1]) % popcount_x1
        print(fn[xi_div] + 1)
    else:
        if popcount_x2 == -1:
            print(0)
        else:
            xi_div = (x_div2 - div2[-i-1]) % popcount_x2
            print(fn[xi_div] + 1)

Solution (Python):
n = int(input())
x = input()
d = [0] * n
t = x.count('1')
a = 0
b = 0


if t == 1:
    for i in range(n):
        d[i] = (a + pow(2, n - i - 1, t + 1)) % (t + 1)
    for i in range(n):
        a *= 2
        if x[i] == '1':
            a += 1
        a %= t + 1
    for i in range(n):
        if x[i] == '1':
            print(0)
        else:
            p = d[i]
            ans = 1
            while p > 0:
                p %= bin(p).count('1')
                ans += 1
            print(ans)
else:
    for i in range(n):
        a *= 2
        b *= 2
        if x[i] == '1':
            a += 1
            b += 1
        a %= t + 1
        b %= t - 1
    for i in range(n):
        if x[i] == '1':
            d[i] = (b - pow(2, n - i - 1, t - 1)) % (t - 1)
        else:
            d[i] = (a + pow(2, n - i - 1, t + 1)) % (t + 1)
    for i in range(n):
        a *= 2
        b *= 2
        if x[i] == '1':
            a += 1
            b += 1
        a %= t + 1
        b %= t - 1
    for p in d:
        ans = 1
        while p > 0:
            p %= bin(p).count('1')
            ans += 1
        print(ans)

Solution (Python):
import sys
import numpy as np
import numba
from numba import njit
i8 = numba.int64

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

N = int(readline())
X = np.array(list(read().rstrip()), np.int64) - ord('0')

@njit((i8, ), cache=True)
def popcount(n):
    ret = 0
    while n:
        ret += n & 1
        n >>= 1
    return ret


@njit((i8, ), cache=True)
def f(n):
    t = 0
    while n:
        t += 1
        n %= popcount(n)
    return t

@njit(cache=True)
def main(X):

    popX = X.sum()
    MOD1 = popX + 1
    MOD2 = popX - 1
    if popX == 1:
        MOD2 = 1
    pow1 = np.ones_like(X)
    pow2 = np.ones_like(X)
    for n in range(1, len(X)):
        pow1[n] = 2 * pow1[n - 1] % MOD1
        pow2[n] = 2 * pow2[n - 1] % MOD2

    X1, X2 = 0, 0
    for x in X:
        X1 = (2 * X1 + x) % MOD1
        X2 = (2 * X2 + x) % MOD2

    ans = np.empty(N, np.int64)
    for i in range(N):
        x = X[N - 1 - i]
        if x == 0:
            nxt = (X1 + pow1[i]) % (popX + 1)
            ans[i] = 1 + f(nxt)
        elif x == 1:
            if popX == 1:
                ans[i] = 0
            else:
                nxt = (X2 - pow2[i]) % (popX - 1)
                ans[i] = 1 + f(nxt)
    return ans[::-1]

ans = main(X)
print('\n'.join(map(str, ans.tolist())))

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

Solution (Python):
def find(x,ones):
    if ones == 0:
        return 0
    total = 0
    n = len(x)
    for i in range(n):
        total += int(x[i])*pow(2,n-i-1,ones)
        total %= ones

    return total

def solve(x,mod):
    x %= mod
    moves = 1
    while x != 0:
        x = x%(bin(x)[2:].count('1'))
        moves += 1

    return moves

def main():
    n = int(input())
    x = input()
    ones = x.count('1')
    less = find(x,ones-1)
    more = find(x,ones+1)
    for i in range(n):
        if x[i] == '0':
            print(solve(more+pow(2,n-i-1,ones+1),ones+1))
        else:
            if ones-1 == 0:
                print(0)
            else:
                print(solve(less-pow(2,n-i-1,ones-1),ones-1))


main()

Solution (Python):
from functools import lru_cache


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


n = int(input())
x = input()
d = x.count('1')
y = int(x, base=2)
y0 = y % (d + 1)
y1 = y % (d - 1) if d > 1 else 0
buf = []

for i in range(n):
    if x[i] == '0':
        m = d + 1
        z = (y0 + pow(2, n - i - 1, m)) % m
        
    else:
        m = d - 1
        if m == 0:
            buf.append(0)
            continue
        z = (y1 - pow(2, n - i - 1, m)) % m
        
    
    buf.append(f(z) + 1)

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

Solution (Python):
def popcount(i): 
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24





import sys
read = sys.stdin.read
readline = sys.stdin.readline


n, = map(int,readline().split())
x = input()

p = x.count("1")
p0 = p-1
p1 = p+1

if p0 != 0:
    r0 = int(x,2)%p0
else:
    r0 = 0
r1 = int(x,2)%p1





for i in range(n):
    if x[i]=="0":
        v = (r1 + pow(2,n-i-1,p1))%p1
    else:
        if p0 == 0:
            print(0)
            continue
        v = (r0 - pow(2,n-i-1,p0))%p0
        
    ans = 1
    while v:
        
        ans += 1
        v %= popcount(v)
    print(ans)

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

popcnt = X.count('1')

if popcnt == 0:
    for _ in range(N):
        print(1)
    exit()

pop1 = popcnt + 1
pop2 = popcnt - 1

x_int = int(X, base = 2)
x_mod_pop1 = x_int % pop1
if pop2 != 0:
    x_mod_pop2 = x_int % pop2

for i, c in enumerate(X):
    if c == '1':
        if popcnt == 1:
            print(0)
        else:
            mod = x_mod_pop2 - pow(2, N-i-1, pop2) 
            mod %= pop2
            c = 1
            while mod:
                mod %= format(mod, 'b').count('1')
                c += 1
            print(c)
    else:
        mod = x_mod_pop1 + pow(2, N-i-1, pop1) 
        mod %= pop1
        c = 1
        while mod:
            mod %= format(mod, 'b').count('1')
            c += 1
        print(c)

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

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

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




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


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

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

Solution (Python):
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    X = input().rstrip('\n')

    M = X.count("1")
    flg = 0
    if M == 1:
        flg = 1
    x_major = 0
    x_minor = 0
    for i in range(N):
        add = int(X[i])
        x_major = (x_major * 2 + add)%(M+1)
        if flg == 0:
            x_minor = (x_minor * 2 + add)%(M-1)
    for i in range(N):
        if X[i] == "1":
            if flg:
                print(0)
                continue
            val = (x_minor - pow(2, N-i-1, M-1)) % (M-1)
        else:
            val = (x_major + pow(2, N-i-1, M+1)) % (M + 1)
        cnt = 1
        while val:
            val = val % bin(val).count("1")
            cnt += 1
        print(cnt)


if __name__ == '__main__':
    main()

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

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

num = S.count('1')

n1 = num + 1
n2 = num - 1

def count(m):
    ret = 1
    while m != 0:
        k = bin(m).count("1")
        m %= k
        ret += 1
    return ret


if n2 != 0:
    start1 = 0
    start2 = 0
    pow1 = [1]
    pow2 = [1]
    for i in range(N):
        s = int(S[-1-i])
        start1 = (start1 + pow1[-1] * s) % n1
        start2 = (start2 + pow2[-1] * s) % n2
        pow1.append(pow1[-1] * 2 % n1)
        pow2.append(pow2[-1] * 2 % n2)


    ans = []
    for i in range(N):
        s = int(S[i])
        if s == 0:
            l = (start1 + pow1[-i-2]) % n1
            ans.append(count(l))
        else:
            l = (start2 - pow2[-i-2]) % n2
            ans.append(count(l))

    print(*ans, sep="\n")
else:
    start1 = 0
    pow1 = [1]
    for i in range(N):
        s = int(S[-1-i])
        start1 = (start1 + pow1[-1] * s) % n1
        pow1.append(pow1[-1] * 2 % n1)

        


    ans = []
    for i in range(N):
        s = int(S[i])
        if s == 0:
            l = (start1 + pow1[-i-2]) % n1
            ans.append(count(l))
        else:
            ans.append(0)

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

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

def ans(x):
    ANS=0
    while x:
        x%=bin(x).count("1")
        ANS+=1
    return ANS

LEN=int(input())
S=input().strip()
ONE=S.count("1")

ONEP=ONE+1
ONEM=ONE-1

PANS=0
MANS=0
for i in range(LEN):
    if S[i]=="1":
        PANS+=pow(2,LEN-1-i,ONEP)
        if ONEM<=0:
            continue
        MANS+=pow(2,LEN-1-i,ONEM)

for i in range(LEN):
    if S[i]=="0":
        print(ans((PANS+pow(2,LEN-1-i,ONEP))%ONEP)+1)
    else:
        if ONEM==0:
            print(0)
        else:
            print(ans((MANS-pow(2,LEN-1-i,ONEM))%ONEM)+1)

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

def ans(x):
    ANS=0
    while x:
        x%=bin(x).count("1")
        ANS+=1
    return ANS

LEN=int(input())
S=input().strip()
ONE=S.count("1")

ONEP=ONE+1
ONEM=ONE-1

PANS=0
MANS=0
for i in range(LEN):
    if S[i]=="1":
        PANS+=pow(2,LEN-1-i,ONEP)
        if ONEM<=0:
            continue
        MANS+=pow(2,LEN-1-i,ONEM)

for i in range(LEN):
    if S[i]=="0":
        print(ans((PANS+pow(2,LEN-1-i,ONEP))%ONEP)+1)
    else:
        if ONEM==0:
            print(0)
        else:
            print(ans((MANS-pow(2,LEN-1-i,ONEM))%ONEM)+1)

Solution (Python):


import os
import sys
from io import BytesIO, IOBase

"""
    for _ in range(int(input())):
    n,m=map(int,input().split())
    n=int(input())
    a = [int(x) for x in input().split()]
"""

def main():
    from functools import lru_cache

    @lru_cache(None)
    def solve(n):
        if n==0:
            return 0
        c=bin(n).count('1')
        return 1+solve(n%c)
    n=int(input())
    s=input()

    ct=s.count('1')

    mod=1
    if ct>1:
        mod*=ct-1
    mod*=ct+1

    p,g=1,0
    for x in s:
        g*=2
        if x=='1':
            g+=1
        g%=mod

    s=s[::-1]
    ans=[0]*len(s)
    for i,x in enumerate(s):
        p%=mod
        if x=='1':
            if ct==1:
                p*=2
                continue
            else:
                ans[i]=1+solve((g-p)%(ct-1))
        else:
            ans[i]=1+solve((g+p)%(ct+1))
        p*=2
    ans=ans[::-1]
    for x in ans:
        print(x)


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")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")



if __name__ == "__main__":
    main()

Solution (Python):
def solve(X):
    cnt = X.count('1')

    memo = [0]*(cnt+2)

    for v in range(1,cnt+2):
        memo[v] = memo[v%(bin(v).count('1'))]+1

    res = [None]*len(X)
    if cnt > 1:
        m = int(X,2)%(cnt-1)

        r = 1
        for i,c in enumerate(reversed(X)):
            if c == '1':
                res[i] = memo[(m-r)%(cnt-1)]+1
            r *= 2
            r %= cnt-1
    else:
        for i,c in enumerate(reversed(X)):
            if c == '1':
                res[i] = 0

    m = int(X,2)%(cnt+1)

    r = 1
    for i,c in enumerate(reversed(X)):
        if c == '0':
            res[i] = memo[(m+r)%(cnt+1)]+1
        r *= 2
        r %= cnt+1

    return '\n'.join(map(str,reversed(res)))



if __name__ == '__main__':
    N = int(input())
    X = input()
    print(solve(X))

Solution (Python):
def popcount(n):
    return str(bin(n)).count('1')
def f(n):
    if n==0:
        return 0
    else:
        return f(n%popcount(n))+1
N=int(input())
X=input()
K=X.count("1")

ONE=0
ZERO=0
tmp1=1
tmp0=1
for i in range(N):
    if X[-i-1]=="1":
        if K>1:
            ONE+=tmp1
            ONE%=(K-1)
        ZERO+=tmp0
        ZERO%=(K+1)
    if K>1:
        tmp1*=2
        tmp1%=(K-1)
    tmp0*=2
    tmp0%=(K+1)
for i in range(N):
    nextnumber=-1
    if X[i]=="1":
        if K==1:
            print(0)
            continue
        else:
            nextnumber=(ONE-pow(2,N-i-1,K-1))%(K-1)
    else:
        nextnumber=(ZERO+pow(2,N-i-1,K+1))%(K+1)
    print(f(nextnumber)+1)