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 = int(input(),2)

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 reversed(range(0,n)):
    tmp = x^(1<<i)
    tmp2 = tmp%popcount(tmp)
    cnt = 1
    while tmp2 > 0:
        tmp = tmp2
        tmp2 = tmp % popcount(tmp)
        cnt += 1
    print(cnt)

Submission status: Runtime Error

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

n = int(input())
x = input()
mod = x.count("1")
U = 2**20
C = [0]*U
for i in range(1, U):
  q = popcount(i)
  C[i] = C[i%q] + 1
t_1 = 0
t_2 = 0
for j, s in enumerate(x):
  if s == "1":
    t_1 += pow(2, n-1-j, mod-1)
    t_1 %= mod-1
    t_2 += pow(2, n-1-j, mod+1)
    t_2 %= mod+1
for i in range(n):
  if x[i] == "1":
    temp = t_1
    temp -= pow(2, n-1-i, mod-1)
    temp %= mod-1
  else:
    temp = t_2
    temp += pow(2, n-1-i, mod+1)
    temp %= mod+1
  res = C[temp] + 1
  print(res)

Submission status: Runtime Error

Solution code:
def popcount(n):
    return str(bin(n)).count("1")
    
def g(n):
    n = n%popcount(n)
    return n
    
def f(n):
    count = 0
    x = n
    while True:
        count += 1
        r = g(x)
        if r != 0:
            x = r
        else:
            return count
            
N = int(input())
X = int(str(input()),2)

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

Submission status: Runtime Error

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


def arrayTo2(A):
    ans = 0
    l = len(A)
    for i in range(l):
        if (A[i] == '1'):
            ans += 2 ** (l-i-1)

    return ans


N = int(input())

popcountA = [0]*(2**N+1)
for i in range(1, 2**N+1):
    popcountA[i] = popcount(i)


X = input()

for i in range(N):
    Xi = []
    for j in range(N):
        if (i == j):
            if (X[i] == '0'):
                Xi.append('1')
            else:
                Xi.append('0')
        else:
            Xi.append(X[j])

    ans = 0
    n = arrayTo2(Xi)
    while (n > 0):
        n = n % popcountA[n]
        ans += 1

    print(ans)

Submission status: Runtime Error

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

'''for i in range(1,n+1):
	xlist = list(x)
	if xlist[i-1]=='0':xlist[i-1]='1'
	else:xlist[i-1]='0'
	xstr=''.join(xlist)
	xint=int(xstr,2)
	res = 0
	while xint>0:
		c=bin(xint).count('1')
		xint=xint%c
		res +=1
	print(res)'''

for i in range(1,n+1):
	if x[i-1]=='0':xint+=2**(n-i)
	else:xint-=2**(n-i)
	res = 0
	while xint>0:
		c=bin(xint).count('1')
		xint=xint%c
		res +=1
	print(res)

Submission status: Runtime Error

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


n=int(input())

s=input()
x=int(s,2)
ans=[]

ans_memo=[0]*(2**(n+2))
#print(ans_memo)
#ans_memo[1]=1
#ans_memo[2]=1

def DEF(x,cnt):
    global ans_memo
    #print(x,cnt,ans_memo)
    if ans_memo[x]!=0:
        return ans_memo[x]
    else:
        if x%(str(bin(x)).count("1"))==0:
            ans_memo[x]=1
            return 1
        else:
            tmp=DEF(x%(str(bin(x)).count("1")),cnt+1)+1
            ans_memo[x]=tmp
            return tmp

ans=[]

for i in range(n):
    tmp=2**(n-i-1)
    tmp_num=x

    #1の時
    if tmp&tmp_num:
        tmp_num-=tmp
        ans.append(DEF(tmp_num,0))
        
    else:
        tmp_num+=tmp
        ans.append(DEF(tmp_num,0))

#print(ans_memo)

for item in ans:
    print(item)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
x = input().rstrip()  
for i in range(n):
    L = list(map(int,x))
    L[i]^=1
    s = ''.join(map(str,L))
    dec = int(s,2)
    rem = 1
    ans = 0
    while rem !=0:
        ans+=1
        count = 0
        num = dec
        while dec!=0 :
            dec &=(dec-1)
            count+=1
        rem = num%count
        dec = rem
    print(ans)
    sys.exit()

Submission status: Runtime Error

Solution code:
def main():
    import sys
    N=int(sys.stdin.readline())
    X=sys.stdin.readline()

    no=X.count('1')
    np=no+1
    nm=no-1

    np_mods=[-1]*N
    nm_mods=[-1]*N
    
    np_mods[0]=1
    nm_mods[0]=1
    
    for i in range(1,N):
        np_mods[i]=(np_mods[i-1]*2)%np
        nm_mods[i]=(nm_mods[i-1]*2)%nm

    np_mods.reverse()
    nm_mods.reverse()

    np_mods_sum=0
    nm_mods_sum=0
    for i in range(N):
        if X[i]=='1':
            np_mods_sum+=np_mods[i]
            nm_mods_sum+=nm_mods[i]

    for i in range(N):
        if X[i]=='0':
            n=(np_mods_sum+np_mods[i])%np

        else:
            n=(nm_mods_sum-nm_mods[i])%nm

        if n==0:
            print(1)
            continue
        count=1
        while True:
            bs=str(bin(n))[2:]
            k=bs.count('1')
            n=n%k
            count+=1
            if n==0:
                break
        print(count)

main()

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    X = input()
    popcount = [0] * (N+1)
    for i in range(1,N+1):
        pop = bin(i).count("1")
        popcount[i] = 1 + popcount[i%pop]


    val_x = int(X, 2)
    cnt_x = X.count("1")
    for i in range(N):
        if X[i] == "0":
            xi = val_x + 2**(N-i-1)
            c = cnt_x + 1
        else:
            xi = val_x - 2**(N-i-1)
            c = cnt_x - 1
        if val_x == 0:
            print(0)
        else:
            print(popcount[xi%c]+1)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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


def arrayTo2(A):
    ans = 0
    l = len(A)
    for i in range(l):
        if (A[i] == '1'):
            ans += 2 ** (l-i-1)

    return ans


N = int(input())

popcountA = [0]*(2**N+1)
for i in range(1, 2**N):
    popcountA[i] = popcount(i)


X = input()

for i in range(N):
    Xi = []
    for j in range(N):
        if (i == j):
            if (X[i] == '0'):
                Xi.append('1')
            else:
                Xi.append('0')
        else:
            Xi.append(X[j])

    ans = 0
    n = arrayTo2(Xi)
    while (n > 0):
        n = n % popcountA[n]
        ans += 1

    print(ans)

Submission status: Runtime Error

Solution code:
n,x=int(input()),input()
g=int(x,2)
c=pow(2,n-1)
memo={}
for b in x:
    if b=="1":
        p=g-c
    else:
        p=g+c
    ret=0
    while p:
        q=bin(p).count("1")
        if (p,q)in memo:print(ret+memo[(p,q)]);break 
        p%=q
        ret+=1
    c//=2
    memo[(p,q)]=ret
    print(ret)

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
temp = x.count("1")
x2 = int(x, 2)
for i in range(n):
    if x[i] == "1":
        temp2 = -1
    else:
        temp2 = 1
    num = x2 ^ (2 ** (n - 1 - i))
    num %= (temp + temp2)
    count = 1
    while num:
        num %= bin(num).count("1")
        count += 1
    print(count)

Submission status: Runtime Error

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

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

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

ans = []
for i in range(0, N):
    cnt = 0
    t = toggle_nth_bit(X, i)
    # print("i={}, t={}".format(i, t))
    while t != 0:
        m = popcount(t)
        t = t%m
        cnt += 1
    ans.append(cnt)

print(*reversed(ans), sep='\n')

Submission status: Runtime Error

Solution code:
def main():

    n = int(input())
    x = list(str(input()))

    p = 0
    for i in range(n):
        if x[i] == '1':
            p += 1

    def power(a, n, mod):
        bi=str(format(n,"b")) #2進数
        res=1
        for i in range(len(bi)):
            res=(res*res) %mod
            if bi[i]=="1":
                res=(res*a) %mod
        return res

    X1 = 0
    X2 = 0
    import copy
    s = copy.copy(x)
    s.reverse()
    #print(s)
    for i in range(n):
        if s[i] == '1':
            X1 += power(2, i, p+1)
            X2 += power(2, i, p-1)

    #print(p)
    #print(X1)
    #print(X2)
    ans = [0]*n
    for i in range(n):
        if x[i] == '0':
            temp = X1
            temp += power(2, n-1-i, p+1)
            temp %= (p+1)
            if temp == 0:
                ans[i] = 1
                continue
            cnt = 0
            d = p+1
            while temp:
                cnt += 1
                temp %= d
                b = format(temp, 'b')
                d = 0
                for j in range(len(b)):
                    if b[j] == '1':
                        d += 1
        else:
            temp = X2
            temp -= power(2, n-1-i, p-1)
            temp %= (p-1)
            if temp == 0:
                ans[i] = 1
                continue
            cnt = 0
            d = p-1
            while temp:
                cnt += 1
                temp %= d
                b = format(temp, 'b')
                d = 0
                for j in range(len(b)):
                    if b[j] == '1':
                        d += 1
        ans[i] = cnt
    #print(*ans)
    for i in range(n):
        print(ans[i])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def popcount(n):
    bin_n = format(n, "b")
    ans = 0
    for e in bin_n:
        if e=="1":
            ans += 1
    return ans

N = int(input())
bin_X = input()

for i in range(N):
    if bin_X[i] == "0":
        bin_new = bin_X[:i] + "1" + bin_X[i+1:]
    else:
        bin_new = bin_X[:i] + "0" + bin_X[i+1:]
    #print(bin_new)
    new = int(bin_new, 2)
    #print(new)
    ans = 0
    while True:
        ans += 1
        new = new % popcount(new)
        if new == 0:
            break
    print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
S = list(map(int, list(input())))

def pp(n):
	v = n
	pc = 0
	while 0<v:
		if v&1:
			pc+=1
		v = v//2
	return pc

def f(n):
#	print("f", n)
	if n==0:
		return 0
	pc = pp(n)
#	print("pc", pc, n%pc)
	return 1 + f(n % pc)

#print(N)
#print(s)

def s2i(s):
	v = 0
	for i in range(N):
		v = v*2 + int(s[i])
#	print(s, v)
	return v


ref = s2i(S)
refPC = pp(ref)

refm = [ ref % (refPC-1+i) for i in range(3) ]

#print("ref", ref)
#print("refPC", refPC)
#print("refm", refm)

m = [ [0]*N for i in range(3) ]
for i in range(3):
	pc = refPC-1+i
	for j in range(N):
		if j==0:
			m[i][N-1-j] = 1 % pc
		else:
			m[i][N-1-j] = (m[i][N-1-(j-1)]*2)%pc

for i in range(N):
	if S[i]:
		pc = refPC-1
		ans = 1+f((refm[0]-m[0][i]+pc)%pc)
	else:
		pc = refPC+1
		ans = 1+f((refm[2]+m[2][i]+pc)%pc)
	print(ans)
#	S[i] = 1-S[i]
#	print(f(s2i(S)))
#	S[i] = 1-S[i]

#print(f(7))

#N = 100000
#print(N)
#print("1" * N)

Submission status: Runtime Error

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

def main():
    n = int(input())
    x = list(input())
    for i in range(n):
        x[i] = int(x[i])
    A0 = 0
    A1 = 0
    B = sum(x)
    for i in range(n):
        A0 += x[i]*pow(2,n-i-1,B+1)
        A1 += x[i]*pow(2,n-i-1,B-1)
        A0 %= B+1
        A1 %= B-1
    for i in range(n):
        if x[i] == 0:
            BB = B + 1
            AA = A0 + pow(2,n-i-1,BB)
        else:
            BB = B - 1
            AA = A1 - pow(2,n-i-1,BB)
        ans = 1
        while AA%BB != 0:
            AA = AA%BB
            AAA = copy.deepcopy(AA)
            BB = 0
            while AAA != 0:
                BB += AAA%2
                AAA //= 2
            ans += 1
        print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

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


def arrayTo2(A):
    ans = 0
    l = len(A)
    for i in range(l):
        if (A[i] == '1'):
            ans += 2 ** (l-i-1)

    return ans


N = int(input())

popcountA = [0]*(N+1)
for i in range(1, 2**N):
    popcountA[i] = popcount(i)


X = input()

for i in range(N):
    Xi = []
    for j in range(N):
        if (i == j):
            if (X[i] == '0'):
                Xi.append('1')
            else:
                Xi.append('0')
        else:
            Xi.append(X[j])

    ans = 0
    n = arrayTo2(Xi)
    while (n > 0):
        n = n % popcountA[n]
        ans += 1

    print(ans)

Submission status: Runtime Error

Solution code:
n=int(input(""))
x=input("")
def pop(n):
    i=0
    while(n>0):
        if(n%2==1):
            i+=1
        n=int(n/2)
    return i
listx=[]
for i in range(n):
    listx+=[int(x[n-1-i])]

for i in range(n):
    listx[n-i-1]=1-listx[n-1-i]
    
    t=0
    for k in range(n):
        t+=listx[k]*2**k
    
    c=0  
    while(t>0):
        s=pop(t)
        t%=s
        c+=1

    



    print(c)
    listx[n-1-i]=1-listx[n-1-i]

Submission status: Runtime Error

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

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))



n = readint()
x = readstr()

a = int(x,2)

bit = x.count('1')

z = [0]*(n+1)
for i in range(1,n+1):
    b = i
    while b>0:
        c = 0
        for j in range(b.bit_length()):
            if b&(1<<j):
                c += 1
        b%=c
        z[i]+=1

print(z)
ans = [1]*n
for i in range(n):
    if a&(1<<i):
        b = a-(1<<i)
        if b==0:
            ans[i]-=1
        b%=bit-1
    else:
        b = a + (1<<i)
        b%=bit+1
    ans[i]+=z[b]

printrows(reversed(ans))

Submission status: Runtime Error

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def s(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")

n = k()
x = X()
for i in range(n):
    a = x.copy()
    if a[i] == "0":
        a[i] = "1"
    else:
        a[i] = "0"
    b = "".join(a)
    c = a.count("1")
    d = int(b,2)
    ans = d % c
    if ans == 0:
        print(1)
    elif ans ==1 or ans % 2 == 0:
        print(2)
    else:
        print(3)

Submission status: Runtime Error

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

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):
    y = x[:]
    if x[i] == "1":
        y[i] = "0"
        z = "".join(y)
        z = int(z, 2)
        ans = 0
        while z > 0:
            z %= popcount(z)
            ans += 1
        print(ans)
    else:
        y[i] = "1"
        z = "".join(y)
        z = int(z, 2)
        ans = 0
        while z > 0:
            z %= popcount(z)
            ans += 1
        print(ans)

Submission status: Runtime Error

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


def solve(N: int, X: str):
    X_oct = int(X, 2)
    X_one_count = sum([1 for x in X if x == '1'])

    memo = {}
    for i, x in enumerate(X):
        if x == '1':
            X_current = X_oct - 2 ** (N-1-i)
            X_one_current = X_one_count - 1
        elif x == '0':
            X_current = X_oct + 2 ** (N - 1 - i)
            X_one_current = X_one_count + 1

        count = 0
        while True:
            X_current = X_current % X_one_current
            X_one_current = sum([1 for x in bin(X_current) if x == '1'])
            count += 1

            if X_current == 0:
                break

            if X_current in memo:
                count += memo[X_current]
                break
        print(count)

    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N = int(input())
    X = input()
    solve(N, X)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
print "2"
print "1"
print "1"

Submission status: Runtime Error

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


def solve(N: int, X: str):
    X_oct = int(X, 2)
    X_one_count = sum([1 for x in X if x == '1'])

    memo = {}
    for i, x in enumerate(X):
        if x == '1':
            X_current = X_oct - 2 ** (N-1-i)
            X_one_current = X_one_count - 1
        elif x == '0':
            X_current = X_oct + 2 ** (N - 1 - i)
            X_one_current = X_one_count + 1

        count = 0
        while True:
            X_current = X_current % X_one_current
            X_one_current = sum([1 for x in bin(X_current) if x == '1'])
            count += 1

            if X_current == 0:
                break

            if X_current in memo:
                count += memo[X_current]
                break
        print(count)

    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = next(tokens)  # type: str
    solve(N, X)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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


def arrayTo2(A):
    ans = 0
    l = len(A)
    for i in range(l):
        if (A[i] == '1'):
            ans += 2 ** (l-i-1)

    return ans


N = int(input())

popcountA = [0]*(N+1)
for i in range(1, N):
    popcountA[i] = popcount(i)


X = input()

for i in range(N):
    Xi = []
    for j in range(N):
        if (i == j):
            if (X[i] == '0'):
                Xi.append('1')
            else:
                Xi.append('0')
        else:
            Xi.append(X[j])

    ans = 0
    n = arrayTo2(Xi)
    while (n > 0):
        n = n % popcountA[n]
        ans += 1

    print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
num = 0
count = 0
for i in range(n):
    if x[-(i+1)] == "1":
        num += 2**i
        count += 1

mod = [0]*n
for i in range(n):
    mod[i] = (2**i%(count-1), 2**i%(count+1))
mod1 = num%(count-1)
mod2 = num%(count+1)

ans = [0]*n
for i in range(n):
    if x[-(i+1)] == "1":
        _num = num-2**i
        if _num == 0:
            continue
        _num = (mod1-mod[i][0])%(count-1)
    else:
        _num = num+2**i
        _num = (mod1-mod[i][1])%(count+1)
    ans[i] += 1
    _count = 0
    for c in bin(_num):
        if c == "1":
            _count += 1
    while True:
        if _num == 0:
            break
        _num %= _count
        _count = 0
        for c in bin(_num):
            if c == "1":
                _count += 1
        ans[i] += 1
for i in range(n):
    print(ans[-(i+1)])

Submission status: Runtime Error

Solution code:
import sys
#import string
#from collections import defaultdict, deque, Counter
#import bisect
#import heapq
#import math
#from itertools import accumulate
#from itertools import permutations as perm
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as combr
#from fractions import gcd
#import numpy as np
import copy

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

def popcount(d,ans):
    c = d.count("1")
    d = int(d,2)
    d = d%c
    if d==0:
        return ans
    else:
        ans += 1
        return popcount(bin(d),ans)





def solve():
    n = int(stdin.readline().rstrip())
    X = str(stdin.readline().rstrip())
    #A, B, C = map(int, stdin.readline().rstrip().split())
    #l = list(map(int, stdin.readline().rstrip().split()))
    #numbers = [[int(c) for c in l.strip().split()] for l in sys.stdin]
    #word = [stdin.readline().rstrip() for _ in range(n)]
    #number = [[int(c) for c in stdin.readline().rstrip()] for _ in range(n)]
    #zeros = [[0] * w for i in range(h)]
    X = list(X)
    for i in range(n):
        x = copy.deepcopy(X)
        if x[i] == "0":
            x[i] = "1"
        else:
            x[i] = "0"
        d = "".join(x)
        ans = 0
        ans = popcount(d,ans)
        print(ans+1)


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

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

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

def f(s):
  # s: bin
  sub = int(s, 2) % popcount(s)
  if sub:
    return 1 + f('{:b}'.format(sub))
  return 1

for n in range(N):
  s = list(X)
  s[n] = '0' if s[n] == '1' else '1'
  print(f(''.join(s)))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)

def pc(n,t):
    if n==0:
        return t
    return pc(n//2,t+n%2)

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

for i in range(N):
    if X[i]=="0":
        x2=x+2**(N-i-1)
        p=pc(x2,0)
    else:
        x2=x-2**(N-i-1)
        p=pc(x2,0)
    ans=0
    while x2>0:
        x2%=p
        p=pc(x2,0)
        ans+=1
    print(ans)

Submission status: Runtime Error

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


def arrayTo2(A):
    ans = 0
    l = len(A)
    for i in range(l):
        if (A[i] == '1'):
            ans += 2 ** (l-i-1)

    return ans


N = int(input())

popcountA = [0]*(N+1)
for i in range(1, N):
    popcountA[i] = popcount(i)


X = input()

for i in range(N):
    Xi = []
    for j in range(N):
        if (i == j):
            if (X[i] == '0'):
                Xi.append('1')
            else:
                Xi.append('0')
        else:
            Xi.append(X[j])

    ans = 0
    n = arrayTo2(Xi)
    while (n > 0):
        n = n % popcountA(n)
        ans += 1

    print(ans)

Submission status: Runtime Error

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

def calc(n,count):
    popcount=bin(n).count("1")
    next_n=n%popcount
    #print(next_n)
    if next_n==0:
        return count+1
    else:
        return calc(next_n, count+1)



for i in range(N):
    if X[i]=="1":
        change="0"
    else:
        change="1"

    nowbin=X[:i]+change+X[i+1:]
    #print(int(nowbin, 2))
    print(calc(int(nowbin, 2),0))

Submission status: Runtime Error

Solution code:
def f(n):
  if n==0:
    return 0
  c=0
  while n>0:
    n%=format(n, 'b').count('1')
    c+=1
  return c

N=int(input())
X=input()
nums=[f(i) for i in range(N+1)]

a=0
b=0
for i in range(N):
  if X[i]=='0':
    a+=1
  else:
    b+=1

s=0
t=0
for i in range(N):
  s=(s+int(X[i])*pow(2, N-1-i, b+1))%(b+1)
  t=(t+int(X[i])*pow(2, N-1-i, b-1))%(b-1)

for i in range(N):
  if X[i]=='0':
    tmp=(s+pow(2, N-1-i, b+1))%(b+1)
    print(nums[tmp]+1)
  else:
    tmp=(t-pow(2, N-1-i, b-1))%(b-1)
    print(nums[tmp]+1)

Submission status: Runtime Error

Solution code:
def count_ones_by_shift_2(num):
    num = (num & 0x55555555) + (num >> 1 & 0x55555555) 
    num = (num & 0x33333333) + (num >> 2 & 0x33333333)
    num = (num & 0x0F0F0F0F) + (num >> 4 & 0x0F0F0F0F)
    num = (num & 0x00FF00FF) + (num >> 8 & 0x00FF00FF)
    num = (num & 0x0000FFFF) + (num >>16 & 0x0000FFFF)
    return num
memo = {0: 0}
def fun(num):
    if num in memo: return memo[num]
    tmp = num % count_ones_by_shift_2(num)
    cnt = 1 + fun(tmp)
    memo[num] = cnt
    return cnt       
    
N = int(input())
X = int(input(), 2)
for i in range(N):        
    xi = X ^ ((2**(N-1)) >> i)
    cnt = fun(xi)
    print(cnt)

Submission status: Runtime Error

Solution code:
n=int(input())

s=input()
x=int(s,2)
ans=[]

ans_memo=[0]*(2**(n+1))
#ans_memo[1]=1
#ans_memo[2]=1

def DEF(x,cnt):
    global ans_memo
    #print(x,cnt,ans_memo)
    if ans_memo[x]!=0:
        return ans_memo[x]
    else:
        if x%(str(bin(x)).count("1"))==0:
            ans_memo[x]=1
            return 1
        else:
            tmp=DEF(x%(str(bin(x)).count("1")),cnt+1)+1
            ans_memo[x]=tmp
            return tmp

ans=[]

for i in range(n):
    tmp=2**(n-i-1)
    tmp_num=x

    #1の時
    if tmp&tmp_num:
        tmp_num-=tmp
        ans.append(DEF(tmp_num,0))
        
    else:
        tmp_num+=tmp
        ans.append(DEF(tmp_num,0))

#print(ans_memo)

for item in ans:
    print(item)

Submission status: Runtime Error

Solution code:
def pc(n,t):
    if n==0:
        return t
    return pc(n//2,t+n%2)

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

for i in range(N):
    if X[i]=="0":
        x2=x+2**(N-i-1)
        p=pc(x2,0)
    else:
        x2=x-2**(N-i-1)
        p=pc(x2,0)
    ans=0
    while x2>0:
        x2%=p
        p=pc(x2,0)
        ans+=1
    print(ans)

Submission status: Runtime Error

Solution code:
def popcount(n):
    temp = str(bin(n))
    return temp.count("1")
    
    
def g(n):
    n = n%popcount(n)
    return n
    
def f(n):
    count = 0
    x = n
    while True:
        count += 1
        if g(x) != 0:
            x = g(x)
        else:
            return count
            
N = int(input())
X = int(str(input()),2)

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

Submission status: Runtime Error

Solution code:
'''
    Auther: ghoshashis545 Ashis Ghosh
    College: jalpaiguri Govt Enggineering College

'''
from os import path
import sys
from heapq import heappush,heappop
from functools import cmp_to_key as ctk
from collections import deque,defaultdict as dd 
from bisect import bisect,bisect_left,bisect_right,insort,insort_left,insort_right
from itertools import permutations
from datetime import datetime
from math import ceil,sqrt,log,gcd
def ii():return int(input())
def si():return input()
def mi():return map(int,input().split())
def li():return list(mi())
abc='abcdefghijklmnopqrstuvwxyz'
mod=1000000007
# mod=998244353
inf = float("inf")
vow=['a','e','i','o','u']
dx,dy=[-1,1,0,0],[0,0,1,-1]

def bo(i):
    return ord(i)-ord('a')

file=0




def f(n):
    s=bin(n)[2:]
    return s.count('1')
def solve():


    # for _ in range(ii()):
    
        

    n=ii()
    s=si()
    c=0
    for i in s:
        if i=='1':
            c+=1
    n1=int(s,2)
    # print(n1,c)
    for i in range(n):
        if s[i]=='1':
            n2=n1-pow(2,n-i-1)
            c1=c-1
        else:
            c1=c+1
            n2=n1+pow(2,n-i-1)

        ans=1
        # print(n2,c1)
        while(n2%c1):
            ans+=1
            n2%=c1
            c1=f(n2)
        print(ans)







        
if __name__ =="__main__":

    if(file):

        if path.exists('input1.txt'):
            sys.stdin=open('input1.txt', 'r')
            sys.stdout=open('output1.txt','w')
        else:
            input=sys.stdin.readline
    solve()

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
temp = x.count("1")
x2 = int(x, 2)
for i in range(n):
    if x[i] == "1":
        temp2 = -1
    else:
        temp2 = 1
    num = x2 ^ (2 ** (n - 1 - i))
    num %= temp + temp2
    count = 1
    while num:
        num %= bin(num).count("1")
        count += 1
    print(count)

Submission status: Runtime Error

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

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N = Z()
    X = input()
    pcnt = 0
    ans = []
    for x in X:
        if x == '1': pcnt += 1
    if pcnt == 0:
        for _ in range(N):
            print(0)
            return
    Xinv = X[::-1]
    ex1 = ex2 = 1
    num1 = num2 = 0
    for x in Xinv:
        num1 += (ex1 * int(x)) % (pcnt + 1)
        num1 %= (pcnt + 1)
        if pcnt > 0:
            num2 += (ex2 * int(x)) % (pcnt - 1)
            num2 %= (pcnt - 1)
        ex1 *= 2
        ex1 %= (pcnt + 1)
        ex2 *= 2
        if pcnt > 0: ex2 %= (pcnt - 1)

    def solve(n, p, s):
        if n == 0 and s > 0: return s
        n %= p
        p = bin(n).count('1')
        return solve(n, p, s+1)

    for i in range(N):
        if X[i] == '1':
            p = pcnt - 1
            if p == 0:
                ans.append(0)
                continue
            num = num2 - pow(2, N-i-1, p)
            ans.append(solve(num, p, 0))
        else:
            p = pcnt + 1
            num = num1 + pow(2, N-i-1, p)
            ans.append(solve(num, p, 0))

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

    return

if __name__ == '__main__':
    main()