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()

x_1 = x.count('1')
flag = 0
if(x_1 == 0):
    flag = 1
if(x_1 == 1):
    flag = 2

data = [0 for i in range(n+1)]
data[0] = 0
for i in range(1,n+1):
    i_str = format(i,'b')
    ne = i % (i_str.count('1'))
    data[i] = data[ne] + 1

print(data)

up = [0 for i in range(n)]
do = [0 for i in range(n)]

d = 1
for i in range(n):
    up[i] = d % (x_1 + 1)
    d *= 2
d = 1
if(flag == 0):
    for i in range(n):
        do[i] = d % (x_1 - 1)
        d *= 2

upp = 0
dow = 0

for i in range(n):
    if(x[n-i-1] == '1'):
        upp += up[i]
        upp %= (x_1+1)
        dow += do[i]
        dow %= (x_1-1)



for i in range(n):
    if(x[i] == '0'):
        sam = upp + up[n-i-1]
        sam %= (x_1+1)
        print(data[sam]+1)
    elif(flag == 0):
        sam = dow - do[n-i-1]
        sam %= (x_1-1)
        print(data[sam]+1)
    elif(flag == 2):
        print('0')

Submission status: Runtime Error

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

res = 0

for i in range(n):
    if(x[i] == '1'): res += 1 << (n - i - 1)

for i in range(n):
    tmp = res
    if(x[i] == '1'):
        tmp -= 1 << (n - i - 1)
    else:
        tmp += 1 << (n - i - 1)
    ans = 0
    while(tmp > 0):
        cnt = 0
        for j in range(0, 31):
            if(tmp & (1 << j)): cnt += 1
        tmp %= cnt
        ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
def cin():
    return input().split()
def qpow(a,b,p):
    if p == 1:
        return 0
    a = (a%p+p)%p
    ans = 1
    while b!=0:
        if (b&1) != 0:
            ans = (ans * a) % p
        b >>= 1
        a = a * a  % p
    return ans

def f(x):
    ans = 0
    if x == 0:
        return ans
    for i in range(31):
        if ((x>>i)&1) == 1:
            ans += 1
    return f(x%ans) + 1

n = int(input())
x = list(input())
x = x[::-1]
cnt = 0;l = len(x)
r1 = 0;r2 = 0
for i in x:
    if i == '1':
        cnt += 1
i = 0
while i < l:
    if x[i] == '1':
        r1 += qpow(2,i,cnt+1)
        r2 += qpow(2,i,cnt-1)
    i += 1
i = 0
a = []
while i < l:
    if x[i] == '0':
        t = f((r1+qpow(2,i,cnt+1))%(cnt+1))+ 1
    else:
        t = f((r1-qpow(2,i,cnt-1)+(cnt-1))%(cnt-1)) + 1
    i += 1
    a.append(t)
a = a[::-1]
for i in a:
    print(i)

Submission status: Runtime Error

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

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


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


bin_x = int(x, 2)

num_one = bc(bin_x)

ans_list = [-1]*(2*10**5+1)

ans = []
haita = 1
for i in range(n):
    tmp_x = bin_x ^ haita
    if x[-i-1] == "0":
        num_one_tmp = num_one+1
    else:
        num_one_tmp = num_one-1

    count = 1
    while(tmp_x % num_one_tmp != 0):
        tmp_x = tmp_x % num_one_tmp
        num_one_tmp = bc(tmp_x)
        count += 1
    ans.append(count)

    haita = haita << 1

for i in reversed(ans):
    print(i)

Submission status: Runtime Error

Solution code:
n = int(input())
inx = input()
x = int('0b'+inx,0)
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):
    rev = 1<<(n-1-i)
    cnt = 0
    y = x^rev
    while y != 0:
        # print("itr" + str(cnt))
        # print(popcount(y))
        # print(y)
        y = y % popcount(y)
        cnt += 1
    print(cnt)

Submission status: Runtime Error

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

@lru_cache(maxsize = None)
def popcount(n):
    if n <= 1:
        return n
    else:
        return (n & 1) + popcount(n // 2)

@lru_cache(maxsize = None)
def f(n):
    ret = 0
    while n > 0:
        n = n % popcount(n)
        ret += 1
    return ret

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

Submission status: Runtime Error

Solution code:
n = int(input())
x = eval("0b" + input())

def toggl_ith_bit(num, i):
    return num ^ (1 << i)

def popcount(num):
    s = 0
    b = num
    while b != 0:
        s += (b & 1 > 0)
        b >>= 1
    return s

x_count = popcount(x)

for i in range(n - 1, -1, -1):
    xi = toggl_ith_bit(x, i)
    xi_count = x_count + 1 if (xi & (1 << i)) else x_count - 1
    cnt = 1
    xi %= xi_count
    while xi != 0:
        cnt += 1
        xi %= popcount(xi)
    print(cnt)

Submission status: Runtime Error

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


def popc(n):
    count = 0
    for i in range(N):
        if n & (1<<i):
            count += 1
    return count

def func(n):
    count = 1
    while n % popc(n):
        n = n % popc(n)
        count += 1
    return count

def change(X, i):
    if X & (1<<(N-i-1)):
        X &= ~(1<<(N-i-1))
    else:
        X |= (1<<(N-i-1))
    return X

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

Submission status: Runtime Error

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

#Sのビット数
bitcount=0
for i in range(N):
  if S[i]=='1':
    bitcount+=1

def f(n):
  c=0
  x=1
  while x<=n:
    if n&x>0:
      c+=1
    x*=2
  return n%c

ls=[0 for i in range(bitcount+2)]  
ls2=[0 for i in range(bitcount+2)]
for i in range(1,bitcount+2):
  ls[i]=f(i)
  ls2[i]=ls2[ls[i]]+1

for i in range(N):
  if S[i]=='0':
    print(ls2[(X^(2**(N-1-i)))%(bitcount+1)]+1)
  else:
    print(ls2[(X^(2**(N-1-i)))%(bitcount-1)]+1)

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
for i in range(n):
    if x[i]=='0':
        target=x[0:i]+'1'+x[i+1:n]
    else:
        target=x[0:i]+'0'+x[i+1:n]
    cnt=0
    flag=True
    while True:
        tmp=target.count('1')
        f=int(target,2)%tmp
        cnt+=1
        if f==0:
            print(cnt)
            break
        target=format(f,'b')

Submission status: Runtime Error

Solution code:

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

N = int(input())
X = input()
f = 0
count = 1
c = []
fi = 0
for i in range(N-1, -1, -1):
    # print(i)
    fi = toggle_nth_bit(int(X, 2), i)
    f = str(bin(toggle_nth_bit(int(X, 2), i)))
    while fi % f.count("1") != 0:
        fi = fi % f.count("1")
        f = str(bin(fi))
        # print(f)
        # print(fi)
        count += 1
        # print(count)
    c.append(count)
    count = 1

# ans = str(bin(toggle_nth_bit(int(X,2), 0)))
for i in c:
    print(i)

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
ans = [0]*n

popcnt = 0
for i in range(n):
    if x[i] == "1":
        popcnt += 1
if popcnt == 0:
    print("owari")

amari = 0
for i in range(len(x)):
    if x[i] == "1":
        amari += pow(2, len(x)-i-1, popcnt)
amari %= popcnt

print(amari)

Submission status: Runtime Error

Solution code:
def popcount(n): 
  if n==1 or n==2: return 1
  else: return 1+ popcount(n%(bin(n).count('1')))
 
n = int(input())
a = int(input(),2)
 
while(n):
  print(popcount(a))
  a = a%(bin(a).count('1'))
  n -= 1

Submission status: Runtime Error

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

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

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

def popcount(x):
    count = 0
    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 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()
for i in range(n):
    if x[i] == "0":
        xi = x[:i] + "1" + x[i+1:]
    else:
        xi = x[:i] + "0" + x[i+1:]
    c = 0
    while xi != "0":
        xi = bin(int(xi, 2)%xi.count("1"))[2:]
        c += 1
    print(c)

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
x = [int(x[i]) for i in range(len(x))]
ans = [-1 for i in range(n+1)]
def popc(n):
	ans = 0
	while(True):
		if n==0:
			break
		if n%2 == 1:
			ans += 1
		n = n//2
	return ans
def conv(a):
	ans = 0
	for i in range(len(a)):
		ans += (2**i)*a[-1*(i+1)]
	return ans

for i in range(n):
	tmp = x[:]
	tmp[i] = 0 if tmp[i] == 1 else 1
	num = conv(tmp)
	popcount = sum(tmp)
	cnt = 0
	while(True):
		num = num%popcount
		cnt += 1
		if num == 0:
			break
		popcount = popc(num)
	print(cnt)

Submission status: Runtime Error

Solution code:
def popcount(x):
    bitx = bin(x)
    cnt = bitx.count('1')
    return cnt

n = int(input())
x = list(input())
for i in range(n):
    tmp = x.copy()
    if tmp[i] == '1':
        tmp[i] = '0'
    else:
        tmp[i] = '1'
    tmp = int(''.join(tmp), 2)
    tmp2 = popcount(tmp)
    if tmp % tmp2 == 0:
        print(1)
    elif tmp % 2 != 0 and tmp2 % 2 == 0:
        print(3)
    else:
        print(2)

Submission status: Runtime Error

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [-int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    N = NI()
    X = SI()

    cnt = [0] * (N+1)
    for i in range(1,N+1):
        x = i % bin(i).count('1')
        if x == 0:
            cnt[i] = 1
        else:
            cnt[i] = cnt[x] + 1

    xc = X.count('1')
    xp = 0
    xm = 0
    xpb = 1
    xmb = 1
    for i in range(N-1,-1,-1):
        xp = (xp + int(X[i]) * xpb) % (xc+1)
        xm = (xm + int(X[i]) * xmb) % (xc-1)
        xpb = (xpb * 2) % (xc+1)
        xmb = (xmb * 2) % (xc-1)

    for i in range(N):
        if X[i] == '0':
            x = (xp + pow(2,N-i-1,xc+1)) % (xc+1)
        else:
            x = (xm - pow(2,N-i-1,xc-1)) % (xc-1)
        print(cnt[x]+1)



if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
digit_cnt = int(input())
default_int = input()

def popcount(n):
  x = bin(n)
  res = 0
  for i in range(len(x)):
    if x[i] == "1":
      res += 1
  return res

def f(n):
  m = popcount(n)
  if n % m == 0:
    return 1
  else:
    return f(n % m) + 1

for i in range(digit_cnt):
  tmp = default_int
  if (default_int[i] == "0"):
    if i > 0:
      tmp = tmp[:i] + "1" + tmp[i+1:]
    else:
      tmp = "1" + tmp[1:]
  else:
    if i > 0:
      tmp = tmp[:i] + "0" + tmp[i+1:]
    else:
      tmp = "0" + tmp[1:]
  tmp_int = int(tmp,2)
  print(f(tmp_int))

Submission status: Runtime Error

Solution code:
LIM=200001
L=[0]*LIM

def bin_sum(Y):
    S=bin(Y)[2:]
    count=0
    for i in range(len(S)):
        count+=int(S[i])
    return count

def bin_sum2(Y):
    count=0
    for i in range(len(Y)):
        count+=int(Y[i])
    return count

for i in range(LIM):
    L[i]+=bin_sum(i)

def pop_num(N,b):
    count=1
    N=N%b
    while N!=0:
        b=L[N]
        N=N%b
        count+=1
    return count
X=int(input())
Y=input()
d=bin_sum2(Y)+1
c=bin_sum2(Y)-1
for i in range(X):
    Y_i=Y[:i]+str(abs(int(Y[i])-1))+Y[i+1:]
    if Y_i[i]=="1":
        b=d
    else:
        b=c
    print(pop_num(int(Y_i,2),b))

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
flg = [0] * n
for i in range(n):
    if x[i] == '1':
        flg[i] = 1
x = int(x, 2)
cnt = sum(flg)
x_a = x % (cnt - 1)
x_b = x % (cnt + 1)


for i in range(n):
    if flg[i] == 1:
        if cnt == 1:
            print(0)
            continue
        t = (x_a - pow(2, n-i-1, cnt-1)) % (cnt - 1)
    else:
        t = (x_b + pow(2, n-i-1, cnt+1)) % (cnt + 1)

    if t == 0:
        print(1)
    else:
        tmp = 1
        while t > 0:
            pop = bin(t).count('1')
            t = t % pop
            tmp += 1

        print(tmp)

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
memo={}
import sys
sys.setrecursionlimit(10**7)

def func(m,i):
  if m in memo:
    return memo[m]
  elif m%i==0:
    memo[m]=1
    return 1
  else:
    ret=0
    mm=m%i
    ii=bin(mm).count('1')
    ret+=func(mm,ii)+1
    memo[m]=ret
    return ret

c=x.count('1')
xx=0
for i in range(n):
  xx+=pow(2,i)*int(x[-1-i])
for i in range(n):
  if x[i]=='0':
    xxx=xx+pow(2,n-1-i)
    cc=c+1
  else:
    xxx=xx-pow(2,n-1-i)
    cc=c-1
  print(func(xxx,cc))
#print(memo)

Submission status: Runtime Error

Solution code:
def popcount(n): 
  if n==1 or n==2: return 1
  else: return 1+ popcount(n%(bin(n).count('1')))

n = int(input())
a = int(input(),2)

while(n):
  print(count(a))
  a = a%(bin(a).count('1'))
  n -= 1

Submission status: Runtime Error

Solution code:
def saiki(x,c,one,dic):
    if int(x,2)%one==0:
        print(c)
    else:
        count = c+1
        #print("A")
        y = dic.get(x,int(x,2)%one)
        one_re=bin(y).count("1")
        saiki(bin(y)[2:],count,one_re,dic)
        
def main():
    N = int(input())
    X = input()
    length=X.count("1")
    dic={}
    for i in range(N):
        dic[i]=0

     

    for i in range(N):
        count=1
        one=-1
        if X[i]=="0":
            x = X[:i]+"1"+X[i+1:]
            one=1
        else:
            x = X[:i]+"0"+X[i+1:]
        #print(x,length,one)
        
        saiki(x,count,length+one,dic)
     
    
main()

Submission status: Runtime Error

Solution code:
def main():
    import copy
    n = int(input())
    x = input()
    x = [x_ for x_ in x]
    dp = [0 for i in range(n+1)]
    for i in range(1,n+1):
        m = bin(i).count('1')
        dp[i] = dp[i%m]+1
    cnt,num = 0,0
    for i in range(n):
        if x[i] == '1':
            cnt += 1
            num += 2**(n-i-1)
    for i in range(n):
        if x[i]=='1':
            c = cnt - 1
            n_ = num - 2**(n-i-1)
        else:
            c = cnt + 1
            n_ = num + 2**(n-i-1)
        m = n_%c
        print(1+dp[m])

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
tmp = sum(X[i] == '1' for i in range(N))

for_zero = tmp + 1
for_one = tmp - 1
zero_S = 0
one_S = 0


numbers = [-1] * N
counts = [1] * N

if tmp == 1:
    for i in range(N):
        if X[i] == '1':
            counts[i] = 0

# =====================first sweep
tmp_zero = 1
tmp_one = 1
for i in range(N):
    if X[-i-1] == '1':
        one_S += tmp_one
        one_S %= for_one
        zero_S += tmp_zero
        zero_S %= for_zero
    tmp_zero *= 2
    tmp_zero %= for_zero
    tmp_one *= 2
    tmp_one %= for_one


# =====================second sweep
tmp_zero = 1
tmp_one = 1
for i in range(N):
    if X[-i-1] == '1':
        numbers[-i - 1] = (one_S - tmp_one) % for_one
    else:
        numbers[-i - 1] = (zero_S + tmp_zero) % for_zero
    tmp_zero *= 2
    tmp_zero %= for_zero
    tmp_one *= 2
    tmp_one %= for_one


def solution(number):
    loop = 0
    while number != 0:
        popcount = 0
        for i in range(30):
            if (1 << i) & number:
                popcount += 1
        number %= popcount
        loop += 1
    return loop

for i in range(N):
    counts[i] += solution(numbers[i])

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

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)) % (popcount_X - 1)
    else:
        temp = (a + pow(2, N-i, popcount_X + 1)) % (popcount_X + 1)
    while temp:
        p = bin(temp)[2:].count('1')
        temp %= p
        ans += 1
    print(ans)

Submission status: Runtime Error

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

def popcount(n):
    bin_str=bin(n)
    cnt=0
    for i in bin_str:
        if i == '1':
            cnt+=1
    return(cnt)

def f(n):
    n=int(str(n), 2)
    cnt=1
    while n % popcount(n) != 0:
        cnt+=1
        n = n % popcount(n)
    return(cnt)


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

Submission status: Runtime Error

Solution code:
def main():
    n = int(input())
    x = input()
    p = x.count("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):
        xi = x[:i] + str(1 - int(x[i])) + x[i + 1:]
        pi = p + int(xi[i]) * 2 - 1
        print(f[int(xi, 2) % pi] + 1)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
times = [0]*200000

for i in range(1,200000):
  bi = format(i, 'b')
  arr = list(map(int, bi))
  sbi = sum(arr)
  if i%sbi == 0:
    times[i] = 1
  else:
    times[i] = 1+times[i%sbi]
    
arr = list(map(int, X))
sbX = sum(arr)
mo = [1,-1]
for i in range(N):
  X10 = int(X,2)^(2**(N-i-1))
  waru = sbX+mo[int(X[i])]
  print(times[X10%waru]+1)

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
memo={}

def func(m,i):
  if m in memo:
    return memo[m]
  elif m%i==0:
    memo[m]=1
    return 1
  else:
    ret=0
    mm=m%i
    ii=bin(mm).count('1')
    ret+=func(mm,ii)+1
    memo[m]=ret
    return ret

c=x.count('1')
xx=0
for i in range(n):
  xx+=pow(2,i)*int(x[-1-i])
for i in range(n):
  if x[i]=='0':
    xxx=xx+pow(2,n-1-i)
    cc=c+1
  else:
    xxx=xx-pow(2,n-1-i)
    cc=c-1
  print(func(xxx,cc))
#print(memo)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
N=int(input())
x=input()
num=0
n=0
ans=[]
def twice(a):
    num=a
    b=0
    while a>0:
        b+=a%2
        a=a//2
    num=num%b
    return 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
        a=A%Num
        Ans+=1
        while a>0:
            a=twice(a)
            Ans+=1
    else:
        Num=n-1
        A=num-2**(N-i-1)
        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:
N = int(input())
X = list(input())
X = [int(x) for x in X]
X.reverse()

def popcnt0(n):
    c = 0
    for i in range(32):
        c += (n >> i) & 1
    return c
  
#最初にNまでの表を作る
D = [0 for _ in range(N+1)]
D[1] = 1
for i in range(2, N+1):
  D[i] = D[i % popcnt0(i)] + 1
  
#次に、Xの１のカウントを求める
ct_1 = 0
for x in X:
  if x == 1:
    ct_1 += 1

#ct_1-1による2^n mod
B = [0 for _ in range(N)]
j = 1
for i in range(N):
  B[i] = j
  j *= 2
  j %= ct_1 - 1 
  
#ct_1+1による2^n mod
C = [0 for _ in range(N)]
j = 1
for i in range(N):
  C[i] = j
  j *= 2
  j %= ct_1 + 1 

#X mod ct_1-1 と、X mod ct_1+1 を求める
s = 0
t = 0
for i in range(N):
  s += X[i] * B[i]
  t += X[i] * C[i]
  s %= ct_1-1
  t %= ct_1+1

X.reverse()
#print(D,B,C)
i = N-1
#各場合の1回目の操作後の数を計算して、Dをつかって答えを出す
for x in X:
  if x == 1:
    k = (s - B[i]) % (ct_1-1)
  else:
    k = (t + C[i]) % (ct_1+1)
  i -= 1
  print(D[k]+1)

Submission status: Runtime Error

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

def pc(n):
    return(str(bin(n)).count("1"))
def reverse(i):
    return X^(1 << i-1)
def f(n):
    a = n
    ans = 0
    while True:
        a = a%pc(a)
        ans += 1
        if a == 0:
            break
    return ans
for i in range(N):
    print(f(reverse(N-i)))

Submission status: Runtime Error

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

dp=[-1]*(n+1)

dp[0]=0
dp[1]=1

def fun(num,step):
    num2=num%sum(list(map(int,bin(num)[2:].zfill(n))))
    if dp[num2]!=-1:
        dp[num]=dp[num2]+step
    else:
        fun(num2,step+1)

for i in range(2,n+1):
    fun(i,1)

for i in range(n):
    x2=x.copy()
    if x[i]=='1':
        x2[i]='0'
    else:
        x2[i]='1'
    num1=''.join(x2)
    num2=int(num1,2)
    num3=num2%sum(list(map(int,x2)))
    print(dp[num3]+1)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
X=input()
XX=int(X,2)
m=X.count('1')
l=[XX%(m+1),(XX%(m-1))]
for i in range(N):
    if X[i]=='0':
        n=l[0]+pow(2,(N-1)-i,m+1)
        n%=m+1
    else:
        n=l[1]-pow(2,(N-1)-i,m-1)
        n%=m-1
    ans=1
    while n>0:
        n=n%bin(n).count('1')
        ans+=1
    print(ans)

Submission status: Runtime Error

Solution code:
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def popcorn(i,k):
    num = 0
    ii = i
    while ii > 0:
        if ii&1:
            num += 1
        ii //= 2
    if i%num:
        return popcorn(i%num,k+1)
    else:
        return k+1

def main():
    n = int(ipt())
    x = list(map(int,list(input())))
    si = sum(x)
    su = si+1
    sd = si-1
    amu = 0
    amd = 0
    n2u = [1]
    if si == 2:
        n2d = [0]
    else:
        n2d = [1]
    for i in x[::-1]:
        if i:
            amu = (amu+n2u[-1])%su
            amd = (amd+n2d[-1])%sd
        n2u.append((n2u[-1]*2)%su)
        n2d.append((n2d[-1]*2)%sd)
    for i,xi in enumerate(x):
        if xi:
            ni = (amd-n2d[-2-i])%sd
            if si == 1:
                print(0)
            elif ni == 0:
                print(1)
            else:
                print(popcorn(ni,1))
        else:
            ni = (amu+n2u[-2-i])%su
            if ni == 0:
                print(1)
            else:
                print(popcorn(ni,1))


    return None

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
flg = [0] * n
for i in range(n):
    if x[i] == '1':
        flg[i] = 1
x = int(x, 2)
cnt = sum(flg)
x_a = x % (cnt - 1)
x_b = x % (cnt + 1)


for i in range(n):
    if flg[i] == 1:
        t = (x_a - pow(2, n-i-1, cnt-1)) % (cnt - 1)
    else:
        t = (x_b - pow(2, n-i-1, cnt+1)) % (cnt + 1)

    if t == 0:
        print(1)
    else:
        tmp = 1
        while t > 0:
            pop = bin(t).count('1')
            t = t % pop
            tmp += 1

        print(tmp)

Submission status: Runtime Error

Solution code:
import sys 
input = lambda:sys.stdin.readline().strip()
def perform(n):
    ans =  1
    val = n.count('1')
    temp = 0
    for i in range(len(n)):
        temp+=pow(2,i,val)*int(n[len(n)-1-i])
        temp%=val
    while temp!=0:
        ans+=1
        temp = temp%(bin(temp).count('1'))
    return ans
n = int(input())
x = list(input())
for i in range(n):
    if x[i]=='0':
        x[i] = '1'
    else:
        x[i] = '0'
    print(perform(x))
    # print(int(''.join(x),2))
    if x[i]=='0':
        x[i] = '1'
    else:
        x[i] = '0'

Submission status: Runtime Error

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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


def f(n):
    p = n % (bin(n).count('1'))
    if p == 0:
        return 1
    else:
        return f(p) + 1


def main(input, print):
    N = int(input())
    X = int(input(), 2)
    for i in reversed(range(N)):
        b = 1 << i
        a = X ^ b
        print(f(a))


if __name__ == '__main__':
    main(sys.stdin.readline, print)

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):
    s = 1
    x = x % c
    while x != 0:
        s += 1
        x = x % countbit(x)
    return s

def main():
    n = int(input())
    x = int(input(), 2)
    c = countbit(x)
    for i in range(n):
        y = x ^ (1<<(n-i-1))
        cc = (x >> (n-i-1)) & 1
        s = count(y, c - 1 if cc else c + 1)
        print(s)


main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# 整数の入力
N = int(input())
# 文字列の入力
X = input()
one = 0
intX = 0
bitnow = 1
for i in reversed(range(len(X))):
    if X[i] == '1':
        one += 1
        intX += bitnow
    bitnow *= 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 one == 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])