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())
X = input()
def popcount(k):
    return bin(k).count('1')

K = int(X, 2)
one = popcount(K)
K_MOD   = K % one
K_MOD_M = K % (one-1)
K_MOD_P = K % (one+1)
#memo = [-1] * (N+1)
#print('k_mod_m=', K_MOD_M)
#print('k_mod_p=', K_MOD_P)
T = 2**(N-1)
for i in range(N):
    if X[i] == '1':
        pop = one - 1
        k = K_MOD_M - T
    else:
        pop = one + 1
        k = K_MOD_P + T
    T //= 2

    if pop == 0:
        print(0)
    else:
        k %= pop
        pop = popcount(k)
        #key = k
        cnt = 1
        while k > 0:
            #print('  ', k, pop, cnt)
            #if memo[key] > 0:
            #    cnt += memo[k]
            #    break
            #else:
            k %= pop
            pop = popcount(k)
            cnt += 1
        #memo[key] = cnt
        print(cnt)

Submission status: Runtime Error

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

N,X = open(0).read().split()
N = int(N)
X = int(X, 2)

if X == 0:
    for i in range(0, N):
        k = 1 << (N - 1 - i)
        x = X ^ k
        ans = 0
        while x != 0:
            x %= popcount(x)
            ans += 1
        print(ans)
else:
    p = popcount(X)
    xi = X % (p + 1)
    xd = X % (p - 1)
    for i in range(0, N):
        k = 1 << (N - 1 - i)
        x = X ^ k
        if x == 0:
            print(0)
            continue

        if x > X:
            pi = p + 1
            x = (xi + (k % pi)) % pi
        else:
            pd = p - 1
            x = (xd - (k % pd)) % pd
        ans = 1
        while x != 0:
            x %= popcount(x)
            ans += 1
        print(ans)

Submission status: Runtime Error

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    N = int(input())
    S = input()
    cnt0 = S.count("1")

    if cnt0 == 0:
        print(*[1]*N, sep="\n")
        raise 1
        return

    X = int(S, 2)

    def f2():
        cache = [-1] * max(9, cnt0+1)
        cache[0] = 0
        for i in range(4): cache[1<<i] = 1
        def f2(x):
            if cache[x] != -1:
                return cache[x]

            y = bin(x).count("1")
            z = 1 + f2(x % y)
            cache[x] = z

            return z
        f2.cache = cache
        return f2
    f2 = f2()

    dc = []
    for v in [1, -1]:
        x = cnt0 + v
        y = X % x if x else 0
        dc.append((x, v, y, [1, N-1]))

    ans = [0] * N
    for i in reversed(range(N)):
        si = S[i]
        cnt, v, n, m1 = dc[0 if si == "0" else 1]

        if cnt == 0:
            ans[i] = 0
            continue

        m2 = (m1[0]<<(m1[1]-i)) % cnt
        n = (n + v*m2) % cnt
        m1[0], m1[1] =  m2, i

        ans[i] = 1 + f2(n)

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


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

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

N,X = open(0).read().split()
N = int(N)
X = int(X, 2)

if X == 0:
    for i in range(0, N):
        k = 1 << (N - 1 - i)
        x = X ^ k
        ans = 0
        while x != 0:
            x %= popcount(x)
            ans += 1
        print(ans)
else:
    p = popcount(X)
    xi = X % (p + 1)
    xd = X % (p - 1)
    for i in range(0, N):
        k = 1 << (N - 1 - i)
        x = X ^ k
        if x == 0:
            print(0)
            continue

        if x > X:
            pi = p + 1
            x = (xi + (k % pi)) % pi
        else:
            pd = p - 1
            x = (xd - (k % pd) % pd)
        ans = 1
        while x != 0:
            x %= popcount(x)
            ans += 1
        print(ans)

Submission status: Runtime Error

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

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

intx = int( "0b"+x ,0 )
popcount0 = x.count("1")

intx_mod_pp1 = intx %(popcount0+1)
intx_mod_pm1 = intx %(popcount0-1)


jisho = ["yet"]*n
# pow2ip = .5
# pow2im = .5

for i in range(n):
    pow2ip = pow(2,n-i-1,popcount0+1)
    pow2im = pow(2,n-i-1,popcount0-1)
#     if x[i]=="0":
#         intxi = intx+pow2i
#     else:
#         intxi = intx-pow2i
#     if intxi==0:
#         print(0)
#         continue
    if False:
        pass
    
    
    else:
        intxi=1
        c=0
        while intxi!=0:
            if c==0:
                if x[i]=="0":
                    pop = popcount0+1
                    intxi = (intx_mod_pp1 + pow2ip%pop )%pop
                else:
                    pop = popcount0-1
                    intxi = (intx_mod_pm1 - pow2im%pop )%pop        
            else:
                if jisho[intxi]=="yet":
                    togo = intxi%popcount(intxi)
                    jisho[intxi]= togo
                    intxi = togo
                else:
                    intxi =jisho[intxi]
                
            #print(intxi)
            c+=1
        print(c)
        #print()
    
#        print("f(n)=",c)

Submission status: Runtime Error

Solution code:
import copy
from  collections import Counter
N=int(input())
X=list(map(int,input()))
A=[]
for i in range(len(X)):
    S=copy.deepcopy(X)
    S[i]=abs(1-S[i])
    A.append(''.join(map(str,S)))
    
dp=[0,1,1,2]
for i in range(21):
    dp=dp+list(map(lambda x: x+1, dp))
    
for i in A:
    z=0
    while True:
        if z==0:
            n=int(i,2)
            f=dp[n]
            n=n%f
            z+=1
        else:
            f=dp[n]
            n=n%f
            z+=1
        if n==0:
            print(z)
            break

Submission status: Runtime Error

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

one_num = X.count("1")
one_mod = one_nom

for i in range(N):
    target = int(X[i])
    if target == 0:
        plus = pow(2,N-i-1)
        ones = one_num + 1
    else:
        plus = -pow(2,N-i-1)
        ones = one_num-1
    Xnow = X10+plus
    count = 0
    if Xnow == 0:
        print(count)
        continue
    Xnow = Xnow%ones
    count+=1
    for j in range(1000):
        if Xnow == 0:
            break
        Xnow2 = bin(Xnow)
        ones = Xnow2.count("1")
        Xnow = Xnow%ones
        count+=1
    print(count)

Submission status: Runtime Error

Solution code:
import sys


def resolve():
    readline = sys.stdin.readline

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

    def func(n: int, cnt: int):
        if n != 0:
            func(n % popcount(n), cnt + 1)
        else:
            print(cnt)

    N = int(readline())
    X = readline()

    calx = popcount(int(X, 2))
    for i in range(N):
        n = X
        if n[i] == '0':
            n = n[:i] + '1' + n[i + 1:]
            cal = int(n, 2) % (calx + 1)
        else:
            n = n[:i] + '0' + n[i + 1:]
            cal = int(n, 2) % (calx - 1)
        func(cal, 1)

resolve()

Submission status: Runtime Error

Solution code:
import copy
from  collections import Counter
N=int(input())
X=list(map(int,input()))
A=[]
for i in range(len(X)):
    S=copy.deepcopy(X)
    S[i]=abs(1-S[i])
    A.append(S)
dp=[0,1,1,2]
for i in range(21):
    dp=dp+list(map(lambda x: x+1, dp))
    
for i in A:
    z=0
    while True:
        if z==0:
            S=''.join(map(str,i))
            n=int(S,2)
            f=dp[n]
            n=n%f
            z+=1
        else:
            f=dp[n]
            n=n%f
            z+=1
        if n==0:
            print(z)
            break

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))


for i in range(N):
    f=0
    while X[i]>0:
        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:
def popcount(x):
    return bin(x).count("1")

N,X = open(0).read().split()
N = int(N)
X = int(X, 2)

p = popcount(X)
if p == 0:
    xi = X
    xd = X
else:
    xi = X % (p + 1)
    xd = X % (p - 1)

for i in range(0, N):
    k = 1 << (N - 1 - i)
    x = X ^ k
    if x == 0:
        print(0)
        continue

    if x > X:
        x = xi + (k % (p + 1))
    else:
        x = xd - (k % (p - 1))
    ans = 1
    while x != 0:
        x %= popcount(x)
        ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
def popcount(k):
    return bin(k).count('1')

K = int(X, 2)
one = popcount(K)
K_MOD   = K % one
K_MOD_M = K % (one-1)
K_MOD_P = K % (one+1)
#print('k_mod_m=', K_MOD_M)
#print('k_mod_p=', K_MOD_P)
T = 2**(N-1)
for i in range(N):
    if X[i] == '1':
        pop = one - 1
        k = K_MOD_M - T
    else:
        pop = one + 1
        k = K_MOD_P + T

    if pop == 0:
        print(0)
    else:
        ans = 1
        #print('  ', k, pop, ans)
        k %= pop
        pop = popcount(k)
        while k > 0:
            k %= pop
            pop = popcount(k)
            ans += 1
            #print('  ', k, pop, ans)
        print(ans)
        T //= 2

Submission status: Runtime Error

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

one_num = X.count("1")
answer = []
for i in range(N):
    target = int(X[i])
    if target == 0:
        plus = pow(2,N-i-1)
        ones = one_num + 1
    else:
        plus = -pow(2,N-i-1)
        ones = one_num-1
    Xnow = X10+plus
    count = 0
    if Xnow == 0:
        answer.append(count)
        continue
    else:
        Xnow = Xnow%ones
        count+=1
        while Xnow > 0:
            Xnow2 = bin(Xnow)
            ones = Xnow2.count("1")
            Xnow = Xnow%ones
            count+=1
        answer.append(count)
    print(*count,sep="\n")

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
 
# 元のpopcount
original_pop_count = x.count('1')
# 反転して-1count
one_pop_count = original_pop_count - 1
# 反転して+1count
zero_pop_count = original_pop_count + 1
 
# ±1それぞれにおける余り
if one_pop_count = 0:
  one_mod = 0
else:
  one_mod = int(x, 2) % one_pop_count
zero_mod = int(x, 2) % zero_pop_count
 
# f の前計算 
f = [0] * 220000
pop_count = [0] * 220000
for i in range(1, 220000):
    pop_count[i] = pop_count[i//2] + i % 2
    f[i] = f[i % pop_count[i]] + 1
 
# pow2 の前計算
one_pow2 = [1] * 220000
zero_pow2 = [1] * 220000
for i in range(1, 220000):
    if one_pop_count != 0:
        one_pow2[i] = one_pow2[i-1] * 2 % one_pop_count
    zero_pow2[i] = zero_pow2[i-1] * 2 % zero_pop_count
    
# n-1, n-2, ,, 0
for i in range(n-1, -1, -1):
    if x[n-1-i] == '1':
        if one_pop_count != 0:
            nxt = one_mod
            # - 2^i % 2
            nxt -= one_pow2[i]
            nxt %= one_pop_count
            print(f[nxt] + 1)
        else:
            print(0)
    if x[n-1-i] == '0':
        nxt = zero_mod
        nxt += zero_pow2[i]
        # + 2^i % 2
        nxt %= zero_pop_count
        print(f[nxt] + 1)

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
def popcount(k):
    return bin(k).count('1')

K = int(X, 2)
one = popcount(K)
K_MOD   = K % one
K_MOD_M = K % (one-1)
K_MOD_P = K % (one+1)
#print('k_mod_m=', K_MOD_M)
#print('k_mod_p=', K_MOD_P)
T = 2**(N-1)
for i in range(N):
    if X[i] == '1':
        pop = one - 1
        k = K_MOD_M - T
    else:
        pop = one + 1
        k = K_MOD_P + T
    k %= pop

    if pop == 0:
        print(0)
    else:
        ans = 1
        #print('  ', k, pop, ans)
        pop = popcount(k)
        while k > 0:
            k %= pop
            pop = popcount(k)
            ans += 1
            #print('  ', k, pop, ans)
        print(ans)
        T //= 2

Submission status: Runtime Error

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

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

intx = int( "0b"+x ,0 )
popcount0 = x.count("1")

intx_mod_pm1 = intx %(popcount0-1)
intx_mod_pp1 = intx %(popcount0+1)


jisho = ["yet"]*n
pow2i = pow(2,n)

for i in range(n):
    pow2i //=2
    if x[i]=="0":
        intxi = intx+pow2i
    else:
        intxi = intx-pow2i
    if intxi==0:
        print(0)
        continue
        
    else:
        c=0
        while intxi!=0:
            if c==0:
                if x[i]=="0":
                    intxi = (intx_mod_pp1 + pow2i%(popcount0+1) )%(popcount0+1)
                else:
                    intxi = (intx_mod_pm1 - pow2i%(popcount0-1) )%(popcount0-1)                 
            else:
                if jisho[intxi]=="yet":
                    togo = intxi%popcount(intxi)
                    jisho[intxi]= togo
                    intxi = togo
                else:
                    intxi =jisho[intxi]
                
            #print(intxi)
            c+=1
        print(c)
        #print()
#        print("f(n)=",c)

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
 
# 元のpopcount
original_pop_count = x.count('1')
# 反転して-1count
one_pop_count = original_pop_count - 1
# 反転して+1count
zero_pop_count = original_pop_count + 1
 
# ±1それぞれにおける余り
one_mod = int(x, 2) % one_pop_count
zero_mod = int(x, 2) % zero_pop_count
 
# f の前計算 
f = [0] * 220000
pop_count = [0] * 220000
for i in range(1, 220000):
    pop_count[i] = pop_count[i//2] + i % 2
    f[i] = f[i % pop_count[i]] + 1
 
# pow2 の前計算
one_pow2 = [1] * 220000
zero_pow2 = [1] * 220000
for i in range(1, 220000):
    if one_pop_count != 0:
        one_pow2[i] = one_pow2[i-1] * 2 % one_pop_count
    zero_pow2[i] = zero_pow2[i-1] * 2 % zero_pop_count
    
# n-1, n-2, ,, 0
for i in range(n-1, -1, -1):
    if x[n-1-i] == '1':
        if one_pop_count != 0:
            nxt = one_mod
            # - 2^i % 2
            nxt -= one_pow2[i]
            nxt %= one_pop_count
            print(f[nxt] + 1)
        else:
            print(0)
    if x[n-1-i] == '0':
        nxt = zero_mod
        nxt += zero_pow2[i]
        # + 2^i % 2
        nxt %= zero_pop_count
        print(f[nxt] + 1)

Submission status: Runtime Error

Solution code:
N = int(input())
X = str(input())
F = [0] * N

def calc_f(n:int)->int:
    global F
    x = n
    res = 0
    while 0 < x:
        if F[x] != 0:
            res += F[x]
            break
        pop = bin(n).count('1')
        x %= pop
        res += 1
    F[n] = res

# 前処理 N以下のF値テーブル
for i in range(1, N):
    calc_f(i)

# ビット反転すると初期の1の個数に対して+1または-1どちらか
pop_ini = X.count('1')
pp = pop_ini + 1  # pop_plus
pm = pop_ini - 1  # pop_minus

# 2進の各桁をppとpmで割った値のテーブル
ap = [0] * N  # arr_plus
am = [0] * N  # arr_minus
for i in range(N):
    ap[i] = pow(2, N-1-i, pp)
    am[i] = pow(2, N-1-i, pm)

# 所与のXで計算、ベースになる値
fp = 0  # f_plus
fm = 0  # f_minus
for i in range(N):
    if X[i] == '1':
        fp = (fp + ap[i]) % pp
        fm = (fm + am[i]) % pm

# 各桁を反転した場合では差分更新のみ
for i in range(N):
    ans = 1
    if X[i] == '1':
        v = (fm + pm - am[i]) % pm
    else:
        v = (fp + ap[i]) % pp
    if 0 < v:
        ans += F[v]
    print(ans)

Submission status: Runtime Error

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect
n=int(input())
x=input()
p=0
for i in x:
    if i=="1":
        p+=1
rp=0
rq=0
for i in range(n):
    if x[i]=="1":
        rp+=pow(2,(n-1-i),p+1)
        rq+=pow(2,(n-1-i),p-1)
        rp%=p+1
        rq%=p-1

def popcnt1(n):
    return bin(n).count("1")
res=[0]*n

for i in range(1,n+1):
    res[i-1]=i%popcnt1(i)

for i in range(n):
    ans=0
    if x[i]=="1":
        q=rq-pow(2,(n-1-i),p-1)
        q%=p-1
        while True:
            if q==0:
                print(1+ans)
                break
            ans+=1
            q=res[q-1]
    else:
        q=rp+pow(2,(n-1-i),p+1)
        q%=p+1
        while True:
            if q==0:
                print(1+ans)
                break
            ans+=1
            q=res[q-1]

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
def popcount(k):
    return bin(k).count('1')

K = int(X, 2)
one = popcount(K)
K_MOD   = K % one
K_MOD_M = K % (one-1)
K_MOD_P = K % (one+1)
#print('k_mod_m=', K_MOD_M)
#print('k_mod_p=', K_MOD_P)
T = 2**(N-1)
for i in range(N):
    if X[i] == '1':
        pop = one - 1
        k = K_MOD_M - T
    else:
        pop = one + 1
        k = K_MOD_P + T
    k %= pop

    if pop == 0:
        print(0)
    else:
        ans = 1
        while k != 0:
            pop = popcount(k)
            k %= pop
            ans += 1
        print(ans)
        T //= 2

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

pc_memo = defaultdict(int)
memo = defaultdict(int)


def to_next(x):
    if x not in pc_memo.keys():
        pc_memo[x] = x % "{:b}".format(x).count('1')
    return pc_memo[x]


def f(x):
    if x == 0:
        return 0
    if x not in memo.keys():
        memo[x] = f(to_next(x))+1
    return memo[x]


for i in range(2*10**5):
    f(i)

n = int(input())
x = input().rstrip()
one_cnt = x.count('1')

mod_minus = 0
mod_plus = 0
for i, a in enumerate(reversed(x)):
    if a == '1':
        mod_minus += pow(2, i, one_cnt-1)
        mod_minus %= one_cnt-1
        mod_plus += pow(2, i, one_cnt+1)
        mod_plus %= one_cnt+1


for i in range(n):
    if x[i] == '0':
        nx = mod_plus+pow(2, n-i-1, one_cnt+1)
        nx %= one_cnt+1
        print(f(nx)+1)
    else:
        nx = mod_minus-pow(2, n-i-1, one_cnt-1)
        nx %= one_cnt-1
        print(f(nx)+1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

pc_memo = defaultdict(int)
memo = defaultdict(int)


def to_next(x):
    if x not in pc_memo.keys():
        pc_memo[x] = x % "{:b}".format(x).count('1')
    return pc_memo[x]


def f(x):
    if x == 0:
        return 0
    if x not in memo.keys():
        memo[x] = f(to_next(x))+1
    return memo[x]


for i in range(2*10**5):
    f(i)

n = int(input())
x = input()
one_cnt = x.count('1')

mod_minus = 0
mod_plus = 0
for i, a in enumerate(reversed(x)):
    if a == '1':
        mod_minus += pow(2, i, one_cnt-1)
        mod_minus %= one_cnt-1
        mod_plus += pow(2, i, one_cnt+1)
        mod_plus %= one_cnt+1


for i in range(n):
    if x[i] == '0':
        nx = mod_plus+pow(2, n-i-1, one_cnt+1)
        nx %= one_cnt+1
        print(f(nx)+1)
    else:
        nx = mod_minus-pow(2, n-i-1, one_cnt-1)
        nx %= one_cnt-1
        print(f(nx)+1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

pc_memo = defaultdict(int)
memo = defaultdict(int)


def to_next(x):
    if x not in pc_memo.keys():
        pc_memo[x] = x % "{:b}".format(x).count('1')
    return pc_memo[x]


def f(x):
    if x == 0:
        return 0
    if x not in memo.keys():
        memo[x] = f(to_next(x))+1
    return memo[x]


for i in range(2*10**5):
    f(i)

    
n = int(input())
x = input()
one_cnt = x.count('1')

mod_minus = 0
mod_plus = 0
for i, a in enumerate(reversed(x)):
    if a == '1':
        mod_minus += pow(2, i, one_cnt-1)
        mod_minus %= one_cnt-1
        mod_plus += pow(2, i, one_cnt+1)
        mod_plus %= one_cnt+1


for i in range(n):
    if x[i] == '0':
        nx = mod_plus+pow(2, n-i-1, one_cnt+1)
        nx %= one_cnt+1
        print(f(nx)+1)
    else:
        nx = mod_minus-pow(2, n-i-1, one_cnt-1)
        nx %= one_cnt-1
        print(f(nx)+1)

Submission status: Runtime Error

Solution code:
from collections import Counter
N = int(input())
X = str(input())
X10 = int(X,2)

one_num = Counter(X)["1"]

for i in range(N):
    target = int(X[i])
    if target == 0:
        plus = pow(2,N-i-1)
        ones = one_num + 1
    else:
        plus = -pow(2,N-i-1)
        ones = one_num-1
    
    Xnow = X10+plus
    count = 0
    if Xnow == 0:
        print(count)
        continue
    else:
        Xnow = Xnow%ones
        count+=1
        while Xnow > 0:
            Xnow2 = format(Xnow, 'b')
            ones = 0
            for j in range(len(Xnow2)):
                if Xnow2[j]==1:
                    ones+=1
            Xnow = Xnow%ones
            count+=1
        print(count)

Submission status: Runtime Error

Solution code:
N = int(input())
s = input()
cnt=s.count("1")
popX=[]
for i in range(N):
    if s[i]=="1":
        popX.append(cnt-1)
    else:
        popX.append(cnt+1)
x=int(s,2)
X=[]
for i in range(N):
    if s[i]=="1":
        X.append(x-2**(N-i-1))
    else:
        X.append(x+2**(N-i-1))


for i in range(N):
    F=0
    while True:
        X[i]=X[i]%popX[i]
        F=F+1
        if X[i]==0:
            break
    print(F)

Submission status: Runtime Error

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

N,X = open(0).read().split()
N = int(N)
X = int(X, 2)

p = popcount(X)
xp = X % p

for i in range(0, N):
    k = 1 << (N - 1 - i)
    x = X ^ k
    if x == 0:
        print(0)
        continue

    if x > X:
        x %= xp + (k % (p + 1))
    else:
        x %= xp + (k % (p - 1))
    ans = 1
    while x != 0:
        x %= popcount(x)
        ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
import sys

n = int(sys.stdin.readline().rstrip("\n"))
x = sys.stdin.readline().rstrip("\n")
for i in range(n):
    if x[i] == '0':
        xi = x[:i]+'1'+x[(i+1):]
    else:
        xi = x[:i]+'0'+x[(i+1):]
    f = 0
    while True:
        xi_num = int(xi, 2)
        pc = xi.count('1')
        if xi_num % pc == 0:
            f += 1
            break
        else:
            f += 1
            xi_num = xi_num % pc
            xi = format(xi_num, 'b')
    print(f)

Submission status: Runtime Error

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    N, S = sys.stdin.read().split()
    N = int(N)
    cnt0 = S.count("1")

    if cnt0 == 0:
        print(*[1]*N, sep="\n")
        raise 1
        return

    X = int(S, 2)

    def f2():
        cache = [-1] * max(9, cnt0+1)
        cache[0] = 0
        for i in range(4): cache[1<<i] = 1
        def f2(x):
            if cache[x] != -1:
                return cache[x]

            y = bin(x).count("1")
            z = 1 + f2(x % y)
            cache[x] = z

            return z
        f2.cache = cache
        return f2
    f2 = f2()

    dc = {}
    for k, v in (("0", 1), ("1", -1)):
        x = cnt0 + v
        y = X % x if x else 0
        dc[k] = (x, v, y, [1, N-1])

    ans = [0] * N
    for i in reversed(range(N)):
        si = S[i]
        cnt, v, n, m1 = dc[si]

        if cnt == 0:
            ans[i] = 0
            continue

        m2 = (m1[0]<<(m1[1]-i)) % cnt
        n = (n + v*m2) % cnt
        m1[0], m1[1] =  m2, i

        ans[i] = 1 + f2(n)

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


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
import copy
from  collections import Counter
N=int(input())
X=list(map(int,input()))
A=[]
for i in range(len(X)):
    S=copy.deepcopy(X)
    S[i]=abs(1-S[i])
    A.append(S)
for i in A:
    z=0
    while True:
        if z==0:
            b=Counter(i)[1]
            S=''.join(map(str,i))
            n=int(S,2)%b
            z+=1
        else:
            b=Counter('{:b}'.format(n))['1']
            n=n%b
            z+=1
        if n==0:
            print(z)
            break

Submission status: Runtime Error

Solution code:
import numpy as np

def popcount(n):
  count = 0
  while n != 0:
    if n%2 == 1:
      count += 1
    n = n >> 1
  return count


N = int(input())
X = int(input(),2)
XX = np.zeros(N,dtype = int)
Pop = np.zeros(2**N,dtype = int)
Ans = np.zeros(2**N,dtype = int)
ans = np.zeros(N,dtype = int)
for i in range(1,N+1):
  a = (X >> (i-1))%2
  if a == 0:
    XX[N-i] = X + 2**(i-1)
  else:
    XX[N-i] = X - 2**(i-1)

for i in reversed(range(N)):
  count_XX = 0
  while XX[i] > 0:
    if Ans[XX[i]] > 0:
      count_XX += Ans[XX[i]]
      XX[i] = 0
    else:
      if Pop[XX[i]] == 0:
        Pop[XX[i]] = popcount(XX[i])
      XX[i] = XX[i] % Pop[XX[i]]
      #print(XX)
      count_XX += 1
  ans[i] = count_XX
  Ans[XX[i]] = count_XX

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

Submission status: Runtime Error

Solution code:
import numpy as np

def popcount(n):
  count = 0
  while n != 0:
    if n%2 == 1:
      count += 1
    n = n >> 1
  return count


N = long int(input())
X = long int(input(),2)
XX = np.zeros(N,dtype = int)
Pop = np.zeros(2**N,dtype = int)
Ans = np.zeros(2**N,dtype = int)
ans = np.zeros(N,dtype = int)
for i in range(1,N+1):
  a = (X >> (i-1))%2
  if a == 0:
    XX[N-i] = X + 2**(i-1)
  else:
    XX[N-i] = X - 2**(i-1)

for i in reversed(range(N)):
  count_XX = 0
  while XX[i] > 0:
    if Ans[XX[i]] > 0:
      count_XX += Ans[XX[i]]
      XX[i] = 0
    else:
      if Pop[XX[i]] == 0:
        Pop[XX[i]] = popcount(XX[i])
      XX[i] = XX[i] % Pop[XX[i]]
      #print(XX)
      count_XX += 1
  ans[i] = count_XX
  Ans[XX[i]] = count_XX

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

Submission status: Runtime Error

Solution code:
N = int(input())
X_2 = input()
X_10 = int(X_2, 2)

y=sum(map(int, X_2))+1
z=y-2

a = X_10%y
b = X_10%z

for i in range(N):
    if X_2[i]=='0':
        c = (2**(N-1-i))%y
        x = (a+c)%y
    elif sum(map(int, X_2[0:i]+X_2[i+1:]))==0:
        print(0)
        continue
    else:
        c = (2**(N-1-i))%z
        x = (b-c)%z
    
    count = 1
    while x != 0:
        x = x%sum(map(int, bin(x)[2:]))
        count+=1
    print(count)

Submission status: Runtime Error

Solution code:
n,x=int(input()),input()
o=x.count("1")
if o==1:
    for i,v in x:
        if v=="1":print(0)
        else:
            if i!=n-1:
                if x[-1]=="0":print(1)
                else:print(2)
            else:print(0)
else:
    m=o-1
    M=o+1
    mp,mm={0:1},{0:1}
    for i in range(1,n):
        mp[i]=mp[i-1]*2%M
        mm[i]=mm[i-1]*2%m
    A=int(x,2)
    a=A%m
    b=A%M
    rest={0:0}
    for i in range(1,o+1):
        rest[i]=1+rest[i%bin(i).count("1")]
    for i,v in enumerate(x):
        if v=="1":
            print(1+rest[(a-mm[n-i-1])%m])
        else:
            print(1+rest[(b+mp[n-i-1])%M])

Submission status: Runtime Error

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

x_num = int(X, 2)
cnt1 = X.count('1')

p_zero = x_num % (cnt1 + 1)
p_one = x_num % ((cnt1 - 1) if cnt1 - 1 > 0 else 0)


def f(cnt):
    if (cnt > 0):
        pcount = p_count(cnt)
        return f(cnt % pcount) + 1
    else:
        return 0


def p_count(x):
    cnt = 0
    while (x > 0):
        if x % 2 != 0:
            cnt += 1
        x //= 2
    return cnt


def f1(x):
    cnt = 0
    while (x > 0):
        x %= bin(x).count('1')
        cnt += 1
    return cnt


for i, x in enumerate(list(X)):
    if (x == '1'):
        #x_num = int(''.join(X), 2)
        if cnt1 - 1 > 0:
            xxx = (p_one - pow(2, (N - (i + 1)), cnt1 - 1)) % (cnt1 - 1)
            xxx += cnt1 - 1 if xxx < 0 else 0
            print(f1(xxx) + 1)
        else:
            print(0)
    else:
        #x_num = int(''.join(X), 2)
        xxx = (p_zero + pow(2, (N - (i + 1)), cnt1 + 1)) % (cnt1 + 1)
        xxx += cnt1 + 1 if xxx < 0 else 0
        print(f1(xxx) + 1)

Submission status: Runtime Error

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

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


def f(n):
    if n== 0:
        return 1
    count = 1
    while n!=0:
        n = n%popcount(n)
        count += 1
    return count


X_popcount = popcount(X)
X_mod_p = X%(X_popcount+1)
X_mod_m = X%(X_popcount-1)
for i in range(N):
    X_i = X ^ (1<<(N-i-1))
    if X_i == 0:
        ans = 0
    elif X>>(N-i-1)&1 == 1:
        if X_popcount == 1:
            ans = 1
        else:
            ans = f((X_mod_m-pow(2, N-i-1, X_popcount-1))%(X_popcount-1))
    else:
        ans = f((X_mod_p+pow(2, N-i-1, X_popcount+1))%(X_popcount+1))
    print(ans)

Submission status: Runtime Error

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

x_num = int(X, 2)
cnt1 = X.count('1')

p_zero = x_num % (cnt1 + 1)
p_one = x_num % (cnt1 - 1)


def f(cnt):
    if (cnt > 0):
        pcount = p_count(cnt)
        return f(cnt % pcount) + 1
    else:
        return 0


def p_count(x):
    cnt = 0
    while (x > 0):
        if x % 2 != 0:
            cnt += 1
        x //= 2
    return cnt


def f1(x):
    cnt = 0
    while (x > 0):
        x %= bin(x).count('1')
        cnt += 1
    return cnt


for i, x in enumerate(list(X)):
    if (x == '1'):
        #x_num = int(''.join(X), 2)
        if cnt1 - 1 > 0:
            xxx = (p_one - pow(2, (N - (i + 1)), cnt1 - 1)) % (cnt1 - 1)
            xxx += cnt1 - 1 if xxx < 0 else 0
            print(f1(xxx) + 1)
        else:
            print(0)
    else:
        #x_num = int(''.join(X), 2)
        xxx = (p_zero + pow(2, (N - (i + 1)), cnt1 + 1)) % (cnt1 + 1)
        xxx += cnt1 + 1 if xxx < 0 else 0
        print(f1(xxx) + 1)

Submission status: Runtime Error

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

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


n = int(input())
x = input().rstrip()
x_dec = int(x,base = 2)

pop_cnt = x.count('1')
pop_cnt_0 = pop_cnt + 1
pop_cnt_1 = pop_cnt - 1

x_bit = [0]*n

for i in range(n-1,-1,-1):
    if x[i] == '0':
        x_bit[i] = (x_dec + pow(2,n-1-i))%pop_cnt_0
        
    else:
        x_bit[i] = (x_dec - pow(2,n-1-i))%pop_cnt_1

anslist = []
for i in range(n):
    ans = 1
    now = x_bit[i]
    while True:
        if now == 0:
            break
        now = now%p_count(now)
        
        ans += 1
    anslist.append(ans)


for ans in anslist:
    print(ans)