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:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
import random
from collections import deque
from decimal import *
import queue

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	X = inputStr()
	X_lin = list(X)

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

		oct = int(tmpX, 2)

		ans_tmp = 0
		while True:
			if oct == 0:
				break
			tmp = count_ones_by_table(oct)
			oct = oct % tmp
			ans_tmp += 1
		ans.append(ans_tmp)

	for i in ans:
		print(i)

def count_ones_by_table(num):
    bit_table_256 = [
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
    ]
    count = 0
    count += bit_table_256[num & 0xFF]
    count += bit_table_256[(num >> 8) & 0xFF]
    count += bit_table_256[(num >> 16) & 0xFF]
    count += bit_table_256[(num >> 24) & 0xFF]
    return count

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Runtime Error

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


def popcount(n, current):
    bit = 1
    count = 0
    while bit <= n:
        if (bit & n) > 0:
            count += 1
        bit = bit << 1
    n = n % count
    if n == 0:
        return 1
    else:
        return 1 + popcount(n, current + 1)


for i in range(len(x)):
    if x[i] == '0':
        y = x_int + 2 ** (n - 1 - i)
    else:
        y = x_int - 2 ** (n - 1 - i)
    print(popcount(y, 0))

Submission status: Runtime Error

Solution code:
N=int(input())
X=input()
def fx(n,c):
    b=n%c
    if b==0:
        return 1
    if b==1 or b==2:
        return 2
    t=bin(b).count("1")
    return fx(b,t)+1
c=X.count("1")
n=int(X,2)
for i in range(N):
    if X[i]=="0":
        print(fx(n+2**(N-i-1),c+1))
    else:
        print(fx(n-2**(N-i-1),c-1))

Submission status: Runtime Error

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

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

N=int(input())
X=input()
bit=[""]*N
for i in range(N):
    bit[i]=X[i]

n=int(X,2)
for i in range(N):
    tmp=n
    if bit[i]=="0":
        tmp+=2**(N-i-1)
    else:
        tmp-=2**(N-i-1)
    print(f(tmp))

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from collections import deque
from collections import Counter
import itertools
import math

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

h = defaultdict(int)
n = readInt()
x = readChar()
base = int(x,2)
def popcorn(v):
	if h[v]!=0:
		return h[v]
	else:
		store = []
		a = -1
		while a!=0:
			t = bin(v)
			c = t.count("1")
			a = v%c
			store.append(v)
			v = a
			#print(store)
		for i in range(len(store)):
			h[store[i]]=len(store)-i
		return len(store)



for i in range(n):
	if x[i]=="0":
		t=base+2**(n-i-1)
	else:
		t=base-2**(n-i-1)
	print(popcorn(t))

Submission status: Runtime Error

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


c = dict()
for i in range(len(X)):
    x = list(X)

    if X[i] == '1':
        x[i] = '0'
    else:
        x[i] = '1'

    c[i] = 0
    while True:
        cnt = x.count('1')
        x_c = "".join(x)
        bins = int(x_c, 2)
        n = bins % cnt
        c[i] += 1
        if n == 0:
            break

        x = format(n, '08b')

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

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
ones = 0
for i in x:
    if i=='1':
        ones += 1
mods = [0, 0]
for i in range(n):
    if x[n-i-1]=='1':
        mods[0] += pow(2, i, ones-1)
        mods[1] += pow(2, i, ones+1)
mods[0] %= ones-1
mods[1] %= ones+1
def f(x):
    if x==0:
        return 1
    cnt = 1
    while x>0:
        p = bin(x).count('1')
        x %= p
        cnt += 1
    return cnt
for i in range(n-1, -1, -1):
    if x[n-i-1]=='1':
        init = (mods[0] - pow(2, i, ones-1))%(ones-1)
    else:
        init = (mods[1] + pow(2, i, ones+1))%(ones+1)
    print(f(init))

Submission status: Runtime Error

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

m = 2*10**5+10
ans = [0] * m
for i in range(1,m):
    nnow = i
    res = 0
    stnow = bin(nnow).count('1')
    while nnow:
        # print(nnow)
        nnow %= stnow
        stnow = bin(nnow).count('1')
        res += 1
    ans[i] = res
# for i in range(10):
#     print(i,ans[i])
n = inp()
s = list(input())
st = s.count('1')
num = 0
for i,x in enumerate(s[::-1]):
    if x == '1': num += pow(2,i)
for i in range(n):
    ntmp = pow(2,n-i-1)
    if s[i] == '0':
        nnow = num + ntmp
        stnow = st + 1
    else:
        nnow = num - ntmp
        stnow = st - 1
    nnow %= stnow
    print(ans[nnow]+1)

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
one=x.count("1")
amari_m=0
amari_p=0
for i in range(n):
	if x[-i-1]=="1":
		amari_p+=pow(2,i,one+1)
		amari_m+=pow(2,i,one-1)
		amari_p%=one+1
		amari_m%=one-1
for i in range(n):
	cnt=0
	if x[i]=="1":
		r=(amari_m-pow(2,(n-i-1),one-1))%(one-1)
	else:
		r=(amari_p+pow(2,(n-i-1),one+1))%(one+1)
	while r:
		r%=bin(r).count("1")
		cnt+=1
	print(cnt+1)

Submission status: Runtime Error

Solution code:
N=int(input())
X=input()
XX=0
for i in range(N):
    XX+=int(X[N-i-1])*2**i
#print(XX)

POPCOUNT_TABLE16 = [0] * 2**16
for index in range(len(POPCOUNT_TABLE16)):
    POPCOUNT_TABLE16[index] = (index & 1) + POPCOUNT_TABLE16[index >> 1]

def popcnt5(v):
    return (POPCOUNT_TABLE16[ v        & 0xffff] +
            POPCOUNT_TABLE16[(v >> 16) & 0xffff] +
            POPCOUNT_TABLE16[(v >> 32) & 0xffff] +
            POPCOUNT_TABLE16[(v >> 48)         ])

def change(x,j):
    if int(x[j]):
        return XX-2**(N-1-j)
    else:
        return XX+2**(N-1-j)

def F(t):
    cnt=0
    n=t
    while n!=0:
        n%=popcnt5(n)
        cnt+=1
    return cnt


for i in range(N):
    #print(change(X,i))
    print(F(change(X,i)))

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
pcnt = x.count("1")
pp = pcnt+1
pn = pcnt-1
ansb = [0,0,0]
def modpcnt(x):
  if x == 0:
    return 0
  b = x.bit_length()
  mod = 0
  for i in range(b):
    if x&1<<i:
      mod += 1
  return 1+modpcnt(x%mod)
for i in range(n):
  if x[i] == "1":
    ansb[1] += pow(2,n-i-1,pcnt)
    ansb[1] %= pcnt
    ansb[0] += pow(2,n-i-1,pp)
    ansb[0] %= pp
    ansb[2] += pow(2,n-i-1,pn)
    ansb[2] %= pn
for i in range(n):
  if x[i] == "0":
    tmp = (ansb[0]+pow(2,n-i-1,pp))%pp
    print(modpcnt(tmp)+1)
  else:
    tmp = (ansb[2]-pow(2,n-i-1,pn))%pn
    print(modpcnt(tmp)+1)

Submission status: Runtime Error

Solution code:
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 g(num_in):
    num = num_in
    cnt = 0
    if num == 0:
        return 0

    while True:
        base = popcount(num)
        if num%base == 0:
            cnt += 1
            break
        else:
            num = num%base
            cnt += 1
    return cnt


n = int(input())
s = input()

st = 0
for c in s:
    if c == "1":
        st += 1

mod_p1 = [0 for i in range(n)]
mod_n1 = [0 for i in range(n)]
base = 1
for i in range(n):
    t1 = base%(st+1)
    t2 = base%(st-1)

    mod_p1[-i-1] = t1
    mod_n1[-i-1] = t2

    base *= 2

p1 = 0
n1 = 0
for i in range(n):
    if s[i] == "1":
        p1 += mod_p1[i]
        n1 += mod_n1[i]

for i in range(n):
    if s[i] == "0":
        base = p1
        base += mod_p1[i]
        base %= st+1
        print(1+g(base))

    else:
        base = n1
        base -= mod_n1[i]
        base %= st-1
        print(1+g(base))

Submission status: Runtime Error

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

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

def process(n):
    return n % popcount(n)

def func(n):
    ret = 0
    while n > 0:
        n = process(n)
        ret += 1
    return ret

pcnt = X.count('1')
mods_plus = []
totalmod_plus = 0
tmp_plus = 1
pp = pcnt+1
mods_minus = []
totalmod_minus = 0
tmp_minus = 1
pm = pcnt-1
for c in reversed(X):
    if c == '1':
        totalmod_plus += tmp_plus
        totalmod_plus %= pp
    mods_plus.append(tmp_plus)
    tmp_plus = tmp_plus*2 % pp
    if pcnt > 0:
        if c == '1':
            totalmod_minus += tmp_minus
            totalmod_minus %= pm
        mods_minus.append(tmp_minus)
        tmp_minus = tmp_minus*2 % pm

for i in range(N):
    if X[i] == '1':
        if pcnt == 1:
            print(0)
        else:
            mod = mods_minus[-i-1]
            print(func((totalmod_minus - mod) % pm) + 1)
    else:
        mod = mods_plus[-i-1]
        print(func((totalmod_plus + mod) % pp) + 1)

Submission status: Runtime Error

Solution code:
def examA():
    L, R, D = LI()
    ans = R//D - (L-1)//D
    print(ans)
    return

def examB():
    N = I()
    A = LI()
    ans = 0
    for i,a in enumerate(A):
        if i%2==0:
            if a%2==1:
                ans += 1
    print(ans)
    return

def examC():
    N = I()
    ans = [0]*N
    for x in range(1,101):
        for y in range(1,101):
            for z in range(1,101):
                cur = x**2 + y**2 + z**2 + x*y + y*z + x*z
                if cur<N+1:
                    ans[cur-1] += 1

    for v in ans:
        print(v)
    return

def examD():
    def cnt(num):
        c = 0
        while(num>0):
            num %= bin(num).count("1")
            c += 1
        return c
    N = I()
    X = SI()
    S_upper = [0]*N
    S_lower = [0]*N
    start_upper = 0
    start_lower = 0
    bit = 0
    ans = [0]*N
    for s in X:
        if s=="1":
            bit += 1
    if bit==1:
        b = 0
        for i in range(N):
            if X[i]=="1":
                ans[i] = 0
                b = i
            else:
                ans[i] = 1
        if b==N-1:
            for i in range(N-1):
                ans[i] += 1
        for v in ans:
            print(v)
        return
    elif bit==0:
        for v in ans:
            print(v+1)
        return

    for i in range(N):
        S_upper[i] = pow(2,N-i-1,bit+1)
        S_lower[i] = pow(2,N-i-1,bit-1)
        if X[i]=="1":
            start_upper += S_upper[i]
            start_lower += S_lower[i]
            start_upper %= (bit+1)
            start_lower %= (bit-1)
    for i in range(N):
        if X[i]=="0":
            cur = (start_upper + S_upper[i]) % (bit+1)
            ans[i] = cnt(cur)+1
        else:
            cur = (start_lower - S_lower[i] + bit -1) % (bit-1)
            ans[i] = cnt(cur)+1
        #print(cur)

    for v in ans:
        print(v)
    return

def examE():
    T = I()
    ans = [0]*T

    for t in range(T):


    for v in ans:
        print(v)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(2*10**6)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Runtime Error

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

x_cnt = x.count('1')
yp = 0
ym = 0
for i in range(n):
    yp *= 2
    yp += int(x[i])
    yp %= x_cnt + 1

    ym *= 2
    ym += int(x[i])
    ym %= x_cnt - 1


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


# print(x, x_cnt, yp, ym)

ans = [0] * n
bp = bm = 1
for i in reversed(range(n)):
    if x[i] == '0':
        z = (yp + bp) % (x_cnt + 1)
    else:
        z = (ym - bm + x_cnt - 1) % (x_cnt - 1)
    ans[i] = 1 + count(z)
    # print(i, z, ans[i])
    bp *= 2
    bp %= x_cnt + 1
    bm *= 2
    bm %= x_cnt - 1

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

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)

    def f(X, result):
        x = X
        count = 0
        while x>=1:
            if x%2==1:
                count += 1
            x//=2
        X = X % count
        result += 1
        if X == 0:
            return print(result)
        else:
            f(X, result)

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

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

def count(num):
    num = (num & 0x55555555) + ((num & 0xAAAAAAAA) >> 1) 
    num = (num & 0x33333333) + ((num & 0xCCCCCCCC) >> 2)
    num = (num & 0x0F0F0F0F) + ((num & 0xF0F0F0F0) >> 4)
    num = (num & 0x00FF00FF) + ((num & 0xFF00FF00) >> 8)
    num = (num & 0x0000FFFF) + ((num & 0xFFFF0000) >> 16)
    
    return num
        

x_10 = int(x,2)

for i in reversed(range(1,n+1)):
    if x[n-i]=='1':
        y=x_10-2**(i-1)
    else:
        y=x_10+2**(i-1)
        
    k=0
    while y!=0:
        y = y % count(y)
        #print(y)
        k+=1
    print(k)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
import random
from collections import deque
from decimal import *
import queue

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	X = inputStr()
	X_lin = list(X)

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

		oct = int(tmpX, 2)

		ans_tmp = 0
		while True:
			if oct == 0:
				break
			tmp = popcount(oct)
			oct = oct % tmp
			ans_tmp += 1
		ans.append(ans_tmp)

	for i in ans:
		print(i)

def popcount(x):
	x = x - ((x >> 1) & 0x5555555555555555)
	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

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[4]:


import copy


# In[35]:


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


# In[36]:


def func(N,X):
    for i in range(N):
        ans = 1
        xi = copy.deepcopy(X)
        xi[i] = str(1-int(X[i]))
        popcount = xi.count("1")
        num = int("".join(xi),2)
        while num%popcount != 0:
            num = num%popcount
            popcount = format(num,"b").count("1")
            ans += 1
        print(ans)


# In[37]:


func(N,X)


# In[ ]:

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:
            AA = A0 + pow(2,n-i-1,B+1)
            BB = B + 1
        else:
            AA = A1 - pow(2,n-i-1,B-1)
            BB = B - 1
        ans = 1
        while AA%BB:
            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:
an=[0 for i in range(12)]
for i in range(1,12):
    a=0
    x=i
    while x:
        a+=1
        x%=bin(x).count('1')
    an[i]=a
n=int(input())
num=int(input(),2)
for i in range(1,n+1):
    nn=num^(1<<(n-i))
    nn%=bin(nn).count('1')
    print(an[nn]+1)

Submission status: Runtime Error

Solution code:
#

import sys
input=sys.stdin.readline

def main():
    N=int(input())
    X=input().strip("\n")[::-1]
    cnt=[0]*N
    for i in range(1,N):
        n=i
        while(n>0):
            pc=0
            for j in range(22):
                if (n>>j)&1==1:
                    pc+=1
            n%=pc
            cnt[i]+=1
    pc=X.count("1")
    t=0
    for i in range(N):
        if X[i]=="1":
            t+=2**i
    X=t
    for i in range(N-1,-1,-1):
        if (X>>i)&1==1:
            x=X-2**i
            pci=pc-1
            print(cnt[x%pci]+1)
        else:
            x=X+2**i
            pci=pc+1
            print(cnt[x%pci]+1)
        
    
    
    
if __name__=="__main__":
    main()

Submission status: Runtime Error

Solution code:
# import time


n = int(input())
x = input()
# kaishi = time.time()
num = int(x, 2)


def popcnt(n):
    c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333)
    c = (c & 0x0F0F0F0F0F0F0F0F) + ((c >> 4) & 0x0F0F0F0F0F0F0F0F)
    c = (c & 0x00FF00FF00FF00FF) + ((c >> 8) & 0x00FF00FF00FF00FF)
    c = (c & 0x0000FFFF0000FFFF) + ((c >> 16) & 0x0000FFFF0000FFFF)
    c = (c & 0x00000000FFFFFFFF) + ((c >> 32) & 0x00000000FFFFFFFF)
    return c


# aは1の数
def calc(a):
    cnt = 0
    while a > 0:
        # print(a)
        temp = popcnt(a)
        a = a % temp
        cnt += 1
    return cnt


ans = [0] * n
for i in range(n):
    t = 1 << (n - 1 - i)
    # print(num ^ t, bin(num ^ t))
    ans[i] = calc(num ^ t)
print(*ans, sep="\n")

# owari = time.time()
# print(owari - kaishi, "sec")

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)

ans = []
for i in range(N):
    ans.append(f(X ^ (1 << i)))

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

Submission status: Runtime Error

Solution code:
N=int(input())
X=input()
def fx(n):
    t=bin(n).count("1")
    b=n%t
    if b==0:
        return 1
    if b==1 or b==2:
        return 2
    return fx(b)+1
c=X.count("1")
n=int(X,2)
for i in range(N):
    if X[i]=="0":
        print(fx(n+2**(N-i-1)))
    else:
        print(fx(n-2**(N-i-1)))

Submission status: Runtime Error

Solution code:
def func(N):
    return N%bin(N).count("1")

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

popcount = X.count("1")
X_num = int(X,2)
bi = 2**(N-1)


for i in range(N):
    if(X[i] == "0"):
        hoge = X_num+bi
        I_count = popcount + 1
    else:
        hoge = X_num-bi
        I_count = popcount - 1
    count = 1
    hoge = hoge%I_count
    while hoge != 0:
        hoge = func(hoge)
        count += 1
    print(count)
    bi >>= 1

Submission status: Runtime Error

Solution code:
def f(x):
    mod = x.count('1')
    n = int(x, 2)
    return format(n%mod, 'b')

N = int(input())
X = input()
# print(X)
for i in range(N):
    if i==0:
        x = str(1-int(X[i])) + X[i+1:]
    elif i==N-1:
        x = X[:i] + str(1-int(X[i]))
    else:
        x = X[:i] + str(1-int(X[i])) + X[i+1:]
    ans = 0
    while x!='0':
        x = f(x)
        ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
def numberOfSetBits(i):
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24

def D():
    N = int(input())
    X = input()
    for i in range(len(X)):
        temp = int(X[:i]+('1' if X[i] == '0' else '0')+X[i+1:], 2)
        count = 0
        while temp > 0:
            # print(temp)
            temp %= numberOfSetBits(temp)
            count += 1
        print(count)
            
D()

Submission status: Runtime Error

Solution code:
from collections import defaultdict

d = defaultdict(int)

def f(x):
    if x % (bin(x).count('1')) == 0:
        d[x] = 1
        return 1

    if d[x]:
        return d[x]
    
    d[x] = f(x % (bin(x).count('1'))) + 1

    return d[x]


def main():
    N = int(input())
    X = input()
    O = int(X, 2)
    Y = list(X)
    for i in range(N):
        tmp = 0
        if Y[i] == '1':
            tmp = O - 2 ** (N - 1 - i)
        else:
            tmp = O + 2 ** (N - 1 - i)
        print(f(tmp))




if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
import random
from collections import deque
from decimal import *
import queue

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	X = inputStr()
	X_lin = list(X)

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

		oct = int(tmpX, 2)

		ans_tmp = 0
		while True:
			if oct == 0:
				break
			tmp = popcnt3(oct)
			oct = oct % tmp
			ans_tmp += 1
		ans.append(ans_tmp)

	for i in ans:
		print(i)

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

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
arr=[0,1,1,2]
n=4*(10**5)+2
for i in range(4,n):
    b=bin(i)[2:]
    k=b.count('1')
    arr.append(arr[i%k]+1)
n=int(input())
z=input()
kk=int(z,2)
d=[1]
for i in range(39):
    d.append(d[-1]*2)
for i in range(n):
    if z[i]=='0':
        print(arr[kk+d[n-1-i]])
    else:
        print(arr[kk-d[n-1-i]])

Submission status: Runtime Error

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

data=[0]*N
for i in range(1,N):
    temp=0
    for j in range(20):
        temp+=(i>>j &1)
    next=i%temp
    data[i]=data[next]+1

base=sum(int(X[i]) for i in range(N))

basedown=0
baseup=0
for i in range(N):
    basedown=(basedown*2)%(base-1)
    baseup=(baseup*2)%(base+1)
    basedown=(basedown+int(X[i]))%(base-1)
    baseup=(baseup+int(X[i]))%(base+1)

for i in range(N):
    if X[i]=="1":
        temp=(basedown-pow(2,N-1-i,base-1))%(base-1)
        print(1+data[temp])
    else:
        temp=(baseup+pow(2,N-1-i,base+1))%(base+1)
        print(1+data[temp])

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

n=II()
s=SI()
p=s.count("1")
p0=p-1
p1=p+1
pw0=[]
pw1=[]
two0=two1=1
for _ in range(n):
    pw0.append(two0)
    pw1.append(two1)
    two0=two0*2%p0
    two1=two1*2%p1

t0=0
t1=0
for i,c in enumerate(s[::-1]):
    if c=="1":
        t0=(t0+pw0[i])%p0
        t1=(t1+pw1[i])%p1

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

dp0=[-1]*n
def f0(x):
    if x==0:return 0
    if dp0[x]==-1:dp0[x]=f0(x%popcnt(x))+1
    return dp0[x]

ans=[]
for i,c in enumerate(s[::-1]):
    if c=="1":
        cur=(t0-pw0[i])%p0
    else:
        cur=(t1+pw1[i])%p1
    ans.append(f0(cur)+1)

for a in ans[::-1]:print(a)

Submission status: Runtime Error

Solution code:
from functools import lru_cache
N = int(input())
S = input()
X = int(S, 2)

P = S.count('1')
if P == 0:
    for i in range(N):
        print(1)
    exit()

Rp = X % (P+1)
Rn = X % (P-1)

@lru_cache(None)
def popcnt(x):
    return bin(x).count('1')

for i in range(N):
    if S[i] == '1':
        if P == 1:
            print(0)
            continue
        p = P-1
        x = (Rn - pow(2, N-1-i, p)) % p
    else:
        p = P+1
        x = (Rp + pow(2, N-1-i, p)) % p

    cnt = 1
    while x:
        x %= popcnt(x)
        cnt += 1
    print(cnt)

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
X = X[::-1]

def count(n):
    if n==0:
        return 0
    m = 0
    for i in range(18):
        if n&2**i:
            m += 1
    n %= m
    return 1+count(n)



p1 = [1]*(N+1)
p2 = [1]*(N+1)
m = 0
for i in range(N):
    if X[i]=='1':
        m += 1
for n in range(N):
    p1[n+1] = 2*p1[n]%(m+1)
    p2[n+1] = 2*p2[n]%(m-1)

num = [0]*N
base1 = 0
base2 = 0
for i in range(N):
    if X[i]=='1':
        base1 += p1[i]
        base2 += p2[i]

for i in range(N):
    if X[i]=='0':
        num[i] = (base1+p1[i])%(m+1)
    else:
        num[i] = (base2-p2[i])%(m-1)

ans = [1]*N

for i in range(N-1,-1,-1):
    ans[i] += count(num[i])
    print(ans[i])