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:
N=int(input())
a=input()
#N=23
#a ="00110111001011011001110"
#print(a[1])

def h(x_):
    if(x_=="0"):
        return "1"
    else:
        return "0"
#print(hanten(a[0]))

def ih(a_,i_):
    ih_=""
    j=0
    for lena_ in range(len(a_)):
        if(j==i_):
            ih_+=h(a[j])
        else:
            ih_+=a[j]
        j+=1
    return ih_
#print(ihanten(a,0))

def c1(a_):
    c=0
    i=0
    for lena_ in range(len(a_)):
        if(a_[i]=="1"):
            c+=1
        i+=1
    return c
#print(c1(a))       

def n_z(a_):
    nz=0
    i=0
    for lena_ in range(len(a_)):
        nz+=int(a_[i])*2**(len(a_)-i-1)
        i+=1
    return nz
#print(n_z(a))

def z_n(x_,N_):
    b=format(x_, 'b')
    return("0"*(N_-len(b))+str(format(x_, 'b')))
#print(z_n(1,N))

def nz_c1_a(a_):
    return n_z(a_) % c1(a_)

def f(a_,j,N_):
    if(nz_c1_a(a_)==0):
        return j
    else:
        return f(z_n(nz_c1_a(a_),N_),j+1,N_)
#print(fX(a,1,N))

i=0
for ih_ in range(N):
    print(f(ih(a,i),1,N))
    i+=1

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:
        print(0)
        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()

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:
        print(0)
        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[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[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()

Submission status: Runtime Error

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

if __name__ == "__main__":
    n = int(input())
    x = input()
    print(x[2])
    d = x.count('1')
    if d == 1:
        for i in x[:-1]:
            if i == '0':
                print(1)
            else:
                print(0)
        if x[-1] == '1':
            print(0)
        else:
            print(2)
        exit()

    ans = []
    M = 0
    for i in x:
        M <<= 1
        if i == '1':
            M += 1
    p = M % (d + 1)
    m = M % (d - 1)
    for i in range(n):
        if x[i] == '0':
            ans.append(f((p + pow(2, n - i - 1, d + 1)) % (d + 1)))
        else:
            ans.append(f((m - pow(2, n - i - 1, d - 1)) % (d - 1)))
    print(*ans, sep='\n')

Submission status: Runtime Error

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


def popcount(s):
    return s.count('1')


x_10 = int(x, 2)
p = popcount(x)
r_p1 = x_10 % (p + 1)
r_m1 = x_10 % (p - 1)
# print("x_10 ={0}, p = {1}, r_p1 = {2}, r_m1 = {3}".format(x_10, p, r_p1, r_m1))

for i in range(n):
    out = 1
    # print("x[i] = {0}".format(x[i]))
    if x[i] == '1':
        m = (r_m1 - ((2 ** (n - i - 1)) % (p - 1))) % (p - 1)
    else:
        m = (r_p1 + ((2 ** (n - i - 1)) % (p + 1))) % (p + 1)
    while m > 0:
        # print("m = {0}".format(m))
        m = m % popcount(format(m, 'b'))
        out += 1
    print(out)

Submission status: Runtime Error

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

n1 = X.count("1")
Xn = int(X, 2)

Xms = (Xn % (n1 - 1)) if n1 > 1 else 0
Xml = Xn % (n1 + 1)


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


dp = [0] * ((10 ** 5) * 2 + 1)
for i in range(1, len(dp)):
    dp[i] = f(i)


for i in range(N):
    cnt = 0
    p2 = 2 ** (N - i - 1)
    Xim = 0

    if X[i] == "1" and n1 == 1:
        print(cnt)
    elif X[i] == "1":
        xi = (Xms - pow(2, N - i - 1, n1 - 1)) % (n1 - 1)
    else:
        xi = (Xml + pow(2, N - i - 1, n1 + 1)) % (n1 + 1)
    cnt = 1
    while xi != 0:
        xi %= bin(xi).count("1")
        cnt += 1
    print(cnt)

Submission status: Runtime Error

Solution code:
n = int(input())
s = input()
x = int(s, 2)
p = s.count("1")
if p > 2:
	pre0 = x%(p-1)
pre1 = x%(p+1)

nxt = [i for i in range(n+10)]
for i in range(1, n+10):
	nxt[i] %= bin(i).count("1")

for i in range(n):
	if x == 1<<(n-1-i):
		print(0)
		continue
	if s[i] == "0":
		tmp = (pre1 + pow(2, n-1-i, p+1)) % (p+1)
	else:
		tmp = (pre0 - pow(2, n-1-i, p-1)) % (p-1)
	ans = 1
	while tmp > 0:
		ans += 1
		tmp = nxt[tmp]
	print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
s = input()
x = int(s, 2)
p = s.count("1")
pre0, pre1 = x%(p-1), x%(p+1)

nxt = [i for i in range(n+10)]
for i in range(1, n+10):
	nxt[i] %= bin(i).count("1")

for i in range(n):
	if x == 1<<(n-1-i):
		print(0)
		continue
	if s[i] == "0":
		tmp = (pre1 + pow(2, n-1-i, p+1)) % (p+1)
	else:
		tmp = (pre0 - pow(2, n-1-i, p-1)) % (p-1)
	ans = 1
	while tmp > 0:
		ans += 1
		tmp = nxt[tmp]
	print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
X = int(input(), 2)
dp = [0]*N
dp[0] = 0
checked = [False]*N
for i in range(1, N):
    c = bin(i).count("1")
    dp[i] = dp[i%c] + 1
for i in range(N):
    Xi = X^2**(N-i-1)
    C = bin(Xi).count("1")
    print(dp[Xi%C]+1)

Submission status: Runtime Error

Solution code:
n = int(input())
s = input()
x = int(s, 2)
p = s.count("1")
pre0, pre1 = x%(p-1), x%(p+1)

nxt = [i for i in range(n+1)]
for i in range(1, n):
	nxt[i] %= bin(i).count("1")

for i in range(n):
	if x == 1<<(n-1-i):
		print(0)
		continue
	if s[i] == "0":
		tmp = (pre1 + pow(2, n-1-i, p+1)) % (p+1)
	else:
		tmp = (pre0 - pow(2, n-1-i, p-1)) % (p-1)
	ans = 1
	while tmp > 0:
		ans += 1
		tmp = nxt[tmp]
	print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
s = input()
x = int(s, 2)
p = s.count("1")
pre0, pre1 = x%(p-1), x%(p+1)

nxt = [i for i in range(n+1)]
for i in range(1, n):
	nxt[i] %= bin(i).count("1")

for i in range(n):
	if x == 1<<(n-1-i):
		print(0)
		continue
	if s[i] == "0":
		tmp = (pre1 + pow(2, n-1-i, p+1)) % (p+1)
	else:
		tmp = (pre0 + pow(2, n-1-i, p-1)) % (p-1)
	ans = 1
	while tmp > 0:
		ans += 1
		tmp = nxt[tmp]
	print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
s = input()
x = int(s, 2)
p = popcount(x)

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

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

for i in range(n):
	ans = 0
	tmp = x ^ (1 << (n-1-i))
	if tmp == 0:
		print(0)
		continue
	if tmp > x:
		ans = 1
		tmp %= p+1
	else:
		ans = 1
		tmp %= p-1
	while tmp > 0:
		ans += 1
		tmp = nxt[tmp]
	print(ans)

Submission status: Runtime Error

Solution code:
from logging import *
basicConfig(level=DEBUG, format='%(levelname)s: %(message)s')
disable(CRITICAL)

n = int(input())
# X = [int(x) for x in input()]
X = input()
debug('n {}'.format(n))
debug('X {}'.format(X))
po = X.count('1')
ro = 0
rp = 0
rm = 0
for x in X:
    ro = (ro*2 + int(x)) % (po)
    rp = (rp*2 + int(x)) % (po+1)
    rm = (rm*2 + int(x)) % (po-1)

b = [0]*(n) # 2^i
bp = [0]*(n) # 2^i % (po+1)
bm = [0]*(n) # 2^i % (po-1)
b[n-1] = 1 % (po)
bp[n-1] = 1 % (po+1)
bm[n-1] = 1 % (po-1)
for i in range(n-1,0,-1):
    # debug('i {}'.format(i))
    b[i-1] = b[i]*2%(po)
    bp[i-1] = bp[i]*2%(po+1)
    bm[i-1] = bm[i]*2%(po-1)

debug('po {}'.format(po))
debug('ro {}'.format(ro))
debug('rp {}'.format(ro))
debug('rm {}'.format(ro))
debug('b {}'.format(b))
debug('bp {}'.format(bp))
debug('bm {}'.format(bm))
debug('===')

def popcount(x):
    c = 0
    while x > 0:
        if x & 1: c += 1
        x //= 2
    return c

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

for i in range(n):
    if X[i] == '0':
        ri = (rp + bp[i]) % (po+1)
    else: # '1'
        ri = (rm - bm[i]) % (po-1)
    debug('ri {}'.format(ri))
    c = f(ri) + 1
    debug('c {}'.format(c))
    print(c)

Submission status: Runtime Error

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

f = {}


def calcF(i, count):
    if i == 0:
        return count
    if i in f:
        return count + f[i]
    icount = bin(i).count("1")
    if icount == 0:
        return count + 1
    r = i % icount
    if r != 0:
        return calcF(r, count + 1)
    else:
        return count + 1


for i in range(1, 2 ** N):
    f[i] = calcF(i, 0)

for i in range(1, N + 1):
    a = X ^ 2 ** ((N - 1) - (i - 1))
    print(f[a])

Submission status: Runtime Error

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

check = [0] * 2000001

for i in range(1, 2000001):
    tmp = 0
    num = i
    while True:
        tmp += 1
        s = bin(num).count('1')
        num = num%s
        
        if check[num] != 0:
            tmp += check[num]
            check[i] += tmp
            break
        
        if num == 0:
            check[i] = tmp
            break

for i in range(n):
    tmp = x.copy()
    if tmp[i] == "1":
        tmp[i] = "0"
    else:
        tmp[i] = "1"
    while True:
        if tmp[0] == "0":
            del tmp[0]
        else:
            break
    num = int("".join(tmp), 2)
    tmp = 0
    while True:
        tmp += 1
        s = bin(num).count('1')
        num = num%s
        
        if check[num] != 0:
            tmp += check[num]
            print(tmp)
            break
        
        if num == 0:
            print(tmp)
            break

Submission status: Runtime Error

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

num_lists = []
x_list = list(x)
for i in range(0, n, 1):
    tmp_list = x_list.copy()
    if tmp_list[i] == '0':
        tmp_list[i] = '1'
    else:
        tmp_list[i] = '0'
    num_lists.append(''.join(tmp_list))

count_list = []
for i in num_lists:
    base_ten = int(i, 2)
    base_ten = base_ten % i.count('1')
    count = 1
    while True:
        if base_ten != 0:
            bin_str = format(base_ten, 'b')
            base_ten = base_ten % bin_str.count('1')
            count += 1
        else:
            count_list.append(count)
            break
for i in count_list:
    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:
        print(0)
        sys.exit()

    x10 = int("".join(x), 2)
    xcount1 = x.count('1')
    modx_plus = x10 % (xcount1 + 1)
    modx_minus = x10 % (xcount1 - 1)
    memo = defaultdict(int)
    for i1 in range(n):
        if x[i1] == '1':
            mod_e = (pow(2, (n - 1 - i1)) % (xcount1 - 1))
            x3 = modx_minus - mod_e
            if x3 < 0:
                x3 += (xcount1 - 1)
            elif x3 > (xcount1 - 1):
                x3 -= (xcount1 - 1)
            elif x3 == (xcount1 - 1):
                x3 = 0
        else:
            mod_e = (pow(2, (n - 1 - i1)) % (xcount1 + 1))
            x3 = modx_plus + mod_e
            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()

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.read
from collections import defaultdict
def main():
    n = int(input())
    x = list(input())
    x10 = int("".join(x), 2)
    xcount1 = x.count('1')
    modx_plus = x10 % (xcount1 + 1)
    modx_minus = x10 % (xcount1 - 1)
    memo = defaultdict(int)
    for i1 in range(n):
        if x[i1] == '1':
            mod_e = (pow(2, (n - 1 - i1)) % (xcount1 - 1))
            x3 = modx_minus - mod_e
            if x3 < 0:
                x3 += (xcount1 - 1)
            elif x3 > (xcount1 - 1):
                x3 -= (xcount1 - 1)
            elif x3 == (xcount1 - 1):
                x3 = 0
        else:
            mod_e = (pow(2, (n - 1 - i1)) % (xcount1 + 1))
            x3 = modx_plus + mod_e
            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()

Submission status: Runtime Error

Solution code:
from functools import lru_cache

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


@lru_cache(maxsize=None)
def popcount(x):
    return x % bin(x).count('1')


def f(x):
    cnt = 1
    while x > 0:
        x = popcount(x)
        cnt += 1

    return cnt


count = X.count('1')
mod_one = count - 1
mod_zero = count + 1
ones = [1 % mod_one]
zeros = [1 % mod_zero]
x_mod_one = 0 if X[-1] == '0' else 1 % mod_one
x_mod_zero = 0 if X[-1] == '0' else 1 % mod_zero

for xi in reversed(X[:-1]):
    ones.append(ones[-1] * 2 % mod_one)
    zeros.append(zeros[-1] * 2 % mod_zero)
    if xi == '1':
        x_mod_one += ones[-1]
        x_mod_one %= mod_one
        x_mod_zero += zeros[-1]
        x_mod_zero %= mod_zero

ones = list(reversed(ones))
zeros = list(reversed(zeros))

for i in range(N):
    if count == 1 and X[i] == '1':
        print(0)
    elif X[i] == '1':
        x = (x_mod_one - ones[i]) % mod_one
        print(f(x))
    else:
        x = (x_mod_zero + zeros[i]) % mod_zero
        print(f(x))

Submission status: Runtime Error

Solution code:
# D - Anything Goes to Zero
import sys
sys.setrecursionlimit(10**8)

N = int(input())
X = str(input())
ones = X.count('1')
intX = int(X, 2)
def check(n, r):
    if n == 0:
        return print(r)
    d = str(bin(n)).count('1')
    check(n%d, r+1)

Xplus = intX % (ones + 1)
Xminus = intX % (ones - 1)
for i in range(N):
    if X[i] == '0':
        num = (Xplus + pow(2, N-1-i, ones + 1)) % (ones + 1)
    else:
        num = (Xminus - pow(2, N-1-i, ones - 1)) % (ones - 1)
    check(num, 1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**8)

N = int(input())
X = str(input())
ones = X.count('1')
intX = int(X, 2)
def check(n, r):
    if n == 0:
        return print(r)
    d = str(bin(n)).count('1')
    check(n%d, r+1)

Xplus = intX % (ones + 1)
Xminus = intX % (ones - 1)
for i in range(N):
    if X[i] == '0':
        num = (Xplus + pow(2, N-1-i)) % (ones + 1)
    else:
        num = (Xminus - pow(2, N-1-i)) % (ones - 1)
    check(num, 1)

Submission status: Runtime Error

Solution code:
def resolve():
  N = int(input())
  X = input()
  base_1_count = X.count("1")
  X_int = int(X, 2)
  X_int_p = X_int%(base_1_count + 1)
  X_int_m = X_int%(base_1_count - 1)

# 高速化バージョン
  for i in range(N):
    if base_1_count == 1 and X[i] == "1":
      print(0)
      continue

    if X[i] == "1":
      Xi = X_int_m - 2**(N-i-1)%(base_1_count-1)
    else:
      Xi = X_int_p + 2**(N-i-1)%(base_1_count+1)
    count = 1
    while Xi != 0:
      # print(Xi)
      num_of_1 = bin(Xi).count("1")
      if num_of_1 != 0:
        Xi %= num_of_1
        count += 1
      else:
        break
    # print("~~~~~~~~~~~~~~~")
    print(count)

# 低速バージョン
  # for i in range(N):
  #   if X[i] == "1":
  #     Xi = X_int - 2**(N-i-1)
  #   else:
  #     Xi = X_int + 2**(N-i-1)
  #   count = 0
  #   while Xi != 0:
  #     # print(Xi)
  #     num_of_1 = bin(Xi).count("1")
  #     Xi %= num_of_1
  #     count += 1
  #   # print("~~~~~~~~~~~~~~~")
  #   print(count)

if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**8)

N = int(input())
X = str(input())
ones = X.count('1')
intX = int(X, 2)
def check(n, r):
    if n == 0:
        return print(r)
    d = str(bin(n)).count('1')
    check(n%d, r+1)

Xplus = intX % (ones + 1)
Xminus = intX % (ones - 1)
print(intX, ones, Xplus, Xminus)
for i in range(N):
    if X[i] == '0':
        num = (Xplus + pow(2, N-1-i)) % (ones + 1)
    else:
        num = (Xminus - pow(2, N-1-i)) % (ones - 1)
    check(num, 1)

Submission status: Runtime Error

Solution code:
n=int(input())
x_=input()
px=x_.count("1")
if not px:
    for i in range(n):
        print(1)
    exit()
if px==1:
#https://atcoder.jp/contests/aising2020/submissions/15163004
    for i in range(n):
        if X[i]=="1":
            cur=i
            break
    for i in range(n):
        if i==cur:
            print(0)
    else:
        if i==n-1 or cur==n-1:
            print(2)
        else:
            print(1)
    # for i in range(n):
    #     if int(x_[-i-1]):
    #         print(0)
    #     else:
    #         if not i or int(x_[-1])==1:###
    #             print(2)
    #         else:
    #             print(1)
    exit()
x=int(x_,2)

pow2=[1]

for i in range(n):
    tmp=pow2[-1]
    tmp*=2
    tmp%=px+1
    pow2.append(tmp)
pow22=[1]
for i in range(n):
    tmp=pow22[-1]
    tmp*=2
    tmp%=px-1
    pow22.append(tmp)
x1=x%(px+1)
x2=x%(px-1)
ans=[]
for i in range(n):
    tmp=0;dv=0
    if int(x_[-i-1]):
        tmp=x2-pow22[i]
        tmp%=(px-1)
        dv=px-1
    else:
        tmp=x1+pow2[i]
        tmp%=(px+1)
        dv=px+1
    
    cnt=1
    while tmp:
        
        dv=bin(tmp).count("1")
        if not dv or not tmp:
            break
        
        tmp%=dv
        cnt+=1
    ans.append(cnt)
for i in ans[::-1]:
    print(i)

Submission status: Runtime Error

Solution code:
def resolve():
  N = int(input())
  X = input()
  base_1_count = X.count("1")
  X_int = int(X, 2)
  X_int_p = X_int%(base_1_count + 1)
  X_int_m = X_int%(base_1_count - 1)

# 高速化バージョン
  for i in range(N):
    if X[i] == "1":
      Xi = X_int_m - 2**(N-i-1)%(base_1_count-1)
    else:
      Xi = X_int_p + 2**(N-i-1)%(base_1_count+1)
    count = 1
    while Xi != 0:
      # print(Xi)
      num_of_1 = bin(Xi).count("1")
      if num_of_1 != 0:
        Xi %= num_of_1
        count += 1
      else:
        break
    # print("~~~~~~~~~~~~~~~")
    print(count)

# 低速バージョン
  # for i in range(N):
  #   if X[i] == "1":
  #     Xi = X_int - 2**(N-i-1)
  #   else:
  #     Xi = X_int + 2**(N-i-1)
  #   count = 0
  #   while Xi != 0:
  #     # print(Xi)
  #     num_of_1 = bin(Xi).count("1")
  #     Xi %= num_of_1
  #     count += 1
  #   # print("~~~~~~~~~~~~~~~")
  #   print(count)

if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
def resolve():
  N = int(input())
  X = input()
  base_1_count = X.count("1")
  X_int = int(X, 2)
  X_int_p = X_int%(base_1_count + 1)
  X_int_m = X_int%(base_1_count - 1)

# 高速化バージョン
  print()
  for i in range(N):
    if X[i] == "1":
      Xi = X_int_m - 2**(N-i-1)%(base_1_count-1)
    else:
      Xi = X_int_p + 2**(N-i-1)%(base_1_count+1)
    count = 1
    while Xi != 0:
      # print(Xi)
      num_of_1 = bin(Xi).count("1")
      Xi %= num_of_1
      count += 1
    # print("~~~~~~~~~~~~~~~")
    print(count)

# 低速バージョン
  # for i in range(N):
  #   if X[i] == "1":
  #     Xi = X_int - 2**(N-i-1)
  #   else:
  #     Xi = X_int + 2**(N-i-1)
  #   count = 0
  #   while Xi != 0:
  #     # print(Xi)
  #     num_of_1 = bin(Xi).count("1")
  #     Xi %= num_of_1
  #     count += 1
  #   # print("~~~~~~~~~~~~~~~")
  #   print(count)

if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
def waru(a):
    onecnt = a.count('1')
    num = int(a, 2)
    return num%onecnt

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

for i in range(len(X)):
    p = X
    str_list = list(p)
    if str_list[i] == '0':
        str_list[i] = '1'
    else:
        str_list[i] = '0'
    p = "".join(str_list)

    cnt = 1
    while (1 == 1):
        amari = waru(p)
        if amari == 0:
            break
        else:
            p = bin(amari)
            cnt += 1

    print(cnt)

Submission status: Runtime Error

Solution code:
n=int(input())
x_=input()
px=x_.count("1")
if not px:
    print(0)
    for i in range(n-1):
        print(1)
    exit()
if px==1:
    for i in range(n):
        if int(x_[-i-1]):
            print(0)
        else:
            if not i or int(x[-1])==1:###
                print(2)
            else:
                print(1)
    exit()
x=int(x_,2)

pow2=[1]

for i in range(n):
    tmp=pow2[-1]
    tmp*=2
    tmp%=px+1
    pow2.append(tmp)
pow22=[1]
for i in range(n):
    tmp=pow22[-1]
    tmp*=2
    tmp%=px-1
    pow22.append(tmp)
x1=x%(px+1)
x2=x%(px-1)
ans=[]
for i in range(n):
    tmp=0;dv=0
    if int(x_[-i-1]):
        tmp=x2-pow22[i]
        tmp%=(px-1)
        dv=px-1
    else:
        tmp=x1+pow2[i]
        tmp%=(px+1)
        dv=px+1
    
    cnt=1
    while tmp:
        
        dv=bin(tmp).count("1")
        if not dv or not tmp:
            break
        
        tmp%=dv
        cnt+=1
    ans.append(cnt)
for i in ans[::-1]:
    print(i)

Submission status: Runtime Error

Solution code:
def popcount(n):
    cnt = 0
    for i in range(n):
        if ((n >> i) & 1):
            cnt +=1
    return cnt

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

def pow(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
    return K * x

def numChange(list, num):
    i = len(list) - 1
    j = 0
    ans = 0
    while i >= 0:
        if list[i] == '1':
            ans += num[j]
        i -= 1
        j += 1
    return ans

if __name__ == "__main__":
    n = int(input())
    x = list(input())
    d = sum([y == '1' for y in x])
    num = []
    a = 1
    for i in range(n):
        num.append(a)
        a *= 2
    xNum = numChange(x, num)
    for i in range(n):
        if x[i] == "1":
            wk = xNum - num[len(x) - i - 1]
            wkd = d - 1
        else:
            wk = xNum + num[len(x) - i - 1]
            wkd = d + 1
        wk %= wkd
        if wk == 0:
            print(1)
        else:
            print(f(wk))

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
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
    else:
        n = mod[1] + (2**(N-1-i)) % popcount[1]
        if n == popcount[1]:
            print(1)
            continue
    ans[i] += 1
    while n != 0:
        n = n % format(n, '0'+str(N)+'b').count('1')
        ans[i] += 1

    print(ans[i])

Submission status: Runtime Error

Solution code:
import copy

n = int(input())
bin_str = input()
x = list(bin_str)
y = list(map(lambda x: int(x), x))


def popcount(k):
  k_str = format(k, 'b')
  return k_str.count('1')


def sousa(x, y):
  kaisu=0
  if x%y == 0:
    kaisu += 1
    return kaisu
  else:
    kaisu += 1
    kaisu += sousa(x%y, popcount(x%y))
    return kaisu
  
for i in range(n):
  y2=copy.copy(y)
  if y2[i]==1:
    y2[i]=0
  else:
    y2[i]=1
  num_1=y2.count(1)
  bin_str_l = list(str(a) for a in y2)
  bin_str = ''.join(bin_str_l)
  bin_num=int(bin_str, 2)
  print(sousa(bin_num, num_1))

Submission status: Runtime Error

Solution code:
def f(n) :
    ans=0
    while n>0 :
        ans+=1
        n=n%bin(n).count("1")
    return ans

def main() :
    n=int(input())
    x=input()

    c1=x.count("1")                                    #初期のpopcount(x)
    cc2=int("0b"+x,0)                                  #初期のn

    if c1==1 :
        for i in range(n) :
            if x[i]=="1" :                             #1を反転させたら1は0個
                print(0)
            else :
                print(f((pow(2,n-i-1,c1+1)+cc2)%(c1+1))+1)  #あらかじめ1回はもう割っておく
    
    cc1=int("0b"+x,0)%(c1-1)
    
    for i in range(n) :
        if x[i]=="1" :
            print(f((-pow(2,n-i-1,c1-1)+cc1)%(c1-1))+1)     #あらかじめ1回はもう割っておく
        else :
            print(f((pow(2,n-i-1,c1+1)+cc2)%(c1+1))+1)



main()

Submission status: Runtime Error

Solution code:
def f(n) :
    ans=0
    while n>0 :
        ans+=1
        n=n%bin(n).count("1")
    return ans

def main() :
    n=int(input())
    x=input()

    c1=x.count("1") 
    cc2=int("0b"+x,0) 

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


main()

Submission status: Runtime Error

Solution code:
def f(n) :
    ans=0
    while n>0 :
        ans+=1
        n=n%bin(n).count("1")
    return ans

#----------------------------------------------------------------------------------------
#こちらで実行

def main() :
    n=int(input())
    x=input()

    c1=x.count("1")                                    #初期のpopcount(x)
    cc2=int("0b"+x,0)                                  #初期のn

    if c1==1 :
        for i in range(n) :
            if x[i]=="1" :                             #1を反転させたら1は0個
                print(0)
            else :
                print(f((pow(2,n-i-1)+cc2)%(c1+1))+1)  #あらかじめ1回はもう割っておく
    
    for i in range(n) :
        if x[i]=="1" :
            print(f((-pow(2,n-i-1)+cc2)%(c1-1))+1)     #あらかじめ1回はもう割っておく
        else :
            print(f((pow(2,n-i-1)+cc2)%(c1+1))+1)


#----------------------------------------------------------------------------------------
#

main()

Submission status: Runtime Error

Solution code:
import numpy as np

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

def func(x):
    if a[x] != -1:
        return a[x]
    else:
        counter = 0
        x_tmp = x
        while x > 0:
            if x % 2 == 1:
                counter += 1
            x = x >> 1
        a[x_tmp] = func(x_tmp % counter) + 1
        return func(x_tmp % counter) + 1
if N <= 10:
    print(func(int(X, 2)))
    
else:
    a = [-1] * (2 * 10 ** 5)
    a[0] = 0
    num_one = X.count("1")
    zero_ver = np.array([pow(2,  i, num_one + 1) for i in range(N)])
    one_ver = np.array([pow(2,  i, num_one - 1) for i in range(N)])
    bool_arr = np.array([True if X[N-i-1] == "1" else False for i in range(N)])
    for i in range(1,N+1):
        tmp_bool = bool_arr.copy()
        start = 0
        if tmp_bool[N-i] == False:
            tmp_bool[N-i] = True
            start = sum(zero_ver[tmp_bool]) % (num_one + 1)
        else:
            tmp_bool[N-i] = False
            start = sum(one_ver[tmp_bool]) %  (num_one - 1)
        print(func(start)+1)