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 = str(input())

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

Xis = []
for i in list(reversed(range(N))):
    Xis.append(toggle_nth_bit(int(X, 2),i))

def popcount(Xi):
    count = 0
    for i in bin(Xi):
        if i == '1':
            count += 1
    return count

for i in Xis:
    count = 0
    while True:
        i = i % popcount(i)
        count += 1
        if i == 0:
            break
    print(count)

Submission status: Runtime Error

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

def popcount(n):
  return bin(n).count("1")
  
def func(n, c):
  next = n%popcount(n)
  c+=1
  if next == 0:
    return c
  else:
    return func(next, c)
  
  
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)
  print(func(itemp, 0))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(5000)
n = int(input())
X = input()
nx = int(X, 2)
dp = [-1] * (10**7+1)
def f(n):
    if dp[n] > 0:
        return dp[n]
    pc = bin(n).count('1')
    nn = n%pc
    if nn == 0:
        return 1
    dp[n] = f(nn) + 1
    return dp[n]

for i in range(n-1, -1, -1):
    # ibit目を反転させる # つまりi**2を引く
    tmp = pow(2, i)

    if (nx>>i)&1:
        nx -= tmp
        print(f(nx))
        nx += tmp
    else:
        nx += tmp
        print(f(nx))
        nx -= tmp

Submission status: Runtime Error

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

def popcount(n):
    r = 0
    for c in n:
        if c == '1':
            r += 1
    return r

def func(n):
    return bin(int(n,2)%popcount(n))[2:]

for i in range(N):
    if X[i] == '0':
        X[i] = '1'
    else:
        X[i] = '0'
    res = 0
    tmp = ''.join(X)
    while tmp != '0':
        tmp = func(tmp)
        res += 1
    print(res)
    if X[i] == '0':
        X[i] = '1'
    else:
        X[i] = '0'

Submission status: Runtime Error

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

N_ub = 2 * 10 ** 5
f = [-1] * (N_ub)
f[0] = 0
for n in range(1, N_ub):
    pc = format(n, "b").count("1")
    f[n] = f[n % pc] + 1

X_pc = X.count("1")
X_res_m1 = 0
X_res_p1 = 0
for i, s in enumerate(reversed(X)):
    if s == "1":
        X_res_m1 += pow(2, i, X_pc - 1)
        X_res_m1 %= X_pc - 1

        X_res_p1 += pow(2, i, X_pc + 1)
        X_res_p1 %= X_pc + 1

ans = []
for i, s in enumerate(reversed(X)):
    if s == "1":
        fx = (X_res_m1 - pow(2, i, X_pc - 1)) % (X_pc - 1)
        ans.append(f[fx] + 1)
    else:
        fx = (X_res_p1 + pow(2, i, X_pc + 1)) % (X_pc + 1)
        ans.append(f[fx] + 1)

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

Submission status: Runtime Error

Solution code:
import sys #追加

n=int(input())
sys.setrecursionlimit(10**5*2)

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

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

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

ans=[]

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

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

#print(ans_memo)

for item in ans:
    print(item)

Submission status: Runtime Error

Solution code:
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n=int(input())
x=input()
m=int(x,2)
c=x.count("1")
for i in range(n):
    che=1
    p=1
    if x[i]=="1":
        p=-1
    nex=(m+p*(2**(n-i-1)))%(c+p)
    while nex!=0:
        nex=nex%str(bin(nex)).count("1")
        che+=1
    print(che)

Submission status: Runtime Error

Solution code:
def power(x, y, p) : 
    res = 1     # Initialize result 
  
    # Update x if it is more 
    # than or equal to p 
    x = x % p  
      
    if (x == 0) : 
        return 0
  
    while (y > 0) : 
          
        # If y is odd, multiply 
        # x with result 
        if ((y & 1) == 1) : 
            res = (res * x) % p 
  
        # y must be even now 
        y = y >> 1      # y = y/2 
        x = (x * x) % p 
          
    return res  

F = [0,1,1]
for i in range(3,100001):
	F += [ 1 + F[i%(bin(i).count('1'))]]
	

n=int(input())
s=input()
ones = s.count('1')
a = ones -1
b = ones
c = ones+1
moda = modb = modc = 0
for i in range(n-1,-1,-1):
	pos = n-1-i
	if s[i]=='1':
		if a>0 : moda = (moda + power(2, pos, a) ) %a
		if b>0 : modb = (modb + power(2, pos, b) ) %b
		modc = (modc + power(2, pos, c) ) %c

for i in range(n):
	if s[i] == '0': #ajout
		add = power(2, n-1-i, c)
		ans = (modc + add) % c
		print(F[ans]+1)
	else: # retrait
		if a<=0: print(0)
		else:
			sub = power(2, n-1-i, a)
			ans = (moda - sub) % a
			print(F[ans]+1)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# 整数の入力
N = int(input())
# 文字列の入力
X = input()
one = 0
intX = 0
bit = 1
for i in reversed(range(len(X))):
    if X[i] == '1':
        one += 1
        intX += bit
    bit *= 2
hi = one + 1
lo = one - 1
hirembase = intX % hi
lorembase = intX % lo
# print(intX)
# print(hi)
# print(lo)
# print(hirembase)
# print(lorembase)
bo = []
for i in range(200010):
    num = 0
    while i != 0:
        bit = bin(i)
        bitnum = 0
        for j in range(len(bit)):
            if j == 0 or j == 1:
                continue
            if bit[j] == '1':
                bitnum += 1
        i = i % bitnum
        num += 1
    bo.append(num)
ans = []
hirem = 1
lorem = 1
for i in reversed(range(len(X))):
    if X[i] == '0':
        num = (hirembase + hirem + hi) % hi
        ans.append(bo[num] + 1)
    else:
        if bit == 1:
            ans.append(0)
        else:
            num = (lorembase - lorem + lo) % lo
            ans.append(bo[num] + 1)
    hirem = (hirem * 2) % hi
    lorem = (lorem * 2) % lo
# print(ans)
# 出力
for i in reversed(range(len(ans))):
    print(ans[i])

Submission status: Runtime Error

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


def fx(x):
    xbin = bin(x)
    popcount = xbin.count("1")
    return (x % popcount)


for i in range(N):
    fn = 0
    Xi = list(X)
    if Xi[i] == "0":
        Xi[i] = "1"
    else:
        Xi[i] = "0"
    Xi = int("".join(Xi), 2)

    while True:
        Xi = fx(Xi)
        fn += 1
        if Xi == 0:
            break
        else:
            pass

    print(fn)

Submission status: Runtime Error

Solution code:
import sys

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

def popcount(num,c):
    one = bin(num).count("1")
    next = num % one
    if next == 0:
        return c
    else:
        return popcount(next,c+1)

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

Submission status: Runtime Error

Solution code:
def popcount(n):
    ans=0
    for i in range(20):
        if n>>i & 1:
            ans+=1
    return ans

N=int(input())
X=input()
n=0

for i in range(N):
    if X[i]=='1':
        n+=1
np1=0
nm1=0
temp1=1
temp2=1
for i in range(N-1,-1,-1):
    if X[i]=='1':
        np1=(np1+temp1)%(n+1)
        nm1=(nm1+temp2)%(n-1)
    temp1=(temp1*2)%(n+1)
    temp2=(temp2*2)%(n-1)
    
for i in range(N):
    ans=1
    if X[i]=='1':
        temp=(nm1-pow(2,(N-1-i),n-1))%(n-1)
        while temp>0:
            pop_n=popcount(temp)
            temp=temp%pop_n
            ans+=1
    elif X[i]=='0':
        temp=(np1+pow(2,(N-1-i),n+1))%(n+1)
        while temp>0:
            pop_n=popcount(temp)
            temp=temp%pop_n
            ans+=1
    print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
X = input()
nx = int(X, 2)
dp = [-1] * (10**7+1)
def f(n):
    if dp[n] > 0:
        return dp[n]
    pc = bin(n).count('1')
    nn = n%pc
    if nn == 0:
        return 1
    dp[n] = f(nn) + 1
    return dp[n]

for i in range(n-1, -1, -1):
    # ibit目を反転させる # つまりi**2を引く
    tmp = pow(2, i)

    if (nx>>i)&1:
        nx -= tmp
        print(f(nx))
        nx += tmp
    else:
        nx += tmp
        print(f(nx))
        nx -= tmp

Submission status: Runtime Error

Solution code:
N = int(input())
X = list(map(int, input().strip()))

count_j = X.count(1)

def calc_table(m):
	if m == 1:
		return [0] * N
	elif m == 0:
		return None
	table = []
	x = 1
	for i in range(N):
		table.append(x)
		x = (x * 2) % m
	table.reverse()
	return table

count_m = count_j - 1
count_p = count_j + 1

mod_m = calc_table(count_m)
mod_j = calc_table(count_j)
mod_p = calc_table(count_p)

original_j = 0
original_m = 0
original_p = 0
for i, b in enumerate(X):
	if b == 1:
		original_j = (original_j + mod_j[i]) % count_j
		original_m = (original_m + mod_m[i]) % count_m
		original_p = (original_p + mod_p[i]) % count_p

#print(mod_p)
#print(original_m, original_j, original_p)

f_cache = [None] * N
def calc_f(x):
	if x == 0:
		return 0
	f = f_cache[x]
	if f != None:
		return f
	count = 0
	i = x
	while i > 0:
		if i % 2 == 1:
			count += 1
		i //= 2
	f = calc_f(x % count) + 1
	f_cache[x] = f
	return f

for i, b in enumerate(X):
	if b == 0:
		x = (original_p + mod_p[i]) % count_p
	else:
		x = (original_m - mod_m[i]) % count_m
	print(calc_f(x) + 1)

Submission status: Runtime Error

Solution code:
import collections
N = int(input())
sX = input()
modX = sX.count('1')
modp = modX + 1
modm = modX - 1
sX = sX[::-1]
Xmodp = 0
Xmodm = 0
for i, b in enumerate(sX):
    if b == '1':
        Xmodp += pow(2, i, modp)
        Xmodp %= modp
        Xmodm += pow(2, i, modm)
        Xmodm %= modm
s = []
for i, b in enumerate(sX):
    if b == '1':
        s += [(Xmodm - pow(2, i, modm)) % modm]
    else:
        s += [(Xmodp + pow(2, i, modp)) % modp]
t = s[::-1]

memo = collections.defaultdict(int)
memo[0] = 0


def f(x):
    if x in memo:
        return memo[x]
    else:
        y = x % bin(x).count('1')
        ret = 1 + f(y)
        memo[x] = ret
        return ret


ans = []
for k in t:
    ans += [1 + f(k)]
print('\n'.join(map(str, ans)))

Submission status: Runtime Error

Solution code:
n=int(input())
x=list(input())
l=[0]*n
def popcount(m,p):
    binst=format(m,'b')
    lis=list(binst)
    num=lis.count('1')
    nm=m%num
    p += 1
    if nm==0:
        return p
    else:
        return popcount(nm,p)
for i in range(n):
    if x[i]=='1':
        x[i]='0'
    else:
        x[i]='1'
    t=''.join(x)
    intnum=int(t,2)
    print(popcount(intnum,0))
    if x[i]=='1':
        x[i]='0'
    else:
        x[i]='1'

Submission status: Runtime Error

Solution code:
n = int(input())
s = input()
su = s.count('1')
sun = int(s,2)

table = [0]*200001
table[1] = 1
for i in range(2,200001):
    table[i] = 1 + table[i % bin(i).count('1')]


for i in range(n):
    if s[i] == '0':
        print(1+table[(sun+2**(n-1-i))%(su+1)])
    else:
        print(1+table[(sun-2**(n-1-i))%(su-1)])

Submission status: Runtime Error

Solution code:
def cal_nums(number):
    cp = number
    cnt = 0
    while cp != 0:
        cnt += cp % 2
        cp //= 2
    return number % cnt

def func(number):
    cnt = 0
    tmp = number
    while(1):
        cnt += 1
        tmp = cal_nums(tmp)
        if tmp == 0:
            break
    return cnt

n = int(input())
string = input()
length = len(string)
tmp = 0
for i in range(length):
    tmp *= 2
    if string[i] == '1':
        tmp += 1

for idx in range(length):
    if string[idx] == '0':
        print(func(tmp+(1<<(length-idx-1))))
        # print(tmp+(1<<(length-idx-1)))
    else:
        print(func(tmp-(1<<(length-idx-1))))
        # print(tmp-(1<<(length-idx-1)))

Submission status: Runtime Error

Solution code:
n = int(input())
x = list(input())
c1 = x.count("1")+1
c2 = c1-2

now1 = 0
now2 = 0

for i in range(n):
    if x[-1-i] == "1":
        now1 += pow(2,i,c1)
        now2 += pow(2,i,c2)
        
    now1 %= c1
    now2 %= c2

for i in range(n):
    if x[i] == "1":
        #print(n-1-i)
        now = (now2-pow(2,n-1-i,c2))%c2
        #print(i,now,c2)
        count = 1
        while now > 0:
            q = bin(now)
            y = q.count("1")
            now %= y
            count += 1
        print(count)
    else:
        #print(n-1-i)
        now = (now1+pow(2,n-1-i,c1))%c1
        #print(i,now,c1)
        count = 1
        while now > 0:
            q = bin(now)
            y = q.count("1")
            now %= y
            count += 1
        print(count)

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 popcnt0(n):
        c = 0
        for i in range(20):
            c += (n >> i) & 1
        return c
    def cnt(num):
        c = 0
        while(num>0):
            #num %= bin(num).count("1")
            num %= popcnt0(num)
            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(1)
        return
    print(hoge)
    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] + 2*(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):
        pass


    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:
import gmpy2

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

for i in range(N):
    Xi = list(X)
    if Xi[i] == '1':
        Xi[i] = '0'
    else:
        Xi[i] = '1'
    
    ans = 0
    n = int(''.join(Xi), 2)
    while n > 0:
        n = n % gmpy2.popcount(n)
        ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
def calc(x):
  num = int(x, base=2)
  s = sum([1 for i in x if i == "1"])
  return num % s

def check(x):
  c = 0
  while True:
    c += 1
    x = format(calc(x), "b")
    if x == "0":
      return c

n = int(input())
x = input()
for i in range(n):
  if x[i] == "1":
    s = format(int(x, base=2) - 2**(n-i-1), "b")
    print(check(s))
  else:
    s = format(int(x, base=2) + 2**(n-i-1), "b")
    print(check(s))

Submission status: Runtime Error

Solution code:
"""
NTC here
"""


#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase

profile = 0
pypy = 1


def iin(): return int(input())


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



def main():
    T = 1
    while T:
        T -= 1
        n = iin()
        a = list(map(int, list(input())))
        ans = []
        def calc(a, md):
            ch = len(a)-1
            rm = 0
            for i in a:
                if i:
                    rm = (rm+ pow(2, ch, md))%md
                ch -= 1
            return rm%md
        
        def bin_calc(a):
            ans = []
            while a:
                ans.append(a&1)
                a >>= 1
            return ans[::-1]
        sm = sum(a)
        for i in range(n):
            sol = 0
            s1 = sm - a[i]
            a[i] = + (not a[i])
            s1 += a[i]
            a1 = a
            while 1:
                # print(a1, s1)
                sol += 1
                rm = calc(a1, s1)
                if rm:
                    a1 = bin_calc(rm)
                    s1 = sum(a1)
                else:
                    break
            a[i] = + (not a[i])
            ans.append(sol)
        print(*ans, sep='\n')





    
        










    




                

        

 
 
 
 
 
 
# region fastio
 
BUFSIZE = 8192
 
 
class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 
if pypy:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
    input = lambda: sys.stdin.readline().rstrip("\r\n")
 
# endregion
 
if __name__ == "__main__":
    if profile:
        import cProfile
        cProfile.run('main()')
    else:
        main()

Submission status: Runtime Error

Solution code:
N = int(input())
a = input()
def bit2(inp):
    A = len(inp)
    ans = 0
    for i in range(A):
        if inp[A-1-i] == "1":
            ans += 2 ** i
    return ans

def bitReverse(bit,i):
    k = "1"
    if bit[i] == "1":
        k = "0"
    return bit[:i] + k + bit[i+1:]
def bitCount(bit):
    count = 0
    for i in bit:
        if i == "1":
            count += 1
    return count
def toBit(inp,keta):
    ans = ""
    for i in range(keta-1,-1,-1):
        if 2 ** i <= inp:
            inp -= 2 ** i
            ans = ans + "1"
        else:
            ans = ans + "0"
    return ans

def answer(bit,count):
    point = bit2(bit)
    c = bitCount(bit)
    if point%c == 0:
        return count+1
    return answer(toBit(point%c,len(bit)),count+1)
    
length = len(a)
for i in range(length):
    k = bitReverse(a,i)
    print(answer(k,0))

Submission status: Runtime Error

Solution code:
def solve():
  N = int(input())
  X = input()
  x = sum(map(int,list(X)))
  dp = [0]*N
  for i in range(1,N):
    dp[i] = dp[i%sum(map(int,list(bin(i)[2:])))]+1
  cnt = 0
  if x==1:
    cnt1 = 0
  elif x>1:
    for i in range(N):
      cnt1 += int(X[-i-1])*pow(2,i,x-1)
      cnt1 %= x-1
  cnt2 = 0
  for i in range(N):
    cnt2 += int(X[-i-1])*pow(2,i,x+1)
    cnt2 %= x+1
  
  ans = [0]*N
  for i in range(N):
    if X[i]=='1':
      if x==1:
        ans[i] = 0
      else:
        num = (cnt1-pow(2,N-i-1,x-1))%(x-1)
        ans[i] = dp[num]+1
    else:
      num = (cnt2+pow(2,N-i-1,x+1))%(x+1)
      ans[i] = dp[num]+1
  return ans
print(*solve(),sep='\n')

Submission status: Runtime Error

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

def popcount(a):
  flg=0
  count=0
  while flg==0:
    n=bin(a)
    ncount=n.count('1')
    a=a % ncount
    count+=1
    if a==0:
      flg=1
  return(count)


for i in range(N):
  if X[i]=='0':
    X[i]='1'
  else:
    X[i]='0'
  
  a=''.join(X)
  
  #print(a)
  
  tmp=int(a,2)
  print(popcount(tmp))
  
  X=list(a)
  
  if X[i]=='0':
    X[i]='1'
  else:
    X[i]='0'

Submission status: Runtime Error

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

Submission status: Runtime Error

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

def popcount(num, count):
    count += 1
    two_num = format(num, 'b')
    two_string = str(two_num)
    ans = two_string.count('1')
    okikae = num % ans
    if okikae == 0:
        return count
    else:
        popcount(okikae, count)

for i in range(n):
    target = x
    if target[i] == '0':
        target = target[0:i] + '1' + target[i+1:]
    else:
        target = target[0:i] + '0' + target[i+1:]
  #  print(target)
    print(popcount(int(target, 2), 0))

Submission status: Runtime Error

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

def f(n, first):
    cnt = 1
    n %= first
    while n!=0:
        pc = bin(n).count("1")
        n = n%pc
        cnt += 1
    return cnt

v = 0
for i, j in enumerate(X[::-1]):
    if j=="1":
        v += 2**i
cnt = X.count("1")

for i in range(N):
    p = N-i-1
    buf = 0
    c2 = 0
    if X[i]=="0":
        buf = v+2**p
        c2 = cnt+1
    else:
        buf = v-2**p
        c2 = cnt-1
    print(f(buf, c2))

Submission status: Runtime Error

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

dp = [0] * n
for i in range(1, n-1):
    tmp = i
    cnt = 0
    while tmp > 0:
        cnt += tmp % 2
        tmp //= 2
    dp[i] = dp[i % cnt] + 1

c = x.count('1')

dp_1 = [0] * n
dp_2 = [0] * n
dp_1[0] = 1 % (c - 1)
dp_2[0] = 1 % (c + 1)
for i in range(1, n):
    dp_1[i] = (2 * dp_1[i-1]) % (c - 1)
    dp_2[i] = (2 * dp_2[i-1]) % (c + 1)

mod_1 = 0
mod_2 = 0
for i in range(n):
    if x[i] == '1':
        mod_1 = (mod_1 + dp_1[n-i-1]) % (c - 1)
        mod_2 = (mod_2 + dp_2[n-i-1]) % (c + 1)

for i in range(n):
    if x[i] == '1':
        mod = (mod_1 - dp_1[n-i-1]) % (c - 1)
        print(dp[mod] + 1)
    else:
        mod = (mod_2 + dp_2[n-i-1]) % (c + 1)
        print(dp[mod] + 1)

Submission status: Runtime Error

Solution code:
N = int(input())
ans_list = [0] * (N+1)
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
for i in range(N):
    if i == 0:
        continue
    else:
        if i %popcnt(i) == 0 :
            ans_list[i] = 1
        else:
            ans_list[i] = ans_list[i%popcnt(i)] + 1
S = input()
count = 0
for i in range(N):
    if S[i] == "1":
        count += 1
high_total = 0
low_total = 0
for i in range(N):
    if S[i] == "1":
        high_total += pow(2,N-1-i,count+1)
        high_total %= (count+1)
        low_total +=  pow(2,N-1-i,count-1)
        low_total %= (count-1)
for i in range(N):
    if S[i] == "1":
        total = (low_total - pow(2,N-1-i,count-1)) % (count-1)
        print(ans_list[total]+1)
    if S[i] == "0":
        total = (high_total + pow(2,N-1-i,count+1)) % (count+1)
        print(ans_list[total]+1)

Submission status: Runtime Error

Solution code:
import sys


def _s(): return sys.stdin.readline().strip()


def _i(): return int(sys.stdin.readline().strip())


def flip(c):
    return "1" if c == "0" else "0"


def main():
    n = _i()
    s = _s()

    lst = [0] * (n+1)
    lst[0] = 0
    for i in range(1, n+1):
        t = i % bin(i)[2:].count("1")
        lst[i] = 1 + lst[t]

    for i in range(n):
        m = s[:i] + flip(s[i]) + s[i+1:]
        t = int(m, 2) % m.count("1")
        print(lst[t] + 1)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from functools import lru_cache
from math import factorial#, gcd
from bisect import bisect_left, bisect_right #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

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

def mn():
    return -1
pops = defaultdict(mn)
dists = defaultdict(mn)

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
def myf(n):
    if pops[n] != -1:
        return pops[n]
    else:
        return n%(popcnt(n))
def cal(n):
    cnt = 0
    while n > 0:
        n = myf(n)
        cnt += 1
    return cnt

@lru_cache(maxsize=None)
def saiki(n):
    if n == 0:
        return 0
    else:
        n = myf(n)
        return saiki(n) + 1

for i in range(N):
    if X[i] == '1':
        val = int(X, 2) - 2**(N-i-1)
    else:
        val = int(X, 2) + 2**(N-i-1)
    res = saiki(val)
    print(res)

Submission status: Runtime Error

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

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

        



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

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
popcount_X = X.count('1')
numX = int(X, 2)
a, b = numX % (popcount_X + 1), numX % (popcount_X - 1)
for i, x in enumerate(X, 1):
    if x == '1' and popcount_X == 1:
        print(0); continue
    ans = 1
    if x == '1':
        temp = b - pow(2, N-i, popcount_X - 1)
    else:
        temp = a + pow(2, N-i, popcount_X + 1)
    while temp:
        p = bin(temp)[2:].count('1')
        temp %= p
        ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import sys
from functools import lru_cache

sys.setrecursionlimit(4100000)
d = defaultdict(int)

@lru_cache(maxsize=None)
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

@lru_cache(maxsize=None)
def f(x):
    if d[x]:
        return d[x]
    
    if x % count_ones_by_shift(x) == 0:
        d[x] = 1
        return 1

    d[x] = f(x % count_ones_by_shift(x)) + 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()