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

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  


def divide(X, s):
    ans = 0
    for i in X:
        ans *= 2
        i = int(i)
        ans += i
        ans = ans % s
    return ans


def popcount(n):
    ans = 0
    while(n > 0):
        ans += n & 1
        n = n >> 1
    return ans


def count(n):
    cnt = 1
    while(n > 0):
        n = n % popcount(n)
        cnt += 1
    return cnt


N = ni()
X = ns()

cnt = X.count("1")

if cnt == 0:
    for i in range(N):
        print(1)
    exit()


cnt_plus = cnt + 1
cnt_minus = cnt - 1
p = 1
m = 1
p_array = []
if cnt_minus > 0:
    m_array = []
for i in range(N):
    p_array.append(p)
    p = p * 2 % cnt_plus
    if cnt_minus > 0:
        m_array.append(m)
        m = m * 2 % cnt_minus

plus_first = divide(X, cnt_plus)
if cnt_minus > 0:
    minus_first = divide(X, cnt_minus)


for i, x in enumerate(X):
    if x == "0":
        first = (plus_first + p_array[-(i+1)]) % cnt_plus
        print(count(first))
    else:
        if cnt_minus == 0:
            print(0)
        else:
            first = (minus_first - m_array[-(i+1)]) % cnt_minus
            print(count(first))

Solution (Python):
def examA():
    L, R, D = LI()
    ans = R//D - (L-1)//D
    print(ans)
    return

def examB():
    N = I()
    A = LI()
    ans = 0
    for i,a in enumerate(A):
        if i%2==0:
            if a%2==1:
                ans += 1
    print(ans)
    return

def examC():
    N = I()
    ans = [0]*N
    for x in range(1,101):
        for y in range(1,101):
            for z in range(1,101):
                cur = x**2 + y**2 + z**2 + x*y + y*z + x*z
                if cur<N+1:
                    ans[cur-1] += 1

    for v in ans:
        print(v)
    return

def examD():
    def popcnt0(n):
        c = 0
        for i in range(20):
            c += (n >> i) & 1
        return c
    def cnt(num):
        c = 0
        while(num>0):
            
            num %= popcnt0(num)
            c += 1
        return c
    N = I()
    X = SI()
    S_upper = [0]*N
    S_lower = [0]*N
    start_upper = 0
    start_lower = 0
    bit = 0
    ans = [0]*N
    for s in X:
        if s=="1":
            bit += 1
    if bit==1:
        b = 0
        for i in range(N):
            if X[i]=="1":
                ans[i] = 0
                b = i
            else:
                ans[i] = 1
        if b==N-1:
            for i in range(N-1):
                ans[i] += 1
        else:
            ans[-1] += 1
        for v in ans:
            print(v)
        return
    elif bit==0:
        for v in ans:
            print(1)
        return
    for i in range(N):
        S_upper[i] = pow(2,N-i-1,bit+1)
        S_lower[i] = pow(2,N-i-1,bit-1)
        if X[i]=="1":
            start_upper += S_upper[i]
            start_lower += S_lower[i]
            start_upper %= (bit+1)
            start_lower %= (bit-1)
    for i in range(N):
        if X[i]=="0":
            cur = (start_upper + S_upper[i]) % (bit+1)
            ans[i] = cnt(cur)+1
        else:
            cur = (start_lower - S_lower[i] + 2*(bit -1)) % (bit-1)
            ans[i] = cnt(cur)+1
        

    for v in ans:
        print(v)
    return

def examE():
    T = I()
    ans = [0]*T

    for t in range(T):
        pass


    for v in ans:
        print(v)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(2*10**6)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Solution (Python):
def solve():
  N = int(input())
  X = input()
  x = sum(map(int,list(X)))
  dp = [0]*N
  for i in range(1,N):
    dp[i] = dp[i%sum(map(int,list(bin(i)[2:])))]+1
  cnt1 = 0
  if x>1:
    for i in range(N):
      cnt1 += int(X[-i-1])*pow(2,i,x-1)
      cnt1 %= x-1
  cnt2 = 0
  for i in range(N):
    cnt2 += int(X[-i-1])*pow(2,i,x+1)
    cnt2 %= x+1
  
  ans = [0]*N
  for i in range(N):
    if X[i]=='1':
      if x==1:
        ans[i] = 0
      else:
        num = (cnt1-pow(2,N-i-1,x-1))%(x-1)
        ans[i] = dp[num]+1
    else:
      num = (cnt2+pow(2,N-i-1,x+1))%(x+1)
      ans[i] = dp[num]+1
  return ans
print(*solve(),sep='\n')

Solution (Python):
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    N = NI()
    X = SI()
    X_pop = X.count("1")
    X_plus = X_pop + 1
    X_minus = X_pop - 1

    RP = [pow(2, i, X_plus) for i in range(N+1)]
    if X_minus > 0:
        RM = [pow(2, i, X_minus) 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_plus
        elif X_minus >= 1:
            tmp = (rem_m - RM[i]) % X_minus
        else:
            print(0)
            continue
        ans = 1
        while tmp > 0:
            tmp = tmp % bin(tmp).count("1")
            ans += 1
        print(ans)






if __name__ == "__main__":
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  
def LS2(): return list(sys.stdin.readline().rstrip())  

N = I()

A = [0]
for i in range(1,2*10**5):
    a = 0
    r = i
    for j in range(18):
        a += (i>>j)&1
    r %= a
    if r == 0:
        A.append(1)
    else:
        A.append(1+A[r])

X = LS2()

b = 0
for i in range(N):
    if X[i] == '1':
        b += 1
if b >= 2:
    c = b-1
    d = b+1

    r1 = 0
    r2 = 0

    amari1 = [1]
    amari2 = [1]
    for i in range(1,N):
        amari1.append((amari1[-1]*2) % c)
        amari2.append((amari2[-1]*2) % d)
    amari1.reverse()
    amari2.reverse()
    for i in range(N):
        if X[i] == '1':
            r1 += amari1[i]
            r1 %= c
            r2 += amari2[i]
            r2 %= d
    ANS = []
    for i in range(N):
        if X[i] == '1':
            e = r1
            e -= amari1[i]
            e %= c
            ANS.append(A[e]+1)
        else:
            f = r2
            f += amari2[i]
            f %= d
            ANS.append(A[f]+1)
else:
    d = b + 1
    r2 = 0


    amari2 = [1]
    for i in range(1, N):
        amari2.append((amari2[-1] * 2) % d)
    amari2.reverse()

    for i in range(N):
        if X[i] == '1':

            r2 += amari2[i]
            r2 %= d
    ANS = []
    for i in range(N):
        if X[i] == '1':

            ANS.append(0)
        else:
            f = r2
            f += amari2[i]
            f %= d
            ANS.append(A[f] + 1)


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

Solution (Python):
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
n = int(input())
x = str(input())
ans = [1 for _ in range(n)]
c = 0
for i in range(n):
  if x[i] == "1":
    c += 1
m1 = c-1
m2 = c+1
a1 = 0
a2 = 0
rl1 = [0 for _ in range(n)]
rl2 = [0 for _ in range(n)]
r1 = 1
r2 = 1
if m1 == 0:
  rl2 = [0 for _ in range(n)]
  ans = [1 for _ in range(n)]
  for i in range(n):
    if x[n-i-1] == "1":
      a2 = (a2+r2)%m2
    rl2[i] = r2
    r2 = (r2*2)%m2
  b = [0 for _ in range(n)]
  for i in range(n):
    if x[i] == "1":
      ans[i] = 0
      b[i] = 0
    else:
      bi = (a2 + (rl2[n-i-1]))%m2
      b[i] = bi
  while sum(b) != 0:
    for i in range(n):
      if b[i] !=0:
        b[i] = b[i]%(popcount(b[i]))
        ans[i] += 1
  for ai in ans:
    print(ai)
  exit()
for i in range(n):
  if x[n-i-1] == "1":
    a1 = (a1+r1)%m1
    a2 = (a2+r2)%m2
  rl1[i] = r1
  rl2[i] = r2
  r1 = (r1*2)%m1
  r2 = (r2*2)%m2
b = [0 for _ in range(n)]
for i in range(n):
  if x[i] == "1":
    bi = (a1 - (rl1[n-i-1]))%m1
    b[i] = bi
  else:
    bi = (a2 + (rl2[n-i-1]))%m2
    b[i] = bi
ans = [1 for _ in range(n)]
while sum(b) != 0:
  for i in range(n):
    if b[i] !=0:
      b[i] = b[i]%(popcount(b[i]))
      ans[i] += 1
for ai in ans:
  print(ai)

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

def f(i):
    if C==1:
        if i==mark:
            return 0
        else:
            if X[i]=='0':
                nex = (d[p+1]+pow(2, N-1-i, p+1))%(p+1)
            else:
                nex = (d[p-1]-pow(2, N-1-i, p-1))%(p-1)
    
            res = 1
    
            while nex>0:
                pc = 0
        
                for i in range(20):
                    if (nex>>i)&1:
                        pc += 1
        
                nex %= pc
                res += 1
    
            return res
        
            
    if X[i]=='0':
        nex = (d[p+1]+pow(2, N-1-i, p+1))%(p+1)
    else:
        nex = (d[p-1]-pow(2, N-1-i, p-1))%(p-1)
    
    res = 1
    
    while nex>0:
        pc = 0
        
        for i in range(20):
            if (nex>>i)&1:
                pc += 1
        
        nex %= pc
        res += 1
    
    return res

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

if X=='0'*N:
    for i in range(N):
        print(1)
    exit()

C = X.count('1')

for i in range(N):
    if X[i]=='1':
        mark = i
    
p = 0

for Xi in X:
    if Xi=='1':
        p += 1

d = defaultdict(int)

if C==1:
    for i in [p, p+1]:
        for j in range(N):
            if X[j]=='1':
                d[i] += pow(2, N-1-j, i)
else:
    for i in [p-1, p, p+1]:
        for j in range(N):
            if X[j]=='1':
                d[i] += pow(2, N-1-j, i)

for i in range(N):
    print(f(i))

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

    
    x = x - ((x >> 1) & 0x5555555555555555)

    
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x = x + (x >> 8) 
    x = x + (x >> 16) 
    x = x + (x >> 32) 
    return x & 0x0000007f

def g(num_in):
    num = num_in
    cnt = 0
    if num == 0:
        return 0

    while True:
        base = popcount(num)
        if num%base == 0:
            cnt += 1
            break
        else:
            num = num%base
            cnt += 1
    return cnt


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

st = 0
for c in s:
    if c == "1":
        st += 1

if st > 1:

    mod_p1 = [0 for i in range(n)]
    mod_n1 = [0 for i in range(n)]
    base1 = 1
    base2 = 1
    for i in range(n):
        t1 = base1%(st+1)
        t2 = base2%(st-1)

        mod_p1[-i-1] = t1
        mod_n1[-i-1] = t2

        base1 *= 2
        base2 *= 2

        base1%=(st+1)
        base2%=(st-1)

    p1 = 0
    n1 = 0
    for i in range(n):
        if s[i] == "1":
            p1 += mod_p1[i]
            n1 += mod_n1[i]

    for i in range(n):
        if s[i] == "0":
            base = p1
            base += mod_p1[i]
            base %= st+1
            print(1+g(base))

        else:
            base = n1
            base -= mod_n1[i]
            base %= st-1
            print(1+g(base))

else:
    mod_p1 = [0 for i in range(n)]
    base1 = 1
    for i in range(n):
        t1 = base1 % (st + 1)

        mod_p1[-i - 1] = t1

        base1 *= 2

        base1 %= (st + 1)

    p1 = 0
    for i in range(n):
        if s[i] == "1":
            p1 += mod_p1[i]

    for i in range(n):
        if s[i] == "0":
            base = p1
            base += mod_p1[i]
            base %= st + 1
            print(1 + g(base))

        else:
            print(0)

Solution (Python):
from collections import defaultdict
from collections import deque
con = 10 ** 9 + 7; INF = float("inf")

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

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

class BFS(object):
	def __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = deque(); self.Q.append(s)
		self.dist = [INF] * N; self.dist[s] = 0
		while self.Q:
			v = self.Q.popleft()
			for i in self.g[v]:
				if self.dist[i] == INF:
					self.dist[i] = self.dist[v] + 1
					self.Q.append(i)


def main():
	N = int(input())
	X = list(map(int, list(input())))

	G = Graph()
	for i in range(1, 2 * (10 ** 5) + 1):
		cnt1 = 0
		n = i
		while True:
			if n % 2 == 1:
				cnt1 += 1
			n = int(n // 2)
			if n == 0:
				break
		a = i % cnt1; b = i
		G.add_edge(a, b)

	BF = BFS(G, 0, 2 * (10 ** 5) + 1)
	dist = BF.dist

	X1cnt = 0
	for i in X:
		if i == 1:
			X1cnt += 1

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

	elif X1cnt == 1:
		Xplus = 0
		for i in range(N):
			Xplus += pow(2, i, X1cnt + 1) * X[-1 - i]

		for i in range(N):
			if X[i] == 1:
				print(0)
			else:
				val = Xplus
				val += pow(2, N - 1 - i, X1cnt + 1)
				val %= X1cnt + 1
				print(dist[val] + 1)

	else:
		Xplus = 0
		Xnone = 0
		Xminus = 0
		for i in range(N):
			Xplus += pow(2, i, X1cnt + 1) * X[-1 - i]
			Xnone += pow(2, i, X1cnt) * X[-1 - i]
			Xminus += pow(2, i, X1cnt - 1) * X[-1 - i]

		Xplus %= X1cnt + 1
		Xnone %= X1cnt
		Xminus %= X1cnt - 1
		for i in range(N):
			if X[i] == 1:
				val = Xminus
				val -= pow(2, N - 1 - i, X1cnt - 1)
				val %= X1cnt - 1
				print(dist[val] + 1)
			else:
				val = Xplus
				val += pow(2, N - 1 - i, X1cnt + 1)
				val %= X1cnt + 1
				print(dist[val] + 1)


if __name__ == '__main__':
	main()

Solution (Python):
import sys
import math
import bisect

def pow_mod(x, n, m):
    if n == 0:
        return 1
    ans = pow_mod(x, n // 2, m) ** 2 % m
    if n % 2 == 1:
        ans = ans * x % m
    return ans

def query_popcount(n):
    ans = 0
    while n:
        ans += n % 2
        n >>= 1
    return ans

def query_value(n):
    if n == 0:
        return 0
    m = query_popcount(n)
    return 1 + query_value(n % m)


def main():
    n = int(input())
    s = input()
    m = 0
    d = {}
    for c in s:
        if c == '1':
            m += 1
    
    if m - 1 != 0:
        val = 0
        for c in s:
            val = val * 2 + ord(c) - ord('0')
            if val >= (m - 1):
                val -= (m - 1)
        d[m-1] = val
    if m + 1 != 0:
        val = 0
        for c in s:
            val = val * 2 + ord(c) - ord('0')
            if val >= (m + 1):
                val -= (m + 1)
        d[m+1] = val
    
    ans = []
    for i in range(n):
        if s[i] == '0':
            r = (d[m+1] + pow_mod(2, n - 1 - i, m + 1)) % (m+1)
            val = 1 + query_value(r)
            ans.append(val)
        elif s[i] == '1':
            if m - 1 == 0:
                ans.append(0)
            else:
                r = (d[m-1] + (m-1) - pow_mod(2, n - 1 - i, m - 1)) % (m-1)
                val = 1 + query_value(r)
                ans.append(val)

    for a in ans:
        print(a)

if __name__ == "__main__":
    main()

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

mem = dict()
def find(n):
    if n == 0 :
        return 0
    elif n in mem :
        return mem[n]

    cur = n 
    bit_count = 0
    while cur > 0 :
        bit_count += cur%2
        cur //= 2

    if bit_count == 1 : 
        mem[n] = 1
    else :
        mem[n] = 1+find(n%bit_count)
    return mem[n] 

bit_count = sum([ int(x) for x in X ])

dp = [ [0]*N for _ in range(2)]   
def build_dp(j, v):
    if v == 0:
        return 
    st = 1
    _dp = dp[j]
    for i in range(N-1,-1,-1):
        _dp[i] = st%v
        st = (st*2)%v

build_dp(0, bit_count-1)
build_dp(1, bit_count+1)

base = [0]*2
k = 0
for v in [bit_count-1, bit_count+1]:
    st = 1 
    if v == 0 :
        continue
    for i in range(N-1,-1,-1):
        if X[i] == '1' :
            base[k] = (base[k]+st)%v
        st = (st*2)%v
    k += 1

for i in range(0,N):
    if X[i] == '1' :
        if bit_count-1 == 0 :
            print(0)
        else :
            value = (base[0]-dp[0][i]+bit_count-1) % (bit_count-1)
            print(1+find(value))
    else :
        value = (base[1]+dp[1][i]+bit_count+1) % (bit_count+1)
        print(1+find(value))

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

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N = Z()
    X = input()
    pcnt = 0
    ans = []
    for x in X:
        if x == '1': pcnt += 1
    if pcnt == 0:
        for _ in range(N):
            print(1)
            return
    Xinv = X[::-1]
    ex1 = ex2 = 1
    num1 = num2 = 0
    for x in Xinv:
        num1 += (ex1 * int(x)) % (pcnt + 1)
        num1 %= (pcnt + 1)
        if pcnt > 1:
            num2 += (ex2 * int(x)) % (pcnt - 1)
            num2 %= (pcnt - 1)
        ex1 *= 2
        ex1 %= (pcnt + 1)
        ex2 *= 2
        if pcnt > 1: ex2 %= (pcnt - 1)

    def solve(n, p, s):
        if n == 0 and s > 0: return s
        n %= p
        p = bin(n).count('1')
        return solve(n, p, s+1)

    for i in range(N):
        if X[i] == '1':
            p = pcnt - 1
            if p == 0:
                ans.append(0)
                continue
            num = num2 - pow(2, N-i-1, p)
            ans.append(solve(num, p, 0))
        else:
            p = pcnt + 1
            num = num1 + pow(2, N-i-1, p)
            ans.append(solve(num, p, 0))

    for i in range(N):
        print(ans[i])

    return

if __name__ == '__main__':
    main()

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

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

def process(n):
    return n % popcount(n)

def func(n):
    ret = 0
    while n > 0:
        n = process(n)
        ret += 1
    return ret

pcnt = X.count('1')
mods_plus = []
totalmod_plus = 0
tmp_plus = 1
pp = pcnt+1
mods_minus = []
totalmod_minus = 0
tmp_minus = 1
pm = pcnt-1
for c in reversed(X):
    if c == '1':
        totalmod_plus += tmp_plus
        totalmod_plus %= pp
    mods_plus.append(tmp_plus)
    tmp_plus = tmp_plus*2 % pp
    if pcnt != 1:
        if c == '1':
            totalmod_minus += tmp_minus
            totalmod_minus %= pm
        mods_minus.append(tmp_minus)
        tmp_minus = tmp_minus*2 % pm

for i in range(N):
    if X[i] == '1':
        if pcnt == 1:
            print(0)
        else:
            mod = mods_minus[-i-1]
            print(func((totalmod_minus - mod) % pm) + 1)
    else:
        mod = mods_plus[-i-1]
        print(func((totalmod_plus + mod) % pp) + 1)

Solution (Python):
n=int(input())
x=input()
one=x.count("1")
amari_m=0
amari_p=0
for i in range(n):
	if x[-i-1]=="1":
		amari_p+=pow(2,i,one+1)
		if one==1:
			amari_m=-1
		else:
			amari_m+=pow(2,i,one-1)
		amari_p%=one+1
		if one!=1:
			amari_m%=one-1
for i in range(n):
	cnt=0
	if x[i]=="1":
		if one==1:
			print(0)
			continue
		r=(amari_m-pow(2,(n-i-1),one-1))%(one-1)
	else:
		r=(amari_p+pow(2,(n-i-1),one+1))%(one+1)
	while r:
		r%=bin(r).count("1")
		cnt+=1
	print(cnt+1)

Solution (Python):
def popcount(x):
    return bin(x)[2:].count("1")

def f(x):
    cnt=0
    while(x>0):
        x%=popcount(x)
        cnt+=1
    return cnt

n=int(input())
s=input()
d=s.count("1")
if d==0:
    for i in range(n):
        print(1)
elif d==1:
    if s[-1]=="1":
        for i in range(n-1):
            print(2)
        else:
            print(0)
    else:
        for i in range(n-1):
            if s[i]=="1":
                print(0)
            else:
                print(1)
        print(2)
else:
    s=s[::-1]
    toaddm=1
    toaddM=1
    m=0
    M=0
    for i in range(n):
        if s[i]=="1":
            m+=toaddm
            M+=toaddM
            m%=d-1
            M%=d+1
        toaddm*=2
        toaddm%=d-1
        toaddM*=2
        toaddM%=d+1
    toaddm=-1
    toaddM=1
    res=[None for i in range(n)]
    for i in range(n):
        if s[i]=="1":
            res[i]=f((m+toaddm)%(d-1))+1
        else:
            res[i]=f((M+toaddM)%(d+1))+1
        toaddm*=2
        toaddm%=d-1
        toaddM*=2
        toaddM%=d+1
    for i in res[::-1]:
        print(i)

Solution (Python):
import sys
sys.setrecursionlimit(1<<30)

N = int(input())
X = input()
ones = X.count('1')

v1 = 0
v2 = 0
m1 = ones + 1
m2 = ones - 1
p1 = 1 % m1
p2 = 1

for i, v in enumerate(reversed(X)):
	if v == '1':
		v1 = (v1 + p1) % m1

		if m2 > 0:
			v2 = (v2 + p2) % m2

	p1 = p1 * 2 % m1
	if m2 > 0:
		p2 = p2 * 2 % m2

from functools import lru_cache

@lru_cache(maxsize=None)
def f(i):
	if i == 0: return 0

	return 1 + f(i % popcount(i))

def popcount(x):
      b=0
      while(x > 0):
          x &= x - 1
          b+=1
      return b


for i in range(N):
	div = ones + 1 if X[i] == '0' else ones - 1
	if div == 0:
		print(0)
	elif div == 1:
		print(1)
	else:

		if div == m1:
			x = (v1 + pow(2, N-i-1, m1)) % m1
		elif div == m2:
			x = (v2 - pow(2, N-i-1, m2)) % m2
		else:
			assert False

		

		print(1 + f(x))

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

n=II()
s=SI()
p=s.count("1")
p0=p-1
p1=p+1
pw0=[]
pw1=[]
two0=two1=1
for _ in range(n):
    pw0.append(two0)
    pw1.append(two1)
    if p0>0:two0=two0*2%p0
    two1=two1*2%p1

t0=0
t1=0
for i,c in enumerate(s[::-1]):
    if c=="1":
        if p0>0:t0=(t0+pw0[i])%p0
        t1=(t1+pw1[i])%p1

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

dp0=[-1]*n
def f0(x):
    if x==0:return 1
    if dp0[x]==-1:dp0[x]=f0(x%popcnt(x))+1
    return dp0[x]

ans=[]
for i,c in enumerate(s[::-1]):
    if p0==0 and c=="1":
        ans.append(0)
        continue
    if c=="1":
        cur=(t0-pw0[i])%p0
    else:
        cur=(t1+pw1[i])%p1
    ans.append(f0(cur))

for a in ans[::-1]:print(a)

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

x_cnt = x.count('1')
yp = 0
ym = 0
for i in range(n):
    yp *= 2
    yp += int(x[i])
    yp %= x_cnt + 1

    if x_cnt != 1:
        ym *= 2
        ym += int(x[i])
        ym %= x_cnt - 1


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




ans = [0] * n
bp = bm = 1
for i in reversed(range(n)):
    if x[i] == '0':
        z = (yp + bp) % (x_cnt + 1)
        ans[i] = 1 + count(z)
    else:
        if x_cnt == 1:
            ans[i] = 0
        else:
            z = (ym - bm + x_cnt - 1) % (x_cnt - 1)
            ans[i] = 1 + count(z)
    
    bp *= 2
    bp %= x_cnt + 1
    if x_cnt != 1:
        bm *= 2
        bm %= x_cnt - 1

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

Solution (Python):
def func(n):
    ans = 0
    while n > 0:
        cnt = 0
        for i in range(33):
            if (n & (1<<i)) != 0:
                cnt += 1
        ans += 1
        n %= cnt
    return ans

def main():
    n = int(input())
    s = input()
    ans = [0]*n
    cnt = 0
    for c in s:
        if c == "1":
            cnt += 1
    ad = cnt + 1
    df = cnt - 1
    start_ad = 0
    start_df = 0
    for i in range(n):
        if ad > 0:
            if s[n-1-i] == "1":
                start_ad += pow(2, i, ad)
                start_ad %= ad
        if df > 0:
            if s[n-1-i] == "1":
                start_df += pow(2, i, df)
                start_df %= df
    for i in range(n):
        if s[i] == "0":
            ans[i] = 1
            tmp = (start_ad + pow(2, n-1-i, ad)) % ad
            ans[i] += func(tmp)
        else:
            if cnt == 1:
                ans[i] = 0
            else:
                ans[i] = 1
                tmp = (start_df - pow(2, n-1-i, df)) % df
                ans[i] += func(tmp)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()

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

A = [0] * 200001
for i in range(1, 200001):
    A[i] = A[i % popcount(i)] + 1


N = int(input())
xx = input()
p = xx.count("1") - 1
q = xx.count("1") + 1

X = int(xx, 2)
xx = xx[::-1]

if p: a = X % p
b = X % q
s = 1
t = 1
ANS = []
for i, x in enumerate(xx):
    if x == "0":
        ANS.append(A[(b + t) % q] + 1)
    else:
        ANS.append(A[(a - s) % p] + 1 if p else 0)
    if p: s = s * 2 % p
    t = t * 2 % q

for ans in ANS[::-1]:
    print(ans)

Solution (Python):
from collections import defaultdict
def main():
    N = int(input())
    S = input()
    D = defaultdict(bool)
    cnt = 0
    all1 = 0
    all2 = 0
    for i in range(N):
        if S[i] == "1":
            D[i] = True
            cnt += 1
        else:
            D[i] == False

    for i in range(N):
        if S[i] == "1":
            all1 += pow(2, N-1-i, cnt+1)
            if cnt != 1:
                all2 += pow(2, N-1-i, cnt-1)

    for i in range(N):
        P = 0
        if S[i] == "1":
            if cnt == 1:
                print(0)
                continue
            else:
                P += all2-pow(2, N-1-i, cnt-1)
            ans = 1
            P = P % (cnt-1)
            while P:
                c = P
                mod = 0
                while c:
                    mod += c & 1
                    c = c >> 1
                P = P % mod
                ans += 1
            print(ans)
            continue
        else:
            P += all1+pow(2, N-1-i, cnt+1)
            ans = 1
            P = P % (cnt+1)
            while P:
                c = P
                mod = 0
                while c:
                    mod += c & 1
                    c = c >> 1
                P = P % mod
                ans += 1
            print(ans)
if __name__=="__main__":
    main()

Solution (Python):
n = int(input())
x = input()
pcnt = x.count("1")
pp = pcnt+1
pn = pcnt-1
ansb = [0,0,0]
def modpcnt(x):
  if x == 0:
    return 0
  b = x.bit_length()
  mod = 0
  for i in range(b):
    if x&1<<i:
      mod += 1
  return 1+modpcnt(x%mod)
for i in range(n):
  if x[i] == "1":
    ansb[1] += pow(2,n-i-1,pcnt)
    ansb[1] %= pcnt
    ansb[0] += pow(2,n-i-1,pp)
    ansb[0] %= pp
    if pn == 0:
      ansb[2] = 0
    else:
      ansb[2] += pow(2,n-i-1,pn)
      ansb[2] %= pn
for i in range(n):
  if x[i] == "0":
    tmp = (ansb[0]+pow(2,n-i-1,pp))%pp
    print(modpcnt(tmp)+1)
  else:
    if pn == 0:
      print(0)
    else:
      tmp = (ansb[2]-pow(2,n-i-1,pn))%pn
      print(modpcnt(tmp)+1)

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

A = [0] * 200001
for i in range(1, 200001):
    A[i] = A[i % popcount(i)] + 1


N = int(input())
xx = input()
p = xx.count("1") - 1
q = xx.count("1") + 1

X = int(xx, 2)
xx = xx[::-1]

if p: a = X % p
b = X % q
s = 1
t = 1
ANS = []
for i, x in enumerate(xx):
    if x == "0":
        ANS.append(A[(b + t) % q] + 1)
    else:
        ANS.append(A[(a - s) % p] + 1 if p else 0)
    if p: s = s * 2 % p
    t = t * 2 % q

for ans in ANS[::-1]:
    print(ans)

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

data=[0]*N
for i in range(1,N):
    temp=0
    for j in range(20):
        temp+=(i>>j &1)
    next=i%temp
    data[i]=data[next]+1

base=sum(int(X[i]) for i in range(N))

if base==0:
    baseup=0
    for i in range(N):
        baseup=(baseup*2)%(base+1)
        baseup=(baseup+int(X[i]))%(base+1)

    for i in range(N):
        if X[i]=="1":
            temp=(basedown-pow(2,N-1-i,base-1))%(base-1)
            print(1+data[temp])
        else:
            temp=(baseup+pow(2,N-1-i,base+1))%(base+1)
            print(1+data[temp])
elif base==1:
    baseup=0
    for i in range(N):
        baseup=(baseup*2)%(base+1)
        baseup=(baseup+int(X[i]))%(base+1)

    for i in range(N):
        if X[i]=="1":
            print(0)
        else:
            temp=(baseup+pow(2,N-1-i,base+1))%(base+1)
            print(1+data[temp])
else:
    basedown=0
    baseup=0
    for i in range(N):
        basedown=(basedown*2)%(base-1)
        baseup=(baseup*2)%(base+1)
        basedown=(basedown+int(X[i]))%(base-1)
        baseup=(baseup+int(X[i]))%(base+1)

    for i in range(N):
        if X[i]=="1":
            temp=(basedown-pow(2,N-1-i,base-1))%(base-1)
            print(1+data[temp])
        else:
            temp=(baseup+pow(2,N-1-i,base+1))%(base+1)
            print(1+data[temp])