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:
## coding: UTF-8
#N = 23
#S = '00110111001011011001110'
#N = 7
#S = '1010111'

N = int(input())
S = input()
P = int(S, 2)
#print(P)

def popcount(x):

    # 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


def count(N):
    warareru = N
    waru = popcount(N)
    counter = 0
    while warareru > 0:
        warareru = warareru % waru
        waru = popcount(warareru)
        counter += 1
    return counter


#前処理
first_popcount = popcount(P)
if(first_popcount == N):
    first_use_pop = [N-1, N-1]
elif(first_popcount == 0):
    first_use_pop = [1, 1]
else:
    first_use_pop = [first_popcount+1, first_popcount-1]

tmp_0 = 1
tmp_1 = 1
kakunou_0 = []
kakunou_1 = []
tmp_0 %= first_use_pop[0]
tmp_1 %= first_use_pop[1]
kakunou_0.append(tmp_0)
kakunou_1.append(tmp_1)
for i in range(0, 2*10**5+10):
    tmp_0 *= 2
    tmp_1 *= 2
    tmp_0 %= first_use_pop[0]
    tmp_1 %= first_use_pop[1]
    kakunou_0.append(tmp_0)
    kakunou_1.append(tmp_1)
#print(first_popcount, first_use_pop, kakunou_0[:50], kakunou_1[:50])


#与えられた数字の初手処理をしておく
syote_0 = 0
syote_1 = 0
#print(S)
for i in range(N-1, -1, -1):
    #print(i, N-1-i, S[i])
    if(S[i] == '1'):
        syote_0 += kakunou_0[N-1-i]
        syote_0 %= first_use_pop[0]
        syote_1 += kakunou_1[N-1-i]
        syote_1 %= first_use_pop[1]
#print(P)
#print(syote_0, syote_1)
#確認OK
#print(P%first_use_pop[0], P%first_use_pop[1])


ans = []
#n = []
for i in range(N):
    if(S[i] == '0'):
        now = syote_0 + kakunou_0[N-1-i]
        now %= first_use_pop[0]
        #n.append(now)
        #if(now == 0):
            #ans.append(1)
        #else:
        ans.append(1+count(now))
    else:
        now = syote_1 - kakunou_1[N-1-i]
        now %= first_use_pop[1]
        #n.append(now)
        #if(now == 0):
            #ans.append(1)
        #else:
        ans.append(1+count(now))

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



'''
ans = [0]
for i in range(1, 2*10**5+10):
    ans.append(count(i))
#print(ans[:100])
#print(ans)

for i in range(100):
    max = 2 ** (2*10**5 - 1) - 1 - i
    #print(count(max))


C = popcount(P)
ret = []
for i in range(N):
    new = []
    for j in range(N):
        if(j != i):
            new.append(S[j])
        else:
            if(S[j] == '0'):
                new.append('1')
                count = C + 1
            else:
                new.append('0')
                count = C - 1
    ten = int(''.join(new), 2)
    res = ans[ten%count] + 1
    ret.append(res)


for i in range(N):
    print(ret[i])
'''

Submission status: Runtime Error

Solution code:
## coding: UTF-8
#N = 23
#S = '00110111001011011001110'
#N = 3
#S = '011'

N = int(input())
S = input()
P = int(S, 2)
#print(P)

def popcount(x):

    # 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


def count(N):
    warareru = N
    waru = popcount(N)
    counter = 0
    while warareru > 0:
        warareru = warareru % waru
        waru = popcount(warareru)
        counter += 1
    return counter


#前処理
first_popcount = popcount(P)
if(first_popcount == N):
    first_use_pop = [N-1, N-1]
elif(first_popcount == 0):
    first_use_pop = [1, 1]
else:
    first_use_pop = [first_popcount+1, first_popcount-1]

tmp_0 = 1
tmp_1 = 1
kakunou_0 = []
kakunou_1 = []
tmp_0 %= first_use_pop[0]
tmp_1 %= first_use_pop[1]
kakunou_0.append(tmp_0)
kakunou_1.append(tmp_1)
for i in range(0, 2*10**5+10):
    tmp_0 *= 2
    tmp_1 *= 2
    tmp_0 %= first_use_pop[0]
    tmp_1 %= first_use_pop[1]
    kakunou_0.append(tmp_0)
    kakunou_1.append(tmp_1)
#print(first_popcount, first_use_pop, kakunou_0[:50], kakunou_1[:50])


#与えられた数字の初手処理をしておく
syote_0 = 0
syote_1 = 0
#print(S)
for i in range(N-1, -1, -1):
    #print(i, N-1-i, S[i])
    if(S[i] == '1'):
        syote_0 += kakunou_0[N-1-i]
        syote_0 %= first_use_pop[0]
        syote_1 += kakunou_1[N-1-i]
        syote_1 %= first_use_pop[1]
#print(syote_0, syote_1)
#確認OK
#print(P%first_use_pop[0], P%first_use_pop[1])


ans = []
for i in range(N):
    if(S[i] == '0'):
        now = syote_0 + kakunou_0[N-1-i]
        now %= first_use_pop[0]
        if(now == 0):
            ans.append(1)
        else:
            ans.append(1+count(now))
    else:
        now = syote_1 - kakunou_1[N-1-i]
        now %= first_use_pop[1]
        if(now == 0):
            ans.append(1)
        else:
            ans.append(1+count(now))

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



'''
ans = [0]
for i in range(1, 2*10**5+10):
    ans.append(count(i))
#print(ans[:100])
#print(ans)

for i in range(100):
    max = 2 ** (2*10**5 - 1) - 1 - i
    #print(count(max))


C = popcount(P)
ret = []
for i in range(N):
    new = []
    for j in range(N):
        if(j != i):
            new.append(S[j])
        else:
            if(S[j] == '0'):
                new.append('1')
                count = C + 1
            else:
                new.append('0')
                count = C - 1
    ten = int(''.join(new), 2)
    res = ans[ten%count] + 1
    ret.append(res)


for i in range(N):
    print(ret[i])
'''

Submission status: Runtime Error

Solution code:
#エイシング　D
n = int(input())
x = input()

def popcount(i):
    return bin(i)[2:].count("1")

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

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

p = x.count("1")
nbit = int(x,2)
namari1 = nbit%(p-1)
namari2 = nbit%(p+1)

for i in range(n):
    a = str(x[:i]) + str(int(not int(x[i]))) + str(x[i+1:])
    a = int(a,2)
    P = n-1-i
    if int(x[i]) == 1:
        if p == 1:
            print(0)
            continue
        else:
            #p>=2
            c = (namari1 - pow(2,P,p-1))%(p-1)
    else:
        #int(x[i])==0
        c = (namari2 + pow(2,P,p+1))%(p+1)
    print(poplist[c]+1)

Submission status: Runtime Error

Solution code:
#エイシング　D
n = int(input())
x = input()

def popcount(i):
    return bin(i)[2:].count("1")

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

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

p = x.count("1")
nbit = int(x,2)
namari1 = nbit%(p-1)
namari2 = nbit%(p+1)

for i in range(n):
    a = str(x[:i]) + str(int(not int(x[i]))) + str(x[i+1:])
    a = int(a,2)
    P = n-1-i
    if int(x[i]) == 1:
        if p == 1:
            print(1)
            continue
        else:
            #p>=2
            c = (namari1 - pow(2,P,p-1))%(p-1)
    else:
        #int(x[i])==0
        c = (namari2 + pow(2,P,p+1))%(p+1)
    print(poplist[c]+1)

Submission status: Runtime Error

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

def popcount(i):
    return bin(i)[2:].count("1")

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

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

p = x.count("1")
nbit = int(x,2)
namari1 = nbit%(p-1)
namari2 = nbit%(p+1)

for i in range(n):
    a = str(x[:i]) + str(int(not int(x[i]))) + str(x[i+1:])
    a = int(a,2)
    P = n-1-i
    if int(x[i]) == 1:
        if p == 1:
            print(1)
            continue
        else:
            #p>=2
            c = (namari1 - 2**P%(p-1))%(p-1)
    else:
        #int(x[i])==0
        c = (namari2 + 2**P%(p+1))%(p+1)
    print(poplist[c]+1)

Submission status: Runtime Error

Solution code:

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
        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
    else:
        cur = (full1 - pow(2, N - i - 1, mod1)) % mod1

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

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

Submission status: Runtime Error

Solution code:

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

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

full0 = 0
full1 = 0
for i in range(N):
    full0 = (full0 + int(X[i]) * pow(2, N - i - 1, mod0)) % mod0
    full1 = (full1 + int(X[i]) * 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
    else:
        cur = (full1 + pow(2, N - i - 1, mod1)) % mod1

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

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

Submission status: Runtime Error

Solution code:
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)
a,b=a%(h-1),a%(h+1)
for i in range(n):
  if x[i]:
    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)

Submission status: Runtime Error

Solution code:
def binaryToDecimal(n): 
    return int(n,2)  

def decimalToBinary(n): 
    return bin(n).replace("0b","") 

def popCount(a):
    count = 0
    while(a!=0):
        if arr[a]==0:
            bi = decimalToBinary(a)
            count_1 = bi.count('1')
            arr[a] = count_1
        else:
            count_1 = arr[a]

        a = a%count_1
        count+=1
    return count

n = int(input())
li = input()
arr=[0]*10000000

for i in range(n):
    s=li
    z = '0'
    if s[i]=='0':
        z='1'
    s = s[:i]+z+s[i+1:]
    a = binaryToDecimal(s)
    print(popCount(a))

Submission status: Runtime Error

Solution code:
def binaryToDecimal(n): 
    return int(n,2)  

def decimalToBinary(n): 
    return bin(n).replace("0b","") 

def popCount(a):
    arr=[0]*10000000
    count = 0
    while(a!=0):
        if arr[a]==0:
            bi = decimalToBinary(a)
            count_1 = bi.count('1')
            arr[a] = count_1
        else:
            count_1 = arr[a]

        a = a%count_1
        count+=1
    return count

n = int(input())
li = input()
for i in range(n):
    s=li
    z = '0'
    if s[i]=='0':
        z='1'
    s = s[:i]+z+s[i+1:]
    a = binaryToDecimal(s)
    print(popCount(a))

Submission status: Runtime Error

Solution code:
def binaryToDecimal(n): 
    return int(n,2)  

def decimalToBinary(n): 
    return bin(n).replace("0b","") 

def popCount(a):
    arr=[0]*10000000
    count = 0
    while(a!=0):
        if arr[a]==0:
            bi = decimalToBinary(a)
            count_1 = bi.count('1')
        else:
            arr[bi] = count_1

        a = a%count_1
        count+=1
    return count

n = int(input())
li = input()
for i in range(n):
    s=li
    z = '0'
    if s[i]=='0':
        z='1'
    s = s[:i]+z+s[i+1:]
    a = binaryToDecimal(s)
    print(popCount(a))

Submission status: Runtime Error

Solution code:
n=int(input())
x=list(input())
binans=0
for i in range(n):
  if x[i]=='1':
    binans+=2**(n-i-1)
  
bincnt=x.count('1')

for i in range(n):
  if x[i]=='0':
    binans+=2**(n-i-1)
    bincnt+=1
    
  else:
    binans-=2**(n-i-1)
    bincnt-=1
    
  cnt=0
    
  while binans!=0:
    cnt+=1
    if binans % bincnt==0:
      break
    else:
      binans=binans % bincnt
      xxx=bin(binans)
      bincnt=xxx.count('1')

  print(cnt)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
(n,), digits = [list(map(int, list(s.rstrip()))) for s in open(0)]

n = int(n)
cnt = sum(digits)
x = int(''.join(map(str, digits)), 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:
        mbase = (mbase * 2) % mmod
    pbase = (pbase * 2) % pmod

while ans:
    print(ans.pop())

Submission status: Runtime Error

Solution code:
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:
        ans.append(calc((mx - mbase)%mmod) + 1)
    else:
        ans.append(calc((px + pbase)%pmod) + 1)
    if mmod > 0:
        mbase = (mbase * 2) % mmod
    pbase = (pbase * 2) % pmod

while ans:
    print(ans.pop())

Submission status: Runtime Error

Solution code:
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

mx = x % mmod
px = x % pmod

mbase = 1
pbase = 1

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

while ans:
    print(ans.pop())

Submission status: Runtime Error

Solution code:
from sys import exit
from collections import defaultdict
n,x = open(0).read().split()
n = int(n)
cnt = x.count('1') 
digits = 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()

mask = 2 ** (n-1)

for digit in digits:
    if digit:
        tcnt = cnt - 1
    else:
        tcnt = cnt + 1
    x ^= mask
#     print(f'{x=}, {tcnt=}, {digit=}')
    print(calc(x % tcnt) + 1)
    x ^= mask
    mask //= 2

Submission status: Runtime Error

Solution code:
from sys import exit
from collections import defaultdict
n,x = open(0).read().split()
n = int(n)
cnt = x.count('1') 
digits = 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))
    exit()

mask = 2 ** (n-1)

for digit in digits:
    if digit:
        tcnt = cnt - 1
    else:
        tcnt = cnt + 1
    x ^= mask
#     print(f'{x=}, {tcnt=}, {digit=}')
    print(calc(x % tcnt) + 1)
    x ^= mask
    mask //= 2

Submission status: Runtime Error

Solution code:
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 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+X[i]) % (pc+1)
    mod_minus_1 = (mod_minus_1*2+X[i]) % (pc-1)


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


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

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

mod_plus_1 = int(X, 2) % (pc+1)
mod_minus_1 = int(X, 2) % (pc-1)


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


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

Submission status: Runtime Error

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

mod_plus_1 = int(X, 2) % (pc+1)
mod_minus_1 = int(X, 2) % (pc-1)


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


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

Submission status: Runtime Error

Solution code:
def g(x):
  S=format(x,"20b")
  cnt=0
  for i in range(15):
    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
#最初に割るのは a-1 or a+1 -> a==1,0に注意
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):
      if X[i]=="1":
        print(0)
      else:
        print(1)
    exit()
D=[1]*n
E=[1]*n
D[0]=D[0]%(a-1)
E[0]=E[0]%(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)

Submission status: Runtime Error

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

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

def f(n):
  i = 0
  while True:
    n = int(n % popcount(n))
    i += 1
    if n == 0 or n == 1:
      break
  
  return(i)

for i in range(len(X)):
  Xd = []

  #TODO performance needs improvement to avoid TLE...
  if X[i] == '1':
    Xd = X[:i] + '0' + X[i+1:]
  else:
    Xd = X[:i] + '1' + X[i+1:]

  print("{}".format(f(int(Xd, 2))))

Submission status: Runtime Error

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

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

def f(n):
  i = 0
  while True:
    n = int(n % popcount(n))
    i += 1
    if n == 0:
      break
  
  return(i)

for i in range(len(X)):
  Xd = []

  if X[i] == '1':
    Xd = X[:i] + '0' + X[i+1:]
  else:
    Xd = X[:i] + '1' + X[i+1:]

  print("{}".format(f(int(Xd, 2))))

Submission status: Runtime Error

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

# n is decimal
def popcount(n):
  count = 1

  while True:
    if n == 1:
      break
    
    if (n % 2 == 1):
      count += 1
    
    n = int(n/2)
  
  return(count)

def f(n):
  i = 0
  while True:
    if (n > 0):
      n = n % popcount(n)
    else:
      break
    
    i += 1
    if n == 0:
      break
  
  return(i)

for i in range(N):
  Xd = []

  if X[i] == '1':
    Xd = X[:i] + '0' + X[i+1:]
  else:
    Xd = X[:i] + '1' + X[i+1:]

  print("{}".format(f(int(Xd, 2))))

Submission status: Runtime Error

Solution code:
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 popcount(x)!=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 popcount(a)!=1:
      b=mi
      b-=pow(2,N-i-1,p-1)
      b%=p-1
    else:
      print(0)
      continue
  print(f(b))

Submission status: Runtime Error

Solution code:
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 popcount!=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 popcount(a)!=1:
      b=mi
      b-=pow(2,N-i-1,p-1)
      b%=p-1
    else:
      print(0)
      continue
  print(f(b))

Submission status: Runtime Error

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

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

pl=a%(popcount(a)+1)
if popcount!=1:
  mi=a%(popcount(a)-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,popcount(a)+1)
    b%=popcount(a)+1
  else:
    if popcount(a)-1!=0:
      b=mi
      b-=pow(2,N-i-1,popcount(a)-1)
      b%=popcount(a)-1
    else:
      print(0)
      continue
  print(f(b))

Submission status: Runtime Error

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

def popcount(x):
  return str(bin(x)).count("1")

pl=a%(popcount(a)+1)
if popcount!=1:
  mi=a%(popcount(a)-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,popcount(a)+1)
    b%=popcount(a)+1
  else:
    if popcount(a)-1!=0:
      b=mi
      b-=pow(2,N-i-1,popcount(a)-1)
      b%=popcount(a)-1
    else:
      print(0)
      continue
  print(f(b))

Submission status: Runtime Error

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

def popcount(x):
  return str(bin(x)).count("1")

pl=a%(popcount(a)+1)
if popcount!=1:
  mi=a%(popcount(a)-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,popcount(a)+1)
    b%=popcount(a)+1
  else:
    if popcount(a)-1!=0:
      b=mi
      b-=pow(2,N-i-1,popcount(a)-1)
      b%=popcount(a)-1
    else:
      print(0)
  print(f(b))

Submission status: Runtime Error

Solution code:
def popcount(x): #xは10進数の整数
    return bin(x).count('1')
ma = 10**5
dp = [0 for i in range (10**5)]
for i in range (1, ma):
    dp[i] = dp[i % popcount(i)] + 1
def solve(N, x):
    p = popcount(int(x, 2))
    nowp_p = int(x, 2) % (p+1)
    if p-1 != 0: 
        nowp_m = int(x, 2) % (p-1)
    x = list(x)#list
    for i in range(N):
        if x[i] == '0':
            print(dp[(nowp_p + 2**(N-i-1)) % (p + 1)] + 1)
        elif x[i] == '1':
            if p == 1:
                print(0)
            else:
                print(dp[(nowp_m - 2**(N-i-1) + p - 1) % (p - 1)] + 1)
N = int(input())
x = input() #str
solve(N, x)

Submission status: Runtime Error

Solution code:
def popcount(x): #xは10進数の整数
    return bin(x).count('1')
def f(x): #xは10進数の整数
    if x == 0:
        return 0
    else:
        return f(x % popcount(x)) + 1
def solve(N, x):
    p = popcount(int(x, 2))
    nowp_p = int(x, 2) % (p+1)
    if p-1 != 0: 
        nowp_m = int(x, 2) % (p-1)
    x = list(x)#list
    for i in range(N):
        if x[i] == '0':
            print(f((nowp_p + 2**(N-i-1)) % (p + 1)) + 1)
        elif x[i] == '1':
            if p == 1:
                     print(0)
            print(f((nowp_m - 2**(N-i-1) + p - 1) % (p - 1)) + 1)
N = int(input())
x = input() #str
solve(N, x)

Submission status: Runtime Error

Solution code:
def popcount(x): #xは10進数の整数
    return bin(x).count('1')
def f(x): #xは10進数の整数
    if x == 0:
        return 0
    else:
        return f(x % popcount(x)) + 1
def solve(N, x):
    p = popcount(int(x, 2
    nowp_p = int(x, 2) % (p+1)
    if p-1 != 0: 
        nowp_m = int(x, 2) % (p-1)
    x = list(x)#list
    for i in range(N):
        if x[i] == '0':
            print(f((nowp_p + 2**(N-i-1)) % (p + 1)) + 1)
        elif x[i] == '1':
            if p == 1:
                     print(0)
            print(f((nowp_m - 2**(N-i-1) + p - 1) % (p - 1)) + 1)
N = int(input())
x = input() #str
solve(N, x)

Submission status: Runtime Error

Solution code:
def popcount(x): #xは10進数の整数
    return bin(x).count('1')
def f(x): #xは10進数の整数
    if x == 0:
        return 0
    else:
        return f(x % popcount(x)) + 1
def solve(N, x):
    p = popcount(int(x, 2))
    nowp_p = int(x, 2) % (p+1)
    if p-1 != 0: 
        nowp_m = int(x, 2) % (p-1)
    else:
        nowp_m = 0
    x = list(x)#list
    for i in range(N):
        if x[i] == '0':
            print(f((nowp_p + 2**(N-i-1)) % (p + 1)) + 1)
        elif x[i] == '1':
            print(f((nowp_m - 2**(N-i-1) + p - 1) % (p - 1)) + 1)
N = int(input())
x = input() #str
solve(N, x)

Submission status: Runtime Error

Solution code:
import copy

# 二進数のビット数
digit_n = int(input())
# 二進数
bit_num = list(input())
# 元の二進数に含まれる1の個数を算出
div_num_1 = bit_num.count('1')
# 各ビットを反転した二進数を作成
# 各ビットを反転した二進数を格納する配列を初期化
xor_list = ['1'] * digit_n
for i in range(digit_n):
    # 二進数の各ビットを反転した二進数を配列に格納
    xor_list = copy.copy(bit_num)
    bit_i = 1^int(bit_num[i])
    xor_list[i] = str(bit_i)
    # 反転した二進数に含まれる1の個数を算出(1なら1増え、0なら1減る)
    div_num_1 = div_num_1 + (-1)**(1 + bit_i)

    # 各ビットを反転した二進数を二進数に含まれている1の個数で割った剰余に置き換えて、剰余が0になるまでの操作回数を出力
    #剰余を格納する変数に反転した二進数をセットして初期化
    surplus = int(str("0b"+''.join(xor_list)),0)
    # 操作回数を格納する変数を0で初期化
    l_count = 0
    while(surplus != 0):
        l_count += 1
        surplus = surplus % div_num_1
        div_num_1 = str(bin(surplus)).count('1')
    print(l_count)

Submission status: Runtime Error

Solution code:
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


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 = I()
x = S()
cnt = sum([int(i) for i in x])
ret1 = 1
ret2 = 1
rem1 = 0
rem2 = 0
for i in range(n - 1, -1, -1):
    if x[i] == "1":
        rem1 = (rem1 + ret1) % (cnt + 1)
        rem2 = (rem2 + ret2) % (cnt - 1)
    ret1 = ret1 * 2 % (cnt + 1)
    ret2 = ret2 * 2 % (cnt - 1)

for j in range(n):
    ans = 1
    if x[j] == "1":
        if cnt == 1:
            print(0)
            continue
        r = (rem2 - pow(2, n - 1 - j, cnt - 1)) % (cnt - 1)
        while r:
            r = r % popcount(r)
            ans += 1
        print(ans)
    else:
        r = (rem1 + pow(2, n - 1 - j, cnt + 1)) % (cnt + 1)
        while r:
            r = r % popcount(r)
            ans += 1
        print(ans)

Submission status: Runtime Error

Solution code:
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


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 = I()
x = S()
cnt = sum([int(i) for i in x])
ret1 = 1
ret2 = 1
rem1 = 0
rem2 = 0
for i in range(n - 1, -1, -1):
    if x[i] == "1":
        rem1 = (rem1 + ret1) % (cnt + 1)
        rem2 = (rem2 + ret2) % (cnt - 1)
    ret1 = ret1 * 2 % (cnt + 1)
    ret2 = ret2 * 2 % (cnt - 1)


for j in range(n):
    ans = 1
    if x[j] == "1":
        r = (rem2 - pow(2, n - 1 - j, cnt - 1)) % (cnt - 1)
        while r:
            r = r % popcount(r)
            ans += 1
        print(ans)
    else:
        r = (rem1 + pow(2, n - 1 - j, cnt + 1)) % (cnt + 1)
        while r:
            r = r % popcount(r)
            ans += 1
        print(ans)