Problem:


Score : 400 points

Problem Statement

Let \mathrm{popcount}(n) be the number of 1s in the binary representation of n.
For example, \mathrm{popcount}(3) = 2, \mathrm{popcount}(7) = 3, and \mathrm{popcount}(0) = 0.

Let f(n) be the number of times the following operation will be done when we repeat it until n becomes 0: "replace n with the remainder when n is divided by \mathrm{popcount}(n)." (It can be proved that, under the constraints of this problem, n always becomes 0 after a finite number of operations.)

For example, when n=7, it becomes 0 after two operations, as follows:

\mathrm{popcount}(7)=3, so we divide 7 by 3 and replace it with the remainder, 1.

\mathrm{popcount}(1)=1, so we divide 1 by 1 and replace it with the remainder, 0.

You are given an integer X with N digits in binary.
For each integer i such that 1 \leq i \leq N, let X_i be what X becomes when the i-th bit from the top is inverted.
Find f(X_1), f(X_2), \ldots, f(X_N).

Constraints

1 \leq N \leq 2 \times 10^5

X is an integer with N digits in binary, possibly with leading zeros.

Input

Input is given from Standard Input in the following format:

N
X

Output

Print N lines. The i-th line should contain the value f(X_i).

Sample Input 1

3
011

Sample Output 1

2
1
1

X_1 = 7, which will change as follows: 7 \rightarrow 1 \rightarrow 0. Thus, f(7) = 2.

X_2 = 1, which will change as follows: 1 \rightarrow 0. Thus, f(1) = 1.

X_3 = 2, which will change as follows: 2 \rightarrow 0. Thus, f(2) = 1.

Sample Input 2

23
00110111001011011001110

Sample Output 2

2
1
2
2
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
3



Sample input:
3
011


Sample output:
2
1
1

Submission status: Runtime Error

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

p = [0]*(N+1)
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 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 ans[next]!=-1:
    return ans[next]+c
  if next == 0:
    return c
  else:
    return func(next, c)
  
ma = "1"*10
maint = int(ma, 2)+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)
  #print(itemp)
  if itemp<=maint:
    print(ans[itemp])
  else:
    print(func(itemp, 0))

Submission status: Runtime Error

Solution code:
def popcount(n):
    bin_num = bin(n)[2:]
    count1 = 0
    for i in bin_num:
            count1 += int(i)

  #  print("count1")
  #  print(count1)
    return count1

def f(n):
    count=0
   # print("n")
   # print(n)

    while(1):
        n=n%popcount(n)
        count=count+1
        if n==0:
            break

    #print("count")
    #print(count)
    return count


if __name__=="__main__":
    N = int(input())
    X=(input())

    for i in range(N):
        if X[i]=="0":
            s=list(X)
            s[i:i+1]="1"
            ss=",".join(s)
#            print(int(ss.replace(",", ""),2))

            print(f(int(ss.replace(",",""),2)))
        else:
            s=list(X)
            s[i:i+1]="0"
            ss=",".join(s)
            print(f(int(ss.replace(",",""),2)))

Submission status: Runtime Error

Solution code:
from itertools import product
from math import log2

N = int(input())
X = input()
f = [0]*(N+1)
m = sum(list(map(int, X)))+1
n = int(log2(m)+1)

i = 0
for p in product([0,1], repeat=n):
    if i>0:
        a = sum(p)
        f[i] = f[i%a]+1
    i += 1

for i in range(N):
    if X[i] == '1':
        x = int(X[0:i]+'0'+X[i+1:], 2)
        a = m-2
    else:
        x = int(X[0:i]+'1'+X[i+1:], 2)
        a = m
    print(f[x%a]+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)

b=[[1]*(n+1) for i in rep(3)]

p=s.count('1')


for i in rep(N):
    #print(x,f(x),bin(x)[2:])
    a[i]=f(i)
    if i<n:
        for j in [-1,0,1]:
            b[j][i+1]=(2*b[j][i])%(p+j)

rem,fx=f_init(s)
#show(rem,fx)

for i in rep(n):
    if s[i]=='0':
        j=1
    else:
        j=-1
        #R=rem[0]+b[1][N-1-i]
    t=(rem[j]+b[j][n-1-i])%(p+j)
    ans=a[t]+1 if t!=0 else 1
    #print(ans,'|',t,a[(rem[j]+b[j][N-1-i])%(p+j)],(rem[j]+b[j][N-1-i]),(p+j),'|',(rem[j],b[j][N-1-i],p+j),N,N-1-i)
    if s[i]=='1' and False:
        #R=rem[-1]+b[-1][N-1-i]
        ans=a[(rem[-1]+b[-1][n-1-i])%(p-1)]
    print(ans)

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

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

for i in range(N):
  if X[i] == '0':
    X[i] = '1'
  else:
    X[i] = '0'
  print(popcount(bin(int(X))))
  if X[i] == '0':
    X[i] = '1'
  else:
    X[i] = '0'

Submission status: Runtime Error

Solution code:
def toggleKthBit(n, k): 
  return (n ^ (1 << (k-1))) 


def bitsoncount(i):
    assert 0 <= i < 0x10000000000
    i = i - ((i >> 1) & 0x5555555555)
    i = (i & 0x3333333333) + ((i >> 2) & 0x3333333333)
    return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24
N = int(input())
X = int(input())

ans = -1
dp = [-1] * 100000000
for i in range(N, 0, -1):
  count = 0
  ans = toggleKthBit((int(str(X), 2)), i)
  while ans != 0:
    if dp[ans] != -1:
      ans = ans % dp[ans]
    else:
      dp[ans] = bitsoncount(ans)
      ans = ans % dp[ans]
    count += 1
  print(count)

Submission status: Runtime Error

Solution code:
def popcount(u):
    t = bin(u)
    h = t.count("1")
    return u % h 
    
n = int(input())
x = list(input())
c = x.count("1") + 1
d = c - 2
amaric = [1 % c]
amarid = [1 % d]
for i in range(n-1):
    amaric.append((amaric[-1]*2)%c)
    amarid.append((amarid[-1]*2)%d)
pri = [-1 for i in range(2*(10**5) + 1)]
pri[0] = 0
for i in range(1,2*(10**5)+1):
    if pri[i] == -1:
        now =  popcount(i)
        pri[i] = pri[now] + 1

motoc = 0
motod = 0
for i in range(n):
    if x[i] == "1":
        motoc += amaric[n-1-i]
        motod += amarid[n-1-i]
for i in range(n):
    if x[i] == "0":
        op = motoc
        op += amaric[n-1-i]
        op %= c
    elif x[i] == "1":
        op = motod
        op -= amarid[n-1-i]
        op %= d
    print(pri[op]+1)

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
    else:
        t = "".join(X[:i]) + '0' + "".join(X[i+1:])
        k = bc-1
    
    m = getMod(t, N, k)
    cnt = 1

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

    ans.append(cnt)

print(*ans)

Submission status: Runtime Error

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

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

N = int(input())
A = list(map(int,input()))


for i in range(len(A)):
    P=0
    Z = A.copy()
    Z[i] ^= 1
    Z.reverse()
    for j in range(0,len(Z)):
        P += Z[j]*2**j 
    print(calc(P))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
def main():
    n = int(input())
    s = int(input(), 2)
    pc0 = bin(s).count("1")
    ans = []
    for i in range(n):
        k = 1 << (n - 1 - i)
        x = k ^ s
        if x >= s:
            pc0 += 1
        else:
            pc0 -= 1
        x %= pc0
        cnt = 1
        while x > 0:
            pc = bin(x).count("1")
            x %= pc
            cnt += 1
        ans.append(cnt)
    print("\n".join(str(y) for y in ans))
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
ma = lambda :map(int,input().split())
ni = lambda:int(input())
import collections
import math
import itertools
gcd = math.gcd
n = ni()
x = input()
xr = x[::-1]
px = x.count("1")
def solve(t):
    ret = 1
    while t>0:
        p = bin(t).count("1")
        t %=p
        ret +=1
    return ret
x_tp = 0
x_tm = 0

for i in range(n):
    x_tp = (x_tp + int(xr[i])*pow(2,i,px+1) ) %(px+1) ## 0->1
if px>0:
    for i in range(n):
        x_tm = (x_tm + int(xr[i])*pow(2,i,px-1) ) %(px-1) # 1->0
ans = []
for i in range(n):
    if xr[i] =="0":
        x_tmp = (x_tp + pow(2,i,px+1) ) %(px+1)
    else:#1->0
        x_tmp = (x_tm - pow(2,i,px-1)) %(px-1)
    t = solve(x_tmp)
    ans.append(t)
for i in range(n-1,-1,-1):
    print(ans[i])

Submission status: Runtime Error

Solution code:
N=int(input())
X = input()
def popcount(string):
    cnt = 0
    for j in range(len(string)):
        if string[j] == "1":
            cnt += 1
    return cnt

for i in range(1,N+1):
    cnt = 0
    cnt_1 = 0
    sum = 0
    string = X
    #反転
    if string[i-1] =="1":
        string=string[:i-1]+ "0"+string[i:]
    else:
        string =string[:i-1]+ "1"+string[i:]
    #print(string)
    bin_num = int(string, 2)
    tmp = popcount(string)
    #print(bin_num,tmp)
    mod = 100
    while mod != 0:
        mod = int(bin_num) % tmp
        cnt+=1
        bin_num = "000000"+format(mod, 'b')
        tmp = popcount(bin_num)
    print(cnt)

Submission status: Runtime Error

Solution code:
x = str(input())
kosu1 = 0
kazu = 0
for i in range(n):
    kazu += 2 ** (n - i - 1) * int(x[i])
    if x[i] == '1':
        kosu1 += 1
if kosu1 ==1:
    kazup = kazu % (kosu1 + 1)
    magic17 = [0, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 2, 3, 1, 2]
    box = [0] * (kosu1 + 1)

    amarip = [1] * n
    amarim = [1] * n
    for i in range(1, n):
        amarip[i] = (amarip[i - 1] * 2) % (kosu1 + 1)
    for i in range(n):
        if x[i] == '1':
            print(0)
        else:
            a = (kazup + amarip[n - 1 - i]) % (kosu1 + 1)

            if a <= 18:
                print(magic17[a] + 1)
            else:
                num = 0
                for i in range(len(str(bin(a)) - 2)):
                    if str(bin(a))[-1 - i] == '1':
                        num += 1
                print(magic17[a % num] + 1)
else:
    kazup = kazu % (kosu1 + 1)
    kazum = kazu % (kosu1 - 1)
    magic17 = [0,1,1,2,1,2,1,2,1,2,1,2,1,2,2,3,1,2,1]
    box = [0] * (kosu1 +1)

    amarip = [1] * n
    amarim = [1] * n
    for i in range(1,n):
        amarip[i] = (amarip[i - 1]*2) % (kosu1 + 1)
        amarim[i] = (amarim[i - 1]*2) % (kosu1 - 1)
    for i in range(n):
        if x[i] == '1':
            a = (kazum - amarim[n-1-i]) % (kosu1 - 1)

            if a <= 18:
                print(magic17[a]+1)
            else:
                num = 0
                for i in range(len(str(bin(a))-2)):
                    if str(bin(a))[-1-i] == '1':
                        num += 1
                print(magic17[a % num] + 1)
        else:
            a = (kazup + amarip[n - 1 - i]) % (kosu1 + 1)
            if a <= 18:
                print(magic17[a] + 1)
            else:
                num = 0
                for i in range(len(str(bin(a)) - 2)):
                    if str(bin(a))[-1 - i] == '1':
                        num += 1
                print(magic17[a % num] + 1)

Submission status: Runtime Error

Solution code:
N = int(input())

dic = dict()
dic[0] = 0
for i in range(1, N+1):
    a = bin(i)
    cnt = 0
    for j in range(2, len(a)):
        if a[j] == '1':
            cnt += 1
    b = i%cnt
    if i not in dic:
        dic[i] = b

y = input()
x = 0
for j in range(N):
    if y[j] == '1':
        x += 1
X = int('0b' + y, 0)

res = 1 << N-1
for i in range(N):
    now = X ^ res
    nx = x
    if y[i] == '1':
        nx -= 1
    else:
        nx += 1
    #print(now, res)
        
    a = bin(now)
    #print(a)
    
    b = now%nx
    #print(now, nx, b)
    ans = 1
    while b > 0:
        b = dic[b]
        ans += 1
    print(ans)
    
    res = res >> 1

Submission status: Runtime Error

Solution code:
def toggleKthBit(n, k): 
  return (n ^ (1 << (k-1))) 


def bitsoncount(i):
    assert 0 <= i < 0x100000000
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24
N = int(input())
X = int(input())

ans = -1
dp = [-1] * 100000000
for i in range(N, 0, -1):
  count = 0
  ans = toggleKthBit((int(str(X), 2)), i)
  while ans != 0:
    if dp[ans] != -1:
      ans = ans % dp[ans]
    else:
      dp[ans] = bitsoncount(ans)
      ans = ans % dp[ans]
    count += 1
  print(count)

Submission status: Runtime Error

Solution code:
def mpower(a, b, n):
    if b == 0:
        return 1
    if b == 1:
        return a % n
    a1 = a
    k = 1
    while a1 < n and k < b:
        a1 = a1 * a
        k = k + 1

    a1 = a1 % n
    b1 = b // k
    a2 = a
    b2 = b % k
    return (mpower(a1, b1, n)*mpower(a2, b2, n)) % n


def main():
    n = int(input())
    x = input()
    k = int(x, 2)
    p = x.count("1")
    kp = [k % (p - 1), k % (p + 1)]
    f = [0] * (n + 1)
    for i in range(1, n + 1):
        f[i] = f[i % bin(i).count("1")] + 1
    for i in range(n):
        if x[i] == "1":
            if p - 1 == 0:
                print(0)
                continue
            print(f[(kp[0] - mpower(2, n - i - 1, pi)) % pi] + 1)
        else:
            pi = p + 1
            print(f[(kp[1] + mpower(2, n - i - 1, pi)) % pi] + 1)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def pop(a):
    b = a
    num = 0
    while b > 0:
        if b % 2 == 1:
            num += 1
        b = int(b/2)
    return int(num)


def function(N, X):
    X = [int(X[i]) for i in range(N)]
    for j in range(N):
        number = 0
        for i in range(N):
            if i == j:
                if X[i] == 0:
                    number += 2**(N-i-1)
            else:
                number += 2**(N-i-1)*X[i]
        ans = 1
        a = number % pop(number)
        while a > 0:
            a = a % (pop(a))
            ans += 1
        print(ans)


if __name__ == '__main__':
    N = int(input())
    X = str(input())
    function(N, X)

Submission status: Runtime Error

Solution code:
def getInts():
    return [ int(x) for x in input().split() ]

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

cache = {}
def divide(n):
    count = 0
    if n in cache:
        return cache[n]
    while True:
        count += 1
        intp = int(n, 2)
        intp = intp%popcount(n)
        if intp ==0:
            break
        n = "{0:b}".format(intp)
    cache[n] = count
    return count
    

def findX(X, i):
    s = list(X)
    if s[i]=='1':
        s[i]='0'
    else:
        s[i]='1'
    return "".join(s)
    

cache = {}
def f(x,y,z):
    if (x,y,z) in cache:
        return cache[(x,y,z)]
    
    v =  x**2+y**2+z**2+x*y+y*z+z*x
    cache[(x,y,z)] = v
    return v

[N] = getInts()
X = input()
for i in range(N):
    xi = findX(X, i)
    print(divide(xi))

Submission status: Runtime Error

Solution code:
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
X = str(input())
start_mod = X.count("1")
if start_mod == 1:
  for i in range(n):
    if X[i] == "1":
      key = 1
else: key = -1
# start_number = int(X,2)
def bin_to_int(n,binstr,mod):
  retval = 0
  for i in range(n-1,-1,-1):
    retval += (pow(2,n-1-i,mod) if binstr[i] == "1" else 0)
    retval %= mod
  return retval
start_number_plus = bin_to_int(n,X,start_mod+1)
start_number_minus = bin_to_int(n,X,start_mod-1)
# print(start_number_plus,start_number_minus,"debug")
for i in range(n):
  if i == key:print(0);continue
  if X[i] == "1":
    now_mod = start_mod - 1
    now_number = (start_number_minus - pow(2,n-1-i,now_mod))%now_mod
      
  else:
    now_mod = start_mod + 1
    now_number = (start_number_plus + pow(2,n-1-i,now_mod))%now_mod
  # print(i,now_number,now_mod,"debug")
  ci = 1
  while now_number != 0:
    # print(now_number,now_mod)
    now_mod = bin(now_number).count("1")
    now_number %= now_mod
    ci += 1
  print(ci)

Submission status: Runtime Error

Solution code:
N = int(input())
# = str(input())
# = map(int, input().split())
X = str(input())
Xlist = 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 = Xlist.count(1)

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:
                clist = list(bin(next))
                clist = clist[2:]
                div = clist.count("1")
                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:
                clist = list(bin(next))
                clist = clist[2:]
                div = clist.count("1")
                next = check%div
                if next == 0:
                    count += 1
                    print(count)
                    break
                else:
                    count += 1
                    check = next

Submission status: Runtime Error

Solution code:
from card3.void.stop_watch import stop_watch
import sys
input = sys.stdin.readline
@stop_watch
def main():
    n = int(input())
    s = int(input(), 2)
    pc0 = bin(s).count("1")
    ans = []
    for i in range(n):
        k = 1 << (n - 1 - i)
        x = k ^ s
        if x >= s:
            pc0 += 1
        else:
            pc0 -= 1
        x %= pc0
        cnt = 1
        while x > 0:
            pc = bin(x).count("1")
            x %= pc
            cnt += 1
        ans.append(cnt)
    print("\n".join(str(y) for y in ans))
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N=int(input())
Xl=list(map(int,list(input())))
#X=int(input())
#print(Xl)

def func(x):
  cnt=0
  while x>0:
    num1=0
    xcopy=x
    while xcopy:
      if xcopy&1:
        num1+=1
      xcopy>>=1
      
    #print(x,num1)
    x=x%num1
    cnt+=1
  return cnt

func_dic={}
for i in range(N):
  func_dic[i]=func(i)
#print(func_dic)

num1_X=Xl.count(1)
#print(num1_X)

mod_nminus=0
mod_nplus=0
for i in range(N):
  mod_nminus*=2
  mod_nplus*=2
  if Xl[i]==1:
    mod_nminus+=1
    mod_nplus+=1

  mod_nminus%=num1_X-1
  mod_nplus%=num1_X+1
#print(mod_nminus,mod_nplus)

answer_list=[]
modpow_plus=1
modpow_minus=1
for i in reversed(range(N)):
  if Xl[i]==0:
    mod=(mod_nplus+modpow_plus)%(num1_X+1)
    answer_list.append(func_dic[mod]+1)
  else:
    mod=(mod_nminus-modpow_minus)%(num1_X-1)
    answer_list.append(func_dic[mod]+1)
  
  modpow_plus*=2
  modpow_minus*=2
  modpow_plus%=num1_X+1
  modpow_minus%=num1_X-1
  
for i in reversed(range(N)):
  print(answer_list[i])

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 for x in range(2**N)]

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


X = int(input(), 2)

for i in range(N):

    Xi = X ^ (1 << (n-i))

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

    print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)

mod = 1000000007
inf = int(1e18)

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft


memo = {}

def countbit(x):
    i = 0
    cnt = 0
    while x >= 1<<i:
        if x & (1<<i):
            cnt += 1
        i += 1
    return cnt


def count(x, c):
    # if c == 0:
    #     return 0
    # s = 1
    # x = x % c
    s = 0
    while x != 0:
        s += 1
        x = x % countbit(x)
    return s

def main():
    n = int(input())
    xs = list(input())
    c = len([i for i in xs if i == '1'])
    # t = 21
    # x = int(xs[-t:], 2)
    for i in range(n):
        base = 1
        cc = c
        if xs[i] == '1':
            cc -= 1
        else:
            cc += 1
        xs[i] = '1' if xs[i] == '0' else '0'
        res = 0
        for j in range(n):
            if xs[-j-1] == '1':
                res += base
            base = base * 2 % cc
        count(int("".join(xs), 2), 0)
        s = count(res % cc, 0) + 1
        xs[i] = '1' if xs[i] == '0' else '0'
        print(s)


main()

Submission status: Runtime Error

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

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

a = X.count("1")
ap, am = a+1, a-1

Ap = []
Am = []
temp = 1

for i in range(N):
  if i == 0:
    Ap.append(temp%ap)
    Am.append(temp%am)
  else:
    temp *= 2
    Ap.append(temp%ap)
    Am.append(temp%am)

Aps = 0
Ams = 0

for i in range(N):
  if X[-1-i] == "1":
    Aps += Ap[i]
    Aps %= ap
    Ams += Am[i]
    Ams %= am

for i in range(N):
  cnt = 1
  if X[i] == "1":
    p = Ams - Am[-1-i]
    p %= am
  else:
    p = Aps + Ap[-1-i]
    p %= ap
  temp = p
  while temp > 0:
    temp %= popcount(temp)
    cnt += 1
  print(cnt)

Submission status: Runtime Error

Solution code:
def toggleKthBit(n, k): 
  return (n ^ (1 << (k-1))) 


def bitsoncount(i):
    assert 0 <= i < 0x100000000
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24
N = int(input())
X = int(input())

ans = -1
dp = [-1] * 10000000
for i in range(N, 0, -1):
  count = 0
  ans = toggleKthBit((int(str(X), 2)), i)
  while ans != 0:
    if dp[ans] != -1:
      ans = ans % dp[ans]
    else:
      dp[ans] = bitsoncount(ans)
      ans = ans % dp[ans]
    count += 1
  print(count)

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
for i in range(n):
    num = x[:i]
    if x[i] == '0':
        num += '1'
    else:
        num += '0'
    num += x[i + 1:]
    #print(num)
    ans = 0
    pop = num.count('1')
    num = int(num, 2) % pop
    num = bin(num)
    ans = 1
    #print(num)
    while int(num, 2) != 0:
        pop = num.count('1')
        num = int(num, 2) % pop
        num = bin(num)
        ans += 1
    print(ans)

Submission status: Runtime Error

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

val = 0
cnt = 0
for i in range(n - 1, -1, -1):
    x[i] = int(x[i])
    val += x[i] << (n - i - 1)
    cnt += x[i]

for i in range(n):
    if x[i] == 1:
        val -= 1 << (n - i - 1)
        cnt -= 1
    else:
        val += 1 << (n - i - 1)
        cnt += 1
    
    tval = val % cnt
    ans = 1
    
    while tval != 0:
        tcnt = 0
        for j in range(30):
            tcnt += (tval >> j) & 1
        tval %= tcnt
        ans += 1
    
    print(ans)

    if x[i] == 1:
        val += 1 << (n - i - 1)
        cnt += 1
    else:
        val -= 1 << (n - i - 1)
        cnt -= 1

Submission status: Runtime Error

Solution code:
n = int(input())
c = input()
#c = list(input())

#print(c)
a = [0] *n
for i in range(n):
    a[i] = int(c[i])
#print(a)

num_11 = [0] *(2*10**5)

for i in range (2*10**5):
    s = bin(i)
    s1 = s[2:]
    num_11[i] = s1.count("1")

num_1 = sum(a)
num_2 = int(c,2)
#print(num_1,num_2)

ans = [0] *n

for i in range(n):
    if a[i] == 1:
        num_i = num_1 -1
        num_j = num_2 -2**(n-i-1)
    else:
        num_i = num_1 +1
        num_j = num_2 + 2**(n-i-1)
    temp = num_j%num_i
    #print(a[i],temp,num_i,num_j)
    count = 1
    if temp == 0:
        ans[i] = 1
        continue
    while temp != 0:
        temp = temp%num_11[temp]
        count += 1
    ans[i] = count

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

Submission status: Runtime Error

Solution code:
n = int(input())
x = str(input())
kosu1 = 0
kazu = 0
for i in range(n):
    kazu += 2 ** (n - i - 1) * int(x[i])
    if x[i] == '1':
        kosu1 += 1
if kosu1 ==1:
    kazup = kazu % (kosu1 + 1)
    magic17 = [0, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 2, 3, 1, 2]
    box = [0] * (kosu1 + 1)

    amarip = [1] * n
    amarim = [1] * n
    for i in range(1, n):
        amarip[i] = (amarip[i - 1] * 2) % (kosu1 + 1)
    for i in range(n):
        if x[i] == '1':
            print(0)
        else:
            a = (kazup + amarip[n - 1 - i]) % (kosu1 + 1)

            if a <= 18:
                print(magic17[a] + 1)
            else:
                num = 0
                for i in range(len(str(bin(a)) - 2)):
                    if str(bin(a))[-1 - i] == '1':
                        num += 1
                print(magic17[a % num] + 1)
else:
    kazup = kazu % (kosu1 + 1)
    kazum = kazu % (kosu1 - 1)
    magic17 = [0,1,1,2,1,2,1,2,1,2,1,2,1,2,2,3,1,2,1]
    box = [0] * (kosu1 +1)

    amarip = [1] * n
    amarim = [1] * n
    for i in range(1,n):
        amarip[i] = (amarip[i - 1]*2) % (kosu1 + 1)
        amarim[i] = (amarim[i - 1]*2) % (kosu1 - 1)
    for i in range(n):
        if x[i] == '1':
            a = (kazum - amarim[n-1-i]) % (kosu1 - 1)

            if a <= 18:
                print(magic17[a]+1)
            else:
                num = 0
                for i in range(len(str(bin(a))-2)):
                    if str(bin(a))[-1-i] == '1':
                        num += 1
                print(magic17[a % num] + 1)
        else:
            a = (kazup + amarip[n - 1 - i]) % (kosu1 + 1)
            if a <= 18:
                print(magic17[a] + 1)
            else:
                num = 0
                for i in range(len(str(bin(a)) - 2)):
                    if str(bin(a))[-1 - i] == '1':
                        num += 1
                print(magic17[a % num] + 1)