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

a = X.count("1")
ap, am = a+1, a-1
Flag = True

if am == 0:
  Flag = False
  am += 1

Ap = [1]
Am = [1]

for i in range(N-1):
  Ap.append(Ap[-1]*2%ap)
  Am.append(Am[-1]*2%am)

Aps = 0
Ams = 0

for i in range(N):
  if X[-1-i] == "1":
    Aps += Ap[i]
    Aps %= ap
    Ams += Am[i]
    Ams %= am
    
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

for i in range(N):
  cnt = 0
  if X[i] == "1":
    if Flag:
      p = Ams - Am[-1-i]
      p %= am
      cnt += 1
    else:
      p = 0
  else:
    p = Aps + Ap[-1-i]
    p %= ap
    cnt += 1
  while p > 0:
    p %= popcount(p)
    cnt += 1
  print(cnt)

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

init_pop_cnt = x.count('1')
init_pop_cnt_less = init_pop_cnt - 1
init_pop_cnt_more = init_pop_cnt + 1

valid_l = init_pop_cnt_less != 0


init_res_less = 0
init_res_more = 0
seed_more = 1
seed_less = 1
for i in range(1, n+1):
  xp = x[-1 * i]
  if xp == '1':
    if valid_l:
      init_res_less += seed_less % init_pop_cnt_less
    init_res_more += seed_more % init_pop_cnt_more
  if valid_l:
    seed_less = (seed_less * 2) % init_pop_cnt_less
  seed_more = (seed_more * 2) % init_pop_cnt_more


dif_less = [0] * (2 * 10**5 + 100)
dif_more = [0] * (2 * 10**5 + 100)
if valid_l:
  dif_less[0] = 1 % init_pop_cnt_less
dif_more[0] = 1 % init_pop_cnt_more
for i in range(1, n+1):
  if valid_l:
    dif_less[i] = (dif_less[i-1] * 2) % init_pop_cnt_less
  dif_more[i] = (dif_more[i-1] * 2) % init_pop_cnt_more


def get_pc(dec):
  out = 0
  while dec > 0:
    if dec % 2 == 1:
      out+=1
    dec = dec // 2
  return out

def f(dec):
  pc = get_pc(dec)
  return dec % pc

cnt = [0] * (2 * 10**5 + 200)

for i in range(1, 2 * 10**5 + 100):
  c = 0
  cur = i
  while cur > 0:
    c += 1
    cur = f(cur)
  cnt[i] = c

for i in range(n):
  xi = x[i]

  if xi == '1':
    if valid_l:
      lx = init_res_less
      lx -= dif_less[n-i-1]
      lx %= init_pop_cnt_less
      print((cnt[lx] % init_pop_cnt_less) + 1)
    else:
      print(0)
  else:
    lx = init_res_more
    lx += dif_more[n-i-1]
    lx %= init_pop_cnt_more
    print((cnt[lx] % init_pop_cnt_more) + 1)

Solution (Python):


import sys
input=sys.stdin.readline


LEN=2*10**5+10

moves=[0]*LEN
for i in range(1,LEN):
  tmp=i
  cnt=0
  while tmp!=0:
    popcount=0
    for j in range(20):
      if tmp&(1<<j):
        popcount+=1
    tmp%=popcount
    cnt+=1
  moves[i]=cnt

n=int(input())
x=input()
k=x.count('1')
if k==0:
    for i in range(n):
        print(1)
elif k==1:
    pos=x.index('1')
    for i in range(n):
        if i==pos:
            print(0)
        else:
            if pos==n-1:
                print(2)
            else:
                if i==n-1:
                    print(2)
                else:
                    print(1)
else:
    sum1=0
    sum2=0
    tmp1=1
    tmp2=1
    for i in range(n-1,-1,-1):
        if x[i]=='1':
            sum1+=tmp1
            sum1%=k+1
            sum2+=tmp2
            sum2%=k-1
        tmp1*=2
        tmp1%=k+1
        tmp2*=2
        tmp2%=k-1
    for i in range(n):
        if x[i]=='0':
            tmp=sum1+pow(2,n-i-1,k+1)
            tmp%=k+1
            print(moves[tmp]+1)
        else:
            tmp=sum2-pow(2,n-i-1,k-1)
            tmp%=k-1
            print(moves[tmp]+1)

Solution (Python):


import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from functools import lru_cache


@lru_cache(maxsize=2*10**5)
def f2(x):
    if x == 0: return 0
    y = bin(x).count("1")
    return 1 + f2(x % y)

def resolve():
    N = int(input())
    W = 16
    S = input()
    cnt0 = S.count("1")

    if cnt0 == 0:
        print(*[1]*N, sep="\n")
        return

    X = int(S, 2)

    dc = {}
    for k, v in (("0", 1), ("1", -1)):
        x = cnt0 + v
        y = X % x if x else 0
        dc[k] = (x, v, y)

    ans = []
    for i, si in enumerate(S):
        cnt, v, n = dc[si]

        if cnt == 0:
            ans.append(0)
            continue

        ni = N - i - 1
        n = (n + v * pow(2, ni, cnt)) % cnt

        ans.append(1+f2(n))

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


if __name__ == "__main__":
    resolve()

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

B_1 = B.count("1")
mod_p1 = int(B,2) % (B_1+1)
if B_1 != 1:
    mod_m1 = int(B,2) % (B_1-1)

def calc_small(n, iter):
    iter += 1
    mod = n % bin(n).count("1")

    if mod == 0:
        return iter
    else:
        return calc_small(mod, iter)

for i in range(N):
    if B_1 == 1 and int(B[i]) == 1:
        print(0)
        continue
    mod = (mod_m1 - pow(2,N-i-1,B_1-1)) % (B_1-1) if int(B[i]) == 1 else (mod_p1 + pow(2,N-i-1,B_1+1)) % (B_1+1)
    iter = 1
    if mod == 0:
        print(iter)
    else:
        print(calc_small(mod, iter))

Solution (Python):
import sys
readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

import numpy as np






N = int(input())
X = input()
Y = int('0b' + X, 0)
X = np.array(list(X), int)

p = int(X.sum())
m1 = Y % (p + 1)
m2 = Y % max(1, p - 1)


count = np.zeros((N + 1, ))
for n in range(1, N):
    i = np.array(list(bin(n))[2:], int).sum()
    count[n] = 1 + count[n % i]

ans = [0] * N
for n in range(1, N + 1):
    flag = 0
    if X[n - 1]:
        z = m2 - pow(2, N - n, max(1, p - 1))
        z %= max(1, p - 1)
        if p - 1 == 0:
            flag = 1
    else:
        z = pow(2, N - n, p + 1) + m1
        z %= p + 1
        if p == 0:
            z = 0

    ans[n - 1] = int(count[z] + 1)
    if z == 0 and flag:
        ans [n - 1] = 0

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

Solution (Python):
from collections import deque

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

memo = {0: 0}

def solve(X):
    x = X
    stack = deque([])
    while x:
        if x in memo:
            break
        stack.append(x)
        x = x % bin(x).count("1")
    cnt = memo[x] + 1
    while stack:
        x = stack.pop()
        memo[x] = cnt
        cnt += 1
    return cnt - 1



ans = []
px = x.count("1")

memo1 = [1 % (px - 1)] if px > 1 else []
memo2 = [1 % (px + 1)]
x1 = 0
x2 = 0

for i in range(n):
    if px > 1:
        memo1.append(memo1[-1] * 2 % (px-1))
    memo2.append(memo2[-1] * 2 % (px+1))

for i in range(n):
    if x[-i-1] == '1':
        if px > 1:
            x1 += memo1[i]
            x1 %= (px-1)
        x2 += memo2[i]
        x1 %= (px+1)

for i in range(n):
    if x[-i-1] == "1":
        if px > 1:
            ans.append(solve((x1-memo1[i])%(px-1)) + 1)
        else:
            ans.append(0)
    else:
        ans.append(solve((x2+memo2[i])%(px+1)) + 1)


for ansi in reversed(ans):
    print(ansi)

Solution (Python):


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

N = int(input())
X = input()
XC = X.count('1')
XI = int(X, 2)
XCP = XC + 1
XCM = XC - 1
XTP = XI % XCP
XTM = XI % XCM if XCM != 0 else 0
for i in range(N):
    if X[i] == "0":
        print(goes_to_zero((XTP + pow(2, N - 1 - i, XCP)) % XCP) + 1)
    else:
        if XCM == 0:
            print(0)
        else:
            print(goes_to_zero((XTM - pow(2,N - 1 - i, XCM)) % XCM) + 1)

Solution (Python):
n = int(input())
x = input()
cnt1 = x.count('1')
x10 = int(x,2)

if cnt1 > 1:
  x10mod_m = x10 % (cnt1-1)
  x10mod_p = x10 % (cnt1+1)
else:
  x10mod_m = 0
  x10mod_p = 0

ans = []
for i in range(n):
  if x[i] == '1':
    if cnt1 == 1:
      print(0)
      continue
    cntx = cnt1-1
    mod = ( x10mod_m - pow(2,n-1-i,cntx) ) % cntx
  else:
    cntx = cnt1+1
    mod = ( x10mod_p + pow(2,n-1-i,cntx) ) % cntx
    
  cnt = 1
  mod = format(mod, 'b')
  
  while True:
    if mod == '0':
      break
    mod = format( int(mod,2) % mod.count('1'), 'b')
    cnt += 1
  print(cnt)

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

def popcnt1(n):
    return bin(n).count("1")

k = [0,1,1,2,1,2,1,2,1,2,1,2,1,2,2,3,1,2,1] 

c = 0
for i in range(N):
    if X[i] == "1":
        c += 1

m1 = 0
p1 = 0

for i in range(N):
    if c != 1:
        if X[i] == "1":
            m1 += pow(2,N-1-i,c-1)
            m1 %= c-1
            p1 += pow(2,N-1-i,c+1)
            p1 %= c+1
    else:
        if X[i] == "1":
            p1 += pow(2,N-1-i,c+1)
            p1 %= c+1

for i in range(N):
    if c != 1: 
        if X[i] == "0":
            B2 = p1 + pow(2,N-1-i,c+1)
            B2 %= c+1
        else:
            B2 = m1 - pow(2,N-1-i,c-1)
            B2 %= c-1
    else:
        if X[i] == "0":
            B2 = p1 + pow(2,N-1-i,c+1)
            B2 %= c+1
        else:
            print(0)
            continue

    S = len(bin(B2))
    c2 = popcnt1(B2)

    if c2 == 0:
        print(1)
    else:
        print(2+k[B2%c2])

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

one = x.count("1")
X = int(x, 2)

if one==1:
    for i in range(n):
        if x[i]=="1":
            print(0)
        elif i==n-1:
            print(2)
        else:
            print(1)
    
    
elif one>1:
    
    Xp = X % (one+1)
    Xm = X % (one-1)

    def f(x):
        if x==0:
            return 0
        return 1+f(x%bin(x).count("1"))

    for i in range(n):
        
        if x[i]=="0":
            c = pow(2, n-i-1, one+1)
            print(f((Xp+c)%(one+1))+1)
        else:
            c = pow(2, n-i-1, one-1)
            print(f((Xm-c)%(one-1))+1)
else:
    for i in range(n):
        print(1)

Solution (Python):

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

def popcount(ni):
    n_b = str(bin(ni))
    return n_b.count("1")

def ans(n,x):
    x_i = int(x, 2)
    x_orig = popcount(x_i)
    x_i_t = x_i % (x_orig+1)
    if x_orig != 1:
        x_i_b = x_i % (x_orig-1)
    else:
        x_i_b = x_i
    solve = 0
    for i in range(n):
        x_count = x_orig
        if x[i] == "0":
            x_count += 1
            solve = x_i_t + pow(2,n-1-i,x_count)
        else:
            x_count -= 1
            if x_count != 0:
                solve = x_i_b - pow(2,n-1-i,x_count)
            else:
                print(0)
                continue
        count = 0

        if x_count != 0 :
            solve = solve % x_count
            count+=1

        while solve > 0:
            solve = solve % popcount(solve)
            count+=1

        print(count)

    
ans(n,x)

Solution (Python):

import sys
N=int(sys.stdin.readline().strip())
X=sys.stdin.readline().strip()

cnt_of_one=0
for x in X:
    if x=="1": cnt_of_one+=1

cnt_of_one_plus_one=cnt_of_one+1    
cnt_of_one_minus_one=cnt_of_one-1   

amari_cnt_of_one_plus_one=0     
amari_cnt_of_one_minus_one=0    
for i,x in enumerate(X[::-1]):
    if x=="1":    
        amari_cnt_of_one_plus_one+=pow(2,i,cnt_of_one_plus_one)
        amari_cnt_of_one_plus_one%=cnt_of_one_plus_one
        if cnt_of_one_minus_one==0: 
            amari_cnt_of_one_minus_one=0
        else:
            amari_cnt_of_one_minus_one+=pow(2,i,cnt_of_one_minus_one)
            amari_cnt_of_one_minus_one%=cnt_of_one_minus_one

def popcount(n):
    ret=0
    while 0<n:
        ret+=n%2
        n/=2
    return ret

def f(n):
    ret=0   
    while 0<n:
        n%=popcount(n)
        ret+=1
    return ret

for i,x in enumerate(X):
    keta=N-i-1
    if x=="0":
        syoki_amari=(amari_cnt_of_one_plus_one+pow(2,keta,cnt_of_one_plus_one))%cnt_of_one_plus_one
        if syoki_amari==0:
            print 1
        else:
            print 1+f(syoki_amari)
    elif x=="1":
        if cnt_of_one_minus_one==0: 
            print 0 
        else:
            syoki_amari=(amari_cnt_of_one_minus_one-pow(2,keta,cnt_of_one_minus_one))%cnt_of_one_minus_one
            if syoki_amari==0:
                print 1
            else:
                print 1+f(syoki_amari)

Solution (Python):
def dfs(n):
    if n == 0:return 0
    return dfs(n % format(n, "b").count("1")) + 1
n = int(input())
x = input()
c = x.count("1")
a = int(x, 2)
if c == 1:
    for i in range(n):
        if x[i] == "1":
            print(0)
        elif i == n - 1:
            print(2)
        else:
            print(1)
else:
    j, k = a % (c + 1), a % (c - 1)
    for i in range(n):
        if x[i] == "1":print(dfs((k - pow(2, n - i - 1, c - 1)) % (c - 1)) + 1)
        else:print(dfs((j + pow(2, n - i - 1, c + 1)) % (c + 1)) + 1)

Solution (Python):
import math
from copy import copy
di = {}
di[0] = 0
for i in range(1, 2*(10**5)+1):
    di[i] = 0
for i in range(1, 2*(10**5)+1):
    count = 0
    for j in range(int(math.log2(i))+4):
        if (i>>j)&1:
            count += 1
    di[i] = di[i%count] + 1
n = int(input())
x = list(input())
x.reverse()
count = 0
for i in x:
    if i =='1':
        count += 1
mod_p = count + 1
mod_m = count - 1
di_p = {}
di_m = {}
for i in range(n):
    di_p[i] = pow(2, i, mod_p)
    if mod_m >= 1:
        di_m[i] = pow(2, i, mod_m)
s_p = 0
s_m = 0
for i in range(n):
    if x[i] == '1':
        s_p += di_p[i]
        if mod_m >= 1:
            s_m += di_m[i]
    else:
        continue
for i in range(n-1, -1, -1):
    sm = copy(s_m)
    sp = copy(s_p)
    if x[i] == '1' and (mod_m == 0 or mod_m == -1):
        print(0)
    elif x[i] == '1':
        sm -= di_m[i]
        sm %= mod_m 
        print(di[sm]+1)
    else:
        sp += di_p[i]
        sp %= mod_p
        print(di[sp]+1)

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")

INF = float("inf")


N = int(input())
S = list(input())
table = [0]*(N+5)
table[1] = 1
for i in range(2,N+3):
    num = i
    cnt = 0
    while num != 0:
        a = num % 2
        num = num // 2
        cnt += a
    p = i % cnt
    table[i] = table[p]+1
c = 0
for s in S:
    if s == "1":
        c += 1
p = 0
q = 0

for i in range(N):
    ss = S[N-1-i]
    p += int(ss)*pow(2,i,c+1)
    if c != 1:
        q += int(ss)*pow(2,i,c-1)
    p %= (c+1)
    if c != 1:
        q %= (c-1)
for i in range(N):
    ss = S[i]
    if ss == "0":
        ans = (p+pow(2,N-1-i,c+1))%(c+1)
        print(table[ans]+1)
    else:
        if c == 1:
            print(0)
        else:
            if c != 1:
                ans = (q-pow(2,N-1-i,c-1))%(c-1)
                print(table[ans]+1)
            else:
                print(0)

Solution (Python):
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N = int(readline())
    X_bin = readline().strip()
    n = X_bin.count("1")
    X = int(X_bin, 2)

    X_pop_p = X % (n + 1)
    if n != 1:
        X_pop_m = X % (n - 1)

    
    def count(x):
        cnt = 1
        while x:
            x %= bin(x).count("1")
            cnt += 1
        return cnt
        
    ans = []
    for i in range(N):
        X_i = X ^ (1 << i)
        if X_i == 0:
            ans.append(0)
        else:
            if X_bin[-(i+1)] == "1":
                mod = (X_pop_m - pow(2, i, n - 1)) % (n - 1)
                ans.append(count(mod))
            else:
                mod = (X_pop_p + pow(2, i, n + 1)) % (n + 1)
                ans.append(count(mod))

    print("\n".join(map(str, ans[::-1])))


if __name__ == "__main__":
    main()

Solution (Python):

import sys
N=int(sys.stdin.readline().strip())
X=sys.stdin.readline().strip()

cnt_of_one=0
for x in X:
    if x=="1": cnt_of_one+=1

cnt_of_one_plus_one=cnt_of_one+1
cnt_of_one_minus_one=cnt_of_one-1

amari_cnt_of_one_plus_one=0
amari_cnt_of_one_minus_one=0
for i,x in enumerate(X[::-1]):
    if x=="1":    
        amari_cnt_of_one_plus_one+=pow(2,i,cnt_of_one_plus_one)
        amari_cnt_of_one_plus_one%=cnt_of_one_plus_one
        if cnt_of_one_minus_one==0: 
            amari_cnt_of_one_minus_one=0
        else:
            amari_cnt_of_one_minus_one+=pow(2,i,cnt_of_one_minus_one)
            amari_cnt_of_one_minus_one%=cnt_of_one_minus_one

def popcount(n):
    ret=0
    while 0<n:
        ret+=n%2
        n/=2
    return ret

def f(n):
    ret=0   
    while 0<n:
        n%=popcount(n)
        ret+=1
    return ret

for i,x in enumerate(X):
    keta=N-i-1
    if x=="0":
        syoki_amari=(amari_cnt_of_one_plus_one+pow(2,keta,cnt_of_one_plus_one))%cnt_of_one_plus_one
        if syoki_amari==0:
            print 1
        else:
            print 1+f(syoki_amari)
    elif x=="1":
        if cnt_of_one_minus_one==0: 
            print 0 
        else:
            syoki_amari=(amari_cnt_of_one_minus_one-pow(2,keta,cnt_of_one_minus_one))%cnt_of_one_minus_one
            if syoki_amari==0:
                print 1
            else:
                print 1+f(syoki_amari)

Solution (Python):
import math
from copy import copy
di = {}
di[0] = 0
for i in range(1, 2*(10**6)+1):
    di[i] = 0
for i in range(1, 2*(10**6)+1):
    count = 0
    for j in range(int(math.log2(i))+4):
        if (i>>j)&1:
            count += 1
    di[i] = di[i%count] + 1
n = int(input())
x = list(input())
x.reverse()
count = 0
for i in x:
    if i =='1':
        count += 1
mod_p = count + 1
mod_m = count - 1
di_p = {}
di_m = {}
for i in range(n):
    di_p[i] = pow(2, i, mod_p)
    if mod_m >= 1:
        di_m[i] = pow(2, i, mod_m)
s_p = 0
s_m = 0
for i in range(n):
    if x[i] == '1':
        s_p += di_p[i]
        if mod_m >= 1:
            s_m += di_m[i]
    else:
        continue
for i in range(n-1, -1, -1):
    sm = copy(s_m)
    sp = copy(s_p)
    if x[i] == '1' and (mod_m == 0 or mod_m == -1):
        print(0)
    elif x[i] == '1':
        sm -= di_m[i]
        sm %= mod_m 
        print(di[sm]+1)
    else:
        sp += di_p[i]
        sp %= mod_p
        print(di[sp]+1)

Solution (Python):
def bitcount(N):  
    bitcnt = [0]
    for _ in range(N):
        bitcnt += [i + 1 for i in bitcnt]
    return bitcnt


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

num, cnt = int(x, 2), x.count('1')
num0, num1 = num % (cnt + 1), num % max(cnt - 1, 1)
lbit = bitcount(18)
for i in range(n):
    ans = 1
    if x[i] == '0':
        ctmp = cnt + 1
        tmp = num0 + pow(2, n - (i + 1), ctmp)
    elif x[i] == '1':
        if cnt <= 1:
            print(0)
            continue
        ctmp = cnt - 1
        tmp = num1 - pow(2, n - (i + 1), ctmp)
    tmp %= ctmp
    ctmp = lbit[tmp]
    while tmp > 0:
        ans += 1
        tmp %= ctmp
        ctmp = lbit[tmp]
    print(ans)

Solution (Python):
N = int(input())
X = input()
ans = [1 for _ in range(N)]

if N == 1:
  if X[0] == '1':
    print(0)
    exit()
  else:
    print(1)
    exit()
 
l = 0
for k in range(N):
  if X[k] == '1':
    l+=1

if l == 0:
  for _ in range(N):
    print(1)
  exit()
if l == 1:
  if X[-1] == '1':
    for _ in range(N-1):
      ans[_] = 2
  else:
    ans[-1] = 2 
  for k in range(N):
    if X[k] =='1':
      ans[k] = 0 
  for _ in range(N):
    print(ans[_])
  exit()
 
 
intN = int(X, 2)
N1 = intN %(l-1)
N0 = intN %(l+1)


start = []
s1 = 1
s0 = 1
for k in range(N-1, -1, -1):
  if X[k] == '1':      
    ia = (N1 - s1)%(l-1)
  else:
    ia = (N0 + s0)%(l+1)
  start.append(ia)
  s1 = s1*2%(l-1)
  s0 = s0*2%(l+1)
start = start[::-1]

ml = len(bin(l+1))-2
poplist = [[] for _ in range(ml)]
poplist[0] = [0,1]
for k in range(1, ml):
  for m in range(k):
    poplist[k] += poplist[m]
  for m in range(len(poplist[k])):
    poplist[k][m] += 1
newpoplist = []
for _ in range(len(poplist)):
  newpoplist += poplist[_] 


for k in range(len(start)):
  for count in range(10*5):
    if start[k] == 0:
      ans[k] += count
      break
    else:
      start[k] = start[k] % newpoplist[start[k]]
 
for k in range(N):
  print(ans[k])

Solution (Python):
from collections import deque
LIM=200004
L=[0]*LIM

def bin_sum(Y):
    S=bin(Y)[2:]
    count=0
    for i in range(len(S)):
        count+=int(S[i])
    return count

def bin_sum2(Y):
    count=0
    for i in range(len(Y)):
        count+=int(Y[i])
    return count

for i in range(1,LIM):
    L[i]+=bin_sum(i)

def pop_num(N,b,L):
    if N==0:
        return 0
    v=N%b
    return pop_num(v,L[v],L)+1
    
M=[0]*200005
for i in range(1,200004):
    M[i]+=pop_num(i,L[i],L)
X=int(input())
Y=input()
d=bin_sum2(Y)
e=int(Y,2)%(d+1)
f=int(Y,2)%max(1,(d-1))
O=[1]*(X+2)
P=[1]*(X+2)
q=max(d-1,1)
for i in range(1,X+1):
    O[i]=O[i-1]*2%q
    P[i]=P[i-1]*2%(d+1)
for i in range(X):
    
    if int(Y[i])==1:
        b=max(d-1,1)
        flag=max(0,d-1)
        g=(f-O[X-1-i]+b)%b
    else:
        b=d+1
        flag=1
        g=(e+P[X-1-i])%b

    if flag==0:
        print(0)
    elif g==0:
        print(1)
    else:
        print(M[g]+1)

Solution (Python):
N = int(input())
X = input()
ans = [1 for _ in range(N)]

l = X.count('1')
if l == 0:
  for _ in range(N):
    print(1)
  exit()
if l == 1:
  if X[-1] == '1':
    for _ in range(N-1):
      ans[_] = 2
  else:
    ans[-1] = 2 
  for k in range(N):
    if X[k] =='1':
      ans[k] = 0 
  for _ in range(N):
    print(ans[_])
  exit()
 
 
intN = int(X, 2)
N1 = intN %(l-1)
N0 = intN % (l+1)
 
 
start = []
if N == 1:
  if X[0] == '1':
    print(0)
    exit()
  else:
    print(1)
    exit()
else:
  s1 = 1
  s0 = 1
  for k in range(N-1, -1, -1):
    if X[k] == '1':      
      ia = (N1 - s1)%(l-1)
    else:
      ia = (N0 + s0)%(l+1)
    start.append(ia)
    s1 = s1*2%(l-1)
    s0 = s0*2%(l+1)
start = start[::-1]
 
ml = len(bin(l+1))-2
poplist = [0 for _ in range(N)]
t = 1
while t < N + 1:
  t *= 2
  for k in range(t//2, N, t):
    for j in range(t//2):
      if k+j>N-1:
        break
      poplist[k+j] += 1
"""
 
def popcount(n):
  c = 0
  n = bin(n)[2:]
  for k in range(len(n)):
    if n[k] == '1':
      c+=1
  return c
"""
for k in range(len(start)):
  for count in range(10*5):
    if start[k] == 0:
      ans[k] += count
      break
    else:
      start[k] = start[k] % poplist[start[k]]
 
for k in range(N):
  print(ans[k])

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

def popcount(l):
    return bin(l).count("1")
def count(l):
    res = 0
    while l != 0:
        p = popcount(l)
        l %= p
        res += 1
    return res
m = popcount(x)
x_plus = x%(m+1)
if m != 1:
    x_minus = x%(m-1)
else:
    x_minus = 1
lis_plus = [0]*n
lis_minus = [0]*n
for i in range(n):
    if i == 0:
        lis_plus[i] = 1%(m+1)
        if m != 1:
            lis_minus[i] = 1%(m-1)
    else:
        lis_plus[i] = lis_plus[i-1]*2%(m+1)
        if m != 1:
            lis_minus[i] = lis_minus[i-1]*2%(m-1)
for i in range(n):
    if (x >> (n-i-1)) & 1:
        if m == 1:
            print(0)
        else:
            print(count((x_minus - lis_minus[-i-1])%(m-1)) + 1)
    else:
        print(count((x_plus + lis_plus[-i-1])%(m+1)) + 1)

Solution (Python):
N = int(input())
X = input()
ans = [1 for _ in range(N)]

if N == 1:
  if X[0] == '1':
    print(0)
    exit()
  else:
    print(1)
    exit()


l = X.count('1')

if l == 0:
  for _ in range(N):
    print(1)
  exit()
if l == 1:
  if X[-1] == '1':
    for _ in range(N-1):
      ans[_] = 2
  else:
    ans[-1] = 2 
  for k in range(N):
    if X[k] =='1':
      ans[k] = 0 
  for _ in range(N):
    print(ans[_])
  exit()
 
 
intN = int(X, 2)
N1 = intN %(l-1)
N0 = intN %(l+1)


start = []
s1 = 1
s0 = 1
for k in range(N-1, -1, -1):
  if X[k] == '1':      
    ia = (N1 - s1)%(l-1)
  else:
    ia = (N0 + s0)%(l+1)
  start.append(ia)
  s1 = s1*2%(l-1)
  s0 = s0*2%(l+1)
start = start[::-1]

ml = len(bin(l+1))-2
poplist = [[] for _ in range(ml)]
poplist[0] = [0,1]
for k in range(1, ml):
  for m in range(k):
    poplist[k] += poplist[m]
  for m in range(len(poplist[k])):
    poplist[k][m] += 1
newpoplist = []
for _ in range(len(poplist)):
  newpoplist += poplist[_] 


for k in range(len(start)):
  for count in range(10*5):
    if start[k] == 0:
      ans[k] += count
      break
    else:
      start[k] = start[k] % newpoplist[start[k]]
 
for k in range(N):
  print(ans[k])

Solution (Python):
N = int(input())
X = input()
ans = [1 for _ in range(N)]

if N == 1:
  if X[0] == '1':
    print(0)
    exit()
  else:
    print(1)
    exit()


l = X.count('1')

if l == 0:
  for _ in range(N):
    print(1)
  exit()
if l == 1:
  if X[-1] == '1':
    for _ in range(N-1):
      ans[_] = 2
  else:
    ans[-1] = 2 
  for k in range(N):
    if X[k] =='1':
      ans[k] = 0 
  for _ in range(N):
    print(ans[_])
  exit()
 
 
intN = int(X, 2)
N1 = intN %(l-1)
N0 = intN %(l+1)


start = []
s1 = 1
s0 = 1
for k in range(N-1, -1, -1):
  if X[k] == '1':      
    ia = (N1 - s1)%(l-1)
  else:
    ia = (N0 + s0)%(l+1)
  start.append(ia)
  s1 = s1*2%(l-1)
  s0 = s0*2%(l+1)
start = start[::-1]



"""
poplist = [0 for _ in range(l+1)]
t = 1
while t < l + 2:
  for k in range(t, l+1, 2*t):
    for j in range(t):
      if k+j>l:
        break
      poplist[k+j] += 1
  t *= 2
"""
ml = len(bin(l+1))-2
poplist = [[] for _ in range(ml)]
poplist[0] = [0,1]
for k in range(1, ml):
  for m in range(k):
    poplist[k] += poplist[m]
  for m in range(len(poplist[k])):
    poplist[k][m] += 1
newpoplist = []
for _ in range(len(poplist)):
  newpoplist += poplist[_] 
poplist = newpoplist

for k in range(len(start)):
  for count in range(10*5):
    if start[k] == 0:
      ans[k] += count
      break
    else:
      start[k] = start[k] % poplist[start[k]]
 
for k in range(N):
  print(ans[k])

Solution (Python):
from functools import lru_cache


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


@lru_cache(maxsize=None)
def rec(n):
    if n == 0:
        return 0
    else:
        return rec(n % popcnt(n)) + 1


n = int(input())
arr = input()

ALL_ARR = int(arr, 2)


cnt = popcnt(int(arr, 2))
init_big = ALL_ARR % (cnt + 1)
if cnt == 1:
    init_small = 0
else:
    init_small = ALL_ARR % (cnt - 1)



li = [0] * n
for i in range(n):
    if arr[i] == "0":
        li[i] = (init_big + pow(2, n - i - 1, cnt + 1)) % (cnt + 1)

    
    elif ALL_ARR - (1 << (n - i - 1)) == 0 or cnt - 1 == 0:
        li[i] = "flg"
    else:
        li[i] = (init_small - pow(2, n - i - 1, cnt - 1)) % (cnt - 1)

ans = []

for x in li:
    if x == "flg":
        ans.append(0)
    else:
        ans.append(rec(x) + 1)

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

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


def popcount(X,ones,count): 
    
    if ones==0:
        return count
    else:
      
        X=X%ones
        
        count+=1
 
        ones=str(bin(X)).count("1")
        
        return popcount(X,ones,count)
 

    
GroundOnes=x.count("1")
GroundX=int(x,2)

if GroundOnes>1:
    CaseOne= GroundX%(GroundOnes-1)
else:
    CaseOne=2

CaseZero= GroundX%(GroundOnes+1)

TwoPowerCaseOne=[]
TwoPowerCaseZero=[]

if GroundOnes>1:
    for j in range(N):
      TwoPowerCaseOne.append(pow(2,(N-j-1) , (GroundOnes-1)))
      TwoPowerCaseZero.append(pow(2,(N-j-1), (GroundOnes+1)))
else:
    for j in range(N):
      TwoPowerCaseZero.append(pow(2,(N-j-1), (GroundOnes+1)))
  
    
for i in range(N):
    
    
    if x[i]=="1":
        ones=GroundOnes-1
        if ones>0:
            X=CaseOne-pow(2,N-i-1,ones)
        else:
            X=0
    
    else:
        ones=GroundOnes+1
        X=CaseZero+pow(2,N-i-1,ones)
            
 
    
    
    
    
    print(popcount(X,ones,0))

Solution (Python):
N = int(input())
X = input()
ans = [1 for _ in range(N)]

if N == 1:
  if X[0] == '1':
    print(0)
    exit()
  else:
    print(1)
    exit()


l = 0
for k in range(N):
  if X[k] == '1':
    l+=1

if l == 0:
  for _ in range(N):
    print(1)
  exit()
if l == 1:
  if X[-1] == '1':
    for _ in range(N-1):
      ans[_] = 2
  else:
    ans[-1] = 2 
  for k in range(N):
    if X[k] =='1':
      ans[k] = 0 
  for _ in range(N):
    print(ans[_])
  exit()
 
 
intN = int(X, 2)
N1 = intN %(l-1)
N0 = intN %(l+1)


start = []
s1 = 1
s0 = 1
for k in range(N-1, -1, -1):
  if X[k] == '1':      
    ia = (N1 - s1)%(l-1)
  else:
    ia = (N0 + s0)%(l+1)
  start.append(ia)
  s1 = s1*2%(l-1)
  s0 = s0*2%(l+1)
start = start[::-1]




poplist = [0 for _ in range(l+1)]
t = 1
while t < l + 2:
  for k in range(t, l+1, 2*t):
    for j in range(t):
      if k+j>l:
        break
      poplist[k+j] += 1
  t *= 2

for k in range(len(start)):
  for count in range(10*5):
    if start[k] == 0:
      ans[k] += count
      break
    else:
      start[k] = start[k] % poplist[start[k]]
 
for k in range(N):
  print(ans[k])

Solution (Python):
from functools import lru_cache


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


@lru_cache(maxsize=None)
def rec(n):
    if n == 0:
        return 0
    else:
        return rec(n % popcnt(n)) + 1


n = int(input())
arr = input()

ALL_ARR = int(arr, 2)


cnt = popcnt(int(arr, 2))
init_big = ALL_ARR % (cnt + 1)
if cnt == 1:
    init_small = 0
else:
    init_small = ALL_ARR % (cnt - 1)



li = [0] * n
for i in range(n):
    if arr[i] == "0":
        li[i] = (init_big + pow(2, n - i - 1, cnt + 1)) % (cnt + 1)

    
    elif ALL_ARR - (1 << (n - i - 1)) == 0 or cnt - 1 == 0:
        li[i] = "flg"
    else:
        li[i] = (init_small - pow(2, n - i - 1, cnt - 1)) % (cnt - 1)

ans = []

for x in li:
    if x == "flg":
        ans.append(0)
    else:
        ans.append(rec(x) + 1)

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

Solution (Python):
N=int(input())
x=input()
def popcount(X,ones,count): 
    
    if ones==0:
        return count
    else:
      
        X=X%ones
        
        count+=1
 
        ones=str(bin(X)).count("1")
        
        return popcount(X,ones,count)
 

    
GroundOnes=x.count("1")
GroundX=int(x,2)

if GroundOnes>1:
    CaseOne= GroundX%(GroundOnes-1)
else:
    CaseOne=2

CaseZero= GroundX%(GroundOnes+1)

TwoPowerCaseOne=[]
TwoPowerCaseZero=[]








  
    
for i in range(N):
    
    
    if x[i]=="1":
        ones=GroundOnes-1
        if ones>0:
            X=CaseOne-pow(2,N-i-1,ones)
        else:
            X=0
    
    else:
        ones=GroundOnes+1
        X=CaseZero+pow(2,N-i-1,ones)
            
 
    
    
    
    
    print(popcount(X,ones,0))