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()
x = X[::-1]
one = X.count('1')
up = 0
down = 0
for i in range(N):
    up += (int(x[i]) * pow(2,i,one+1) % (one+1))
    up %= one+1
    if one > 1:
        down += (int(x[i]) * pow(2,i,one-1) % (one-1))
        down %= one-1

def f(ud,one):
    if one <= 0:
        return 0
    else:
        if ud == 0:
            return 1

        cnt = 0
        while ud != 0:
            ud = ud % one
            one = format(ud,'b').count('1')
            cnt += 1
        return cnt



for i in range(len(X)):
    if X[i] == '1':
        if one > 1:
            print(f((down - pow(2,(len(X)-1) - i, one-1)) % (one-1),one-1))
        
        else:
            print(0)

    else:
        print(f((up + pow(2,(len(X)-1) - i, one+1)) % (one+1),one+1))

Solution (Python):

N = int(input())
X = input()
X_10 = int(X, 2)
popcount_X = X.count("1")
popcount_X_plus = popcount_X + 1
popcount_X_minus = popcount_X - 1
f_plus = X_10 % popcount_X_plus
f_minus = X_10 % popcount_X_minus if popcount_X_minus != 0 else 0

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

def f(n):
  if n == 0:
    return 0
  return n % popcount(n)

for i in range(N):
  j = N - (i + 1)
  n = 0
  ans = 1
  
  if X[i] == '0':

    n = (f_plus + pow(2, j, popcount_X_plus)) % popcount_X_plus
  else:
    if popcount_X_minus == 0:
      print(0)
      continue
    else:

      n = (f_minus - pow(2, j, popcount_X_minus) + popcount_X_minus) % popcount_X_minus
  
  while n > 0:
    n = f(n)
    ans += 1
  print(ans)

Solution (Python):

N = int(input())
X = input()
X_10 = int(X, 2)
popcount_X = X.count("1")
popcount_X_plus = popcount_X + 1
popcount_X_minus = popcount_X - 1
f_plus = X_10 % popcount_X_plus
f_minus = X_10 % popcount_X_minus if popcount_X_minus != 0 else 0

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

def f(n):
  if n == 0:
    return 0
  return n % popcount(n)

for i in range(N):
  j = N - (i + 1)
  n = 0
  ans = 1
  
  if X[i] == '0':

    n = (f_plus + pow(2, j, popcount_X_plus)) % popcount_X_plus
  else:
    if popcount_X_minus == 0:
      print(0)
      continue
    else:

      n = (f_minus - pow(2, j, popcount_X_minus) + popcount_X_minus) % popcount_X_minus
  
  while n > 0:
    n = f(n)
    ans += 1
  print(ans)

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


def f(n):
    if n == 0:
        return 0
    return f(n % pop_count(n)) + 1


N = int(input())
X = list(map(int, input()))
X_m = 0
X_p = 0
pop_X = X.count(1)
for i in range(N):
    if X[i] == 0:
        continue
    X_p += pow(2, N - i - 1, pop_X + 1)
    X_p %= pop_X + 1
    if pop_X > 1:
        X_m += pow(2, N - i - 1, pop_X - 1)
        X_m %= pop_X - 1

for i in range(N):
    ans = 1
    if X[i] == 0:
        ans += f((X_p + pow(2, N - i - 1, pop_X + 1)) % (pop_X + 1))
    elif pop_X > 1:
        ans += f((X_m - pow(2, N - i - 1, pop_X - 1)) % (pop_X - 1))
    else:
        ans = 0
    print(ans)

Solution (Python):
def solve():
  N = int(input())
  X = input()
  bl = X.count('1')
  bitp = 0
  for i in range(N):
    bitp += int(X[i])*pow(2,N-1-i,bl+1)
    bitp %= bl+1
  bitm = 0
  if bl>1:
    for i in range(N):
      bitm += int(X[i])*pow(2,N-1-i,bl-1)
      bitm %= bl-1
  
  ans = [0]*N
  dp = [0]*(N+1)
  for i in range(1,N+1):
    dp[i] = dp[i%(bin(i).count('1'))]+1
  for i in range(N):
    if X[i]=='1':
      bl1 = bl-1
      if bl1==0:
        ans[i] = 0
        continue
      bit1 = bitm - pow(2,N-1-i,bl1)
    else:
      bl1 = bl+1
      bit1 = bitp + pow(2,N-1-i,bl1)
    ans[i] = dp[bit1%bl1]+1
  return ans
print(*solve(),sep='\n')

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

ansl = [0]*n
for i in range(1,n):
    ans = 0
    num = i
    while True:
        pc = bin(num).count("1")
        num %= pc
        ans += 1
        if num == 0: break
    ansl[i] = ans

pc = bin(x).count("1")
if pc == 0:
    for i in range(n):
        print(1)
        exit()


next_num = x%pc
next_num_p1 = x%(pc+1)
if pc != 1:
    next_num_m1 = x%(pc-1)
else:
    next_num_m1 = None

for i in range(n):
    bit = (1<<(n-1-i))
    if xs[i] == '0':
        num = (next_num_p1 + pow(2,n-1-i,pc+1)) % (pc+1)
        ans = ansl[num] + 1
    else:
        if pc != 1:
            num = (next_num_m1 - pow(2,n-1-i,pc-1)) % (pc-1)
            ans = ansl[num] + 1
        else:
            ans = 0
    print(ans)

Solution (Python):
def solve():
  N = int(input())
  X = input()
  bl = X.count('1')
  bitp = 0
  for i in range(N):
    bitp += int(X[i])*pow(2,N-1-i,bl+1)
    bitp %= bl+1
  bitm = 0
  if bl>1:
    for i in range(N):
      bitm += int(X[i])*pow(2,N-1-i,bl-1)
      bitm %= bl-1
  
  ans = [0]*N
  dp = [0]*(N+1)
  for i in range(1,N+1):
    dp[i] = dp[i%(bin(i).count('1'))]+1
  for i in range(N):
    if X[i]=='1':
      bl1 = bl-1
      if bl1==0:
        ans[i] = 0
        continue
      bit1 = bitm - pow(2,N-1-i,bl1)
    else:
      bl1 = bl+1
      bit1 = bitp + pow(2,N-1-i,bl1)
    ans[i] = dp[bit1%bl1]+1
  return ans
print(*solve(),sep='\n')

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


def power(a, n, mod):
    bi=str(format(n,"b")) 
    res=1
    for i in range(len(bi)):
        res=(res*res) %mod
        if bi[i]=="1":
            res=(res*a) %mod
    return res

p = x.count('1')

if p == 0:
    ans = [1]*n
    for i in range(n):
        print(ans[i])
    exit()

if p == 1:
    if x[-1] != '1':
        ans = [1]*n
        for i in range(n):
            if x[i] == '1':
                ans[i] = 0
        ans[-1] = 2
    else:
        ans = [2]*n
        ans[-1] = 0
    for i in range(n):
        print(ans[i])
    exit()

x = list(x)
x.reverse()
temp1 = 0
for i in range(len(x)):
    temp1 += int(x[i])*power(2, i, p+1)
temp1 %= (p+1)

temp2 = 0
for i in range(len(x)):
    temp2 += int(x[i])*power(2, i, p-1)
temp2 %= (p-1)

ans = [0]*n

for i in range(n):
    if x[n-1-i] == '1':
        temp = temp2-power(2, n-1-i, p-1)
        c = p-1
    else:
        temp = temp1+power(2, n-1-i, p+1)
        c = p+1
    temp %= c
    
    cnt = 1
    while temp != 0:
        x_ = format(temp, 'b')
        c = x_.count('1')
        x_ = list(x_)
        x_.reverse()
        temp = 0
        for j in range(len(x_)):
            temp += int(x_[j])*power(2, j, c)
        temp %= c
        cnt += 1
    
    ans[i] = cnt

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

Solution (Python):

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

mod0 = X.count("1") + 1
mod1 = X.count("1") - 1

full0 = 0
full1 = 0
for i in range(N):
    if X[i] == "1":
        full0 = (full0 + pow(2, N - i - 1, mod0)) % mod0
        if mod1 > 0:
            full1 = (full1 + pow(2, N - i - 1, mod1)) % mod1

ans = [0] * N
for i in range(N):
    if X[i] == "0":
        cur = (full0 + pow(2, N - i - 1, mod0)) % mod0
        res = 1
    else:
        if mod1 > 0:
            cur = (full1 - pow(2, N - i - 1, mod1)) % mod1
            res = 1
        else:
            cur = 0
            res = 0

    while cur > 0:
        cur %= bin(cur).count("1")
        res += 1
    ans[i] = res

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

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

cnt1 = X.count("1")
p_cnt = cnt1+1
m_cnt = cnt1-1
p_amari = val%(cnt1+1)
if cnt1-1 != 0:
  m_amari = val%(cnt1-1)
else:
  m_amari = 0

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

for i in range(N):
  ans = 0
  if X[i] == "0":
    amari = p_amari + pow(2,N-i-1,p_cnt)
    amari %= p_cnt
    ans += 1
  else:
    if cnt1-1==0:
      print(0)
      continue
    amari = m_amari - pow(2,N-i-1,m_cnt)
    amari %= m_cnt
    ans += 1

  ans += f(amari)
  print(ans)

Solution (Python):
def solve(n,m):
  if not n:return 1
  n%=m
  return-~solve(n,bin(n).count('1'))
n=int(input())
s=input()
a=int(s,2)
*x,=map(int,s)
h=sum(x)
try:a,b=a%(h-1),a%(h+1)
except:b=a%(h+1)
for i in range(n):
  if x[i]:
    if not h-1:
      print(0)
      continue
    x[i]=0
    t=(a-pow(2,~i+n,h-1))%(h-1)
  else:
    x[i]=1
    t=(b+pow(2,~i+n,h+1))%(h+1)
  r=solve(t,bin(t).count('1'))
  x[i]^=1
  print(r)

Solution (Python):
from functools import*
@lru_cache(None)
def solve(n,m):
  if not n:return 1
  n%=m
  return-~solve(n,bin(n).count('1'))
n=int(input())
s=input()
a=int(s,2)
*x,=map(int,s)
h=sum(x)
try:a,b=a%(h-1),a%(h+1)
except:b=a%(h+1)
for i in range(n):
  if x[i]:
    if not h-1:
      print(0)
      continue
    x[i]=0
    t=(a-pow(2,~i+n,h-1))%(h-1)
  else:
    x[i]=1
    t=(b+pow(2,~i+n,h+1))%(h+1)
  r=solve(t,bin(t).count('1'))
  x[i]^=1
  print(r)

Solution (Python):
from functools import*
@lru_cache(None)
def solve(n,m):
  if not n:return 1
  n%=m
  return-~solve(n,bin(n).count('1'))
n=int(input())
s=input()
a=int(s,2)
*x,=map(int,s)
h=sum(x)
try:a,b=a%(h-1),a%(h+1)
except:b=a%(h+1)
for i in range(n):
  if x[i]:
    if not h-1:
      print(0)
      continue
    x[i]=0
    t=(a-pow(2,~i+n,h-1))%(h-1)
  else:
    x[i]=1
    t=(b+pow(2,~i+n,h+1))%(h+1)
  r=solve(t,bin(t).count('1'))
  x[i]^=1
  print(r)

Solution (Python):
from collections import defaultdict
n,x = open(0).read().split()
n = int(n)
cnt = x.count('1') 
digits = list(map(int, list(x)))
x = int(x, 2)

d = defaultdict(int)
d[0] = 0
def calc(m):
    if m not in d:
        nxt = m % bin(m).count('1')
        d[m] = calc(nxt) + 1
    return d[m]

mmod = cnt - 1
pmod = cnt + 1

if mmod:
    mx = x % mmod
px = x % pmod

mbase = 1
pbase = 1

ans = []
while digits:
    digit = digits.pop()
    
    if digit and not mmod:
        ans.append(0)
    else:
        if digit:
            nx = (mx - mbase)%mmod
        else:
            nx = (px + pbase)%pmod
        ans.append(calc(nx) + 1)

    if mmod > 0:
        mbase = (mbase * 2) % mmod
    pbase = (pbase * 2) % pmod

while ans:
    print(ans.pop())

Solution (Python):
from collections import defaultdict
n,x = open(0).read().split()
n = int(n)
cnt = x.count('1') 
digits = list(map(int, list(x)))
x = int(x, 2)

d = defaultdict(int)
d[0] = 0
def calc(m):
    if m not in d:
        nxt = m % bin(m).count('1')
        d[m] = calc(nxt) + 1
    return d[m]

mmod = cnt - 1
pmod = cnt + 1

if mmod > 0:
    mx = x % mmod
px = x % pmod

mbase = 1
pbase = 1

ans = []
while digits:
    digit = digits.pop()
    
    if digit and mmod <= 0:
        ans.append(0)
    else:
        if digit:
            nx = (mx - mbase)%mmod
        else:
            nx = (px + pbase)%pmod
        ans.append(calc(nx) + 1)

    if mmod > 0:
        mbase = (mbase * 2) % mmod
    pbase = (pbase * 2) % pmod

while ans:
    print(ans.pop())

Solution (Python):
from sys import exit
from collections import defaultdict
n,x = open(0).read().split()
n = int(n)
cnt = x.count('1') 
digits = list(map(int, list(x)))
x = int(x, 2)

d = defaultdict(int)
d[0] = 0
def calc(m):
    if m not in d:
        nxt = m % bin(m).count('1')
        d[m] = calc(nxt) + 1
    return d[m]

if n == 1:
    print(calc(x^1))
    exit()

mmod = cnt - 1
pmod = cnt + 1

if mmod > 0:
    mx = x % mmod
px = x % pmod

mbase = 1
pbase = 1

ans = []
while digits:
    digit = digits.pop()
    
    if digit and mmod <= 0:
        ans.append(0)
    else:
        if digit:
            nx = (mx - mbase)%mmod
        else:
            nx = (px + pbase)%pmod
        ans.append(calc(nx) + 1)

    if mmod > 0:
        mbase = (mbase * 2) % mmod
    pbase = (pbase * 2) % pmod

while ans:
    print(ans.pop())

Solution (Python):
def count1(c):
  cnt = 0
  while c != 0:
    if c % 2 == 1:
      cnt += 1
    c //= 2
  return cnt
n = int(input())
x = input()
y = int(x, 2)
z = list(x).count('1')
l = []
a = y % (z + 1)
if z > 1:
  l2 = []
  b = y % (z - 1)
for i in range(n):
  l.append(pow(2, n - i - 1, z + 1))
  if z > 1:
    l2.append(pow(2, n - i - 1, z - 1))
for i in range(n):
  if x[i] == '0':
    c = a + l[i]
    c %= z + 1
  elif z == 1 and x[i] == '1':
    print(0)
    continue
  else:
    c = b - l2[i]
    c %= z - 1
  cnt = 1
  while c != 0:
    d = count1(c)
    c %= d
    cnt += 1
  print(cnt)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)

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


if pc == 0:
    print(*[1]*N, sep='\n')
    exit()
elif pc == 1:
    if int(X, 2) == 1:
        for i in range(N-1):
            print(2)
        print(0)
        exit()
    else:
        for i in range(N):
            if i == N-1:
                print(2)
            elif X[i] == '0':
                print(1)
            else:
                print(0)
        exit()

mod_plus_1, mod_minus_1 = 0, 0
for i in range(N):
    mod_plus_1 = (mod_plus_1*2+int(X[i])) % (pc+1)
    mod_minus_1 = (mod_minus_1*2+int(X[i])) % (pc-1)


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


mods_p1, mods_m1 = [1 % (pc+1)], [1 % (pc-1)]
for i in range(N-1):
    mods_p1.append(mods_p1[-1]*2 % (pc+1))
    mods_m1.append(mods_m1[-1]*2 % (pc-1))
mods_p1 = mods_p1[::-1]
mods_m1 = mods_m1[::-1]


for i in range(N):
    if X[i] == '0':
        x = mod_plus_1 + mods_p1[i]
        x %= (pc+1)
    else:
        x = mod_minus_1 - mods_m1[i]
        x %= (pc-1)

    if x == 0:
        print(1)
    else:
        print(f(x)+1)

Solution (Python):
N = int(input())
X = input()
pc = X.count("1")

if pc == 1:
    if X[-1] == "0":
        for i, s in enumerate(X):
            if i == N - 1:
                print(2)
            elif s == "0":
                print(1)
            else:
                print(0)
    else:
        ans = [2] * (N - 1) + [0]
        print(*ans, sep="\n")
    exit()


m01 = 0
m10 = 0
for i, s in enumerate(X[::-1]):
    if s == "1":
        m01 += pow(2, i, pc + 1)
        m01 %= pc + 1
        m10 += pow(2, i, pc - 1)
        m10 %= pc - 1


memo = [-1] * 200005


def pop_count(T):
    T = (T & 0x55555555) + ((T >> 1) & 0x55555555)
    T = (T & 0x33333333) + ((T >> 2) & 0x33333333)
    T = (T & 0x0F0F0F0F) + ((T >> 4) & 0x0F0F0F0F)
    T = (T & 0x00FF00FF) + ((T >> 8) & 0x00FF00FF)
    T = (T & 0x0000FFFF) + ((T >> 16) & 0x0000FFFF)
    return T


def F(n):
    if memo[n] != -1:
        return memo[n]
    if n == 0:
        return 0
    memo[n] = F(n % pop_count(n)) + 1
    return memo[n]


ans = [0] * N
for i, s in enumerate(X[::-1]):
    if s == "0":
        m = m01
        m += pow(2, i, pc+1)
        m %= pc + 1
    else:
        m = m10
        m -= pow(2, i, pc-1)
        m %= pc - 1
    ans[i] = F(m) + 1

print(*ans[::-1], sep="\n")

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

N = int(input())
X = input()
pc = X.count("1")

if pc == 1:
    if X[-1] == "0":
        for i, s in enumerate(X):
            if i == N - 1:
                print(2)
            elif s == "0":
                print(1)
            else:
                print(0)
    else:
        ans = [2] * (N - 1) + [0]
        print(*ans, sep="\n")
    exit()


m01 = 0
m10 = 0
b01 = 1
b10 = 1
for i, s in enumerate(X[::-1]):
    if s == "1":
        m01 += b01
        m01 %= pc + 1
        m10 += b10
        m10 %= pc - 1
    b01 *= 2
    b01 %= pc + 1
    b10 *= 2
    b10 %= pc - 1


def pop_count(T):
    T = (T & 0x55555555) + ((T >> 1) & 0x55555555)
    T = (T & 0x33333333) + ((T >> 2) & 0x33333333)
    T = (T & 0x0F0F0F0F) + ((T >> 4) & 0x0F0F0F0F)
    T = (T & 0x00FF00FF) + ((T >> 8) & 0x00FF00FF)
    T = (T & 0x0000FFFF) + ((T >> 16) & 0x0000FFFF)
    return T


memo = [0] * (N + 10)
for i in range(1, N + 10):
    p = pop_count(i)
    memo[i] = memo[i % p] + 1


ans = [0] * N
b01 = 1
b10 = 1
for i, s in enumerate(X[::-1]):
    if s == "0":
        m = m01
        m += b01
        m %= pc + 1
    else:
        m = m10
        m -= b10
        m %= pc - 1
    ans[i] = memo[m] + 1
    b01 *= 2
    b01 %= pc + 1
    b10 *= 2
    b10 %= pc - 1

print(*ans[::-1], sep="\n")

Solution (Python):
def g(x):
  S=format(x,"22b")
  cnt=0
  for i in range(20):
    if S[-1-i]=="1":
      cnt=cnt+1
  return x%cnt

n=int(input())
X=input()
a=0
for i in range(n):
  if X[i]=="1":
    a=a+1

if a==0:
  for i in range(n):
    print(1)
  exit()
if a==1:
  if X[-1]=="1":
    for i in range(n-1):
      print(2)
    print(0)
    exit()
  else:
    for i in range(n-1):
      if X[i]=="1":
        print(0)
      else:
        print(1)
    print(2)
    exit()
D=[0]*n
E=[0]*n
D[0]=1%(a-1)
E[0]=1%(a+1)
b=int(X[-1])%(a-1)
c=int(X[-1])%(a+1)
for i in range(n-1):
  D[i+1]=(D[i]*2)%(a-1)
  E[i+1]=(E[i]*2)%(a+1)
  if X[-2-i]=="1":
    b=(b+D[i+1])%(a-1)
    c=(c+E[i+1])%(a+1)
for i in range(n):
  if X[i]=="1":
    x=(b+a-1-D[-1-i])%(a-1)
    ans=1
    while x!=0:
      x=g(x)
      ans=ans+1
    print(ans)
  else:
    x=(c+E[-1-i])%(a+1)
    ans=1
    while x!=0:
      x=g(x)
      ans=ans+1
    print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    X = input()

    cnt_init = X.count("1")
    x_init = int(X, 2)
    a = x_init % (cnt_init + 1)
    if cnt_init - 1 != 0:
        b = x_init % (cnt_init - 1)

    for i in range(n):
        if X[i] == "0":
            cnt = cnt_init + 1
            x = (a + pow(2, (n - i - 1), cnt)) % cnt
            res = 1
        else:
            cnt = cnt_init - 1
            if cnt != 0:
                x = (b - pow(2, (n - i - 1), cnt)) % cnt
                res = 1
            else:
                x = 0
                res = 0

        while x:
            cnt = bin(x).count("1")
            x %= cnt
            res += 1
        print(res)


if __name__ == '__main__':
    resolve()

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

def popcount(x):
  return bin(x).count("1")
p=X.count('1')

pl=a%(p+1)
if p!=1:
  mi=a%(p-1)

def f(x):
  if x==0:
    return 1
  else:
    return f(x%popcount(x))+1

for i in range(N):
  if X[i]=='0':
    b=pl
    b+=pow(2,N-i-1,p+1)
    b%=p+1
  else:
    if p!=1:
      b=mi
      b-=pow(2,N-i-1,p-1)
      b%=p-1
    else:
      print(0)
      continue
  print(f(b))

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

def popcount(x):
  return bin(x).count("1")
p=X.count('1')

pl=a%(p+1)
if p!=1:
  mi=a%(p-1)

def f(x):
  if x==0:
    return 1
  else:
    return f(x%popcount(x))+1

for i in range(N):
  if X[i]=='0':
    b=pl
    b+=pow(2,N-i-1,p+1)
    b%=p+1
  else:
    if p!=1:
      b=mi
      b-=pow(2,N-i-1,p-1)
      b%=p-1
    else:
      print(0)
      continue
  print(f(b))

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n = I()
x = input()
cnt = x.count("1")
if cnt == 1:
    for i in range(n):
        if x[i] == "1":
            print(0)
        elif i == n - 1:
            print(2)
        else:
            print(1)
    exit()

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

xx = int(x, 2)
Y = xx % (cnt + 1)
Z = xx % (cnt - 1)
for i in range(n):
    if x[i] == '1':
        print(1 + f((Z - pow(2, n - i - 1, cnt - 1)) % (cnt - 1)))
    else:
        print(1 + f((Y + pow(2, n - i - 1, cnt + 1)) % (cnt + 1)))

Solution (Python):
N=int(input())
X=input()
Y=int(X,2)
Z=Y
C=X.count('1')
if C==1:
  for i in range(N):
    if X[i]=='1':
      print(0)
    elif i==N-1:
      print(2)
    else:
      print(1)
  exit()
Y,Z=Y%(C+1),Z%(C-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]=='1':
    print(1+f((Z-pow(2,N-i-1,C-1))%(C-1)))
  else:
    print(1+f((Y+pow(2,N-i-1,C+1))%(C+1)))

Solution (Python):
n = int(input())
s = input()
x = [0] * n

def pcnt(x):
    return bin(x).count('1')

def f(x):
    if x == 0: return 0
    return f(x % pcnt(x)) + 1

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

pc = sum(x)
ans = [0] * n
for b in range(2):
    npc = pc
    if b == 0:
        npc += 1
    else:
        npc -= 1

    if npc <= 0: continue

    r0 = 0
    for i in range(n):
        r0 = (r0 * 2) % npc
        r0 += x[i]

    k = 1
    for i in range(n - 1, -1, -1):
        if x[i] == b:
            r = r0
            if b == 0:
                r = (r + k) % npc
            else:
                r = (r - k + npc) % npc
            ans[i] = f(r) + 1
        k = (k * 2) % npc

for i in ans:
    print(i)

Solution (Python):
n = int(input())
s = input()
x = [0] * n

def pcnt(x):
    return bin(x).count('1')

def f(x):
    if x == 0: return 0
    return f(x % pcnt(x)) + 1

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

pc = sum(x)
ans = [0] * n
for b in range(2):
    npc = pc
    if b == 0:
        npc += 1
    else:
        npc -= 1

    if npc <= 0: continue

    r0 = 0
    for i in range(n):
        r0 = (r0 * 2) % npc
        r0 += x[i]

    k = 1
    for i in range(n - 1, -1, -1):
        if x[i] == b:
            r = r0
            if b == 0:
                r = (r + k) % npc
            else:
                r = (r - k + npc) % npc
            ans[i] = f(r) + 1
        k = (k * 2) % npc

for i in ans:
    print(i)

Solution (Python):
n = int(input())
x = input()
original_pop_count = x.count('1')
one_pop_count = original_pop_count-1
zero_pop_count = original_pop_count+1

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

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


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

Solution (Python):
N=int(input())
X=input()
A=[0,1,1,2,1,2,1,2,1,2,1,2,1,2,2,3,1]

ppx=0

for i in range(N):
  if X[i]=="1":
    ppx+=1
if ppx<=1:
  ppxm1=1
else:
  ppxm1=ppx-1
Xmod=[0,0]
XmodP=[0]*N
XmodM=[0]*N
XmodP[0]=1%(ppx+1)
XmodM[0]=1%(ppxm1)
Xmod=[XmodP[0]*(X[-1]=="1"),XmodM[0]*(X[-1]=="1")]
for i in range(N-1):
  XmodP[i+1]=(XmodP[i]*2)%(ppx+1)
  XmodM[i+1]=(XmodM[i]*2)%(ppxm1)
  if X[-2-i]=="1":
    Xmod[0]=(Xmod[0]+XmodP[i+1])%(ppx+1)
    Xmod[1]=(Xmod[1]+XmodM[i+1])%(ppxm1)
for i in range(N):
  if X[i]=="0":
    Xm=(Xmod[0]+XmodP[-1-i])%(ppx+1)
  else:
    Xm=(Xmod[1]-XmodM[-1-i])%(ppxm1)
  if ppx==1 and X[i]=="1":
    print(0)
  elif Xm==0:
    print(1)
  else:
    px=0
    temp=Xm
    while temp>0:
      if temp%2==1:
        px+=1
        temp=(temp-1)/2
      else:
        temp=temp/2
    p=Xm%px
    print(A[p]+2)

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



X_int = int(X_bin, 2)  


def calc_bin_cnt(next_int):
    if next_int == 0:
        return 0
    next_bin = bin(next_int)[2:]
    
    cnt = 0
    for i in next_bin:
        if i == '1':
            cnt += 1
    return cnt


def calc_ans(next_int, cnt=None):
    if next_cnt == 0:
        return 0
    if next_int == 0:
        return 1
    if cnt is None:
        cnt = calc_bin_cnt(next_int)
    next_int = next_int % cnt
    if next_int > 0:
        ans = calc_ans(next_int) + 1
    else:
        ans = 1
    return ans


X_cnt = calc_bin_cnt(X_int)
f_p = X_int % (X_cnt+1)
if X_cnt-1 == 0:
    f_m = 0
else:
    f_m = X_int % (X_cnt-1)
for i in range(N):
    if X_bin[i] == '1':
        next_cnt = X_cnt - 1
        if next_cnt == 0:
            next_int = 0
        else:
            next_int = f_m - pow(2, (N-i-1), next_cnt)  
    else:
        next_cnt = X_cnt + 1
        next_int = f_p + pow(2, (N-i-1), next_cnt)
    print(calc_ans(next_int, next_cnt))

Solution (Python):
def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c


N = int(input())
X = input()
pc = X.count('1')
if pc == 0:
    for i in range(N):
        print(1)
elif pc == 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)
else:
    modX1 = 0
    modX2 = 0
    Xi = [None] * N
    x1 = 1
    x2 = 1
    for i in range(N):
        if X[-i-1] == '1':
            Xi[-i-1] = x1
            modX1 = (modX1+x1) % (pc-1)
            modX2 = (modX2+x2) % (pc+1)
        else:
            Xi[-i-1] = x2
        x1 = x1 * 2 % (pc-1)
        x2 = x2 * 2 % (pc+1)
    for i in range(N):
        ans = 1
        x = (modX1 - Xi[i]) % (pc-1) if X[i] == '1' else (modX2 + Xi[i]) % (pc+1)
        while x != 0:
            x = x % popcnt(x)
            ans += 1
        print(ans)

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

N = int(input())
X = input()
Xint = int(X, 2)
Xcount = X.count("1")

"""
0010
1010 10(mod2) -> 0
i = n-1の時だけ +1
0011 -> 3 -> 1->0
0110 -> 6(mod2) -> 0
"""

if Xcount == 1:
    for i in range(N):
        if X[i] == "1":
            print(0)
        elif i == N-1:
            print(2)
        else:
            print(1)
    exit()

Modplus, Modminus = Xint%(Xcount+1), Xint%(Xcount-1)

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

for i in range(N):
    if X[i] == "1":
        print(1+f((Modminus-pow(2, N-1-i, Xcount-1))%(Xcount-1)))
    else:
        print(1+f((Modplus+pow(2, N-1-i, Xcount+1))%(Xcount+1)))

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

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

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

    dp = d+1
    dm = d-1
    mp = X % dp
    mm = X % dm if dm else 0
    
    

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

resolve()

Solution (Python):
n=int(input())
X=input()
x=X.count('1')
x_plus=int(X,2)%(x+1)
keta=n-1
if x==1:
    for i in range(n):
        tmp=0
        ans=1
        if X[i]=='0':
            tmp+=x_plus
            tmp+=pow(2,keta,(x+1))
            tmp%=(x+1)
            while tmp:
                tmp=tmp%(bin(tmp).count('1'))
                ans+=1
            print(ans)
        else:
            print(0)
        keta-=1
else:
    x_minus=int(X,2)%(x-1)
    for i in range(n):
        tmp=0
        ans=1
        if X[i]=='0':
            tmp+=x_plus
            tmp+=pow(2,keta,(x+1))
            tmp%=(x+1)
            while tmp:
                tmp=tmp%(bin(tmp).count('1'))
                ans+=1
            print(ans)
        else:
            tmp+=x_minus
            tmp-=pow(2,keta,(x-1))
            tmp%=(x-1)
            while tmp:
                tmp=tmp%(bin(tmp).count('1'))
                ans+=1
            print(ans)
        keta-=1

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


decX = int(strX,2)


pop_c = strX.count('1')


f_p = decX % (pop_c + 1)


if pop_c == 1:
  f_m = 0
else:
  f_m = decX % (pop_c - 1)

for i in range(0,N):
  if strX[i] == '0':
    pop_a = (f_p + pow(2,(N-1-i),(pop_c + 1))) % (pop_c + 1) 
    Ans = 1
    
  elif pop_c == 1:
    pop_a = 0
    Ans = 0
    
  else:
    pop_a = f_m - (pow(2,(N-1-i),(pop_c - 1)))
    if pop_a < 0:
      pop_a = pop_a + pop_c - 1
    Ans = 1
  
  while pop_a > 0:
    wkpop = bin(pop_a).count('1')
    pop_a = pop_a % wkpop
    Ans += 1
  
  print(Ans)

Solution (Python):

import math
from collections import defaultdict,deque
ml=lambda:map(int,input().split())
ll=lambda:list(map(int,input().split()))
ii=lambda:int(input())
ip=lambda:list(input())
ips=lambda:input().split()

"""========main code==============="""

def fast_expo(x,y,m):
    res=1
    while(y):
        if(y&1):
            res*=x
            res%=m
        x*=x
        x%=m
        y>>=1
    return res    

dp=defaultdict(int)
dp[1]=1
dp[2]=1
for i in range(3,200001):
    k=i
    cnt=0
    while(k):
        if(k%2): cnt+=1
        k>>=1
    dp[i]=dp[i%cnt]+1
n=ii()
a=ip()
a=a[::-1]
c=a.count('1')

min_1=0
max_1=0

for i in range(n):
    if(a[i]=='1'):
        if(c-1!=0):
            min_1+=fast_expo(2,i,c-1)
            min_1%=(c-1)
        max_1+=fast_expo(2,i,c+1)
        
        max_1%=(c+1)
    
ans=[]    

for i in range(n):
    if(a[i]=='1'):
        if(c-1==0):
            ans.append(0)
        else:    
            ans.append(dp[(min_1-fast_expo(2,i,c-1)+(c-1))%(c-1)]+1)
    else:
        ans.append(dp[(max_1+fast_expo(2,i,c+1))%(c+1)]+1)
ans=ans[::-1]
for i in ans:
    print(i)