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:
from functools import lru_cache

def resolve():
    N = int(input())
    X_ori = list(input())  # string ["0", "1", "1"]

    #N = 20000
    #X_ori = ["0"]*N

    def popcount_(s):
        return s.count("1")

    @lru_cache(maxsize=1000000)
    def popcount(x):
        x_bin = bin(x)[2:]
        n = popcount_(x_bin)
        return n

    @lru_cache(maxsize=1000000)
    def func(n):
        if n == 0:
            return 0
        c = 0
        while True:
            c += 1
            n_c = popcount(n)
            n = n % n_c
            if n == 0:
                break

        return c

    X_ini = "".join(X_ori)
    n_ini = popcount_(X_ini)

    for i in range(len(X_ori)):
        X = X_ori[:]
        X[i] = "1" if X[i] == "0" else "0"
        n_st = n_ini + 1 if X[i] == "1" else n_ini - 1
        X = "".join(X)
        X_dec = int(X, 2)
        X_st = X_dec % n_st
        c = func(X_st) + 1
        print(c)
    

if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
def popcount(n):
    count = 0
    if n != 0:
        while n > 0:
            count += 1
            n = n % bin(n).count("1")
    return count


n = int(input())

a = input()

#x = bin(int(input()))

x = int(a,2)
nlis = range(n)

c1 = bin(x).count("1")

#for i in reversed(nlis):
for i in range(n):
    #check = 2 ** i
    #ans = x ^ check

    if a[i] == "0":
        c2 = c1 + 1
        ans = x + 2 ** (n - 1 - i)
        #print(i,n)
    else:
        c2 = c1 - 1
        #print(n)
        ans = x - 2 ** (n - 1 - i)
        #print(i,n)
    #print(i,ans)
    ans = ans % c2


    ans = popcount(ans) + 1

    print(ans)

#print(c1)

#print(popcount(int(a)))

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
# N = 2 * 10 ** 5
# X = "10"*(10**5)
cnt = X.count('1')

base = int(X, 2)
if cnt == 1:
    base_m1 = 0
else:
    base_m1 = base % (cnt - 1)
base_p1 = base % (cnt + 1)

c = dict()
for i in range(N):

    if X[i] == '1':
        bins = base_m1 - 2 ** (N - i - 1) % (cnt - 1)
        nc = cnt - 1
    else:
        bins = base_p1 + 2 ** (N - i - 1) % (cnt + 1)
        nc = cnt + 1

    c[i] = 0
    while True:
        if nc == 0:
            print(c[i])
            break
        n = bins % nc
        c[i] += 1
        if n == 0:
            print(c[i])
            break

        bins = n
        nc = bin(n).count('1')

Submission status: Runtime Error

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

Y = int(X, 2)
Z = list(map(int,list(X)))
X_1 = bin(Y).count("1")
X_1m = X_1-1
X_1p = X_1+1
Ym = Y%X_1m
Yp = Y%X_1p


temp = []
for i in range(200001):
    ans = 0
    while i > 0:
        i %= bin(i).count("1")
        ans += 1
    temp.append(ans)

temp2p = []
temp2m = []
ansp = 1
ansm = 1
for i in range(200001):
    ansp %= X_1p
    ansm %= X_1m
    temp2p.append(ansp)
    temp2m.append(ansm)
    ansp *= 2
    ansm *= 2    

for i in range(N):
    if Z[i]==0:
        Xi = Yp + temp2p[(N-i-1)]
        Xi %= X_1p
        
        print(1+temp[Xi])
    else:
        Xi = Ym - temp2m[(N-i-1)]
        Xi %= X_1m
        print(1+temp[Xi])

Submission status: Runtime Error

Solution code:
n = int(input())
x = list(str(input()))
import copy

def B(X, n):
    X_dumy = X
    out = ''
    while X_dumy>0:
        out = str(X_dumy%n)+out
        X_dumy = int(X_dumy/n)
    return out

for i in range(n):
    a = 0
    s = x.copy()
    if x[i] == '1':
        s[i] = '0'
    if x[i] == '0':
        s[i] = '1'
    s = ''.join(s)
    s = int(s, 2)
    z = s
    for k in range(z):
        if s == 0:
            break
        y = (B(s,2)).count('1')
        s = s % y
        a += 1
    print(a)

Submission status: Runtime Error

Solution code:
import numpy as np

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

t = [0]

pl = np.array([1])
tmp = [np.array([1])]
for i in range(18):
    ne = np.concatenate([tmp[-1], tmp[-1]+1])
    tmp.append(ne)
pl = np.concatenate(tmp)


for n in range(1, 100):
    c = pl[n-1]
    t.append(1 + t[n%c])


base = X.count("1")
basex = int(X, 2)
for n in range(N):
    if X[n] == "0":
        c = base + 1
        x = basex + 2**(N-n-1)
    else:
        c = base - 1
        x = basex - 2**(N-n-1)
    
    if c == 0:
        print(0)
    else:
        print(1 + t[x%c])

Submission status: Runtime Error

Solution code:
import sys
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(rs())
def rs_(): return [_ for _ in rs().split()]
def ri_(): return [int(_) for _ in rs().split()]

N = ri()
X = [int(i) for i in reversed(rs())]
f = [10 ** 9] * (N + 1)
f[0] = 0
for i in range(1, N+1):
    pc = bin(i).count("1")
    f[i] = f[i % pc] + 1
pc = sum(X)
#amari = [((2 ** i) % pc) * j for i, j in enumerate(X)]
amari1 = sum([((2 ** i) % (pc + 1)) * j for i, j in enumerate(X)])
amari2 = sum([((2 ** i) % (pc - 1)) * j for i, j in enumerate(X)])
ans = [0] * N
for i in range(N):
    if X[i] == 1:
        ans[i] = f[(amari2 - (2 ** i) % (pc - 1)) % (pc - 1)] + 1
    else:
        ans[i] = f[(amari1 + (2 ** i) % (pc + 1)) % (pc + 1)] + 1
for i in reversed(range(N)):
    print(ans[i])

Submission status: Runtime Error

Solution code:
from copy import copy


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

for i in range(N):
    X_i = copy(X)
    if X_i[i] == "0":
        X_i[i] = "1"
    else:
        X_i[i] = "0"
    X_i = "0b" + "".join(X_i)
    count = 0
    while True:
        count += 1
        popcount = X_i.count("1")
        X_i = int(X_i, 2) % popcount
        if X_i == 0:
            break
        X_i = bin(X_i)
    print(int(count))

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
a = []
s = int(x, 2)
k = x.count('1')

for i in range(n):
    a.append(int(x[i]))
#print(a)
#print(s)

for i in range(n):
    if int(x[i]) == 0:
        S = s + 2**(n-i-1)
        K = k + 1
    else:
        S = s - 2**(n-i-1)
        K = k - 1
    ans = 1
    S = S % K
    while S != 0:
        S = S % str(bin(S)).count('1')
        ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x = x + (x >> 8) 
    x = x + (x >> 16) 
    x = x + (x >> 32) 
    x = x + (x >> 64)
    return x & 0x0000007f
  
def func(n, c):
  next = n%popcount(n)
  c+=1
  if ans[next]!=-1:
    return ans[next]+c
  if next == 0:
    return c
  else:
    return func(next, c)

def solve(n, c):
  next = n%popcount(n)
  return ans[next]+1

maint = 2*(10**5)+1
n=int(input())
x=input()
ans = [-1]*maint
ans[0]=0
for i in range(1, maint):
  ans[i] = func(i, 0)

for i in range(n):
  temp=list(x)
  if x[i]=="0":
    temp[i]="1"
  else:
    temp[i]="0"
  itemp = int("".join(temp), 2)
  if itemp<=maint:
    print(ans[itemp])
  else:
    print(solve(itemp, 0))

Submission status: Runtime Error

Solution code:
N = int(input())
S = list(map(int,list(input())))
S.reverse()
r = [0 for _ in range(2 * 10 ** 5 + 100)]
p0 = [0 for _ in range(N + 10)]
q0 = 0
p1 = [0 for _ in range(N + 10)]
q1 = 0
q = S.count(1)
p0[0] = 1
p1[0] = 1

for i in range(N):
    p0[i + 1] = (p0[i] * 2) % (q + 1)
    if S[i] == 1:
        q0 += p0[i]
        q0 %= q + 1

for i in range(N):
    p1[i + 1] = (p1[i] * 2) % (q - 1)
    if S[i] == 1:
        q1 += p1[i]
        q1 %= q - 1

r[0] = 0
for i in range(1,2 * (10 ** 5) +10):
    qx = 0
    for i2 in range(22):
        if i >> i2 & 1:
            qx += 1
    r[i] = r[i % qx] + 1

for i in range(N):
    if S[N - i - 1] == 0:
        print(r[(q0 + p0[N-i-1]) % (q + 1)] + 1)
    else:
        print(r[(q1 - p1[N-i-1]) % (q - 1)] + 1)

Submission status: Runtime Error

Solution code:
N = int(input())
x__ = list(input())
X = []
for i in range(N):
    x_ = x__[:]
    x_[i] = "1" if x_[i] == "0" else "0"
    X.append(int("".join(x_),2))


popcounts = [-1 for i in range(2*(10**5)+1)]

for x in X:
    n = x
    cnt = 0

    n = n%(str(bin(n)).count("1"))
    cnt += 1

    while n != 0:
        #print(n)
        if popcounts[n] == -1:
            popcounts[n] = str(bin(n)).count("1")

        n = n%popcounts[n]
        cnt += 1
    print(cnt)

Submission status: Runtime Error

Solution code:
n = int(input())
x = int(input(), 2)
max_value = 2 * 10 ** 5 + 2
max_value = n + 1
popcount = [-1] * max_value
popcount[0] = 0
resultcount = [-1] * max_value
resultcount[0] = 0
for i in range(1, max_value):
    popcount[i] = bin(i).count('1')

for i in range(1, max_value):
    count = 0
    tmp = i
    while tmp != 0:
        tmp = tmp % popcount[tmp]
        count += 1
    resultcount[i] = count

for i in range(n):
    operator = 1 << (n - 1 - i)
    value = x ^ operator
    one_count = str(bin(value)).count('1')
    value = value % one_count
    if value == 0:
        print('1')
    else:
        print(resultcount[value] + 1)

Submission status: Runtime Error

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

def main():
    N = int(input())
    X = [None] * N
    l = list(input())
    Xc = 0
    for i in range(N):
        X[i] = int(l[i])
        Xc += X[i]

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

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

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

def initMemo(n):
    memo = {}
    for i in range(1, n):
        memo[i] = popcount(i)
    return memo

def popcount(n):
    cnt = 0
    while n != 0:
        cnt += 1
        n = n % bin(n).count('1')
        if n in memo:
            cnt += memo[n]
            break
        
    return cnt

memo = initMemo(N)

for i in range(N):
    temp_X = [l for l in X]
    if temp_X[i] == '0':
        temp_X[i] = '1'
    else:
        temp_X[i] = '0'
    temp_X = ''.join(temp_X)
    
    n = int(temp_X, 2)
    memo.setdefault(n, 0)
    
    output = popcount(n)
    print(output)
    memo[n] = output

Submission status: Runtime Error

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


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


# print(popcount(N))

def popcnt3(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


cnt = 0


def func(n):
    global cnt
    if n == 0:
        return cnt
    n = n % popcnt3(n)
    cnt += 1
    return func(n)


# print(func(7))

def toggle_nth_bit(num: int, n: int):
    return num ^ (1 << n)


for i in range(N - 1, -1, -1):
    n = toggle_nth_bit(int(X, 2), i)
    ans = func(n)
    print(ans)
    cnt -= ans

Submission status: Runtime Error

Solution code:
import math
from copy import copy
di = {}
di[0] = 0
for i in range(1, 2*(10**6)+1):
    di[i] = 0
for i in range(1, 2*(10**6)+1):
    count = 0
    for j in range(int(math.log2(i))+4):
        if (i>>j)&1:
            count += 1
    di[i] = di[i%count] + 1
n = int(input())
x = list(input())
x.reverse()
count = 0
for i in x:
    if i =='1':
        count += 1
mod_p = count + 1
mod_m = count - 1
di_p = {}
di_m = {}
for i in range(n):
    di_p[i] = pow(2, i, mod_p)
    di_m[i] = pow(2, i, mod_m)
s_p = 0
s_m = 0
for i in range(n):
    if x[i] == '1':
        s_p += di_p[i]
        s_m += di_m[i]
for i in range(n-1, -1, -1):
    sm = copy(s_m)
    sp = copy(s_p)
    if x[i] == '1':
        sm -= di_m[i]
        sm %= mod_m 
        print(di[sm]+1)
    else:
        sp += di_p[i]
        sp %= mod_p
        print(di[sp]+1)

Submission status: Runtime Error

Solution code:
def func(Y):
    m = 0
    while True:
        m += 1
        Y = Y % format(Y, 'b').count('1')
        if Y == 0:
            break
    return m
N = int(input())
X = str(input())
for i in range(N):
    Y = list(X)
    Y[i] = str(1 - int(Y[i]))
    print(func(int(''.join(Y), 2)))

Submission status: Runtime Error

Solution code:
def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)

    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f

N = int(input())
X = int(input(),2)
counts = []

for i in range(1,N+1,1):
    count = 0
    Xi = X ^ 2**(N-i)
    while Xi!=0:
        count+=1
        #popcount
        #Xi = Xi%bin(Xi).count("1")
        Xi = Xi % popcount(Xi)
    counts.append(count)

for k in counts:
    print(k)

Submission status: Runtime Error

Solution code:
import sys
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(rs())
def rs_(): return [_ for _ in rs().split()]
def ri_(): return [int(_) for _ in rs().split()]

import numpy as np
N = ri()
X = [int(i) for i in reversed(rs())]
f = [10 ** 9] * (N + 1)
f[0] = 0
for i in range(1, N+1):
    pc = bin(i).count("1")
    f[i] = f[i % pc] + 1
pc = sum(X)
#amari = [((2 ** i) % pc) * j for i, j in enumerate(X)]
amari1 = sum([((2 ** i) % (pc + 1)) * j for i, j in enumerate(X)])
amari2 = sum([((2 ** i) % (pc - 1)) * j for i, j in enumerate(X)])
ans = [0] * N
for i in range(N):
    if X[i] == 1:
        ans[i] = f[(amari2 - (2 ** i) % (pc - 1)) % (pc - 1)] + 1
    else:
        ans[i] = f[(amari1 + (2 ** i) % (pc + 1)) % (pc + 1)] + 1
for i in reversed(range(N)):
    print(ans[i])

Submission status: Runtime Error

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

cnt = 0
for i in range(N):
    if X[i] == "1":
        cnt += 1
    
down = [0] * N
up = [0] * N
ald = 0
alu = 0
for i in range(N):
    down[i] = pow(2, N-1-i, cnt-1)
    up[i] = pow(2, N-1-i, cnt+1)
    if X[i] == "1":
        ald += down[i]
        ald %= cnt-1
        alu += up[i]
        alu %= cnt+1

for i in range(N):
    if X[i] == "1":
        n = (ald - down[i]) % (cnt-1)
    else:
        n = (alu + up[i]) % (cnt+1)
    ans = 1
    while n != 0:
        c = 0
        for j in range(18):
            if (n >> j) % 2 == 1:
                c += 1
        n %= c
        ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
def f(n):
    if n in memo:
        return memo[n]
    c=list(str(bin(n)))[2:].count('1')
    r=n%c
    if r>0:
        memo[n]=f(r)+1
    else:
        memo[n]=1
    return memo[n]

memo={0:0}
N=int(input())
X=list(input())
XC=X.count('1')
XN=int('0b'+''.join(X),2)
for i in range(N):
    if X[i]=='1':
        tx=(XN%(XC-1)-pow(2,N-i-1,XC-1))
        if tx<0:
            tx+=XC-1
        tx%=XC-1
    else:
        tx=(XN%(XC+1)+pow(2,N-i-1,XC+1))%(XC+1)
    print(f(tx)+1)

Submission status: Runtime Error

Solution code:
n = int(input())
x = list(input())
y = int(''.join(x), 2)

memo = [0]


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


for i in range(1, n):
    tmp = i % popcount(i)
    memo.append(memo[tmp] + 1)

B = 2**(n-1)
for d in x:
    tmp = y
    if d == '0':
        tmp += B
    else:
        tmp -= B

    tmp = int(tmp)

    if tmp == 0:
        print(0)
        continue

    tmp = tmp % popcount(tmp)
    print(memo[tmp] + 1)
    B /= 2

Submission status: Runtime Error

Solution code:
def countpop(n):
    return n.count('1')
def reverse(num,n):
    return num ^ (1<<n)
N = int(input())
X = int(input(),2)
count = 0
for i in range(N):
    T = X
    T = reverse(T,N-1-i)
    while True:
        T = T % countpop(bin(T))
        count += 1
        if(T == 0):
            print(count)
            break
    count = 0

Submission status: Runtime Error

Solution code:
# coding: utf-8


def bi(x, n_digit):
    output = ""
    for i in range(n_digit-1, -1, -1):
        if x >= 2**i:
            x -= 2**i
            output += "1"
        else:
            output += "0"
    return output


def popcount(bi_n):
    output = 0
    for c in bi_n:
        if c == "1":
            output += 1
    return output


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

    fs = [None] * 20

    def rec(x):
        pop_x = popcount(bi(x, 18))
        r = x % pop_x
        if r == 0:
            return 1
        elif fs[r] is not None:
            return 1 + fs[r]
        else:
            return 1 + rec(r)

    for i in range(1, 20):
        fs[i] = rec(i)
    fs[0] = 0
    
    pop_X = popcount(bi_X)
    qp = pop_X+1
    qm = pop_X-1

    bi_qp = [None] * N
    bi_qm = [None] * N
    bi_qp[0] = 1 % qp
    bi_qm[0] = 1 % qm
    bi_qp[1] = 2 % qp
    bi_qm[1] = 2 % qm
    for i in range(2, N):
        bi_qp[i] = ((bi_qp[1])*(bi_qp[i-1])) % qp
        bi_qm[i] = ((bi_qm[1])*(bi_qm[i-1])) % qm
    
    rp = 0
    rm = 0
    for i in range(N):
        p = N-1-i
        coo = int(bi_X[i])
        rp = (rp + (((coo % qp) * bi_qp[p]) % qp)) % qp
        rm = (rm + (((coo % qm) * bi_qm[p]) % qm)) % qm

    for i in range(N):
        if bi_X[i] == "0":
            ri = (rp + bi_qp[N-1-i]) % qp
            if ri <= 20:
                print(1 + fs[ri])
            else:
                pop_ri = popcount(bi(ri, 18))
                print(2 + fs[ri % pop_ri])
        else:
            ri = (rm - bi_qm[N-1-i]) % qm
            if ri <= 20:
                print(1 + fs[ri])
            else:
                pop_ri = popcount(bi(ri, 18))
                print(2 + fs[ri % pop_ri])



main()
# print(main())

Submission status: Runtime Error

Solution code:
memo = {0: 0}
def fun(num):
    if num in memo: return memo[num]
    tmp = num % bin(num).count("1")
    cnt = 1 + fun(tmp)
    memo[num] = cnt
    return cnt       
    
N = int(input())
bX = input()
num_of_1 = bX.count("1")
X = int(bX, 2)
for i in range(N):
    xi = X ^ ((2**(N-1)) >> i)
    x = X >> (N-1-i) & 1
    cnt = 1 + fun(xi % (num_of_1+(-1) ** (x==1)))
    print(cnt)

Submission status: Runtime Error

Solution code:
import copy
n = int(input())
x = list(map(str,input()))
fun =0


for j in range(n):
    ans =0
    xi = copy.copy(x)
    if xi[j] =='0':
        xi[j] ='1'
    else:
        xi[j] ='0'
    fun = int("".join(xi), 2)
    popcount = xi.count('1')

    for i in range(100):
        fun = fun % popcount
        popcount = str(format(fun,'b')).count('1')
        if fun == 0:
            ans = i+1
            break
    print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
cnt = X.count('1')
Y, Z = 0, 0
for i in range(N):
    Y = (Y + int(X[i])*pow(2, N-i-1, cnt-1))%(cnt-1)
    Z = (Z + int(X[i])*pow(2, N-i-1, cnt+1))%(cnt+1)

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

for i in range(N):
    if X[i] == '1':
        pc = cnt - 1
        if pc == 0:
            print(0)
            continue
        else:
            Y_i = (Y - pow(2, N-i-1, cnt-1))%(cnt-1)
            ans = 1
            while Y_i > 0:
                Y_i = Y_i % popcount(Y_i)
                ans += 1
            print(ans)
    else:
        Z_i = (Z + pow(2, N-i-1, cnt+1))%(cnt+1)
        ans = 1
        while Z_i > 0:
            Z_i = Z_i % popcount(Z_i)
            ans += 1
        print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
xx = int(x, 2)
value = [0, 1]
count_1 = x.count('1')
for i in range(2, 2 * (10 ** 5) + 1):
    ans = 1
    i = i % bin(i).count('1')
    value.append(ans + value[i])

for i in range(n):
    print(xx)

Submission status: Runtime Error

Solution code:
import sys

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())


def toggle_nth_bit(num: int, n: int):
    return num ^ (1 << n)

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

N = I()
X = S()
result = []
for i in reversed(range(0,N)):
    hanten = toggle_nth_bit(int(X, 2),i)
    count = 0
    while True:
        hanten = hanten % bc(hanten)
        count += 1
        if hanten == 0:
            break
    print(count)

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
d=[0]*(2**10+1)
for j in range(n):
  bin_num=j
  iti2=0
  count=0
  X=bin(bin_num)
  for i in X:
    if i=="1":
      iti2+=1
  while bin_num!=0:
    count+=1
    if iti2==0:
      break
    bin_num=bin_num%iti2
    bin_num2=bin(bin_num)
    iti2=0
    for i in bin_num2:
      if i=="1":
        iti2+=1
  d[j]=count
  


iti=0
zero=0
for i in x:
  if i=="1":
    iti+=1
zero=n-iti
z_flag=False
i_flag=False

for i in range(n):
  ans=0
  if x[i]=="1":
    X="0b"+x[:i]+"0"+x[i+1:]
    iti2=iti-1
  else:
    x[i]=="1"
    X="0b"+x[:i]+"1"+x[i+1:]
    iti2=iti+1
  bin_num = int(X, 0)
  bin_num=bin_num%iti2
  print(d[bin_num]+1)

Submission status: Runtime Error

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


def bc(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ごと = 全部の合計
    x = x + (x >> 64)
    return x & 0x0000007f


dp = [0] * 1000000
for i in range(n - 1, -1, -1):
    num = (2 ** i) ^ x
    ans = 0
    bit_count_init = bc(num)
    while True:
        bit_count = bc(num)
        if num == 0:
            print(ans)
            dp[bit_count_init] = ans
            break
        num %= bit_count
        ans += 1
        if dp[num] != 0:
            print(dp[num] + ans)
            break

Submission status: Runtime Error

Solution code:
from collections import Counter

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

if X == '1':
    print(1)
    exit()
elif X == '0':
    print(0)
    exit()
    
x1 = 0
for i in X:
    if i == '1':
        x1 += 1

for i in range(N):
    if X[i] == '1':
        tmp = - (1<<(N-i-1))
        tmp2 = -1
    else:
        tmp = (1<<(N-i-1))
        tmp2 = 1
    
    n = int(X, 2) + tmp
    n %= x1 + tmp2
    cnt = 1
    while n != 0:
        c = 0
        for j in bin(n):
            c += j=='1'
        n %= c
        cnt += 1
    print(cnt)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N = int(input())
    X = input()
    count_1 = X.count('1')
    X = int('0b'+X,0)
    if X == 1:
        print(0)
        sys.exit()

    memo = [-1] * (2**N)

    def f(X):
        if memo[X]!=-1:
            return memo[X]
        x = X
        count = 0
        while x>=1:
            if x%2==1:
                count += 1
            x//=2
        if X%count == 0:
            memo[X] = 1
            return memo[X]
        else:
            memo[X] = f(X%count)+1
            return memo[X]

    for i in range(N-1,-1,-1):
        x = X^(1<<i)
        print(f(x))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

def initMemo(n):
    memo = {}
    for i in range(1, n):
        memo[i] = popcount(i)
    return memo

def popcount(n):
    cnt = 0
    while n != 0:
        cnt += 1
        n = n % bin(n).count('1')
        if n in memo:
            cnt += memo[n]
            break
        
    return cnt

memo = initMemo(N)

for i in range(N):
    temp_X = [l for l in X]
    if temp_X[i] == '0':
        temp_X[i] = '1'
    else:
        temp_X[i] = '0'
    temp_X = ''.join(temp_X)
    
    n = int(temp_X, 2)
    memo.setdefault(n, 0)
    
    output = popcount(n)
    memo[n] = output

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
t=int(x,2)
c=x.count('1')
m=[0]*n
k=1
while k<n: m[k]=1; k*=2
def popcount(x):
  x = x - ((x >> 1) & 0x5555555555555555)
  x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
  x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
  x = x + (x >> 8)
  x = x + (x >> 16)
  x = x + (x >> 32)
  return x & 0x0000007f
def f(x):
  if x==0: return 0
  if m[x]: return m[x]
  return f(x%popcount(x))+1
for i in range(n):
  if int(x[i]):
    d=c-1
    if c<1: print(0)
    else: print(f((t-pow(2,n-i-1,d))%d)+1)
  else:
    d=c+1
    print(f((t+pow(2,n-i-1,d))%d)+1)

Submission status: Runtime Error

Solution code:
n = int(input())
x = list(map(str, (input())))
L = [0, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 2, 3, 1, 2, 1, 2, 1, 1, 2, 3, 1, 2, 2, 3, 2, 2, 2, 2, 1, 2, 1, 2, 1, 2, 2, 3, 1, 2, 1, 3, 2, 2, 2, 2, 1, 2, 2, 3, 2, 2, 2, 1, 2, 2, 2, 2, 1, 2, 2, 3, 1, 2, 1, 2, 1, 1, 2, 3, 1, 2, 2, 3, 2, 2, 2, 2, 1, 1, 2, 3, 1, 2, 2, 2, 2, 2, 2, 2, 1, 3, 2, 3, 1, 2, 2, 3, 2]
for i in range(n):
    s = ''
    for j in range(n):
        if i != j:
            s += x[j]
        else:
            if x[i] == '1':
                s += '0'
            else:
                s += '1'
    xx = int(s, 2)
    p = str(bin(xx)).count('1')
    print(1 + L[xx % p])

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
num=int(x, 2)
first_one_count=x.count("1")

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

pop_list=[]
for i in range(2*(10**5)):
    pop_list.append(popcount(i))

x_mae=["",x[0]]
for i in range(1,len(x)):
    x_mae.append(x_mae[-1]+x[i])
x_mae.append("")

x_re=list(reversed(x))
x_ushiro=["",x_re[0]]
for i in range(1,len(x)):
    x_ushiro.append(x_ushiro[-1]+x_re[i])
x_ushiro.append("")

for i in range(n):
    if x[i]=='0':
        target=x_mae[i]+"1"+x_ushiro[n-1-i]
        one_count=first_one_count+1
    else:
        target=x_mae[i]+"0"+x_ushiro[n-1-i]
        one_count=first_one_count-1
    target="0b"+target
    target=int(target,2)%one_count
    cnt=1
    while target>0:
        target=target%popcount(target)
        cnt+=1
    print(cnt)

Submission status: Runtime Error

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

fn = dict()

def f(n, count):
    binary = list(bin(n))[2:]
    popcount = 0
    for b in binary:
        if b == '1':
            popcount += 1
    count += 1
    if n%popcount == 0:
        return count
    else:
        if n in fn:
            return fn[n]
        else:
            x = f(n%popcount, count)
            fn[n%popcount] = x- count
            # fn[n] = x
            return x

for i in range(N):
    X_i = X[:]
    if X_i[i] == '1':
        X_i[i] = '0'
    else:
        X_i[i] = '1'
    X_i = ''.join(X_i)
    n = int(X_i, 2)
    ans = f(n, 0)
    fn[n] = ans
    print(ans)
    # print(fn)
# print(fn)

Submission status: Runtime Error

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

n= int(input())
a=list(input())

v=a.count('1')

ans=[0]*n
A=[0]*n
# n以下の残り回数を記録
for i in range(n):
    x=i
    cnt=0
    while x>0:
        cnt+=1
        r = 0
        for j in range(5):
            if (x>>j)&1:
                r+=1
        x=x%r
    ans[i]=cnt

# 各桁をv＋１で割ったあまり
q = [0]*n
# 各桁をv-1で割ったあまり
r = [0]*n
for i in range(n):
    if a[i]=='1':
        if v!=0:
            q[i] = pow(2, n-i-1) % (v + 1)
        if v!=1:
            r[i] += pow(2, n-i-1) % (v - 1)
qq=sum(q)
rr=sum(r)

for i in range(n):
    if a[i]=='1':
        if v!=1:
            z = rr - pow(2,n-i-1)%(v-1)
            cnt = z % (v - 1)
            A[i] = 1 + ans[cnt]
    else:
        z=qq+pow(2,n-i-1)%(v+1)
        cnt=z%(v+1)
        A[i]=1+ans[cnt]

for i in A:
    print(i)

Submission status: Runtime Error

Solution code:
import copy

N = int(input())
X = int(input(), 2)

def rev(num, i):
  i = N - 1 - i
  return num ^ (1 << i)



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



for i in range(N):
  n = rev(X, i)
  cnt = 0
  
  while n != 0:
    n = n % popcount(n)
    cnt += 1
  print(cnt)