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, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
X = str(input())
start_mod = X.count("1")
if start_mod == 1:
  for i in range(n):
    if X[i] == "1":
      key = i
else: key = -1

def bin_to_int(n,binstr,mod):
  retval = 0
  for i in range(n-1,-1,-1):
    retval += (pow(2,n-1-i,mod) if binstr[i] == "1" else 0)
    retval %= mod
  return retval

start_number_plus = bin_to_int(n,X,start_mod+1)
if key == -1:
  start_number_minus = bin_to_int(n,X,start_mod-1)



for i in range(n):
  if i == key:print(0);continue
  if X[i] == "1":
    now_mod = start_mod - 1
    now_number = (start_number_minus - pow(2,n-1-i,now_mod))%now_mod
      
  else:
    now_mod = start_mod + 1
    now_number = (start_number_plus + pow(2,n-1-i,now_mod))%now_mod
  
  ci = 1
  while now_number != 0:
    
    now_mod = bin(now_number).count("1")
    now_number %= now_mod
    ci += 1
  print(ci)

Solution (Python):
def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    X = input().decode()
    K = int(X, 2)
    X = list(X)

    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

    
    
    
    
    C = X.count("1")
    dpL = [0]*N
    dpR = [0]*N
    tmp = 1
    dpL[0] = 1 % (C+1)
    L = K % (C+1)

    if C == 1:
        R = 0
    else:
        R = K % (C-1)
        dpR[0] = 1 % (C-1)

    for i in range(1, N):
        dpL[i] = dpL[i-1]*2 % (C+1)
        if C > 1:
            dpR[i] = dpR[i-1]*2 % (C-1)

    dp = [0]*N
    dp[0] = 0
    for i in range(1, N):
        k = i % popcount(i)
        dp[i] = 1 + dp[k]

    

    for i in range(N):
        if X[i] == "0":
            print(dp[(L + dpL[N-i-1]) % (C+1)] + 1)
        else:
            if C == 1:
                print(0)
                continue
            X[i] = '0'
            print(dp[(R - dpR[N-i-1]) % (C-1)] + 1)
            
            X[i] = '1'


main()

Solution (Python):
import sys

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

if n==1:
    if x=="0":
        print(1)
    else:
        print(0)
    sys.exit()


lis=[0,1]

for i in range(2,n+1):
    ni=i
    cnti=0
    while ni!=0:
        if ni%2==1:
            cnti+=1
        ni=ni//2
    lis.append(lis[i%cnti]+1)

cnt=0
for i in range(len(x)):
    if x[i]=="1":
        cnt+=1

cpls=cnt+1
cmns=cnt-1

cplis=[1]
if cpls!=0:
    for i in range(n):
        cplis.append((cplis[i]*2)%cpls)
cmlis=[1]
if cmns!=0:
    for i in range(n):
        cmlis.append((cmlis[i]*2)%cmns)

cpsum=0
cmsum=0
for i in range(n):
    if x[i]=="1":
        cpsum=(cpsum+cplis[n-1-i])%cpls
        if cmns!=0:
            cmsum=(cmsum+cmlis[n-1-i])%cmns

for i in range(n):
    if x[i]=="0":
        Xi=(cpsum+cplis[n-1-i])%cpls
        print(lis[Xi]+1)
    else:
        if cmns==0:
            print(0)
        else:
            Xi=(cmsum-cmlis[n-1-i])%cmns
            print(lis[Xi]+1)

Solution (Python):
import sys
N = int(input())
X = int(input(), 2)
x_popcount = sum(map(int, bin(X)[2:]))
is_zeroflg = [x_popcount-1 <= 0, False]
x_popcounts = [max(1, x_popcount - 1), x_popcount + 1]
X_per_popcounts = [X % x_popcounts[0], X % x_popcounts[1]]
mods = [0, 0]
ans = [0]*N


def f(n):
    cnt = 0
    while n != 0:
        popcount = sum(map(int, bin(n)[2:]))
        n = n % popcount
        cnt += 1
    return cnt


flg = X & 1 ^ 1
mods[0] = (-1) % x_popcounts[0]
mods[1] = 1 % x_popcounts[1]
tmp = (X_per_popcounts[flg] + mods[flg]) % x_popcounts[flg]
ans[0] = f(tmp) + 1
if is_zeroflg[flg]:
    ans[0] = 0

for i in range(1, N):
    flg = (X >> i) & 1 ^ 1
    mods[0] = (mods[0] * 2) % (x_popcounts[0])
    mods[1] = (mods[1] * 2) % (x_popcounts[1])
    tmp = (X_per_popcounts[flg] + mods[flg]) % x_popcounts[flg]
    ans[i] = f(tmp) + 1
    if is_zeroflg[flg]:
        ans[i] = 0

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

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

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

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

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

Solution (Python):
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

@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]

N = int(readline())
X = np.array(list(read().rstrip()), np.int64) - ord('0')
ans = main(X)
print('\n'.join(map(str, ans.tolist())))

Solution (Python):
N = int(input())
X = input()
MAX = 2 * (10 ** 5) + 1

base = [0] * (MAX+1)
for num in range(1, MAX+1):
  cnt = 0
  bin_num = bin(num)[2:]
  for j in bin_num:
    cnt += int(j)
  p = num % cnt
  base[num] = base[p]+1

xcnt = 0
for i in range(N):
  xcnt += int(X[i])


X0to1 = [1] * N
X0to1sum = 0
k = 1
for i in range(N-1, -1, -1):
  X0to1[i] = k % (xcnt+1)
  X0to1sum += X0to1[i] * int(X[i])
  k = (k*2)%(xcnt+1)


  

X1to0 = [0] * N
X1to0sum = 0
if(xcnt >= 2):
  k = 1
  for i in range(N-1, -1, -1):
    X1to0[i] = k % (xcnt-1)
    X1to0sum += X1to0[i] * int(X[i])
    k = (k*2)%(xcnt-1)


for i in range(N):
  if(X[i] == '0'):
    print(base[(X0to1sum + X0to1[i])%(xcnt+1)]+1)
  else:
    if(xcnt >= 2):
      print(base[(X1to0sum - X1to0[i])%(xcnt-1)]+1)
    else:
      print(0)

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



Xp = sum(X)
        

a = 0
b = 0


for i, x in enumerate(X):
    i_reverse = N-i-1
    if Xp > 1:
        a = (a + x * pow(2, i_reverse, Xp-1)) % (Xp-1)
    b = (b + x * pow(2, i_reverse, Xp+1)) % (Xp+1)
    
    




for i in range(N):
    i_reverse = N-i-1
    if Xp > 1:
        m = ([a, b][X[i]==0] + [-1, 1][X[i]==0] * pow(2, i_reverse, [Xp-1, Xp+1][X[i]==0])) % [Xp-1, Xp+1][X[i]==0]
    else:
        if X[i]==0:
            m = (b + pow(2, i_reverse, Xp+1)) % (Xp+1)
        else:
            print(0)
            continue
    count = 1
    
    
    while m > 0:
        p = sum([int(c) for c in str(bin(m)[2:])])
        m = m % p
        count += 1
    print(count)

Solution (Python):
def main():
    n_ansl = [0]*(2*(10**5))
    for i in range(1,2*(10**5)):
    
        cnt = 0
        one_cnt = bin(i).count("1")
        rem = i
        while rem != 0:
            one_cnt = bin(rem).count("1")
            rem = rem%one_cnt   
            cnt += 1
        n_ansl[i] = cnt
 
    n = int(input())
    x = input()
    one_cnt = x.count('1')

    if one_cnt == 0:
        for i in range(n):
            print(1)
        exit()
    
    curr_2b = 1
    curr_2b_p = 1
    curr_2b_m = 1
    curr_sum = 0
    curr_sum_p1 = 0
    curr_sum_m1 = 0
    for i in range(n-1, -1, -1):
        if x[i] == '1':
            curr_sum += curr_2b
            curr_sum_p1 += curr_2b_p
            curr_sum_m1 += curr_2b_m
            curr_sum%=one_cnt
            curr_sum_p1%=(one_cnt+1)
            if one_cnt > 1:
                curr_sum_m1%=(one_cnt-1)
        curr_2b*=2
        curr_2b_p*=2
        curr_2b_m*=2
        curr_2b%=one_cnt
        curr_2b_p%=(one_cnt+1)
        if one_cnt > 1:
            curr_2b_m%=(one_cnt-1)
 
        
 
    curr_2b = 1
    curr_2b_p = 1
    curr_2b_m = 1
    ansl = [0]*(n)
    for i in range(n-1, -1, -1):
        if x[i] == '1':
            diff = (-1)*curr_2b_m
            if one_cnt > 1:
                ans = (curr_sum_m1 + diff)%(one_cnt-1)
                ansl[i] = n_ansl[ans]+1
            else:
                ansl[i] = 0
        else:
            diff = curr_2b_p
            ans = (curr_sum_p1 + diff)%(one_cnt+1)
            ansl[i] = (n_ansl[ans]+1)
        
        curr_2b*=2
        curr_2b_p*=2
        curr_2b_m*=2
        curr_2b%=one_cnt
        curr_2b_p%=(one_cnt+1)
        if one_cnt > 1:
            curr_2b_m%=(one_cnt-1)
 
 
    
    for a in ansl:
        print(a)
 
if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
x = input()
num = 0
count = 0
for i in range(n):
    if x[-(i+1)] == "1":
        num += 2**i
        count += 1

mod = [[0, 0] for _ in range(n)]
mod[0][0] = 1%(count-1) if count!=1 else 0
mod[0][1] = 1%(count+1)
for i in range(1, n):
    if mod[i-1][0] != 0:
        mod[i][0] = (mod[i-1][0]*2)%(count-1)
    if mod[i-1][1] != 0:
        mod[i][1] = (mod[i-1][1]*2)%(count+1)
mod1 = num%(count-1) if count!=1 else 0
mod2 = num%(count+1)

table = [0]*(2*10**5+10)
for i in range(2*10**5+10):
    _num = i
    while True:
        _count = 0
        for c in bin(_num):
            if c == "1":
                _count += 1
        if _num == 0:
            break
        _num %= _count
        table[i] += 1

ans = [0]*n
for i in range(n):
    if x[-(i+1)] == "1":
        _num = num-2**i
        if _num == 0:
            continue
        _num = (mod1-mod[i][0])%(count-1)
    else:
        _num = num+2**i
        _num = (mod2+mod[i][1])%(count+1)
    ans[i] = 1+table[_num]
for i in range(n):
    print(ans[-(i+1)])

Solution (Python):
N = int(input())
X = input()
B = X.count('1')


base_mod_1 = [1 for i in range(N)] 
if B > 1:
  base_mod_2 = [1 for i in range(N)] 

for i in range(1, N):
  base_mod_1[i] = (base_mod_1[i-1] * 2) % (B+1)
  if B > 1:
    base_mod_2[i] = (base_mod_2[i-1] * 2) % (B-1)

def num(A):
  b = 1
  r = 0
  for i in range(len(A)):
    r += b * int(A[-i-1])
    b *= 2
  return r

def f(n):
  global call
  call += 1
  bit = 0
  m = n
  while m > 0:
    if m % 2 == 1:
      bit += 1
    m //= 2
  next_n = n % bit
  if next_n > 0:
    f(next_n)

x = num(X)
x1 = x % (B+1)
if B > 1:
  x2 = x % (B-1)


for i in range(N):
  call = 0
  if X[i] == '0':
    y = (x1 + base_mod_1[-i-1]) % (B+1)
    R = B + 1
    call = 1
  else:
    if B > 1:
      y = (x2 - base_mod_2[-i-1]) % (B-1)
      R = B - 1
      call = 1
    else:
      y = 0

  if y > 0:
    f(y)
  print(call)

Solution (Python):
n = int(input())
x = list(input())
bits = sum(list(map(int, x)))
if bits == 0:
    for i in range(n):
        print(1)
    exit()
if bits == 1:
    if x[-1] == '1':
        for i in range(n-1):
            print(2)
        print(0)
    else:
        for i in range(n-1):
            if x[i] == '1':
                print(0)
            else:
                print(1)
        print(2)
    exit()


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



s_m = []
s_p = []


bits_m = bits - 1
bits_p = bits + 1
surp_m = int(x[0]) % bits_m
surp_p = int(x[0]) % bits_p

two_m = [1 % bits_m]
two_p = [1 % bits_p]
for i in range(1, n):
    surp_m = (2 * surp_m + int(x[i])) % bits_m
    surp_p = (2 * surp_p + int(x[i])) % bits_p
    two_m += [(two_m[i-1] * 2) % bits_m]
    two_p += [(two_p[i-1] * 2) % bits_p]

for i in range(n-1, -1, -1):
    s_m += [(surp_m - two_m[i]) % bits_m]
    s_p += [(surp_p + two_p[i]) % bits_p]

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


for i in range(n):
    if x[i] == '1':
        print(f[s_m[i]] + 1)
    else:
        print(f[s_p[i]] + 1)

Solution (Python):
import math
def main():

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

    memo = dict()
    memo[0] = 0
    for i in range(1, N+1):
        v = i
        cnt = 0
        while v > 0:
            cnt += v % 2
            v //= 2
        u = i % cnt
        memo[i] = memo[u] + 1

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

    if cnt == 1:
        mod_plus = []
        p = (1 % (cnt + 1))
        for i in range(0, N+1):
            mod_plus.append(p)
            p *= 2
            p %= (cnt + 1)

        v_plus = 0
        for i in range(N):
            if X[i] == '1':
                v_plus = mod_plus[N-1-i]
                break

        for i in range(N):
            if X[i] == '1':
                print(0)
            else:
                u_plus = mod_plus[N-1-i]
                v_plus = (v_plus + u_plus) % (cnt + 1)
                print(1 + memo[v_plus])

    else:
        mod_plus = []
        p = (1 % (cnt + 1))
        for i in range(0, N+1):
            mod_plus.append(p)
            p *= 2
            p %= (cnt + 1)

        mod_minus = []
        p = (1 % (cnt - 1))
        for i in range(0, N+1):
            mod_minus.append(p)
            p *= 2
            p %= (cnt - 1)

        v_plus = 0
        v_minus = 0
        for i in range(N):
            if X[i] == '1':
                v_plus += mod_plus[N-1-i]
                v_minus += mod_minus[N-1-i]
                v_plus %= (cnt + 1)
                v_minus += (cnt - 1)

        for i in range(N):
            if X[i] == '1':
                u = mod_minus[N-1-i]
                v = (v_minus - u) % (cnt - 1)
            else:
                div = cnt + 1
                u = mod_plus[N-1-i]
                v = (v_plus + u) % (cnt + 1)
            print(1 + memo[v])


if __name__ == '__main__':
    main()

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

x_1 = x.count('1')
flag = 0
if(x_1 == 0):
    flag = 1
if(x_1 == 1):
    flag = 2

data = [0 for i in range(n+1)]
data[0] = 0
for i in range(1,n+1):
    i_str = format(i,'b')
    ne = i % (i_str.count('1'))
    data[i] = data[ne] + 1

up = [0 for i in range(n)]
do = [0 for i in range(n)]

d = 1
upp = 0
for i in range(n):
    up[i] = d
    if(x[n-i-1] == '1'):
        upp += d
        upp %= (x_1+1)
    d *= 2
    d %= (x_1 + 1)
d = 1
dow = 0
if(flag == 0):
    for i in range(n):
        do[i] = d
        if(x[n-i-1] == '1'):
            dow += d
            dow %= (x_1-1)
        d *= 2
        d %= (x_1 - 1)


for i in range(n):
    if(x[i] == '0'):
        sam = upp + up[n-i-1]
        sam %= (x_1+1)
        print(data[sam]+1)
    elif(flag == 0):
        sam = dow - do[n-i-1]
        sam %= (x_1-1)
        print(data[sam]+1)
    elif(flag == 2):
        print('0')

Solution (Python):
n = int(input())
x = input()
COUNT = x.count('1')
mod1 = COUNT - 1
mod2 = COUNT + 1


mod = [[0, 0] for _ in range(n+1)]
mult = 1
if mod1 != 0:
    mod[0][0] = 1 % mod1
mod[0][1] = 1 % mod2
for i in range(1, n+1):
    if mod1 != 0:
        mod[i][0] = (mod[i-1][0] * (2 % mod1)) % mod1
    mod[i][1] = (mod[i-1][1] * (2 % mod2)) % mod2

all_mod1 = 0
all_mod2 = 0
for i in range(n):
    if x[i] == '1':
        if mod1 != 0:
            all_mod1 = (all_mod1 + mod[n-1-i][0])
        all_mod2 = (all_mod2 + mod[n-1-i][1])
if mod1 != 0:
    all_mod1 %= mod1
all_mod2 %= mod2

def popcount(idx):
    idx -= 1
    ret = 0
    if x[idx] == '1':
        if mod1 != 0:
            ret = (all_mod1 - mod[n-1-idx][0]) % mod1
        else:
            ret = -1
    else:
        ret = (all_mod2 + mod[n-1-idx][1]) % mod2
    return ret

bit_cnt_table = [0 for _ in range(n+1)]
bit_cnt_table[1] = 1
base = 0
i = 2
while i <= n:
    if i % (2 ** base) == 0:
        base += 1
    bit_cnt_table[i] = 1 + bit_cnt_table[i - 2**(base)]
    i += 1

def func(num):
    if bit_cnt_table[num] == 0:
        return 0
    return num % bit_cnt_table[num]

f = [-1 for _ in range(n+1)]
f[0] = 0
f[1] = 1
for i in range(2, n+1):
    tmp = func(i)
    f[i] = 1 + f[tmp]

ans = []
for i in range(1, n+1):
    p = popcount(i)
    if p == -1:
        ans_i = 0
    else:
        ans_i = 1 + f[p]
    
    ans.append(str(ans_i))
print("\n".join(ans))

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())
    X = readline().strip()
    p = X.count('1')

    power_down = [0] * N
    power_up = [0] * N
    power_down[0] = 1
    power_up[0] = 1
    for i in range(N - 1):
        if p > 1:
            power_down[i + 1] = power_down[i] * 2 % (p - 1)
        power_up[i + 1] = power_up[i] * 2 % (p + 1)

    base_down = base_up = 0
    for i in range(N):
        if X[i] == '1':
            if p > 1:
                base_down = (base_down + power_down[N - i - 1]) % (p - 1)
            base_up = (base_up + power_up[N - i - 1]) % (p + 1)

    ans = [1] * N
    for i in range(N):
        if p == 1 and X[i] == '1':
            ans[i] = 0
            continue

        if X[i] == '1':
            m = (base_down - power_down[N - i - 1]) % (p - 1)
            q = p - 1
        else:
            m = (base_up + power_up[N - i - 1]) % (p + 1)
            q = p + 1

        while m:
            ans[i] += 1
            q = bin(m).count('1')
            m %= q

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


if __name__ == '__main__':
    main()

Solution (Python):
def popcount(n):
    return bin(n).count("1")


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


n = int(input())

F = [f(i) for i in range(n + 2)]
x = input()
pcx = x.count("1")


a, b = 0, 0
if pcx == 1:
    for i in range(n):
        if x[i] == "1":
            b += pow(2, n - i - 1, pcx + 1)
            b %= (pcx + 1)
    for i in range(n):
        if x[i] == "1":
            print(0)
        else:
            print(1 + f((b + pow(2, n - i - 1, pcx + 1)) % (pcx + 1)))
    exit()

if pcx > 1:
    for i in range(n):
        if x[i] == "1":
            a += pow(2, n - i - 1, pcx - 1)
            a %= (pcx - 1)
            b += pow(2, n - i - 1, pcx + 1)
            b %= (pcx + 1)
else:
    for i in range(n):
        print(1)
    exit()
for i in range(n):
    if x[i] == "1":
        print(1 + f((a - pow(2, n - i - 1, pcx - 1)) % (pcx - 1)))
    else:
        print(1 + f((b + pow(2, n - i - 1, pcx + 1)) % (pcx + 1)))

Solution (Python):
import math

A = [0]*200001
for i in range(18):
    for j in range(2**i,2**(i+1)):
        if j <= 200000:
            A[j] = i + 1

def bii(x):
    a = A[x]
    o = [0]*a
    for i in range(a):
        o[i] = x % 2
        x //= 2
    return o

def f(x):
    bi = bii(x)
    popcount = sum(bi)
    a = x % popcount
    if a == 0:
        return 1
    else:
        return f(a)+1

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

popc = sum(X)
D = dict()
E = dict()
for j in [popc-1,popc+1]:
    E[j] = 0
    D[j] = [0]*N
    b = 1
    if j == 0:
        continue
    for i in range(N):
        D[j][i] = b
        E[j] += X[i] * b
        E[j] %= j
        b *= 2
        b %= j

aaaa = []
for i in range(N):
    an = X[-(i+1)]
    bb = 1 - 2 * an
    
    
    if popc == 1 and an == 1:
        print(0)
        continue
    j = popc + bb
    su = (E[j] + bb * D[j][-(i+1)] + j) % j
    if su == 0:
        print(1)
        continue
    else:
        print(f(su)+1)
        continue

Solution (Python):
def power(x, y, p) : 
    if y==0: return 1%p
    res = 1     
  
    
    
    x = x % p  
      
    if (x == 0) : 
        return 0
  
    while (y > 0) : 
          
        
        
        if ((y & 1) == 1) : 
            res = (res * x) % p 
  
        
        y = y >> 1      
        x = (x * x) % p 
    return res  

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

n=int(input())
s=input()
ones = s.count('1')
a = ones -1
b = ones
c = ones+1
moda = modb = modc = 0
for i in range(n-1,-1,-1):
	pos = n-1-i
	if s[i]=='1':
		if a>0 : moda = (moda + power(2, pos, a) ) %a
		modc = (modc + power(2, pos, c) ) %c

for i in range(n):
	if s[i] == '0': 
		add = power(2, n-1-i, c)
		ans = (modc + add) % c
		
		print(F[ans]+1)
	else: 
		if a<=0: print(0)
		else:
			sub = power(2, n-1-i, a)
			ans = (moda - sub) % a
			print(F[ans]+1)

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))



def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) 
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    


MOD = 10**9 + 7
INF = 2**31  

from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  
from functools import reduce








N = a_int()
X = read()[:-1]
px0 = X.count('1')
px0p = px0 + 1
px0n = (px0 - 1) if px0 != 1 else -1

x0n = 0
x0 = 0
x0p = 0

for i, bit in enu(reversed(X)):
    if bit == '1':
        x0n += pow(2, i, px0n)
        x0n %= px0n
        x0 += pow(2, i, px0)
        x0 %= px0
        x0p += pow(2, i, px0p)
        x0p %= px0p


x0 = [x0n, x0, x0p]  

first_mod = []  
for i, bit in enumerate(reversed(X)):
    if bit == '0':
        
        first_mod.append((x0[2] + pow(2, i, px0p)) % (px0p))
    elif bit == '1':
        if px0n != -1:
            first_mod.append((x0[0] - pow(2, i, px0n)) % (px0n))
        else:
            first_mod.append(-1)





ans = []
for x in reversed(first_mod):
    if x == -1:
        ans.append(0)
        continue
    cnt = 1  
    while x != 0:
        x = x % bin(x).count('1')
        cnt += 1
    ans.append(cnt)


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

Solution (Python):
def f(n):
    cnt = 0
    while n:
        buf = n
        pc = 0
        while buf:
            pc += buf%2
            buf //= 2
        n = n%pc
        cnt += 1
    return cnt

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

v1, v2 = 0, 0
cnt = X.count("1")
for i, j in enumerate(X[::-1]):
    if j=="1":
        v1 += pow(2, i, cnt+1)
        v1 %= (cnt+1)

        if cnt>1:
            v2 += pow(2, i, cnt-1)
            v2 %= (cnt-1)

for i in range(N):
    p = N-i-1
    buf = 0
    c2 = 0
    if X[i]=="0":
        c2 = cnt+1
        buf = (v1+pow(2, p, c2))%c2
        print(f(buf)+1)
    else:
        c2 = cnt-1
        if c2>0:
            buf = (v2-pow(2, p, c2))%c2
            print(f(buf)+1)
        else:
            print(0)

Solution (Python):
def main():
  N = int(input())
  s = str(input())
  num_bit = 0
  for i in range(N):
    if s[i] == '1':
      num_bit += 1
  ans_1 = 0
  for i in range(N):
    if s[N-1-i] == "1":
      ans_1 += pow(2, i, num_bit+1)
      ans_1 %= (num_bit+1)
  ans_2 = 0
  if num_bit > 1:
    for i in range(N):
      if s[N-1-i] == "1":
        ans_2 += pow(2, i, num_bit-1)
        ans_2 %= (num_bit-1)
  ans = [0] * N
  for i in range(N):
    ans_temp = 1
    if s[N-1-i] == '1':
      if num_bit == 1:
        f = 0
        ans_temp = 0
      else:
        f = ans_2 - pow(2, i, num_bit-1)
        f %= (num_bit-1)
    else:
      f = ans_1 + pow(2, i, num_bit + 1)
      f %= (num_bit+1)
    while f != 0:
      f = f % bin(f).count('1')
      ans_temp += 1
    ans[N-1-i] = ans_temp
  for i in ans:
    print(i)
  
if __name__ == "__main__":
  main()

Solution (Python):
from itertools import repeat

import random

def bitcount(x):
	result = 0
	while x > 0:
		if x % 2 == 1: 
			result += 1

		x //= 2
	return result

ff = {}

def f(x):
	count = 0
	while x != 0:
		count += 1
		
		x = x % bitcount(x)	
	return count

def brute(s):
	chars = [char for char in s]

	result = []

	def flip(i):
		if chars[i] == '1':
			chars[i] = '0'
		else:
			chars[i] = '1'

	for i in range(len(s)):
		flip(i)
		x = int("".join(chars), 2)
		result.append(f(x))
		flip(i)

	return result

def solve(n, s):
	bc = s.count('1')

	x = 0
	pow = 1
	for bit in reversed(range(n)):
		if s[bit] == '1':
			x += pow
		pow *= 2


	mods1 = []
	mod1, mod2 = bc + 1, bc - 1
	mods2 = []

	

	pow = 1
	mods1.append(pow % mod1)

	if mod2 != 0:
		mods2.append(pow % mod2)

	for bit in range(1, n):
		if mod1 != 0:
			mods1.append(2 * mods1[bit - 1] % mod1)
		if mod2 != 0:
			mods2.append(2 * mods2[bit - 1] % mod2)

	mods1 = list(reversed(mods1))
	mods2 = list(reversed(mods2))

	
	

	x_mod_1 = 0
	x_mod_2 = 0
	for bit in reversed(range(n)):
		if s[bit] == '1':		
			x_mod_1 = (x_mod_1 + mods1[bit]) % mod1
			if mod2 != 0:
				x_mod_2 = (x_mod_2 + mods2[bit]) % mod2

	

	result = []

	for bit in reversed(range(n)):
		if s[bit] == '0':
			new_mod = (x_mod_1 + mods1[bit]) % mod1
			result.append(1 + f(new_mod))

		else:
			if mod2 == 0:
				result.append(0)
			else:				
				new_mod = (x_mod_2 - mods2[bit]) % mod2
				
				result.append(1 + f(new_mod))

	return list(reversed(result))



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


sol = solve(n, s)
for x in sol:
	print(x)

Solution (Python):
N = int(input())
X = input()
def popcount(n):
    tmp = n
    cnt = 0
    while tmp:
        cnt += tmp % 2
        tmp >>= 1
    return cnt
def f(n):
    tmp = n
    cnt = 0
    while tmp:
        cnt += 1
        ff = popcount(tmp)
        tmp %= ff
    return cnt
cnt = 0
LL = [0 for _ in range(200010)]
for i in range(200010):
    LL[i] = f(i)
for i in range(N):
    cnt += X[i] == '1'
A = [1 for _ in range(N+1)]
B = [1 for _ in range(N+1)]
for i in range(N):
    A[i+1] = A[i] << 1
    A[i+1] %= cnt + 1
for i in range(N):
    B[i+1] = B[i] << 1
    if cnt > 1:
        B[i+1] %= cnt - 1
    else:
        B[i+1] = 0
S = 0
T = 0
for i in range(N):
    S += X[i] == '1'
    T += X[i] == '1'
    if i != N-1:
        S <<= 1
        T <<= 1
        S %= cnt + 1
        if cnt > 1:
            T %= cnt - 1
        else:
            T = 0
C = [S for _ in range(N)]
D = [T for _ in range(N)]
for i in range(N):
    if X[i] == '1':
        D[i] -= B[N-1-i]
        if cnt == 1:
            print(0)
        else:
            D[i] %= cnt - 1
            print(LL[D[i]]+1)
    else:
        C[i] += A[N-1-i]
        C[i] %= cnt + 1
        print(LL[C[i]]+1)

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): 
	return list(map(int,input().split()))
def m(): 
	return map(int,input().split())
def onem(): 
	return int(input())
def s(x): 
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): 
	return " ".join(map(str,x))
def max2(x): 
	return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""





n = onem()

po = input()

co = po.count("1")

num = [0,0]

for i in range(n):
	num[0] *= 2
	num[1] *= 2
	if po[i] == "1":
		num[0] += 1
		num[1] += 1
	if co > 1:
			num[0] %= co-1
	num[1] %= co+1
	

for i in range(n):
	if po[i] == "0":
		coco = co + 1

		ima = num[1] + pow(2,(n-1-i),coco)
		ima %= coco
		coco = format(ima,"b").count("1")
		count = 1
		while True:
			if ima == 0:
				break
			else:
				ima %= coco
				count += 1
				"""
				if ima >= 10**5 + 1:
					coco = dp[ima-(10**5 + 1)]
				else:
				"""
				coco = format(ima,"b").count("1")

	else:
		coco = co - 1
		if coco == 0:
			count = 0
			print(count)
			continue
		ima = num[0] - pow(2,(n-1-i),coco)
		ima %= coco
		count = 1
		coco = format(ima,"b").count("1")
		while True:
			if ima == 0:
				break
			else:
				ima %= coco
				count += 1
				"""
				if ima >= 10**5 + 1:
					coco = dp[ima-(10**5 + 1)]
				else:
				"""
				coco = format(ima,"b").count("1")
	print(count)