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:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in R(V)]
    FromStdin=True if ls==None else False
    for i in R(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

ans=0

def f(x):
    c=0
    while x>0:
        c+=1
        y=bin(x).count('1')
        x%=y
    return c

def f_init(x):
    rt=[0]*3
    p=x.count('1')
    N=len(x)
    for i in range(N):
        if x[i]=='1':
            for j in [-1,0,1]:
                rt[j]+=b[j][N-1-i]
                rt[j]%=p+j
#    show('init',x,rt,1+a[rt[0]])
    ans=[0]*3
    for j in [-1,0,1]:
        ans[j]=1+f(rt[j])
    return rt,ans
    


n=I()
s=S_()

N=2*10**5+10
a=[0]*(N+1)
p=s.count('1')


if p==1:
    a=[0]*10**10
    
for i in rep(N):
    a[i]=f(i)

t=1
t_p=1
t_m=1
p_p=p+1
p_m=p-1

f_x=0
f_p=0
f_m=0
for i in rep(n)[::-1]:
    if s[i]=='1':
        f_x+=t%p
        f_p+=t_p%p_p
        f_m+=t_m%p_m
    t*=2
    t_p*=2
    t_m*=2
    t%=p
    t_p%=p_p
    t_m%=p_m

t_p=1
t_m=1
ans=[]
for i in rep(n)[::-1]:
    if s[i]=='1':
        nx=f_m-t_m%p_m
        nx%=p_m
    if s[i]=='0':
        nx=f_p+t_p%p_p
        nx%=p_p
    ans+=a[nx]+1,

    t*=2
    t_p*=2
    t_m*=2
    t%=p
    t_p%=p_p
    t_m%=p_m


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

Submission status: Runtime Error

Solution code:
import numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    N = int(input())
    X = int(input(), 2)

    p = np.zeros((2**N), dtype='int32')
    def popcount(n):
        if n <= 0:
            return 0
        if p[n] > 0:
            return p[n]
        temp = n
        while temp > 0:
            if temp & 1 == 1:
                p[n] += 1
            temp = temp >> 1
        return p[n]
    ff = np.zeros((2**N), dtype='int32')
    def f(n):
        if n <= 0:
            return 0
        if ff[n] > 0:
            return ff[n]
        temp = n
        while temp > 0:
            pop = popcount(temp)
            temp %= pop
            ff[n] += 1
        return ff[n]

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

main()

Submission status: Runtime Error

Solution code:
MOD = 10 ** 9 + 7

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

lst = [-1] * (N + 10)
lst[0] = 0
lst[1] = 1

def calc(x):
    if lst[x] != -1:
        return lst[x]
    count = 0
    y = x
    while y:
        if y % 2 == 1:
            count += 1
        y //= 2
    lst[x] = calc(x % count) + 1
    return lst[x]



count = X.count('1') #1の数
# print (count)
total = 0
for i in range(N):
    if X[N - 1 - i] == '1':
        total += pow(2, i, MOD)
        total %= MOD
# print ('total', total)

for i in range(N):
    if X[i] == '1':
        tmp_total = (total - pow(2, N - 1 - i, MOD)) % MOD
        amari = tmp_total % (count - 1)
        ans = calc(amari) + 1
        print (ans)
    else: # 0の時
        tmp_total = (total + pow(2, N - 1 - i, MOD)) % MOD
        amari = tmp_total % (count + 1)
        ans = calc(amari) + 1
        print (ans)

Submission status: Runtime Error

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

def calc(a):
    cnt = 0
    while True:
        cnt += 1
        bitstr = format(a,'b')
        bitnum = bitstr.count('1')
        a = a % bitnum
        if a == 0:
            break
    return cnt

for i in range(N):
    mask = bin(2**(N-1-i))
    ask = X^(int(mask,2))
    print(calc(ask))

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
  
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)
  c+=1
  if next <= maint and ans[next]!=-1:
    return ans[next]+c
  if next == 0:
    return c
  else:
    return func(next, c)
  

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:
import sys
sys.setrecursionlimit(100000000)

n = int(input())
x = input()

c1 = x.count('1')
cc1 = int('0b' + x, 0) % (c1 - 1)
cc2 = int('0b' + x, 0) % (c1 + 1)

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

for i in range(n):
    if x[i] == '1':
        print(f((-pow(2, n-i-1, c1-1) + cc1) % (c1 - 1)) + 1)
    else:
        print(f((pow(2, n-i-1, c1+1) + cc2) % (c1 + 1)) + 1)

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)
    for k in range(s):
        y = (B(s,2)).count('1')
        s = s % y
        a += 1
        if s == 0:
            break
    print(a)

Submission status: Runtime Error

Solution code:
from collections import Counter

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

x = Counter(X)
cnt = x["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:
N = int(input())
X = input()
Xint = int(X, 2)

def popcount(n):
  bin_n = bin(n)
  return sum(map(int, bin_n[2:]))

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

base = f(Xint)
for i in range(len(X)-1,-1, -1):
  xi = Xint ^ (1 << i)
  print(f(xi))

Submission status: Runtime Error

Solution code:
from numba import jit

@jit
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


n=int(input())
x=int(input(),2)
A=[]
for i in range(n):
    num=x^(2**i)
    cnt=0
    while num!=0:
        num %=popcount(num)
        cnt +=1
    A.append(cnt)

for i in A[::-1]:
    print(i)

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
# Python3 implementation of the approach 

# Function to return the value of (str % k) 
def getMod(_str, n, k) : 

	# pwrTwo[i] will store ((2^i) % k) 
	pwrTwo = [0] * n 
	pwrTwo[0] = 1 % k 
	for i in range(1, n): 
		pwrTwo[i] = pwrTwo[i - 1] * (2 % k) 
		pwrTwo[i] %= k 

	# To store the result 
	res = 0
	i = 0
	j = n - 1
	while (i < n) : 

		# If current bit is 1 
		if (_str[j] == '1') : 

			# Add the current power of 2 
			res += (pwrTwo[i]) 
			res %= k 
			
		i += 1
		j -= 1

	return res 


bc = 0
for b in X:
    if b == '1':
        bc += 1

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

    if X[i] == '0':
        t = "".join(X[:i]) + '1' + "".join(X[i+1:])
        k = bc + 1
    else:
        t = "".join(X[:i]) + '0' + "".join(X[i+1:])
        k = bc-1

    # print("i:", i)
    # print("orig:", X)
    # print("chng:", t)
    
    m = getMod(t, N, k)
    cnt = 1

    while m != 0:
        t = popcount(m)
        m = m%t
        cnt += 1

    ans.append(cnt)

for a in ans:
    print(a)

Submission status: Runtime Error

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

def ten(s):
    n = 0
    p = 0
    for i in range(N)[::-1]:
        n += (int(s[i]) * 2**p)
        p += 1
    return n

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

for i in range(N):
    n = (1 << N-1-i) ^ ten(X)
    ans = 1
    t = popcount(n)
    while n % t != 0:
        n = n % t
        t = popcount(n)
        ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
# https://qiita.com/zawawahoge/items/8bbd4c2319e7f7746266
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

N = int(input())
X = input()
N_max = 2*(10**5)
table = [0] * (N_max + 1)
arrive = [False] * (N_max + 1) 
for i in range(1, N_max + 1):
    x = i
    flag = False
    cnt = 0
    arrive[i] = True
    while flag == False:
        x = x % popcount(x)
        cnt += 1
        if x == 0:
            table[i] = cnt
            flag = True
        elif arrive[x]:
            cnt += table[x]
            table[i] = cnt
            flag = True

for i in range(N):
    if X[i] == '0':
        tmp = '1'
    else:
        tmp = '0'
    tmp_X = X[0:i] + tmp + X[i+1::]
    x = int(tmp_X, 2)
    x = x % popcount(x)
    if x == 0:
        print(1)
    else:
        print(1 + table[x])

Submission status: Runtime Error

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


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



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:
n = int(input())
X = list(input())

def count_ones_by_shift(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
    
cnt_l = [2] * 2 * 10 ** 5

l = list(range(1, 2*10**5))

l_1 = [i%count_ones_by_shift(i) for i in l]
l_2 = []

for i,x in enumerate(l_1):
    if x != 0:
        cnt_l[i] += 1
        l_2.append(x%count_ones_by_shift(x))
    
    else:
        l_2.append(0)

for i,x in enumerate(l_2):
    if x == 1:
        cnt_l[i] += 1
    
    if x == 2:
        cnt_l[i] += 1
    
    if x == 3:
        cnt_l[i] += 2




base = int(''.join(X), 2)
base_c = X.count('1')

for i,x  in enumerate(X):
    cnt = 0
    if x == '1':
        a = base - (2**(n-i-1))
        b = base_c - 1
        c = a%b
        
        if c == 0:
            print(1)
        
        else:
            print(cnt_l[c-1])
        
            
    
    else:
        a = base + (2**(n-i-1))
        b = base_c + 1
        c = a%b
        
        if c == 0:
            print(1)
        
        else:
            print(cnt_l[c-1])

Submission status: Runtime Error

Solution code:
n = int(input())
x = str(input()")
x_int = np.array(list(map(int, x)))[::-1].dot(np.power(np.ones(n)*2, np.arange(n)))
for i in range(n):
    z_int = int(x_int + 2**(n-1-i)) if x[i] == "0" else int(x_int - 2**(n-1-i))
    print(calc_i(z_int, 0))

Submission status: Runtime Error

Solution code:
n=int(input())
popn=[0 for i in range(n+1)]
for i in range(1,n+1):
  popn[i]=i%bin(i).count("1")
#print(popn)
ans=[0 for i in range(n)]
x=int(input(),2)
num=bin(x).count("1")
for i in range(n):
  if (x>>n-i-1)&1==0:
    popc=num+1
  else:
    popc=num-1
  y=x^(1<<(n-i-1))
  #print(i,y,popc)
  cnt=1
  y=y%popc
  #print(i,y)
  flag=True
  if y==0:
    flag=False
  while flag:
    if popn[y]==0:
      flag=False
      cnt+=1
    else:
      y=popn[y]
      cnt+=1
  ans[i]=cnt
for i in ans:
  print(i)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(2000)

def input_int():
    return map(int, input().split())

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

N=one_int()
S=one_str()

bit_count = S.count("1")

bit_count

#bit数
calc_dict = {i:-1 for i in range(22)}

def mods(N, m, count):
    temp = N%m
    if temp==0:
        return count+1
    
    if calc_dict[temp]==-1:
        calc_dict[temp] = bin(temp).count("1")

    return mods(temp, calc_dict[temp], count+1)

bit_count = S.count("1")
for i in range(len(S)):
    if S[i]=="0":

        bit_count+=1
        num = int(S,2) + 2**(N-i-1)
        print(mods(num, bit_count, 0))
        bit_count-=1
    else:

        bit_count-=1
        num = int(S,2) - 2**(N-i-1)
        print(mods(num, bit_count, 0))
        bit_count+=1

Submission status: Runtime Error

Solution code:
from sys import stdin
from collections import deque, defaultdict
input = stdin.readline

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

q = deque([])
b = X.count("1")
d = defaultdict(int)

for i in range(N):
    if X[i] == "0":
        X[i] = "1"
        q.append(["".join(X), b + 1])
        X[i] = "0"
    else:
        X[i] = "0"
        q.append(["".join(X), b - 1])
        X[i] = "1"

while q:
    n, b = q.popleft()
    n = int(n, 2)
    cnt = 0
    sn, sb = n, b

    if (n, b) in d:
        print(d[(n, b)])
        continue
    else:
        if b == 1 or n % b == 0:
            cnt = 1
            print(cnt)
            continue

        while n > 0:
            if (n, b) in d:
                cnt += d[(n, b)]
                break
            n = n % b
            b = bin(n).count("1")
            cnt += 1

        d[(sn, sb)] = cnt
        print(cnt)

Submission status: Runtime Error

Solution code:
n = 100000
ans_count = [-1 for _ in range(n)]

for i in range(1,n+1):
    b = bin(i)
    b=list(b)
    a = b.count("1")
    f = i%a
    if f == 0:
        ans_count[i-1]=1
    else:
        ans_count[i-1] = ans_count[f-1]+1

ans_count = [0]+ ans_count

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

org = int(inp, 2)
if "1" in x:      
    l = x.count("1")
else:
    l = 0


# for _ in range(n):
#     print(0)

for i in range(n):
    a = x[i]
    if a=="0":
        N = org+(2**(n-i-1))
        m= N%(l+1)
        print(ans_count[m]+1)
    else:
        N = org-(2**(n-i-1))
        m=N%(l-1)
        print(ans_count[m]+1)

Submission status: Runtime Error

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


def calc(i, count):
    r = i % bin(i).count("1")
    if r != 0:
        return calc(r, count + 1)
    else:
        return count + 1


for i in range(1, N + 1):
    a = X ^ int((bin(1 << ((N - 1) - (i - 1)))), 2)
    b = calc(a, 0)
    print(b)

Submission status: Runtime Error

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

pop = []
num = X.count("1")
n = int("".join(map(str, X)), 2)


def f(n):
    count = 0
    while n != 0:
        a = str(bin(n))
        n %= a.count("1")
        count += 1
    return count


for i in range(num+1):
    ans = f(i)
    pop.append(ans)

for i in range(N):
    if X[i] == "1":
        a = n-2**(N-1-i)
        if a < num-1:
            print(pop[n])
        else:
            a %= num-1
            print(pop[a]+1)
    if X[i] == "0":
        a = n+2**(N-1-i)
        if a < num+1:
            print(pop[n])
        else:
            a %= num+1
            print(pop[a]+1)

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 = list(input())
one = X.count('1')
L1 = [1]
L2 = [1]

for _ in range(N-1):
    if one == 0:
        L1.append(0)
    else:
        L1.append((L1[-1] * 2) % (one - 1))
    L2.append((L2[-1] * 2) % (one + 1))

x1 = 0
x2 = 0
power1 = 1
power2 = 1

for i in range(N):
    if X[N-i-1] == '1':
        if one - 1 != 0:
            x1 += power1
        x2 += power2
    power1 *= 2
    power2 *= 2
    if one - 1 != 0:
        power1 %= one - 1
    power2 %= one + 1

def solve(X, cnt):
    if X == 0:
        return cnt
    
    X %= bin(X).count('1')
    return solve(X, cnt+1)

for i in range(N):
    if X[i] == '0':
        tmp = (x2 + L2[N-i-1]) % (one + 1)
        ans = solve(tmp, 0) + 1
    else:
        if one - 1 == 0:
            ans = 0
        else:
            tmp = (x1 - L1[N-i-1]) % (one - 1)
            ans = solve(tmp, 0) + 1
    print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
x=input()
num=0
n=0
ans=[]
pop=[-1]*(2**(N+1))
def twice(a):
    if pop[a]!=-1:
        an=pop[a]
        return an
    num=a
    pop[num]=a
    b=0
    while a>0:
        b+=a%2
        a=a//2
    pop[num]=pop[num]%b
    return pop[num]
for i in range(N):
    num+=2**(N-1-i)*int(x[i])
    if x[i]=="1":
        n+=1
for i in range(N):
    Ans=0
    if x[i]=="0":
        Num=1+n
        A=2**(N-i-1)+num
        if Num==0:
            Ans=0
        else:
            a=A%Num
            Ans+=1
            while a>0:
                a=twice(a)
                Ans+=1
    else:
        Num=n-1
        A=num-2**(N-i-1)
        if Num==0:
            Ans=0
        else:
            a=A%Num
            Ans+=1
            while a>0:
                a=twice(a)
                Ans+=1
    ans.append(Ans)
for i in range(N):
    print(ans[i])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000000)

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):
    ttt = xx & pow(2, n - i - 1)
    if ttt > 0:
        t = xx - pow(2, n - i - 1)
        point = count_1 - 1
    else:
        t = xx + pow(2, n - i - 1)
        point = count_1 + 1
    ans = 1
    t = (t % point)
    print(ans + value[t])

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):
  X = rev(X, i)
    
  fn = copy.deepcopy(X)
  cnt = 0
  
  while fn != 0:
    fn = fn % popcount(fn)
    cnt += 1
  print(cnt)
  
  X = rev(X, i)

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)

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

from functools import lru_cache


bit = {}
@lru_cache(maxsize=None)
def popcount2(bits):
    if bits in bit:
        return bit[bits]
    ori_bit = bits
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555)
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333)
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f)
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff)
    ans = (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff)
    bit[ori_bit] = ans
    return ans


memo = {0: 0}
@lru_cache(maxsize=None)
def rec(n):
    if n in memo:
        return memo[n]
    
    p = popcount2(n)
    new_n = n % p
    ans = rec(new_n) + 1
    memo[n] = ans
    return memo[n]


def submit():
    n = int(input())
    xs = input()
    x = int('0b' + xs, 0)

    # 前準備
    for i in range(1, 200001):
        rec(i)

    base_bit = 0
    for c in xs:
        if c == "1":
            base_bit += 1
    bit[x] = base_bit
    mask = 1 << (n - 1)
    for i in range(1, n + 1):
        if xs[i - 1] == "0":
            xi = x + mask
            bit[xi] = bit[x] + 1
        else:
            xi = x - mask
            bit[xi] = bit[x] - 1
        new_n = xi % bit[xi]
        print(memo[new_n] + 1)
        mask >>= 1


if __name__ == "__main__":
    submit()

Submission status: Runtime Error

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

def count_ones_by_bin(num):
    bin_num = bin(num)[2:]
    count = 0
    for i in bin_num:
            count += int(i)
    return count

def waru(nn):
    one_count = count_ones_by_bin(nn)
    if nn % one_count == 0:
        return -1
    return nn % one_count

for i in range(1, n+1):
    x_copy = copy.copy(x)
    if x_copy[i-1] == '0':
        x_copy[i-1] = '1'
    else:
        x_copy[i-1] = '0'
    str_x = "".join(x_copy)
    num_x = int(str_x,2)
    result_count = 0
    while True:
        if num_x == -1:
            break
        result_count += 1
        num_x = waru(num_x)
    print(result_count)

Submission status: Runtime Error

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

def f(x):
    ans = 0
    m = 1
    
    while True:
        if m == 0:
            return ans

        m = int(x, 2) % popcount(x)
        x = bin(m)
        ans += 1

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

for i in range(n):
    x_c = x.copy()
    if x_c[i] == "0":
        x_c[i] = "1"
    else:
        x_c[i] = "0"

    ans = f("".join(x_c))
    print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
# = str(input())
# = map(int, input().split())
X = str(input())
Xlist = np.array(list(map(int, X)))
total = int(X, 2)
# = [int(input()) for i in range(N)]
# = [list(map(int, input().split())) for i in range(N)]
one = np.sum(Xlist)

for i in range(N):
    count = 0
    joe = N-1-i
    check = int(total)
    if Xlist[i] == 1:
        div = one -1
        next = (check%div - (2**joe)%div)%div
        if next == 0:
            count += 1
            print(count)
        else:
            count += 1
            check = next
            while check > 0:
                b = bin(next)
                clist = list(map(int, b[2:]))
                clist = np.array(clist)
                div = np.sum(clist)
                next = check%div
                if next == 0:
                    count += 1
                    print(count)
                    break
                else:
                    count += 1
                    check = next

    else:
        div = one +1
        next = (total%div + (2**joe)%div)%div
        if next == 0:
            count += 1
            print(count)
        else:
            count += 1
            check = next
            while check > 0:
                b = bin(next)
                clist = list(map(int, b[2:]))
                clist = np.array(clist)
                div = np.sum(clist)
                next = check%div
                if next == 0:
                    count += 1
                    print(count)
                    break
                else:
                    count += 1
                    check = next

Submission status: Runtime Error

Solution code:
N = int(input())
X = input().strip()
C = X.count("1")
D = int(X, 2)

p = [0]*(2*10**5+2)
for i in range(1, len(p)):
    n = i
    while True:
        b = bin(n).count("1")
        if b <= 0:
            break
        n = n % b
        p[i] += 1

for i in range(1, N+1):
    d = D
    c = C
    if X[i-1] == "1":
        c -= 1
        d -= 1 << (N-i)
    else:
        c += 1
        d += 1 << (N-i)

    d = d % c
    print(p[d]+1)

Submission status: Runtime Error

Solution code:

def fastExpMod(b, e):
    result = 1
    while e != 0:
        if (e&1) == 1:
            # ei = 1, then mul
            result = (result * b)
        e >>= 1
        # b, b^2, b^4, b^8, ... , b^(2^n)
        b = (b*b)
    return result



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

cnt = 0
for i in range(len(s)):
    if(s[i]=='1'):
        cnt+=1

number = 0
now =len(s)
for i in range(len(s)):
    if(s[i]=='1'):
        number+=fastExpMod(2,now-1)
    now-=1
#print(number)
for i in range(n):
    #$print(str(n)+" "+str(i))
    ss = s
    cal = number
    ccnt = cnt
    if(s[i]=='0'):
        cal+=fastExpMod(2,n-i-1)
        ccnt+=1
    else:
        cal-=fastExpMod(2,n-i-1)
        ccnt-=1
    x = cal%ccnt
    #print(str(cal)+" "+str(ccnt))
    if(x==0):
        print(1)
    elif x%2==0:
        print(2)
    elif x==1:
        print(2)
    else:
        print(3)

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
sum = x.count('1')
for i in range(n):
    if x[i]=='1':
        sum0=sum-1
        cnt=1
        str = x[:i]+'0'+x[(i+1):]
        p = int(str,2)%sum0
        while p:
            sum0 = bin(p).count('1')
            p = p%sum0
            cnt+=1
    else:
        sum0=sum+1
        cnt=1
        str = x[:i]+'1'+x[(i+1):]
        p = int(str,2)%sum0
        while p:
            sum0 = bin(p).count('1')
            p = p%sum0
            cnt+=1
    print(cnt)