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:
import copy

# 二進数のビット数
digit_n = int(input())
# 二進数
bit_num = list(input())
if test == 1:
    print(''.join(bit_num))

# 二進数の各ビットを反転した二進数を格納する配列を初期化
xor_list = [[0] * digit_n for i in range(digit_n)]
# 各ビットを反転した二進数を作成
for i in range(digit_n):
    xor_list[i] = copy.copy(bit_num)
    xor_list[i][i] = str(1^int(bit_num[i]))
    # 各ビットを反転した二進数を二進数に含まれている1の個数で割った剰余に置き換えて、剰余が0になるまでの操作回数を出力
    sam_num = "0b"+''.join(xor_list[i])
    #剰余を格納する変数に反転した二進数を10進数に変換した数値をセットして初期化
    surplus = int(sam_num, 0)
    # 割る数を二進数に出現する1の数で初期化
    div = xor_list[i].count('1')
    # 操作回数を格納する変数を0で初期化
    l_count = 0
    while(surplus != 0):
        l_count += 1
        surplus = surplus % div
        div = str(bin(surplus)).count('1')
    print(l_count)

Submission status: Runtime Error

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

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

def g(n):
    if popcount(n) == 0:
        return("ZERO")
    else:
        return n % popcount(n)

def f(n):
    temp = n
    count = 0
    while True:
        count += 1
        if g(temp) == 0:
            return count
            break
        elif g(temp) == "ZERO":
            return count - 1
        else:
            temp = g(temp)


popcount_help = [popcount(X) - 1]
popcount_help.append(popcount_help[0] + 1)
popcount_help.append(popcount_help[0] + 2)

gn_help = [X % popcount_help[0]]
gn_help.append(X % popcount_help[1])
gn_help.append(X % popcount_help[2])

for i in range(N):
    temp = X ^ (1 << (N - i - 1))
    if X_raw[i] == "1":
        popcount_temp = popcount_help[0]
        gn_temp = gn_help[0]
        temp = (gn_temp - (2 ** (N - i - 1) % popcount_temp)) % popcount_temp
        
    elif X_raw[i] == "0":
        popcount_temp = popcount_help[2]
        gn_temp = gn_help[2]
        temp = (gn_temp + (2 ** (N - i - 1) % popcount_temp)) % popcount_temp
        
    ans = f(temp) + 1
    print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
X_bin = input()
#N = 10**5
#X_bin = '1' * N

X_int = int(X_bin, 2)  # bin => int


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


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


X_cnt = calc_bin_cnt(X_int)
f_p = X_int % (X_cnt+1)
if X_cnt-1 == 0:
    f_m = 0
else:
    f_m = X_int % (X_cnt-1)
for i in range(N):
    if X_bin[i] == '1':
        next_cnt = X_cnt - 1
        next_int = f_m - pow(2, (N-i-1), next_cnt)  # マイナスでも正しく求まる？
    else:
        next_cnt = X_cnt + 1
        next_int = f_p + pow(2, (N-i-1), next_cnt)
    print(calc_ans(next_int, next_cnt))
    #calc_ans(next_cnt, next_cnt)

Submission status: Runtime Error

Solution code:
N = int(input())
X_bin = input()
#N = 10**5
#X_bin = '1' * N

X_int = int(X_bin, 2)  # bin => int


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


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


X_cnt = calc_bin_cnt(X_int)
f_p = X_int % (X_cnt+1)
if X_cnt-1 == 0:
    f_m = 0
else:
    f_m = X_int % (X_cnt-1)
for i in range(N):
    if X_bin[i] == '1':
        next_int = f_m - (2**(N-i-1))  # マイナスでも正しく求まる？
        next_cnt = X_cnt - 1
    else:
        next_int = f_p + (2**(N-i-1))
        next_cnt = X_cnt + 1
    print(calc_ans(next_int, next_cnt))
    #calc_ans(next_cnt, next_cnt)

Submission status: Runtime Error

Solution code:
import math


N = int(input())
X_bin = input()

X_int = int(X_bin, 2)  # bin => int


def calc_bin_cnt(next_int):
    '''
    next_bin = bin(next_int)[2:]
    # popcount
    cnt = 0
    for i in next_bin:
        if i == '1':
            cnt += 1
    '''
    cnt = 0
    n = int(math.log2(next_int))
    for i in range(n, -1, -1):
        if next_int >= 2**i:
            next_int -= 2**i
            cnt += 1
    return cnt


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


X_cnt = calc_bin_cnt(X_int)
for i in range(N):
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1)), X_cnt-1))
    else:
        print(calc_ans(X_int + (2**(N-i-1)), X_cnt+1))

Submission status: Runtime Error

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

X_int = int(X_bin, 2)  # bin => int


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


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


X_cnt = calc_bin_cnt(X_int)
for i in range(N):
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1)), X_cnt-1))
    else:
        print(calc_ans(X_int + (2**(N-i-1)), X_cnt+1))

Submission status: Runtime Error

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


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

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

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

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

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

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

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

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

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
#N, K = (int(i) for i in input().split())
#B = [int(x) for x in input().split()]
#A = [[int(i) for i in input().split()] for i in range(N)]


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


def f(x, cur):
    #print(x, cur)
    cnt = cur
    tmp = x
    while tmp:
        tmp = tmp%my_popcount(tmp)
        cnt +=1
    return cnt


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

Xint = int(X, 2)
popcountX = X.sum()
#print("test", Xint, popcountX)
plus = Xint%(popcountX+1)
minus = 0
if popcountX != 1:
    minus = Xint%(popcountX-1)

X = list(X)
for i in range(N):
    if X[i] == "0":
        #print("arg", Xint%(popcountX+1), (2**(N-1-i))%(popcountX+1))
        print(f((plus + (2**(N-1-i))%(popcountX+1))%(popcountX+1), 1))
    else:
        if popcountX == 1:
            print(0)
        else:
            print(f((minus - (2**(N-1-i))%(popcountX-1))%(popcountX-1), 1))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
#N, K = (int(i) for i in input().split())
#B = [int(x) for x in input().split()]
#A = [[int(i) for i in input().split()] for i in range(N)]


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

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

Xint = int(X, 2)
popcountX = X.count("1")
#print("test", Xint, popcountX)
plus = Xint%(popcountX+1)
minus = Xint%(popcountX-1)

for i in range(N):
    if X[i] == "0":
        #print("arg", Xint%(popcountX+1), (2**(N-1-i))%(popcountX+1))
        print(f((plus + (2**(N-1-i))%(popcountX+1))%(popcountX+1), 1))
    else:
        if popcountX == 1:
            print(0)
        else:
            print(f((minus - (2**(N-1-i))%(popcountX-1))%(popcountX-1), 1))

Submission status: Runtime Error

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

X_int = int(X_bin, 2)  # bin => int


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


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


X_cnt = calc_bin_cnt(X_int)
for i in range(N):
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1)), X_cnt-1))
    else:
        print(calc_ans(X_int + (2**(N-i-1)), X_cnt+1))

Submission status: Runtime Error

Solution code:
N = int(input())
X_bin = input()
#N = 2 * 10**4
#X_bin = '1' * N

X_int = int(X_bin, 2)  # bin => int
# popcount
X_cnt = 0
for i in X_bin:
    if i == '1':
        X_cnt += 1
dp = {0: 0, 1: 1}
bin_cnt = {}


def calc_bin_cnt(next_int):
    #if next_int in bin_cnt.keys():
    #    cnt = bin_cnt[next_int]
    #else:
    next_bin = bin(next_int)[2:]
    # popcount
    cnt = 0
    for i in next_bin:
        if i == '1':
            cnt += 1
    return cnt


def calc_ans(next_int, cnt=None):
    key = next_int
    #if key in dp.keys():
    #    ans = dp[key]
    #else:
    if cnt is None:
        cnt = calc_bin_cnt(next_int)
    #else:
    #    bin_cnt[key] = cnt
    #bin_cnt[next_int] = cnt
    next_int = next_int % cnt
    if next_int > 0:
        ans = calc_ans(next_int) + 1
    else:
        ans = 1
    #dp[key] = ans
    return ans


for i in range(N):
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1)), X_cnt-1))
    else:
        print(calc_ans(X_int + (2**(N-i-1)), X_cnt+1))

Submission status: Runtime Error

Solution code:
import sys


N = int(input())
X_bin = input()

X_int = int(X_bin, 2)  # bin => int
# popcount
X_cnt = 0
for i in X_bin:
    if i == '1':
        X_cnt += 1
dp = {1: 1}
bin_cnt = {}

sys.setrecursionlimit(10**5)


def calc_bin_cnt(next_int):
    if next_int in bin_cnt.keys():
        cnt = bin_cnt[next_int]
    else:
        next_bin = format(next_int, 'b')
        # popcount
        cnt = 0
        for i in next_bin:
            if i == '1':
                cnt += 1
    return cnt


def calc_ans(next_int, cnt=None):
    key = next_int
    if key in dp.keys():
        ans = dp[key]
    else:
        if cnt is None:
            cnt = calc_bin_cnt(next_int)
        else:
            bin_cnt[key] = cnt
        bin_cnt[next_int] = cnt
        next_int = next_int % cnt
        if next_int > 0:
            ans = calc_ans(next_int) + 1
        else:
            ans = 1
        dp[key] = ans
    return ans


for i in range(N):
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1)), X_cnt-1))
    else:
        print(calc_ans(X_int + (2**(N-i-1)), X_cnt+1))

Submission status: Runtime Error

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

X_int = int(X_bin, 2)  # bin => int
dp = {1: 1}
bin_cnt = {}

import sys
sys.setrecursionlimit(10**5)


def calc_bin_cnt(next_int):
    if next_int in bin_cnt.keys():
        cnt = bin_cnt[next_int]
    else:
        next_bin = format(next_int, 'b')
        # popcount
        cnt = 0
        for i in next_bin:
            if i == '1':
                cnt += 1
        bin_cnt[next_int] = cnt
    return cnt


def calc_ans(next_int):
    key = next_int
    if key in dp.keys():
        ans = dp[key]
    else:
        '''
        next_bin = format(next_int, 'b')
        # popcount
        cnt = 0
        for i in next_bin:
            if i == '1':
                cnt += 1
        '''
        cnt = calc_bin_cnt(next_int)
        bin_cnt[next_int] = cnt
        next_int = next_int % cnt
        if next_int > 0:
            ans = calc_ans(next_int) + 1
        else:
            ans = 1
        dp[key] = ans
    return ans


for i in range(N):
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1))))
    else:
        print(calc_ans(X_int + (2**(N-i-1))))

Submission status: Runtime Error

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

X_int = int(X_bin, 2)  # bin => int
dp = {1: 1}
bin_cnt = {}


def calc_bin_cnt(next_int):
    if next_int in bin_cnt.keys():
        cnt = bin_cnt[next_int]
    else:
        next_bin = format(next_int, 'b')
        # popcount
        cnt = 0
        for i in next_bin:
            if i == '1':
                cnt += 1
        bin_cnt[next_int] = cnt
    return cnt


def calc_ans(next_int):
    key = next_int
    if key in dp.keys():
        ans = dp[key]
    else:
        '''
        next_bin = format(next_int, 'b')
        # popcount
        cnt = 0
        for i in next_bin:
            if i == '1':
                cnt += 1
        '''
        cnt = calc_bin_cnt(next_int)
        bin_cnt[next_int] = cnt
        next_int = next_int % cnt
        if next_int > 0:
            ans = calc_ans(next_int) + 1
        else:
            ans = 1
        dp[key] = ans
    return ans


for i in range(N):
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1))))
    else:
        print(calc_ans(X_int + (2**(N-i-1))))

Submission status: Runtime Error

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

X_int = int(X_bin, 2)  # bin => int
dp = {1: 1}
bin_cnt = {}


def calc_bin_cnt(next_int):
    print('calc_bin')
    if next_int in bin_cnt.keys():
        print('bin dp')
        cnt = bin_cnt[next_int]
    else:
        next_bin = format(next_int, 'b')
        # popcount
        cnt = 0
        for i in next_bin:
            if i == '1':
                cnt += 1
        bin_cnt[next_int] = cnt
    return cnt


def calc_ans(next_int):
    key = next_int
    if key in dp.keys():
        print('dp')
        ans = dp[key]
    else:
        '''
        next_bin = format(next_int, 'b')
        # popcount
        cnt = 0
        for i in next_bin:
            if i == '1':
                cnt += 1
        '''
        cnt = calc_bin_cnt(next_int)
        bin_cnt[next_int] = cnt
        next_int = next_int % cnt
        if next_int > 0:
            ans = calc_ans(next_int) + 1
        else:
            ans = 1
        dp[key] = ans
    return ans


for i in range(N):
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1))))
    else:
        print(calc_ans(X_int + (2**(N-i-1))))

Submission status: Runtime Error

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

X_int = int(X_bin, 2)  # bin => int
dp = {1: 1}
bin_cnt = {}


def calc_bin_cnt(next_int):
    if next_int in bin_cnt.keys():
        cnt = bin_cnt[next_int]
    else:
        next_bin = format(next_int, 'b')
        # popcount
        cnt = 0
        for i in next_bin:
            if i == '1':
                cnt += 1
        bin_cnt[next_int] = cnt
    return cnt


def calc_ans(next_int):
    key = next_int
    if key in dp.keys():
        ans = dp[key]
    else:
        '''
        next_bin = format(next_int, 'b')
        # popcount
        cnt = 0
        for i in next_bin:
            if i == '1':
                cnt += 1
        '''
        cnt = calc_bin_cnt(next_int)
        next_int = next_int % cnt
        if next_int > 0:
            ans = calc_ans(next_int) + 1
        else:
            ans = 1
        dp[key] = ans
    return ans


for i in range(N):
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1))))
    else:
        print(calc_ans(X_int + (2**(N-i-1))))

Submission status: Runtime Error

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

X_int = int(X_bin, 2)  # bin => int
dp = {1: 1}


def calc_ans(next_int):
    key = next_int
    if key in dp.keys():
        ans = dp[key]
    else:
        next_bin = format(next_int, 'b')
        # popcount
        cnt = 0
        for i in next_bin:
            if i == '1':
                cnt += 1
        next_int = next_int % cnt
        if next_int > 0:
            ans = calc_ans(next_int) + 1
        else:
            ans = 1
        dp[key] = ans
    return ans


for i in range(N):
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1))))
    else:
        print(calc_ans(X_int + (2**(N-i-1))))

Submission status: Runtime Error

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

X_int = int(X_bin, 2)  # bin => int

# popcount
X_cnt = 0
for i in X_bin:
    if i == '1':
        X_cnt += 1


def calc_ans(next_int, cnt):
    next_int = next_int % cnt
    ans = 1
    while next_int > 0:
        next_bin = format(next_int, 'b')
        # popcount
        cnt = 0
        for i in next_bin:
            if i == '1':
                cnt += 1
        next_int = next_int % cnt
        next_bin = format(next_int, 'b')
        ans += 1
    return ans


for i in range(N):
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1)), X_cnt-1))
    else:
        print(calc_ans(X_int + (2**(N-i-1)), X_cnt+1))

Submission status: Runtime Error

Solution code:
N = int(input())
strX = input()
 
#10進数に変換
decX = int(strX,2)
 
#1の数をカウント
pop_c = strX.count('1')
 
f_p = decX % (pop_c + 1)


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

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

Submission status: Runtime Error

Solution code:
N = int(input())
strX = input()
 
#10進数に変換
decX = int(strX,2)
 
#1の数をカウント
pop_c = strX.count('1')
 
f_p = decX % (pop_c + 1)
# X % popcount-1(0になる時は0)
if pop_c == 1:
      f_m = 0
else:
    f_m = decX % (pop_c - 1)

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

Submission status: Runtime Error

Solution code:
N = int(input())
strX = input()
 
#10進数に変換
decX = int(strX,2)
 
#1の数をカウント
pop_c = strX.count('1')
 

# X % popcount-1(0になる時は0)
if pop_c == 1:
      f_m = 0
else:
    f_m = decX % (pop_c - 1)

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

Submission status: Runtime Error

Solution code:
#import sys
#input = sys.stdin.readline

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

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

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

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

min_1=0
max_1=0

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

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

Submission status: Runtime Error

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

#10進数に変換
decX = int(strX,2)

#1の数をカウント
pop_c = strX.count('1')

# X % popcount+1
f_p = decX % (pop_c + 1)

# X % popcount-1(0になる時は0)
if pop_c == 1:
  f_m = 0
else:
  f_m = decX % (pop_c - 1)

#(2**i)÷popcountを保存するリストを作成
f_tp = [0] * N  
f_tm = [0] * N  

for i in range(0,N):
  f_tp[i] = (2**(N-1-i)) % (pop_c + 1) 
  f_tm[i] = (2**(N-1-i)) % (pop_c - 1) 

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

Submission status: Runtime Error

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

#10進数に変換
decX = int(strX,2)

#1の数をカウント
pop_c = strX.count('1')

# X % popcount+1
f_p = decX % (pop_c + 1)

# X % popcount-1(0になる時は0)
if pop_c == 1:
  f_m = 0
else:
  f_m = decX % (pop_c - 1)

#(2**i)÷popcountを保存するリストを作成
f_tp = [0] * N  
f_tm = [0] * N  

for i in range(0,N):
  f_tp[i] = (2**(N-1-i)) % (pop_c + 1) 
  f_tm[i] = (2**(N-1-i)) % (pop_c - 1) 

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

Submission status: Runtime Error

Solution code:
MAX = 2*10**5
def popcount(x):
    return bin(x).count("1")
def solve(n):
    if n == 0:
        return 0
    return 1+solve(n % popcount(n))

N = int(input())
X = input()
num_x = int(X, 2)
p_cnt = X.count('1')
r0_p = num_x % (p_cnt+1)
r0_m = num_x % (p_cnt-1)
for i in range(N):
    if X[i] == '0':
        c_p_cnt = p_cnt+1
        r = r0_p + (2**(N-1-i) % c_p_cnt)
    else:
        c_p_cnt = p_cnt-1
        if c_p_cnt == 0:
            print(0)
            continue
        r = r0_m - (2**(N-1-i) % c_p_cnt)
    print(1 + solve(r % c_p_cnt))

Submission status: Runtime Error

Solution code:
MAX = 2*10**5
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
s_map = [0 for i in range(MAX+1)]
def solve(n):
    if n == 0:
        return 1
    if s_map[n] > 0:
        return s_map[n]
    s_map[n] = 1 + solve(n % popcount(n))
    return s_map[n]

N = int(input())
X = input()
num_x = int(X, 2)
p_cnt = X.count('1')
amari_p = num_x % (p_cnt+1)
amari_m = num_x % (p_cnt-1)
for i in range(N):
    if X[i] == '0':
        c_p_cnt = p_cnt+1
        amari = amari_p + 2**(N-1-i) % c_p_cnt
    else:
        c_p_cnt = p_cnt - 1
        amari = amari_m - 2**(N-1-i) % c_p_cnt
    print(solve(amari % c_p_cnt))

Submission status: Runtime Error

Solution code:
MAX = 2*10**5
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
s_map = [0 for i in range(MAX+1)]
def solve(n):
    if n == 0:
        return 1
    if s_map[n] > 0:
        return s_map[n]
    s_map[n] = 1 + solve(n % popcount(n))
    return s_map[n]

N = int(input())
X = input()
num_x = int(X, 2)
p_cnt = X.count('1')
for i in range(N):
    c_p_cnt = p_cnt+1 if X[i] == '0' else p_cnt-1
    x = num_x + 2**(N-1-i) if X[i] == '0' else num_x - 2**(N-1-i)
    print(solve(x % c_p_cnt))

Submission status: Runtime Error

Solution code:
#D
N=int(input())
X=str(input())
   
CNT=0
for i in range(N):
    if X[i]=="1":
        CNT+=1
NUM=int(X,2)

to0_cnt=[0 for i in range(N)]
for i in range(1,N):
    ans=0
    num=i
    while True:
        cnt=0
        for j in bin(num)[2:]:
            if j=="1":
                cnt+=1
        if cnt==0:
            break
        r=num%cnt
        ans+=1
        if r==0:
            break
        num=r
    to0_cnt[i]=ans
                

R=[NUM%(CNT+1),NUM%(CNT-1)]
for i in range(N):
    if X[i]=="0":
        cnt=CNT+1
        r=(R[0]+2**(N-i-1))%cnt
    else:
        cnt=CNT-1
        r=(R[1]-2**(N-i-1))%cnt
    
    ans=1+to0_cnt[r]
    print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
num = input()
X = int(num,2)
c = num.count('1')
def A(s):
    if s == 0:
        return 1
    return A(s%(bin(s).count('1'))) + 1
if c==1:
  for i in range(N):
    if num[i] == '1':
      print(0)
    elif i == N-1:
      print(2)
    else:
      print(1)
  exit()
amari1 = X%(c+1)
amari2 = X%(c-1)
for i in range(N):
    if num[i] == '1':
        print(A((amari2-pow(2,N-1-i,c-1))%(C-1)))
    else:
        print(A((amari1+pow(2,N-1-i,c+1))%(C-1)))

Submission status: Runtime Error

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

decX = int(strX,2)
cnt = strX.count('1')

pop_p = decX % (cnt + 1)
pop_m = decX % (cnt - 1)

for i in range(0,N):
  if strX[i] == '0':
    pop = (2**(N-1-i) + pop_p) % (cnt + 1)
    Ans = 1
    
  elif strX[i] == '1' and cnt == 1:
    pop = 0
    Ans = 0
    
  else:
    pop = (2**(N-1-i) - pop_m) % (cnt - 1)
    Ans = 1
  
  while pop > 0:
    wkcnt = bin(pop).count('1')
    pop = pop % wkcnt
    Ans += 1
  
  print(Ans)

Submission status: Runtime Error

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

decX = int(strX,2)
cnt = strX.count('1')

pop_p = decX % (cnt + 1)
pop_m = decX % (cnt - 1)

for i in range(0,N):
  if strX[i] == '0':
    pop = (pop_p + (2**(N-1-i) % (cnt + 1))) % (cnt + 1)
    Ans = 1
    
  elif strX[i] == '1' and cnt == 1:
    pop = 0
    Ans = 0
    
  else:
    pop = (pop_m - (2**(N-1-i) % (cnt - 1))) % (cnt - 1)
    Ans = 1
  
  while pop > 0:
    wkcnt = bin(pop).count('1')
    pop = pop % wkcnt
    Ans += 1
  
  print(Ans)

Submission status: Runtime Error

Solution code:
#D
N=int(input())
X=str(input())
   
CNT=0
for i in range(N):
    if X[i]=="1":
        CNT+=1
NUM=int(X,2)

R=[NUM%(CNT+1),NUM%(CNT-1)]
for i in range(N):
    if X[i]=="0":
        cnt=CNT+1
        r=(R[0]+2**(N-i-1))%cnt
    else:
        cnt=CNT-1
        r=(R[1]-2**(N-i-1))%cnt
    
    ans=1
    while True:
        if r==0:
            print(ans)
            break

        num=r
        cnt=0
        for i in bin(num)[2:]:
            if i=="1":
                cnt+=1
        r=num%cnt
        ans+=1

Submission status: Runtime Error

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

decX = int(strX,2)
cnt = strX.count('1')

for i in range(0,N):
#  print('i=' + str(i))
  if strX[i] == '0':
    wkstr = strX[:i] + '1' + strX[i+1:N+1]
  else:
    wkstr = strX[:i] + '0' + strX[i+1:N+1]
  
  wkcnt = wkstr.count('1')
#  print(wkstr)
#  print(wkcnt)
  wkdec = int(wkstr,2)
  pop = wkdec % wkcnt
  Ans = 1
  
  while pop > 0:
    wkcnt = bin(pop).count('1')
    pop = pop % wkcnt
    Ans += 1
  
  print(Ans)

Submission status: Runtime Error

Solution code:
from collections import Counter
N = int(input())
X = input()

memo = {}
def calc(A,cnt):
  if A in memo:
    return memo[A]
  a = int(A,2)
  c = Counter(list(A))
  
  #print(a,c['1'])
  x = a % c['1']
  if x == 0:
    memo[A] = cnt+1
    return cnt+1
  else:
    wk = calc(format(x, 'b'), cnt+1)
    memo[A] = wk
    return wk

for i in range(N-1,-1,-1):
  x = format(int(X,2) ^ (2**i), 'b')
  #print(x)
  print(calc(x,0))

Submission status: Runtime Error

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

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

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

for i in range(len(X),0,-1):
    if X[-i]=='1':
        tmp=base-2**(i-1)
    else:
        tmp=base+2**(i-1)
    print(f(tmp))