Problem:


Score : 400 points

Problem Statement

Let \mathrm{popcount}(n) be the number of 1s 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



Sample input:
3
011


Sample output:
2
1
1

Submission status: Runtime Error

Solution code:
def p(x):
  a = list(bin(x))
  return a.count('1')

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

N = int(input())
X = input()
##最初の操作だけこっちでやっちゃう
cnt = X.count('1')
x = int(X,2)
a = x % (cnt + 1)
b = x % (cnt - 1)

t = [0] * N ##tは一回X[i]をp(X[i])で割った余りで置き換えた配列
for i in range(N):
  if X[i] == '0':
    t[i] = (a + 2**(N-i-1) % (cnt + 1)) % (cnt + 1)
  if X[i] == '1':
    if cnt == 1:
      t[i] = 0
      continue
    t[i] = (b - 2**(N-i-1) % (cnt - 1)) % (cnt - 1)  
  

result = []
for j in range(N):
  result.append(1 + f(t[j]))
print(*result, sep='\n')

Submission status: Runtime Error

Solution code:

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


def popcount(n):
    ans = 0
    for i in n:
        if i == "1":
            ans += 1

    return ans

def f(n):
    cnt = 0
    while n != 0:
        n = n % pop_memo[n]
        cnt += 1

    return cnt

pop_memo = [0] * 220001
for i in range(22001):
    pop_memo[i] = bin(i).count("1")

pop_origin = popcount(X)
pop_one = pop_origin - 1
pop_zero = pop_origin + 1

for i in range(N):

    if X[i] == "1":
        tem = int(X, 2) - pow(2, N - i -1)
        n = tem % pop_one
        print(f(n) + 1)

    elif X[i] == "0":
        tem = int(X, 2) + (2  ** (N - i - 1))
        n = tem % pop_zero
        print(f(n) + 1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(300000)

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI0(): return map(lambda s: int(s) - 1, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
def LMI0(): return list(map(lambda s: int(s) - 1, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N = I()
X = input()

popcount = X.count('1')

def mod(popcount):
    if popcount == 1:
        return [0] * N
    a = []
    base = 1
    for i in range(N):
        if i == 0:
            a.append(1)
        else:
            base = base * 2 % popcount
            a.append(base)
    return a

def summod(modX, popcount):
    a = 0
    for i, x in enumerate(modX):
        if X[i] == '1':
            a = (a + x) % popcount
    return a

modXm = list(reversed(mod(popcount - 1)))
modXp = list(reversed(mod(popcount + 1)))

s_modXm = summod(modXm, popcount - 1)
s_modXp = summod(modXp, popcount + 1)

for i in range(N):
    if X[i] == '1':
        if popcount - 1 == 0:
            print(0)
            continue
        if popcount - 1 == 1:
            print(1)
            continue
        modX, s, m = modXm, s_modXm, popcount - 1
        s = (s + m - modX[i]) % m
    else:
        modX, s, m = modXp, s_modXp, popcount + 1
        s = (s + modX[i]) % m
    ans = 1
    while True:
        pc = bin(s).count('1')
        if pc == 0:
            break
        s = s % pc
        ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
def popcount(i):
    return(bin(i).count("1"))
N = int(input())
X = input()
xi = int("0b" + X,0)
xp = popcount(xi)
M = 2 * (10 ** 5) + 1
l = [0] * M
for i in range(1,M):
    pcnt = popcount(i)
    m = i % pcnt
    l[i] = 1 + l[m]
for n in range(N):
    s = X[n]
    i = int(s)
    ns = str(i ^ 1)
    np = xp
    if i == 1:
        np -= 1
    else:
        np += 1
    Xi = "0b" + X[0:n] + ns + X[n+1:N]
    xi = int(Xi,0)
    m = xi % np
    print(l[m] + 1)

Submission status: Runtime Error

Solution code:

import sys
sys.setrecursionlimit(10**6)

n = int(input())
x = input()
xi = int('0b' + x, 2)
xc = x.count("1")

if xc == 0:
  for _ in range(n):
    print(1)
  exit()

xip = xi % (xc+1)
xim = xi % (xc-1)

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

for i in range(n):
  if x[i] == "0":
    # y = xip + (pow(2, n-i-1, )%(xc+1))
    y = xip + pow(2, n-i-1, xc+1)
    y = y % (xc+1)
  elif xc == 1:
    print(0)
    continue
  else:
    # y = xim - (pow(2, n-i-1)%(xc-1))
    y = xim - pow(2, n-i-1, xc-1)
    y = y % (xc-1)

  print(f(y)+1)

Submission status: Runtime Error

Solution code:

import sys
sys.setrecursionlimit(10**6)

n = int(input())
x = input()
xi = int('0b' + x, 2)
xc = x.count("1")

xip = xi % (xc+1)
xim = xi % (xc-1)

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

for i in range(n):
  if x[i] == "0":
    # y = xip + (pow(2, n-i-1, )%(xc+1))
    y = xip + pow(2, n-i-1, xc+1)
    y = y % (xc+1)
  elif xc == 1:
    print(0)
    continue
  else:
    # y = xim - (pow(2, n-i-1)%(xc-1))
    y = xim - pow(2, n-i-1, xc-1)
    y = y % (xc-1)

  print(f(y)+1)

Submission status: Runtime Error

Solution code:

import sys
sys.setrecursionlimit(10**6)

n = int(input())
x = input()
xi = int('0b' + x, 2)
xc = x.count("1")

xip = xi % (xc+1)
xim = xi % (xc-1)

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

for i in range(n):
  if x[i] == "0":
    # y = xip + (pow(2, n-i-1, )%(xc+1))
    y = xip + pow(2, n-i-1, xc+1)
    y = y % (xc+1)
  else:
    # y = xim - (pow(2, n-i-1)%(xc-1))
    y = xim - pow(2, n-i-1, xc-1)
    y = y % (xc-1)

  print(f(y)+1)

Submission status: Runtime Error

Solution code:

n = int(input())
x = input()
xi = int('0b' + x, 2)
xc = x.count("1")

xip = xi % (xc+1)
xim = xi % (xc-1)

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

for i in range(n):
  if x[i] == "0":
    y = xip + (pow(2, n-i-1)%(xc+1))
    y = y % (xc+1)
  else:
    y = xim - (pow(2, n-i-1)%(xc-1))
    y = y % (xc-1)

  print(f(y)+1)

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
import sys
sys.setrecursionlimit(10**7)
if n==1:
  print(1 if x=='1' else 0)
  exit()
def pc(x):
  a=bin(x)[2:]
  return a.count('1')
def func(x):
  if x==0:
    return 0
  else:
    return func(x%pc(x))+1
pcx=x.count('1')
if pcx==0:
  for _ in range(n):
    print(1)
else:
  x0,x1=0,0
  
  for i in range(n):
    if x[i]=='1':
      #if pcx!=1:
      x0+=pow(2,n-1-i,pcx-1)
      x0%=pcx-1
      x1+=pow(2,n-1-i,pcx+1)
      x1%=pcx+1
  for i in range(n):
    ans=0
    if x[i]=='1':
      if pcx==1:
        print(0)
      else:
        xx=x0-pow(2,n-1-i,pcx-1)
        xx%=pcx-1
        print(func(xx)+1)
    else:
      xx=x1+pow(2,n-1-i,pcx+1)
      xx%=pcx+1
      print(func(xx)+1)

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
import sys
sys.setrecursionlimit(10**7)

def pc(x):
  a=bin(x)[2:]
  return a.count('1')
def func(x):
  if x==0:
    return 0
  else:
    return func(x%pc(x))+1
pcx=x.count('1')
x0,x1=0,0
for i in range(n):
  if x[i]=='1':
    x0+=pow(2,n-1-i,pcx-1)
    x0%=pcx-1
    x1+=pow(2,n-1-i,pcx+1)
    x1%=pcx+1
for i in range(n):
  ans=0
  if x[i]=='1':
    xx=x0-pow(2,n-1-i,pcx-1)
    xx%=pcx-1
    print(func(xx)+1)
  else:
    xx=x1+pow(2,n-1-i,pcx+1)
    xx%=pcx+1
    print(func(xx)+1)

Submission status: Runtime Error

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

def pc(x):
  a=bin(x)[2:]
  return a.count('1')
def func(x):
  if x==0:
    return 0
  else:
    return func(x%pc(x))+1
pcx=x.count('1')
x0,x1=0,0
for i in range(n):
  if x[i]=='1':
    x0+=pow(2,n-1-i,pcx-1)
    x0%=pcx-1
    x1+=pow(2,n-1-i,pcx+1)
    x1%=pcx+1
for i in range(n):
  ans=0
  if x[i]=='1':
    xx=x0-pow(2,n-1-i,pcx-1)
    xx%=pcx-1
    print(func(xx)+1)
  else:
    xx=x1+pow(2,n-1-i,pcx+1)
    xx%=pcx+1
    print(func(xx)+1)

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(input())
X = str(input())
num_one = X.count("1")

dp = [-1] * N
dp[0] = 0
def dfs(n):
    if dp[n] == -1:
        dp[n] = 1 + dfs(n % bin(n).count('1'))
    return dp[n]

num_one = X.count("1")
bool_arr = np.array([True if X[N-i-1] == "1" else False for i in range(N)])
zero_ver = np.array([pow(2,  i, num_one + 1) for i in range(N)])
zero_ver_sum = sum(zero_ver[bool_arr])

one_ver = -1
flag = False
if num_one != 1:
    one_ver = np.array([pow(2,  i, num_one - 1) for i in range(N)])
else:
    flag = True
one_ver_sum = sum(one_ver[bool_arr])
for i in range(1,N+1):
    start = 0
    if bool_arr[N-i] == False:
        start = (zero_ver_sum + pow(2, N - i, num_one + 1)) % (num_one + 1)
        print(dfs(start)+1)
    else:
        if flag:
            print(0)
        else:
            start = (one_ver_sum - pow(2, N - i, num_one - 1))  %  (num_one - 1)
            print(dfs(start)+1)

Submission status: Runtime Error

Solution code:
def f(x):
  if p(x) == 0:
    return 0
  if x % p(x) == 0:
    return 1
  return f(x%p(x)) + 1

def p(x):
  a = list(bin(x))
  return a.count('1')
  
N = int(input())
X = input()
##最初の操作だけこっちでやっちゃう
cnt = X.count('1')
x = int(X,2)
a = x % (cnt + 1)
b = x % (cnt - 1)

t = [0] * N ##tは一回X[i]をp(X[i])で割った余りで置き換えた配列
for i in range(N):
  if X[i] == '0':
    t[i] = (a + 2**i % (cnt + 1)) % (cnt + 1)
  if X[i] == '1':
    t[i] = (b - 2**i % (cnt - 1)) % (cnt - 1)  
  

result = []
for j in range(N):
  result.append(1 + f(t[j]))
print(*result, sep='\n')

Submission status: Runtime Error

Solution code:
#4
N = int(input())
X = list(input() )#リストで取得
x = [0]*N

#Xiが入った配列xを作成
for i in range(N):
    initialized_X = X
    if initialized_X[i] == '0':
        initialized_X[i] = '1'
    else:
        initialized_X[i] = '0'
    x[i] = "".join(initialized_X )
    #初期化
    if initialized_X[i] == '0':
        initialized_X[i] = '1'
    else:
        initialized_X[i] = '0'

#xi　について調べる
count = 0
for xi in x:
    count = 0
    while xi != 0:
        pop_count = xi.count('1')

        xi = int(xi, 2) % pop_count
        if xi != 0:
            xi = format(xi, 'b') #2２進数に変換
        count += 1 
    print(count)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

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

def popcount(x):
    """

    """
    z = x.count("1")
    
    return int(x, 2) % z

for i in range(N):
    if X[i] == "1":
        c = "0"
    else:
        c = "1"
    x = X[:i] + c + X[i + 1:]
    ans = 0
    while True:
        ans += 1
        x = bin(popcount(x))[2:]
        if x == "0":
            break
    print(ans)

Submission status: Runtime Error

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

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f


n=int(input())
x=input()
num=int(x,2)
cnt=popcount(num)
mod1,mod2=num%(cnt+1),num%(cnt-1)

for i in range(n):
    if x[i]=="0":
        ans=(mod1+pow(2,n-i-1,cnt+1))%(cnt+1)
    elif x[i]=="1" and cnt<=1:
        print(0)
        continue
    else:
        ans=(mod2-pow(2,n-i-1,cnt-1))%(cnt-1)
    point=1
    while ans!=0:
        ans %=popcount(ans)
        point +=1
    print(point)

Submission status: Runtime Error

Solution code:
N=int(input())
X=input()
def popcount(x):
    return sum([i == '1' for i in bin(x)])
def func(n):
  ans=1
  x=n
  while x!=0:

    x=x%popcount(x)
    ans+=1
  return ans
base=popcount(int(X,2))
value=int(X, 2)
for i in range(N):
  kari=base
  tmpv=value
  if X[i]=="0":
    tmpv+=2**(N-i-1)
    kari+=1
  else:
    tmpv-=2**(N-i-1)
    kari-=1
  tmp=tmpv%kari
  print(func(tmp))

Submission status: Runtime Error

Solution code:
N = int(input())
bin_X = input()
int_X = int(bin_X, 2)

pop_cnt_1 = 0
for i in bin_X:
    if i == '1':
        pop_cnt_1 += 1
pop_cnt_0 = pop_cnt_1 + 1
pop_cnt_1 = pop_cnt_1 - 1

int_X_0 = int_X % pop_cnt_0
int_X_1 = int_X % pop_cnt_1

def pop_cnt(n):
    c = 0
    for i in bin(n):
        if i == '1':
            c += 1
    return c

for i in range(N):
    if bin_X == '0':
        print(0)
        continue
    
    z = 2 ** (N-i-1)
    if bin_X[i] == '1':
        n = (int_X-z)%pop_cnt_1
    else:
        n = (int_X+z)%pop_cnt_0
   
    cnt = 1
    while n != 0:
        n = n % pop_cnt(n)
        cnt += 1
    print(cnt)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# D

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
sys.setrecursionlimit(1000000)

N = int(input())
X = input()[:-1][::-1]
origin = 0
for i in range(len(X)):
    origin += int(X[i]) * (2**i)

c_plus = bin(origin).count('1') + 1
plus = origin % c_plus

c_minus = bin(origin).count('1') - 1
minus = origin % c_minus

dic = defaultdict(int)

def calc_(n):
    global dic
    if n == 0:
        return 0
    if dic[n]>0:
        return dic[n]
    else:
        n_next = n % bin(n).count('1')
    temp = calc_(n_next)
    dic[n] = temp+1

    return temp + 1


for i in list(range(N))[::-1]:
    ans = 1
    if origin >> i & 1 == 1:
        # val = origin - 2 ** i
        val = minus - (2**i % c_minus)
        val = val % c_minus
    else:
        # val = origin + 2 ** i
        val = plus + (2**i % c_plus)
        val = val % c_plus

    while val >0:
        val = val % bin(val).count('1')
        ans += 1

    print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import sys
from functools import lru_cache

sys.setrecursionlimit(4100000)

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


def main():
    N = int(input())
    X = input()
    O = int(X, 2)
    pc = X.count('1')
    Y = list(X)
    ans = [0] * N
    pre = 1
    for i in range(N-1,-1,-1):
        if Y[i] == '1':
            tmp = (O - pre) % (pc - 1)
        else:
            tmp = (O + pre) % (pc + 1)
        ans[i] = f(tmp) + 1
        pre *= 2

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


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:

n = int(input())
#x = list(input())
x = int('0b' + input(), 2)
tmp = []
z = []


def popcount(nn):
    bin_str = bin(nn)
    counter = 0
    for i in range(len(bin_str)):
        if(bin_str[i] == '1'):
            counter += 1
    return(counter)


for i in range(n):
    rev_bit = (0b1 << i)
    tmp.append(x ^ rev_bit)

z = tmp[::-1]

for i in range(len(z)):
    counter__ = 1
    z2 = z[i]
    while(z2%popcount(z2) != 0):
        counter__ += 1
        z2 = z2%popcount(z2)

    print(counter__)

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
pc1 = X.count('1')-1
pc0= X.count('1')+1
ans = [0]*N
X_num = int(X,2)

for i in range(N):
  X_list = list(X)
  if X_list[i]=='1':
    pc = pc1
  else:
    pc = pc0
  a = (X_num % pc + 2**(N-i-1) % pc) % pc
  a_str = format(a, 'b')
  X_list = list(a_str)
  count = 1
  while a!=0:
    s = ''.join(X_list)
    num_1 = s.count('1')
    s_10 = int(s,2)
    a = s_10 % num_1
    a_2 = bin(a)
    a_str = format(a, 'b')
    X_list = list(a_str)
    count += 1
  print(count)

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
pc1 = X.count('1')-1
pc0= X.count('1')+1
ans = [0]*N
X_num = int(X,2)

for i in range(N):
  X_list = list(X)
  if X_list[i]=='1':
    pc = pc1
  else:
    pc = pc0
  a = (X_num % pc + 2**i % pc) % pc
  a_str = format(a, 'b')
  X_list = list(a_str)
  count = 1
  while a!=0:
    s = ''.join(X_list)
    num_1 = s.count('1')
    s_10 = int(s,2)
    a = s_10 % num_1
    a_2 = bin(a)
    a_str = format(a, 'b')
    X_list = list(a_str)
    count += 1
  print(count)

Submission status: Runtime Error

Solution code:
def popcount(x):
    xb = bin(x)
    return xb.count("1")
def solve(x, count_1):
    temp = x %count_1
    if(temp == 0):
        return 1
    else:
        return 1 + solve(temp, popcount(temp))
n = int(input())
x = input()
x_b = int(x, 2)
mod = x.count("1")
xm1 = x_b %(mod+1) 
xm2 = x_b %(mod-1)
for i in range(n):
    if(x[i] == "0"):
        mi = (((pow(2, n-1-i, mod+1) + xm1) % (mod+1)))
        if(mi == 0):
            print(1)
        else:
            print(1 + solve(mi, popcount(mi)))
    else:
        mi = ((xm2-pow(2, n-1-i, mod-1)) % (mod-1))
        if((x_b - xm2 == 0)):
            print(0)
        elif(mi == 0):
            print(1)
        else:
            print(1 + solve(mi, popcount(mi)))

Submission status: Runtime Error

Solution code:
N = int(input())
X = int(str(input()), 2)
X_bin = format(X, '0'+str(N)+'b')
popcount = [X_bin.count('1') - 1, X_bin.count('1') + 1]
mod = [X % popcount[0], X % popcount[1]]

ans = [0] * N
dp = [0] * 2 ** 18
for i in range(N):
    if X_bin[i] == '1':
        if X_bin.count('1') == 1:
            print(0)
            continue
        n = mod[0] - (2 ** (N - 1 - i)) % popcount[0]
        if n == popcount[0]:
            print(1)
            continue
        elif n < 0:
            n += popcount[0]
    else:
        n = mod[1] + (2 ** (N - 1 - i)) % popcount[1]
        if n == popcount[1]:
            print(1)
            continue

    tmp = []
    ans[i] += 1
    while n != 0:
        if dp[n]:
            ans[i] += dp[n]
            break
        tmp.append(n)
        n = n % format(n, '0' + str(N) + 'b').count('1')
        ans[i] += 1
    for j in range(len(tmp)):
        dp[tmp[j]] = ans[i] - 1 - j

    print(ans[i])

Submission status: Runtime Error

Solution code:
def popcount(x):
    xb = bin(x)
    return xb.count("1")
def solve(x, count_1):
    temp = x %count_1
    if(temp == 0):
        return 1
    else:
        return 1 + solve(temp, popcount(temp))
n = int(input())
x = input()
x_b = int(x, 2)
mod = x.count("1")
xm1 = x_b %(mod+1) 
xm2 = x_b %(mod-1)
for i in range(n):
    if(x[i] == "0"):
        mi = (((2**(n-1-i))%(mod+1) + xm1) % (mod+1))
        if(mi == 0):
            print(1)
        else:
            print(1 + solve(mi, popcount(mi)))
    else:
        mi = ((xm2-(2**(n-1-i))%(mod-1)) % (mod-1))
        if((x_b - xm2 == 0)):
            print(0)
        elif(mi == 0):
            print(1)
        else:
            print(1 + solve(mi, popcount(mi)))

Submission status: Runtime Error

Solution code:
def popcount(x):
    xb = bin(x)
    mod = 0
    for i in list(xb):
        if(i == "1"):
            mod+=1
    return mod
def solve(x, count_1):
    temp = x %count_1
    if(temp == 0):
        return 1
    else:
        return 1 + solve(temp, popcount(temp))
n = int(input())
x = input()
x_b = int(x, 2)
mod = 0
for i in list(x):
    if(i == "1"):
        mod+=1
for i in range(n):
    if(x[i] == "0"):
        mi = ((x_b+ 2**(n-1-i))%(mod+1))
        if(mi == 0):
            print(1)
        else:
            print(1 + solve(mi, popcount(mi)))
    else:
        mi = ((x_b- 2**(n-1-i))%(mod-1))
        if(mi == 0):
            print(1)
        else:
            print(1 + solve(mi, popcount(mi)))

Submission status: Runtime Error

Solution code:
def popcount(num):
    ans = 0
    while num:
        if num % 2 == 1:
            ans += 1
        num //= 2
    return ans


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

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

tmp4p = int(X, 2) % (popcount_X+1)
tmp4m = int(X, 2) % (popcount_X-1)

for i in range(N):
    bit = X[i]

    f = 0
    if (popcount_X == 1 and bit == "1"):
        print(f)
        continue
    
    if bit == "1":
        nxt = ( tmp4m - pow(2, N-i-1, (popcount_X-1))  + (popcount_X-1) ) % (popcount_X-1)
    else:
        nxt = ( tmp4p + pow(2, N-i-1, (popcount_X+1))  ) % (popcount_X+1)

    f += 1
    while nxt:
        pc = popcount(nxt)
        nxt = nxt % pc
        f += 1
    
    print(f)

Submission status: Runtime Error

Solution code:
def popcount(num):
    ans = 0
    while num:
        if num % 2 == 1:
            ans += 1
        num //= 2
    return ans


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

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

tmp4p = int(X, 2) % (popcount_X+1)
tmp4m = int(X, 2) % (popcount_X-1)

for i in range(N):
    bit = X[i]

    f = 0
    if (popcount_X == 1 and bit == 1):
        print(f)
        continue
    
    if bit == "1":
        nxt = ( tmp4m - pow(2, N-i-1, (popcount_X-1))  + (popcount_X-1) ) % (popcount_X-1)
    else:
        nxt = ( tmp4p + pow(2, N-i-1, (popcount_X+1))  ) % (popcount_X+1)

    f += 1
    while nxt:
        pc = popcount(nxt)
        nxt = nxt % pc
        f += 1
    
    print(f)

Submission status: Runtime Error

Solution code:
def popcount(num):
    ans = 0
    while num:
        if num % 2 == 1:
            ans += 1
        num //= 2
    return ans

def first_popcount(X_i, pc):
    # bin_pc = ""
    # while pc:
    #     bin_pc = bin_pc + str(pc%2)
    #     pc //= 2
    
    # ans = 0
    # while 1:
    #     if len(X_i) <= len(bin_pc) and int(X_i, 2) < int(bin_pc, 2):
    #         break

    # return ans
    return int(X_i, 2) % pc

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

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

tmp4p = first_popcount(X, popcount_X+1)
tmp4m = first_popcount(X, popcount_X-1)

for i in range(N):
    bit = X[i]

    f = 0
    if (popcount_X == 1 and bit == 1):
        print(f)
        continue
    
    if bit == "1":
        nxt = ( tmp4m - pow(2, N-i-1, (popcount_X-1))  + (popcount_X-1) ) % (popcount_X-1)
    else:
        nxt = ( tmp4p + pow(2, N-i-1, (popcount_X+1))  ) % (popcount_X+1)

    f += 1
    while nxt:
        pc = popcount(nxt)
        nxt = nxt % pc
        f += 1
    
    print(f)

Submission status: Runtime Error

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

count = x.count("1")

mod1 = 0 # 1少ない
mod2 = 0 # 1多い

#　初回の各桁のbitを反転させた場合のmod結果を格納するリスト
mod1_list = [0]*n
mod2_list = [0]*n

now1 = 1

x = x[::-1]

# mod1の計算
for i in range(n):
    mod1_list[i] = now1
    if x[i] == "1":
        mod1 += now1%(count+1)
    now1 *= 2
    now1 %= (count+1)

mod1 %= (count+1)

now2 = 1

# mod2の計算
if count >= 3:
    for i in range(n):
        mod2_list[i] = now2
        if x[i] == "1":
            mod2 += now2%(count-1)
        now2 *= 2
        now2 %= (count-1)
    
    mod2 %= (count-1)

mod1_list = mod1_list[::-1]
mod2_list = mod2_list[::-1]
x = x[::-1]

for i in range(n):
    total = 1
    if x[i] == "1":
        now = mod2-mod2_list[i]
        now %= (count-1)
    else:
        now = mod1+mod1_list[i]
        now %= (count+1)
        
    while now != 0:
        now = now%(bin(now).count("1"))
        total += 1

    print(total)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.read
from collections import defaultdict
def main():
    n = int(input())
    x = list(input())
    # n=1だと0除算ありえるため対処。
    if n == 1:
        if x[0] == '1':
            print(0)
        else:
            print(1)
        sys.exit()
    # xの10進数換算と１の数カウント。
    x10 = int("".join(x), 2)
    xcount1 = x.count('1')
    # 2**i(mod 1の数)をケースごとに用意する。
    mod2plus = [0] * n
    mod2plus[0] = (1 % (xcount1+1))
    mod2plus[1] = (2 % (xcount1+1))
    for j1 in range(2, n):
        mod2plus[j1] = (mod2plus[j1 - 1] * 2) % (xcount1+1)
    mod2minus = [0] * n
    mod2minus[0] = (1 % (xcount1-1))
    mod2minus[1] = (2 % (xcount1-1))
    for j1 in range(2, n):
        mod2minus[j1] = (mod2minus[j1 - 1] * 2) % (xcount1-1)
    # x(mod 1の数)をケースごとに用意する。
    modx_plus = x10 % (xcount1 + 1)
    if xcount1 == 1:
        modx_minus = x10
    else:
        modx_minus = x10 % (xcount1 - 1)
    memo = defaultdict(int)
    for i1 in range(n):
        if x[i1] == '1':
            if xcount1 == 1:
                print(0)
                continue
            else:
                x3 = modx_minus - mod2minus[n - 1 - i1]
                if x3 < 0:
                    x3 += (xcount1 - 1)
                elif x3 > (xcount1 - 1):
                    x3 -= (xcount1 - 1)
                elif x3 == (xcount1 - 1):
                    x3 = 0
        else:
            x3 = modx_plus + mod2plus[n - 1 - i1]
            if x3 < 0:
                x3 += (xcount1 + 1)
            elif x3 > (xcount1 + 1):
                x3 -= (xcount1 + 1)
            elif x3 == (xcount1 + 1):
                x3 = 0
        r = 1
        while x3:
            r += 1
            if memo[x3] == 0:
                p = bin(x3).count('1')
                if p == 0:
                    break
                else:
                    memo[x3] = p
                    x3 = x3 % p
            else:
                x3 = x3 % memo[x3]
        print(r)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:

def f(n,cnt):
  c = 0
  ncp = n
  while ncp > 0:
    c += (ncp & 0b01)
    ncp=ncp>>1
  if n % c == 0 :
    return cnt
  else:
    return f(n % c,cnt + 1)
   


N = int(input())

X = int(input(),2)

for i in range(N,0,-1):
	mask = 0b01 << (i-1)
	if (X & mask) > 0 :
		Xi = X - mask
	else:
		Xi = X | mask
	print(f(Xi,1))

Submission status: Runtime Error

Solution code:
n = int(input())
s = input()
a = 0
for i in range(n):
    if s[i] == '1':
        a += int(pow(2, n - i - 1))
for i in range(n):
    add = int(pow(2, n - i - 1))
    if s[i] == '1':
        add *= -1
    copy = a + add
    x = bin(copy).count('1')
    cnt = 1
    while copy % x != 0:
        copy %= x
        x = bin(copy).count('1')
        cnt += 1
    print(cnt)

Submission status: Runtime Error

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

if X == "1":
  print(1)
  return True

if X == "0":
  print(0)
  return True

base_1_count = X.count("1")
if base_1_count == 0:
  for _ in range(N):
    print(1)
  return True

X_int = int(X, 2)
X_int_p = X_int%(base_1_count + 1)

# RE 対策
if base_1_count == 1:
  for i in range(N):
    if X[i] == "1":
      print(0)
    else:
      Xi = X_int_p
      count = 1
      while Xi != 0:
        Xi %= bin(Xi).count("1")
        count += 1
      print(count)
  return True

X_int_m = X_int%(base_1_count - 1)
for i in range(N):
  # 初期値計算を高速にやる
  if X[i] == "1":
    temp_1_count = base_1_count-1
    pow_2 = 2**(N-i-1)%(base_1_count-1)
    if X_int_m < pow_2:
      Xi = (X_int-2**(N-i-1))%(base_1_count-1)
    else:
      Xi = X_int_m - pow_2
  else:
    temp_1_count = base_1_count+1
    Xi = X_int_p + 2**(N-i-1)%(base_1_count+1)

  # print("1_c={0}".format(temp_1_count))
  if temp_1_count == Xi:
    print(1)
    continue

  count = 1
  while Xi != 0:
    num_of_1 = bin(Xi).count("1")
    # print("Xi={0}".format(Xi))
    Xi %= num_of_1
    count += 1
  print(count)

Submission status: Runtime Error

Solution code:
#関数リスト
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def bin2dec(target):
    out = 0
    index = 0
    while target > 0:
        out += (target % 10) * 2**index
        target //= 10
        index += 1
    return out

n = I()
x = I()

#２進数にした際の桁数
keta = [0] * (2**n+1)
keta[1] = 1
keta[2] = 1
for i in range(2, 2**n+1):
    keta[i] = (i & 1) + keta[i>>1]

#操作回数
d = [0] * (2**n+1)
d[1] = 1
d[2] = 1
d[3] = 2
for i in range(2, 2**n+1):
    amari = i % keta[i]
    d[i] = d[amari] + 1

num = bin2dec(x)
result = []


for i in range(0,n):
    temp1 = num >> i
    temp2 = num
    #bit反転
    if temp1 & 1 == 0:
        temp2 += 2**i
    else:
        temp2 += 2**i - 2**(i+1)
    result.append(d[temp2])

for i in reversed(result):
    print(i)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.read
from collections import defaultdict
def main():
    n = int(input())
    x = list(input())
    if n == 1:
        if x[0] == '1':
            print(0)
        else:
            print(1)
        sys.exit()

    x10 = int("".join(x), 2)
    xcount1 = x.count('1')
    mod2plus = [0] * n
    mod2plus[0] = (1 % (xcount1+1))
    mod2plus[1] = (2 % (xcount1+1))
    for j1 in range(2, n):
        mod2plus[j1] = (mod2plus[j1 - 1] * 2) % (xcount1+1)
    mod2minus = [0] * n
    mod2minus[0] = (1 % (xcount1-1))
    mod2minus[1] = (2 % (xcount1-1))
    for j1 in range(2, n):
        mod2minus[j1] = (mod2minus[j1 - 1] * 2) % (xcount1-1)
    modx_plus = x10 % (xcount1 + 1)
    if xcount1 == 1:
        modx_minus = x10
    else:
        modx_minus = x10 % (xcount1 - 1)
    memo = defaultdict(int)
    for i1 in range(n):
        if x[i1] == '1':
            if xcount1 == 1:
                print(0)
                continue
            else:
                x3 = modx_minus - mod2minus[n - 1 - i1]
                if x3 < 0:
                    x3 += (xcount1 - 1)
                elif x3 > (xcount1 - 1):
                    x3 -= (xcount1 - 1)
                elif x3 == (xcount1 - 1):
                    x3 = 0
        else:
            x3 = modx_plus + mod2plus[n - 1 - i1]
            if x3 < 0:
                x3 += (xcount1 + 1)
            elif x3 > (xcount1 + 1):
                x3 -= (xcount1 + 1)
            elif x3 == (xcount1 + 1):
                x3 = 0
        r = 1
        while x3:
            r += 1
            if memo[x3] == 0:
                p = bin(x3).count('1')
                memo[x3] = p
                x3 = x3 % p
            else:
                x3 = x3 % memo[x3]
        print(r)

if __name__ == '__main__':
    main()