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())
s = input()
cnt=s.count("1")
popX=[]
x=int(s,2)
X=[]
for i in range(N):
    if s[i]=="1":
        popX.append(cnt-1)
        X.append(x-2**(N-i-1))
    else:
        popX.append(cnt+1)
        X.append(x+2**(N-i-1))
xm=x%(cnt-1)
xp=x%(cnt+1)
for i in range(N):
    f=0
    while X[i]>0:
        if popX[i]==cnt+1:
            a=xm+2**(N-i-1)%cnt+1
            if a==cnt+1:
                a=0
            X[i]=a
        elif popX[i]==cnt-1:
            a=xm+2**(N-i-1)%(cnt-1)
            if a==cnt-1:
                a=0
            X[i]=a
        else:
            X[i]=X[i]%popX[i]
            
        S=bin(X[i])
        S=str(S)
        popX[i]=S.count("1")
        
        f=f+1
    print(f)

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(input())
X = str(input())
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)])


def func(x):
    if x == 0:
        return 0
    else:
        counter = 0
        x_tmp = x
        while x > 0:
            if x % 2 == 1:
                counter += 1
            x = x >> 1
        return func(x_tmp % counter) + 1

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)

Submission status: Runtime Error

Solution code:
import sys
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(sys.stdin.readline())
def ria(): return list(map(int, sys.stdin.readline().split()))
def ws(s): sys.stdout.write(s); sys.stdout.write('\n')
def wi(n): sys.stdout.write(str(n)); sys.stdout.write('\n')
def wia(a, sep=' '): sys.stdout.write(sep.join([str(x) for x in a])); sys.stdout.write('\n')


def main():
    n = ri()
    x = rs()

    k = int(x, 2)
    d = x.count('1')
    k0 = 0
    if d > 0:
        k0 = k % (d-1)
    k1 = k % (d+1)

    f = [0] * (n + 1)
    for i in range(1, n+1):
        f[i] = f[i % bin(i).count('1')] + 1

    for i in range(n):
        cnt = 0
        if x[i] == '1' and d - 1 > 0:
            cnt += f[(k0 - pow(2, n - i - 1, d - 1)) % (d - 1)] + 1
        elif x[i] == '0':
            cnt += f[(k1 + pow(2, n - i - 1, d + 1)) % (d + 1)] + 1
        wi(cnt)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

cnt = X.count('1')
if cnt == 1:
    print(*([1] + N), sep='\n')
    exit()

M = 0
for x in X:
    M <<= 1
    if x == '1':
        M += 1

def solve(n):
    ret = 1
    while n > 0:
        ret += 1
        n %= bin(n).count('1')
    return ret

ans = []
p = M % (cnt + 1)
m = M % (cnt - 1)

for i in range(N):
    if X[i] == '0':
        ans.append(solve((p + pow(2, N - i - 1, cnt + 1)) % (cnt + 1)))
    else:
        ans.append(solve((m - pow(2, N - i - 1, cnt - 1)) % (cnt - 1)))
print(*ans, sep='\n')

Submission status: Runtime Error

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

cnt = X.count('1')
M = 0
for x in X:
    M <<= 1
    if x == '1':
        M += 1

def solve(n):
    ret = 1
    while n > 0:
        ret += 1
        n %= bin(n).count('1')
    return ret

ans = []
p = M % (cnt + 1)
m = M % (cnt - 1)

for i in range(N):
    if X[i] == '0':
        ans.append(solve((p + pow(2, N - i - 1, cnt + 1)) % (cnt + 1)))
    else:
        ans.append(solve((m - pow(2, N - i - 1, cnt - 1)) % (cnt - 1)))
print(*ans, sep='\n')

Submission status: Runtime Error

Solution code:
N = int(input())
X = int(str(input()), 2)
X_bin = format(X, '0'+str(N)+'b')

ans = [0] * N
dp = [0] * 2 ** (X_bin.count('1') + 1)
for i in range(N):
    if X_bin[i] == '1':
        n = X - (1 << (N - 1 - i))
    else:
        n = X + (1 << (N - 1 - i))

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

    print(ans[i])

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
X2 = [int(i) for i in X]
S = int(X, 2)

p = bin(S).count("1")
a = S % (p + 1)
b = S % (p - 1)

def f(n):
    r = 1
    while n:
        n = n % bin(n).count("1")
        r += 1
    return r

d = 2 ** N
for i in range(1, N+1):
    d = d // 2
    if not X2[i-1]:
        if S + d == 0:
            print(0)
            continue
        t = a + d
        s = t % (p + 1)
    else:
        if S - d == 0:
            print(0)
            continue
        t = b - d
        s = t % (p - 1)
    print(f(s))

Submission status: Runtime Error

Solution code:
import sys
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(sys.stdin.readline())
def ria(): return list(map(int, sys.stdin.readline().split()))
def ws(s): sys.stdout.write(s); sys.stdout.write('\n')
def wi(n): sys.stdout.write(str(n)); sys.stdout.write('\n')
def wia(a, sep=' '): sys.stdout.write(sep.join([str(x) for x in a])); sys.stdout.write('\n')


def main():
    n = ri()
    x = rs()

    k = int(x, 2)
    d = x.count('1')
    k0 = 0
    if d > 0:
        k0 = k % (d-1)
    k1 = k % (d+1)

    f = [0] * (n + 1)
    for i in range(1, n+1):
        f[i] = f[i % bin(i).count('1')] + 1

    for i in range(n):
        if x[i] == '1':
            dd = d - 1
            if dd == 0:
                wi(0)
                continue
            wi(f[(k0 - pow(2, n - i - 1, dd)) % dd] + 1)
        else:
            dd = d + 1
            wi(f[(k1 + pow(2, n - i - 1, dd)) % dd] + 1)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
l=[]
for i in range(n):
    p=list(x[::])
    p[i]=str(1-int(p[i]))
    l+=[int("".join(p),2)]
for i in l:
    j=i
    t=0
    while True:
        k=bin(j).count("1")
        t+=1
        if j%k==0:
            break
        j=j%k
    print(t)

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
X2 = [int(i) for i in X]
S = int(X, 2)

p = bin(S).count("1")
a = S % (p + 1)
b = S % (p - 1)

def f(n):
    r = 1
    while n:
        n = n % bin(n).count("1")
        r += 1
    return r

for i in range(1, N+1):
    d = 2 ** (N-i)
    if not X2[i-1]:
        if S + d == 0:
            print(0)
            continue
        t = a + d
        s = t % (p + 1)
    else:
        if S - d == 0:
            print(0)
            continue
        t = b - d
        s = t % (p - 1)
    print(f(s))

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
X2 = [int(i) for i in X]
S = int(X, 2)

p = bin(S).count("1")
a = S % (p + 1)
b = S % (p - 1)

def f(n):
    r = 1
    while n:
        n = n % bin(n).count("1")
        r += 1
    return r

for i in range(1, N+1):
    d = 2 ** (N-i)
    if not X2[i-1]:
        if S + d == 0:
            print(0)
            continue
        t = a + d
        s = t % (p + 1)
    else:
        if S - d == 0:
            print(0)
            continue
        t = b - d
        s = t % (p - 1)
    print(f(s))

Submission status: Runtime Error

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


def pop_count(nbin):
    return nbin.count("1")


def bin2dec(nbin):
    nbin_str = "".join(nbin)
    return int(nbin_str, 2)


def reverse(nbin, dig):
    nbin_list = list(nbin)
    if nbin_list[dig] == "0":
        nbin_list[dig] = "1"
    else:
        nbin_list[dig] = "0"
    return nbin_list


def f(nbin):
    counter = 0
    nbin_str = "".join(nbin)
    while nbin_str != "0b0":
        new_n = bin2dec(nbin_str) % pop_count(nbin_str)
        nbin_str = bin(new_n)
        counter += 1
    return counter


N = int(input())
X = "0b" + input()

for i in range(N):
    print(f(reverse(X, i + 2)))

Submission status: Runtime Error

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


def pop_count(nbin):
    return nbin.count("1")


def bin2dec(nbin):
    nbin_str = "".join(nbin)
    return int(nbin_str, 2)


def reverse(nbin, dig):
    nbin_list = list(nbin)
    if nbin_list[dig] == "0":
        nbin_list[dig] = "1"
    else:
        nbin_list[dig] = "0"
    return nbin_list


def f(nbin):
    counter = 0
    while nbin != "0b0":
        new_n = bin2dec(nbin) % pop_count(nbin)
        nbin = bin(new_n)
        counter += 1
    return counter


N = int(input())
X = "0b" + input()

for i in range(N):
    print(f(reverse(X, i + 2)))

Submission status: Runtime Error

Solution code:
from functools import lru_cache


a = int(input())
b = input()
X = b.count("1")
ans1 = []
ans2 = []

@lru_cache(maxsize=None)
def func1(c):
    x = X + 1
    if x == 0:
        return 0
    n = 1
    nsum = 0
    for i in reversed(range(len(c))):
        ans1.append(n)
        nsum += n * int(c[i])
        n = n % x if n > x else n
        n *= 2
    return nsum
    
@lru_cache(maxsize=None)
def func2(c):
    x = X - 1
    if x == 0:
        return 0
    n = 1
    nsum = 0
    for i in reversed(range(len(c))):
        ans2.append(n)
        nsum += n * int(c[i])
        n = n % x if n > x else n
        n *= 2
    return nsum    

def func(c):
    x = c.count("1")
    if x == 0:
        return 0
    n = 1
    nsum = 0
    for i in reversed(range(len(c))):
        nsum += n * int(c[i])
        n = n % x if n > x else n
        if n == 0:
            break
        n *= 2
    nsum %= x
    cans = bin(nsum).count("1")
    if cans == 0:
        return 1
    else:
        return 1 + func(bin(nsum)[2:])
    
allans1 = func1(b)
allans2 = func2(b)
ans1 = ans1[::-1]
ans2 = ans2[::-1]
c = list(b)
for i in range(a):
    if c[i] == "0":
        ans = (allans1 + ans1[i]) % (X + 1)
        ans = func(bin(ans)[2:]) + 1
        print(str(ans))
    else:
        ans = (allans2 - ans2[i]) % (X - 1)
        ans = func(bin(ans)[2:]) + 1
        print(str(ans))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**6)
INF = float("inf")

def popcount(n):
    ret = 0
    for i in range(18):
        if n>>i & 1:
            ret += 1
    return ret

def main():
    N = int(input())
    X = input().decode().rstrip()

    # X に含まれる "1" の数
    x_cnt = 0
    for i in range(N):
        if X[i] == "1":
            x_cnt += 1

    # i 桁目が 0 : x_cnt += 1
    # i 桁目が 1 : x_cnt -= 1
    # より, X mod x_cnt +1, X mod x_cnt-1 を事前計算しておく
    n_plus,n_minus = 0,0
    t_plus,t_minus = 1,1
    for i in range(N-1,-1,-1):
        if X[i]=="1":
            n_plus += t_plus
            n_plus %= x_cnt + 1
            n_minus += t_minus
            n_minus %= x_cnt - 1
        t_plus = (t_plus*2) % (x_cnt + 1)
        t_minus = (t_minus*2) % (x_cnt - 1)
    
    for i in range(N):
        ans = 1
        if X[i] == "1":
            # 1 -> 0 に変換した結果, １が全く存在しない場合
            #if x_cnt == 1:
            #    print(0)
            #    continue
            a = (n_minus - pow(2,(N-1-i), x_cnt-1)) % (x_cnt-1)
        else:
            a = (n_plus + pow(2,(N-1-i), x_cnt+1)) % (x_cnt+1)

        while a > 0:
            pop_cnt = popcount(a)
            a %= pop_cnt
            ans += 1

        print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python

def popcount(n):
    ret = 0
    for i in range(18):
        if n>>i & 1:
            ret += 1
    return ret

def main():
    N = int(input())
    X = input()

    # X に含まれる "1" の数
    x_cnt = 0
    for i in range(N):
        if X[i] == "1":
            x_cnt += 1

    # i 桁目が 0 : x_cnt += 1
    # i 桁目が 1 : x_cnt -= 1
    # より, X mod x_cnt +1, X mod x_cnt-1 を事前計算しておく
    n_plus,n_minus = 0,0
    t_plus,t_minus = 1,1
    for i in range(N-1,-1,-1):
        if X[i]=="1":
            n_plus += t_plus
            n_plus %= x_cnt + 1
            n_minus += t_minus
            n_minus %= x_cnt - 1
        t_plus = (t_plus*2) % (x_cnt + 1)
        t_minus = (t_minus*2) % (x_cnt - 1)
    
    for i in range(N):
        ans = 1
        if X[i]=="1":
            # 1 -> 0 に変換した結果, １が全く存在しない場合
            if x_cnt == 1:
                print(0)
                continue
            a = (n_minus - pow(2,(N-1-i), x_cnt-1)) % (x_cnt-1)
        else:
            a = (n_plus + pow(2,(N-1-i), x_cnt+1)) % (x_cnt+1)
        while a > 0:
            pop_cnt = popcount(a)
            a %= pop_cnt
            ans += 1
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def func(nStep:int, X) -> int:
    nStep += 1
    newX = X % bin(X).count('1')
    if newX == 0:
        return nStep
    else:
        return func(nStep, newX)

def solve():
    N = int(input())
    X = input()
    for i in range(N):
        print(func(0, int(X,2)^(1<<(N-i-1))))

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python

def popcount(n):
    ret = 0
    for i in range(18):
        if n>>i & 1:
            ret += 1
    return ret

def main():
    N = int(input())
    X = input()

    # X に含まれる "1" の数
    x_cnt = 0
    for i in range(N):
        if X[i] == "1":
            x_cnt += 1

    # i 桁目が 0 : x_cnt += 1
    # i 桁目が 1 : x_cnt -= 1
    # より, X mod x_cnt +1, X mod x_cnt-1 を事前計算しておく
    n_plus,n_minus = 0,0
    for i in range(N):
        if X[i]=="1":
            n_plus += 2**(N-1-i)
            n_plus %= x_cnt + 1
            n_minus += 2**(N-1-i)
            n_minus %= x_cnt - 1
    
    for i in range(N):
        ans = 1
        if X[i]=="1":
            # 1 -> 0 に変換した結果, １が全く存在しない場合
            if x_cnt == 1:
                print(0)
                continue
            a = (n_minus - pow(2,(N-1-i), x_cnt-1)) % (x_cnt-1)
        else:
            a = (n_plus + pow(2,(N-1-i), x_cnt+1)) % (x_cnt+1)
        while a > 0:
            pop_cnt = popcount(a)
            a %= pop_cnt
            ans += 1
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**6)
INF = float("inf")
MOD = 10**9+7

def popcount(n):
    ret = 0
    for i in range(18):
        if n>>i & 1:
            ret += 1
    return ret

def main():
    N = int(input())
    X = input().decode().rstrip()

    # X に含まれる "1" の数
    x_cnt = 0
    for i in range(N):
        if X[i]=="1":
            x_cnt += 1

    # i 桁目が 0 : x_cnt += 1
    # i 桁目が 1 : x_cnt -= 1
    # より, X mod x_cnt +1, X mod x_cnt-1 を事前計算しておく
    n_plus,n_minus = 0,0
    for i in range(N):
        if X[i]=="1":
            n_plus += 2**(N-1-i)
            n_plus %= x_cnt + 1
            n_minus += 2**(N-1-i)
            n_minus %= x_cnt - 1
    
    for i in range(N):
        ans = 1
        if X[i]=="1":
            # 1 -> 0 に変換した結果, １が全く存在しない場合
            if x_cnt == 1:
                print(0)
                continue
            a = (n_minus - pow(2,(N-1-i), x_cnt-1)) % (x_cnt-1)
        else:
            a = (n_plus + pow(2,(N-1-i), x_cnt+1)) % (x_cnt+1)
        while a > 0:
            pop_cnt = popcount(a)
            a %= pop_cnt
            ans += 1
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def search(n):
    res = 0
    while n:
        n %= bin(n).count("1")
        res += 1
    return res


def main():
    n = int(input())
    x = list(map(int, list(input())))
    first_mod = x_decimal = 0
    diff = pow(2, n - 1)
    for i in range(n):
        if x[i]:
            first_mod += 1
            x_decimal += diff
        diff //= 2
    increase_base = x_decimal % (first_mod + 1)  # 反転させる桁が元々0だった場合
    decrease_base = x_decimal % (first_mod - 1)  # 反転させる桁が元々1だった場合
    diff = pow(2, n - 1)
    for i in range(n):
        cnt = 0
        if x[i] == 1 and first_mod > 1:
            cnt = 1 + search((decrease_base - diff % (first_mod - 1)) % (first_mod - 1))
        elif x[i] == 0:
            cnt = 1 + search((increase_base + diff % (first_mod + 1)) % (first_mod + 1))
        diff //= 2
        print(cnt)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

def p(x):
  a = list(bin(x))
  return a.count('1')
  
N = int(input())
X = input()
A = [0] * N
for i in range(N):
  if X[i] == '1':
    A[i] = int(X,2) - 2**(N-i-1)
  else:
    A[i] = int(X,2) + 2**(N-i-1)
for j in A:
  print(f(j))

Submission status: Runtime Error

Solution code:
def func(nStep:int, X) -> int:
    nStep += 1
    newX = X % bin(X).count('1')
    if newX == 0:
        return nStep
    else:
        return func(nStep, newX)

def solve():
    N = int(input())
    X = input()
    for i in range(N):
        print(func(0, int(format(int(X,2)^(1<<(N-i-1)),'b').zfill(N), 2)))

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**6)
INF = float("inf")
MOD = 10**9+7

def popcount(n):
    ret = 0
    for i in range(18):
        if n>>i & 1:
            ret += 1
    return ret

def main():
    N = int(input())
    X = input().decode().rstrip()

    # X に含まれる "1" の数
    x_cnt = X.count("1")

    # i 桁目が 0 : x_cnt += 1
    # i 桁目が 1 : x_cnt -= 1
    # より, X mod x_cnt +1, X mod x_cnt-1 を事前計算しておく
    n_plus,n_minus = 0,0
    for i in range(N):
        if X[i]=="1":
            n_plus += 2**(N-1-i)
            n_plus %= x_cnt + 1
            n_minus += 2**(N-1-i)
            n_minus %= x_cnt - 1
    
    for i in range(N):
        ans = 1
        if X[i]=="1":
            # 1 -> 0 に変換した結果, １が全く存在しない場合
            if n_minus == 0:
                print(0)
                continue
            a = (n_minus - pow(2,(N-1-i), x_cnt-1)) % (x_cnt-1)
        else:
            a = (n_plus + pow(2,(N-1-i), x_cnt+1)) % (x_cnt+1)
        while a > 0:
            pop_cnt = popcount(a)
            a %= pop_cnt
            ans += 1
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
chk0=chk1=chk2=0
b=x.count("1")
if b==1 and x=="1":
    print(0)
    exit()
elif b==1 and x[-1]=="1":
    for i in range(n-1):
        print(2)
    print(0)
    exit()
elif b==1:
    for i in range(n):
        if i=="0": print(1//0)
        else: print(0//0)
    exit()
for i,j in enumerate(x[::-1]):
    if j=="1":
        chk1+=pow(2,i,b+1)
        if b>1: chk2+=pow(2,i,b-1)
        else: chk2=0
l=[]
for i,j in enumerate(x[::-1]):
    if b: a1=pow(2,i,b+1)
    else: a1=1
    if b>1: a2=pow(2,i,b-1)
    else: a2=1
    if j=="0":
        t=chk1+a1
    else:
        if b>1: t=chk2+b-1-a2
        else: t=0
    ans,f=0,1
    while t:
        if f:
            if j=="0": t%=(b+1)
            else: t%=(b-1)
            f=0
        else:
            t%=bin(t).count("1")
        ans+=1
    l.append(ans)
for i in l[::-1]:
    print(i)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**6)
INF = float("inf")
MOD = 10**9+7

def popcount(n):
    ret = 0
    for i in range(18):
        if n>>i & 1:
            ret += 1
    return ret

def main():
    N = int(input())
    X = input().decode().rstrip()

    # X に含まれる "1" の数
    x_cnt = X.count("1")

    # i 桁目が 0 : x_cnt += 1
    # i 桁目が 1 : x_cnt -= 1
    # より, X mod x_cnt +1, X mod x_cnt-1 を事前計算しておく
    n_plus,n_minus = 0,0
    for i in range(N):
        if X[i]=="1":
            n_plus += 2**(N-1-i)
            n_plus %= x_cnt + 1
            n_minus += 2**(N-1-i)
            n_minus %= x_cnt - 1
    
    for i in range(N):
        ans = 1
        if X[i]=="1":
            a = (n_minus - pow(2,(N-1-i), x_cnt-1)) % (x_cnt-1)
        else:
            a = (n_plus + pow(2,(N-1-i), x_cnt+1)) % (x_cnt+1)
        while a > 0:
            pop_cnt = popcount(a)
            a %= pop_cnt
            ans += 1
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
chk0=chk1=chk2=0
b=x.count("1")
if b==1 and x=="1":
    print(0)
    exit()
elif b==1 and x[-1]=="1":
    for i in range(n-1):
        print(2//0)
    print(0)
    exit()
elif b==1:
    for i in range(n):
        if i=="0": print(1//0)
        else: print(0//0)
    exit()
for i,j in enumerate(x[::-1]):
    if j=="1":
        chk1+=pow(2,i,b+1)
        if b>1: chk2+=pow(2,i,b-1)
        else: chk2=0
l=[]
for i,j in enumerate(x[::-1]):
    if b: a1=pow(2,i,b+1)
    else: a1=1
    if b>1: a2=pow(2,i,b-1)
    else: a2=1
    if j=="0":
        t=chk1+a1
    else:
        if b>1: t=chk2+b-1-a2
        else: t=0
    ans,f=0,1
    while t:
        if f:
            if j=="0": t%=(b+1)
            else: t%=(b-1)
            f=0
        else:
            t%=bin(t).count("1")
        ans+=1
    l.append(ans)
for i in l[::-1]:
    print(i)

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
chk0=chk1=chk2=0
b=x.count("1")
if b==1 and x=="1":
    print(0//0)
    exit()
elif b==1 and x[-1]=="1":
    for i in range(n-1):
        print(2//0)
    print(0)
    exit()
elif b==1:
    for i in range(n):
        if i=="0": print(1//0)
        else: print(0//0)
    exit()
for i,j in enumerate(x[::-1]):
    if j=="1":
        chk1+=pow(2,i,b+1)
        if b>1: chk2+=pow(2,i,b-1)
        else: chk2=0
l=[]
for i,j in enumerate(x[::-1]):
    if b: a1=pow(2,i,b+1)
    else: a1=1
    if b>1: a2=pow(2,i,b-1)
    else: a2=1
    if j=="0":
        t=chk1+a1
    else:
        if b>1: t=chk2+b-1-a2
        else: t=0
    ans,f=0,1
    while t:
        if f:
            if j=="0": t%=(b+1)
            else: t%=(b-1)
            f=0
        else:
            t%=bin(t).count("1")
        ans+=1
    l.append(ans)
for i in l[::-1]:
    print(i)

Submission status: Runtime Error

Solution code:
N = int(input())
X = int(str(input()), 2)
X_bin = format(X, '0'+str(N)+'b')

ans = [0] * N
dp = [0] * 2 ** (N + 1)
for i in range(N):
    if X_bin[i] == '1':
        n = X - (1 << (N - 1 - i))
    else:
        n = X + (1 << (N - 1 - i))

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

    print(ans[i])

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
chk0=chk1=chk2=0
b=x.count("1")
if b==1 and x=="1":
    print(1)
#elif b==1:
else:
    print(n//0)
    exit()

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
c = x.count("1")


for i in range(n):
    a = int(x[i])
    if a == 1:
        a = 0
        cc = c - 1
    else:
        a = 1
        cc = c + 1
    ref = int(x[:i] + str(a) + x[i + 1:], 2)
    cnt = 0
    ref = ref%cc
    cnt += 1
    while ref > 0:
        bitcnt = bin(ref).count("1")
        ref = ref%bitcnt
        cnt += 1
    print(cnt)

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
chk0=chk1=chk2=0
b=x.count("1")
if b==1:
    print(n//0)
    exit()
for i,j in enumerate(x[::-1]):
    if j=="1":
        chk1+=pow(2,i,b+1)
        if b>1: chk2+=pow(2,i,b-1)
        else: chk2=0
l=[]
for i,j in enumerate(x[::-1]):
    if b: a1=pow(2,i,b+1)
    else: a1=1
    if b>1: a2=pow(2,i,b-1)
    else: a2=1
    if j=="0":
        t=chk1+a1
    else:
        if b>1: t=chk2+b-1-a2
        else: t=0
    ans=0
    f=1
    while t:
        if f:
            if j=="0": t%=(b+1)
            else: t%=(b-1)
            f=0
        else:
            t%=bin(t).count("1")
        ans+=1
    l.append(ans)
for i in l[::-1]:
    print(i)

Submission status: Runtime Error

Solution code:
class ModInt:
    def __init__(self, x, MOD):
        self.x = x % MOD
        self.m = MOD

    def __add__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x + other.x, self.m)
        else:
            return ModInt(self.x + other, self.m)

    __radd__ = __add__

    def __sub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x - other.x, self.m)
        else:
            return ModInt(self.x - other, self.m)

    def __rsub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(other.x - self.x, self.m)
        else:
            return ModInt(other - self.x, self.m)

    def __pow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(self.x, other.x, self.m), self.m)
        else:
            ModInt(pow(self.x, other, self.m), self.m)

    def __rpow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(other.x, self.x, self.m), self.m)
        else:
            ModInt(pow(other, self.x, self.m), self.m)

N = int(input())
X = list(map(int, input()))
Xc = sum(X)

if Xc == 0:
    [print(1) for i in range(N)]
elif Xc == 1:
    ans1 = ModInt(0, Xc+1)
    for j in range(N):
        if X[j]:
            ans1 += ModInt(2,Xc+1) ** (N-1-j)

    for j in range(N):
        if X[j]:
            print(0)
        else:
            print(2) if X[N-1] or j == N-1 else print(1)
else:
    ans1 = ModInt(0, Xc+1)
    ans2 = ModInt(0, Xc-1)
    for j in range(N):
        if X[j]:
            ans1 += pow(2,N-1-j,Xc+1)
            ans2 += pow(2,N-1-j,Xc-1)

    for i in range(N):
        if X[i]:# 1->0
            ans = ans2 - pow(2,N-1-i,Xc-1)
        else:# 0->1
            ans = ans1 + pow(2,N-1-i,Xc+1)
        count = 1
        while ans.x > 0:
            tmp = str(bin(ans.x)).count('1')
            ans.x %= tmp
            count += 1
        print(count)

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
if bin(x).count("1")==0:
  for i in x:
    print(1)
else:
  print(0)

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
if bin(x).count("1")==0:
  for i in x:
    print(1)
else:
  	print(0)

Submission status: Runtime Error

Solution code:
a = [input() for i in range(2)]
def popcount(n):
    count=0
    while n!=0:
        if n%2==1:
            count+=1
        n=int(n/2)
    return count

def f(n):
    c=0
    while n!=0:
        n=int(n%popcount(n))
        c+=1
    print(c)

b=[]
for i in range(int(a[0])):
    k=0
    b=list(a[1])
    if b[i]=='0':
        b[i]='1'
    else :
        b[i]='0'
    for j in range(int(a[0])):
        k = k*2 + int(b[j])
    f(k)

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
p=x.count('1')

#popcount(x)が0,1だった場合に対応
if p==0:
    exit()
    for i in range(n):
        print(1)
    exit()
#elif p==1:
#    z=x.index('1')
#    for i in range(n):
#        if i==z:
#            print(0)
#        else:
#            print(1)
#    exit()

#愚直に解く関数を定義
def solve(n):
    count=0
    while n:
        popcount=bin(n).count('1')
        n%=popcount
        count+=1
    return count

#2^i mod(p+1),2^i mod(p-1)のリストを作成
a,b=[],[]
for i in range(n):
    a.append(pow(2,i,p+1))
    b.append(pow(2,i,p-1))

#x mod(p+1),x mod(p-1)を計算
a1,b1=0,0
for i in range(n):
    if x[-1-i]=='1':
        a1+=a[i]
        b1+=b[i]

#本計算
for i in range(n):
    if x[i]=='1':
        tmp=(b1-b[-1-i])%(p-1)
    else:
        tmp=(a1+a[-1-i])%(p+1)
    print(solve(tmp)+1)

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
p=x.count('1')

#popcount(x)が0,1だった場合に対応
if p==0:
    for i in range(n):
        print(1)
    exit()
#elif p==1:
#    z=x.index('1')
#    for i in range(n):
#        if i==z:
#            print(0)
#        else:
#            print(1)
#    exit()

#愚直に解く関数を定義
def solve(n):
    count=0
    while n:
        popcount=bin(n).count('1')
        n%=popcount
        count+=1
    return count

#2^i mod(p+1),2^i mod(p-1)のリストを作成
a,b=[],[]
for i in range(n):
    a.append(pow(2,i,p+1))
    b.append(pow(2,i,p-1))

#x mod(p+1),x mod(p-1)を計算
a1,b1=0,0
for i in range(n):
    if x[-1-i]=='1':
        a1+=a[i]
        b1+=b[i]

#本計算
for i in range(n):
    if x[i]=='1':
        tmp=(b1-b[-1-i])%(p-1)
    else:
        tmp=(a1+a[-1-i])%(p+1)
    print(solve(tmp)+1)

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
p=x.count('1')

#popcount(x)が0,1だった場合に対応
#if p==0:
#    for i in range(n):
#        print(1)
#    exit()
#elif p==1:
#    z=x.index('1')
#    for i in range(n):
#        if i==z:
#            print(0)
#        else:
#            print(1)
#    exit()

#愚直に解く関数を定義
def solve(n):
    count=0
    while n:
        popcount=bin(n).count('1')
        n%=popcount
        count+=1
    return count

#2^i mod(p+1),2^i mod(p-1)のリストを作成
a,b=[],[]
for i in range(n):
    a.append(pow(2,i,p+1))
    b.append(pow(2,i,p-1))

#x mod(p+1),x mod(p-1)を計算
a1,b1=0,0
for i in range(n):
    if x[-1-i]=='1':
        a1+=a[i]
        b1+=b[i]

#本計算
for i in range(n):
    if x[i]=='1':
        tmp=(b1-b[-1-i])%(p-1)
    else:
        tmp=(a1+a[-1-i])%(p+1)
    print(solve(tmp)+1)

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
p=0
chk0=chk1=chk2=0
b=x.count("1")
for i,j in enumerate(x[::-1]):
    if j=="1":
        chk1+=pow(2,i,b+1)
        chk2+=pow(2,i,b-1)
l=[]
for i,j in enumerate(x[::-1]):
    a1=pow(2,i,b+1)
    a2=pow(2,i,b-1)
    if j=="0":
        t=chk1+a1
    else:
        t=chk2+b-1-a2
    ans=0
    f=1
    while t:
        if f:
            if j=="0": t%=(b+1)
            else: t%=(b-1)
            f=0
        else:
            t%=bin(t).count("1")
        ans+=1
    l.append(ans)
for i in l[::-1]:
    print(i)