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:
def popcntdiv(a):
  return int(a,2) % a.count("1")

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

for i in range(n):
  ans = 0
  l = list(x)
  l[i] = str(1-int(l[i]))
  k = "".join(l)
  
  while k != "0":
    k = str(format(popcntdiv(k),"b"))
    ans += 1 
  print(ans)

Submission status: Runtime Error

Solution code:
a=int(input())
b=input()
c=int(b, 2)
print(c)
pop1=bin(c).count("1")
pop=pop1+2

list1=[1]*pop
for i in range(1,pop) :
  t=i
  count=0
  while(t!=0) :
    m=bin(t).count("1")

    t=t%m
    count+=1
  list1[i]+=count
print(list1)
for i in range(a) :
  if b[i]=='0' :
    s=(c+2**(a-i-1))%(pop1+1)

    print(list1[s])
  else :
    s = (c - 2 ** (a - i - 1)) % (pop1 - 1)

    print(list1[s])

Submission status: Runtime Error

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

cnt = 0
for i in range(N):
    if X[i] == "1":
        cnt += 1
    
down = [0] * N
up = [0] * N
ald = 0
alu = 0
for i in range(N):
    down[i] = pow(2, N-1-i, cnt-1)
    up[i] = pow(2, N-1-i, cnt+1)
    if X[i] == "1":
        ald += down[i]
        ald %= cnt-1
        alu += up[i]
        alu %= cnt+1

for i in range(N):
    if X[i] == "1":
        n = (ald - down[i]) % (cnt-1)
    else:
        n = (alu + up[i]) % (cnt+1)
    ans = 1
    while n != 0:
        c = 0
        for j in range(20):
            if (n >> j) % 2 == 1:
                c += 1
        n %= c
        ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
def countpop(n):
    return n.count('1')
def reverse(num,n):
    return num ^ (1<<n)
N = int(input())
X = int(input(),2)
count = 0
for i in range(N):
    T = X
    T = T ^ (1<<N-1-i)
    while True:
        T = T % bin(T).count('1')
        count += 1
        if(T == 0):
            print(count)
            break
    count = 0

Submission status: Runtime Error

Solution code:
import math
from copy import copy
di = {}
di[0] = 0
for i in range(1, 2*(10**6)+1):
    di[i] = 0
for i in range(1, 2*(10**6)+1):
    count = 0
    for j in range(int(math.log2(i))+4):
        if (i>>j)&1:
            count += 1
    di[i] = di[i%count] + 1
n = int(input())
x = list(input())
x.reverse()
count = 0
for i in x:
    if i =='1':
        count += 1
mod_p = count + 1
mod_m = count - 1
di_p = {}
di_m = {}
for i in range(n):
    di_p[i] = pow(2, i, mod_p)
    if mod_m <= 0:
        continue
    di_m[i] = pow(2, i, mod_m)
s_p = 0
s_m = 0
for i in range(n):
    if x[i] == '1':
        s_p += di_p[i]
        s_m += di_m[i]
for i in range(n-1, -1, -1):
    sm = copy(s_m)
    sp = copy(s_p)
    if x[i] == '1':
        sm -= di_m[i]
        sm %= mod_m 
        print(di[sm]+1)
    else:
        sp += di_p[i]
        sp %= mod_p
        print(di[sp]+1)

Submission status: Runtime Error

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

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

for n in range(N-1, -1, -1):
  xi = '{:b}'.format(int(X, 2) ^ 2**n)
  sub = 1
  cnt = 0
  while sub:
    cnt += 1
    sub = int(xi, 2) % popcount(xi)
    if sub:
      xi = '{:b}'.format(sub)
  print(cnt)

Submission status: Runtime Error

Solution code:
def resolve():
    #n=int(input())
    #a,b=map(int,input().split())
    #x=list(map(int,input().split()))
    #a=[list(map(lambda x:int(x)%2,input().split())) for _ in range(h)]

    def calc(x):#xは数字
        if x==0:
            return 0
        xn=x
        x=bin(x)[2:]
        cnt=sum(list(map(int,list(x))))
        return xn%cnt

    n=int(input())
    f=[]
    f.append(0)
    for i in range(1,2**18+1):
        f.append(f[calc(i)]+1)

    x=input()
    cnt=sum(list(map(int,list(x))))
    x=int(x,2)
    ans=[]
    for i in range(n):
        if x>>i&1:
            ans.append(f[(x-2**i)%(cnt-1)]+1)
        else:
            ans.append(f[(x+2**i)%(cnt+1)]+1)
    print(*ans[::-1],sep='\n')

if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

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

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-1,-1,-1):
    t=x^(2**(i))
    print(popcount(t,0))

Submission status: Runtime Error

Solution code:
n = int(input())
x = list(input())
y = int(''.join(x), 2)

memo = [0]


def popcount(p):
    return bin(p).count("1")


for i in range(1, n):
    tmp = i % popcount(i)
    memo.append(memo[tmp] + 1)

B = 2**(n-1)
for d in x:
    tmp = y
    if d == '0':
        tmp += B
    else:
        tmp -= B

    tmp = int(tmp)

    if tmp == 0:
        print(0)
        B /= 2
        continue

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

Submission status: Runtime Error

Solution code:
import itertools
n=int(input())
x=input()
l=[0]*n
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
for i in range(n-1):
	one=x.count('1')
	if x[i]=='0':
		y=x[:i]+'1'+x[i+1:]
		one+=1
	else:
		y=x[:i]+'0'+x[i+1:]
		one-=1
	t=getMod(y,len(y),one)
	c=1
	while t!=0:
		c+=1
		if t%(bin(t).count('1'))==0:
			break
		t=t%(bin(t).count('1'))
	l[i]=c

one=x.count('1')
if x[-1]=='0':
		y=x[:i]+'1'
		one+=1	
else:
		y=x[:i]+'0'
		one-=1	

t=getMod(y,len(y),one)
c=1
while t!=0:
		c+=1
		if t%(bin(t).count('1'))==0:
			break
		t=t%(bin(t).count('1'))
l[-1]=c
for i in range(len(l)):
	print(l[i])

Submission status: Runtime Error

Solution code:
n = int(input())
x = int(input(), 2)
max_value = 2 * 10 ** 5 + 2
max_value = n + 1
popcount = [-1] * max_value
popcount[0] = 0
resultcount = [-1] * max_value
resultcount[0] = 0
for i in range(1, max_value):
    popcount[i] = bin(i).count('1')

for i in range(1, max_value):
    count = 0
    tmp = i
    while tmp != 0:
        if resultcount[tmp] != -1:
            count += resultcount[tmp]
            break
        tmp = tmp % popcount[tmp]
        count += 1
    resultcount[i] = count

for i in range(n):
    operator = 1 << (n - 1 - i)
    value = x ^ operator
    one_count = str(bin(value)).count('1')
    value = value % one_count
    if value == 0:
        print('1')
    else:
        print(resultcount[value] + 1)

Submission status: Runtime Error

Solution code:
from sys import stdin
from sys import setrecursionlimit
from collections import Counter, deque, defaultdict
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
import random

INF = int(1e10)
MOD = int(1e9 + 7)

def main():
    from builtins import int, map
    N = int(input())
    X = input()
    
    # 余りが0からN - 1
    Xpc = X.count("1")
    iX = int(X, 2)
    rem_groups = [0] * (200_001)
    for k in range(1, N):
        rem_groups[k] = k % bin(k).count("1")

    # ans = [-1] * (N + 1)
    for k in range(N - 1, -1, -1):
        # f(k)を計算
        Xk = iX ^ (1 << k)
        Xkpc = Xpc
        if (iX & (1 << k)) >> k:
            Xkpc -= 1
        else:
            Xkpc += 1
        ans = rem_groups[Xk % Xkpc] + 1 + (0 if Xk % Xkpc == 0 else 1)
        print(ans)



if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

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

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

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



count = X.count('1') #1の数

count1 = count - 1
count2 = count + 1

# print (count)
total1 = 0
total2 = 0

for i in range(N):
    if X[N - 1 - i] == '1':
        total1 += pow(2, i, count1)
        total1 %= (count1)

        total2 += pow(2, i, count2)
        total2 %= (count2)
# print ('total', total)

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

Submission status: Runtime Error

Solution code:
N = int(input())
x = input()
cnt_1 = x.count('1')
X = int(x, 2)

if cnt_1%2 == 1:
    if x[0] == '1':
        print(1)
    else:
        print(2)
    for i in range(1,N-1):
        t = x[n]
        if t == '1':
            print(2)
        else:
            print(1)
    if x[N-1] == '1':
        print(1)
    else:
        print(3)
else:
    for i in range(N):
        t = x[i]
        if t == '1':
            print(1)
        else:
            print(2)

Submission status: Runtime Error

Solution code:
from collections import Counter
from copy import deepcopy

N = int(input())
bin_X = input()
dec_X = int(bin_X, 2)
X = list(bin_X)
total = Counter(X)['1']
amari_table = [None] * (total + 2)
amari_table[0] = 1
for i in range(N):
    tmp_total = deepcopy(total)
    if X[i] == '1':
        tmp_total -= 1
        tmp_dec_X = dec_X - 2 ** (N - i - 1)
    else:
        tmp_total += 1
        tmp_dec_X = dec_X + 2 ** (N - i - 1)
    amari = tmp_dec_X % tmp_total
    if amari_table[amari] is not None:
        print(amari_table[amari])
    else:
        count = 1
        orig_amari = deepcopy(amari)
        while True:
            tmp_total = Counter(bin(amari))['1']
            amari %= tmp_total
            count += 1
            if amari == 0:
                break
        amari_table[orig_amari] = count
        print(count)

Submission status: Runtime Error

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


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

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


def f(n):
    if cache[n] != -1:
        return cache[n]
    if n == 0:
        return 0
    t = n % popcount(n)
    if t == 0:
        cache[n] = 1
    else:
        cache[n] = f(t) + 1
    return cache[n]

def g(n, m):
    if n < 60:
        return (1 << n) % m
    else:
        t = n // 2
        return g(t, m) * g(n - t, m) % m


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

c = X.count('1')
t1 = [0] * N
t2 = [0] * N
for i in range(N):
    n = N - 1 - i
    t1[i] = g(n, c - 1)
    t2[i] = g(n, c + 1)

x1, x2 = 0, 0
for i in range(N):
    if X[i] == '1':
        x1 += t1[i]
        x2 += t2[i]

result = []
for i in range(N):
    if X[i] == '1':
        n = x1 - t1[i]
        n %= c - 1
    elif X[i] == '0':
        n = x2 + t2[i]
        n %= c + 1
    result.append(f(n) + 1)
print(*result, sep='\n')

Submission status: Runtime Error

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

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

p = [-1 for _ in range(2*(10**6)+1)]
cnt = x.count('1')

def calc(a):
  #print('a=',a)
  if p[a] != -1:
    return p[a]
  else:
    if a == 0:
      ret = 0
    else:
      b = bin(a).count('1')
      ret = 1+calc(a%b)
    p[a] = ret
    return ret

x0 = int(x,2)%(cnt-1)
x1 = int(x,2)%(cnt+1)
xx0 = [1]
for i in range(n+1):
  xx0.append((xx0[-1]*2)%(cnt-1))
xx1 = [1]
for i in range(n+1):
  xx1.append((xx1[-1]*2)%(cnt+1))

y = list(x)  
for i in range(n):
  if y[i] == '0':
    xx = xx1[n-i-1]
    print(calc((x1+xx)%(cnt+1))+1)
  else:
    xx = xx0[n-i-1]
    print(calc((x0-xx)%(cnt-1))+1)

Submission status: Runtime Error

Solution code:
import collections
N=int(input())
X=list(input())
X=list(map(int,X))
#print(X)
ans1=0
ans2=0
c=collections.Counter(X)
div=c[1]
for i in range(N):
    ans1=(ans1+X[i]*pow(2,N-i-1,div+1))%(div+1)
    ans2=(ans2+X[i]*pow(2,N-i-1,div-1))%(div-1)
    #print(ans1)
#print(ans1,div+1)
#print(ans2,div-1)
#ここまででXについてのXのbit数、X%(Xのbit数)がわかる
for i in range(N):
    cnt = 1
    if (X[i]==0):
        num=(ans1+pow(2,N-i-1,div+1))%(div+1)
        #print(num)
    else:
        num=(ans2+div-1-pow(2,N-i-1,div-1))%(div-1)
        #print(num)
    while num != 0:
        di = 0
        for j in range(18):
            if (num >> j)&1 == 1:
                di = di + 1
        num = num % di
        cnt = 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):
    x = n % popcount(n)
    if x > 0:
        return 1+f(x)
    else:
        return 1

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:
# x^n % mod
def pow_k(x, n, mod):
  if n == 0:
    return 1

  K = 1
  while n > 1:
    if n % 2 != 0:
      K = (x * K) % mod
        
    x = (x * x) % mod

    n //= 2

  return (x * K) % mod

def func(dic, n):
  
  if n in dic:
    return dic[n]
  
  if n == 0:
    return 0
  
  t = bin(n)
  tmp = len(t) - len(t.replace('1','' ))

  n2 = n % tmp
    
  dic[n] = 1 + func(dic, n2)
  
  return dic[n]


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

num1 = len(x.replace('0', ''))

x_rev = list(reversed(x))

array_minus = [-1] * n
array_plus = [-1] * n

minus = 0
plus = 0
for i in range(n):
  if x_rev[i] == '0':
    array_minus[i] = 0
    array_plus[i] = 0
  
  else:
    array_minus[i] = pow_k(2, i, num1-1)
    minus += array_minus[i]
    minus %= num1-1
    array_plus[i] = pow_k(2, i, num1+1)
    plus += array_plus[i]
    plus %= num1+1
    
dic = {}
for i in range(n):
  if x[i] == '0':
    tmp = pow_k(2, n-1-i, num1+1) + plus
    tmp %= num1+1
  
  else:
    tmp = minus - array_minus[n-i-1]
    tmp %= num1 -1
    
  print(func(dic, tmp)+1)

Submission status: Runtime Error

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

s = int(tmp, 2)
nn = sum([int(a) for a in tmp if a == '1'])


def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f  # 8bitごと
    x = x + (x >> 8)  # 16bitごと
    x = x + (x >> 16)  # 32bitごと
    x = x + (x >> 32)  # 64bitごと = 全部の合計
    return x & 0x0000007f


def division_binary_shift(a, b):
    """
    a // b

    :param a: dividend
    :param b: divisor
    :return: quotient
    """
    if a < b:
        return 0
    if b == 0:
        raise ZeroDivisionError

    q = 0
    sq = 1
    ori_b = b
    while a >= b:
        b <<= 1
        if a >= b:
            sq <<= 1
        else:
            b >>= 1
            a -= b
            q += sq
            sq = 1
            b = ori_b

    return q


for i in range(n):
    ss = s ^ (1 << (n-i-1))
    c = 0
    t = popcount(ss)
    while ss != 0:
        ss -= t*division_binary_shift(ss, t)
        t = popcount(ss)
        c += 1
    print(ss, popcount(ss), c)
    print(c)

Submission status: Runtime Error

Solution code:
N=int(input())
X=input()
Xint = int(X, 2)
res = [0]*N
bc = X.count('1')
amari_1 = Xint%bc
amari_2 = Xint%(bc+1)
amari_3 = Xint%(bc-1)
first = [0]*N
for i in range(N):
    bc_tmp = bc
    if X[i]=='1':
        first[i] = (amari_3 - pow(2,N-i-1,bc-1))%(bc-1)
    else:
        first[i] = (amari_2 + pow(2,N-i-1,bc+1))%(bc+1)
for i in range(N):
    c = 1
    tmp = first[i]
    if tmp==0:
        print(1)
        continue
    while 1:
        bc = bin(tmp).count('1')
        tmp = tmp%bc
        c += 1
        if tmp == 0:
            res[i] = c
            print(c)
            break

Submission status: Runtime Error

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

def popcnt(n):
    return n.count("1")


for i in range(n):
    if x2[i] == "0":
        x2[i] = "1"
    else:
        x2[i] = "0"
    #x2.insert(0,'0')
    #x2.insert(1,"b")
    a = (''.join(x2))
    p = popcnt(a)
    xx = int(a,2)
    ans = 0
    for i in range(1,10**5):
        xx = int(bin(xx % p), 2)
        if xx == 0:
            print(i)
            break
        else:
            p = popcnt(str(xx))
        if p ==0:
            print(i+1)
            break

    x2 = list(copy.deepcopy(x))

Submission status: Runtime Error

Solution code:
import numpy as np

def popcount(n):
    s = 0
    while 0 < n:
        s += n%2
        n = int(n/2)
    return s

def func(n):
    s = 0
    while 0 < n:
        n = n % popcount(n)
        s += 1
    return s


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

p = 0
for x in X:
    p += int(x)



Xi = np.zeros(N)
for i in range(N):  # i桁目
    for j in range(N):
        if i == j:
            Xi[j] += (1-int(X[i])) * 2**(N-i-1)
        else:
            Xi[j] += int(X[i])   * 2**(N-i-1)


A = np.zeros(N)
for i in range(N):
    A[i] = func(int(Xi[i]))


for a in A:
    print(int(a))

Submission status: Runtime Error

Solution code:
import sys
#import string
#from collections import defaultdict, deque, Counter
#import bisect
#import heapq
#import math
#from itertools import accumulate
#from itertools import permutations as perm
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as combr
#from fractions import gcd
#import numpy as np
import copy

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

def solve():
    n = int(stdin.readline().rstrip())
    X = str(stdin.readline().rstrip())
    #A, B, C = map(int, stdin.readline().rstrip().split())
    #l = list(map(int, stdin.readline().rstrip().split()))
    #numbers = [[int(c) for c in l.strip().split()] for l in sys.stdin]
    #word = [stdin.readline().rstrip() for _ in range(n)]
    #number = [[int(c) for c in stdin.readline().rstrip()] for _ in range(n)]
    #zeros = [[0] * w for i in range(h)]
    X = list(X)
    for i in range(n):
        x = copy.deepcopy(X)
        if x[i] == "0":
            x[i] = "1"
        else:
            x[i] = "0"
        bind = "".join(x)
        d = int(bind,2)
        ans = 0
        while d >= 0:
            c = bind.count("1")
            d = int(bind,2)
            d = d%c
            bind = bin(d)
            if d==0:
                print(ans+1)
                break
            else:
                ans += 1



if __name__ == '__main__':
    solve()

Submission status: Runtime Error

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

outf = {}
res = []

dec_d = {}
def get_dec(bin):
  if bin in dec_d.items():
    return dec_d[bin]
  s = 0
  seed = 2 ** (len(bin)-1)
  for el in bin:
    if el == '1':
      s += seed
    seed = seed // 2
  dec_d[bin] = s
  return s

bin_d = {}
def get_bin(dec):
  if dec in bin_d.items():
    return bin_d[dec]
  s = ''
  while dec > 0:
    if dec % 2 == 1:
      s = s + '1'
    else:
      s = s + '0'
    dec = dec // 2
  bin_d[dec] = s
  return s

pop_d = {}
def popcount(n):
  if n in pop_d.items():
    return pop_d[n]
  out = 0
  while n > 0:
    if n % 2 == 1:
      out += 1
    n = n // 2
  pop_d[n] = out
  return out


for i in range(n):
  if x[i] == '0':
    x = x[:i] + '1' + x[i+1:]
  else:
    x = x[:i] + '0' + x[i+1:]
  x_dec = get_dec(x)
  res.append(x_dec)

  # calc f
  kp = []
  f = 0
  while x_dec > 0:
    st = get_bin(x_dec)
    if st in outf.items():
      f += outf[st]
      break
    kp.append(x_dec)
    f += 1
    pc = popcount(x_dec)
    x_dec = x_dec % pc

  # keep
  lf = f
  for k in kp:
    st = get_bin(k)
    outf[st] = lf
    lf -= 1

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


for i in res:
  st = get_bin(i)
  print(outf[st])

Submission status: Runtime Error

Solution code:
import numpy as np

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

t = [0]

pl = np.array([1])
tmp = [np.array([1])]
for i in range(18):
    ne = np.concatenate([tmp[-1], tmp[-1]+1])
    tmp.append(ne)
pl = np.concatenate(tmp)


for n in range(1, int((N+1)/10)):
    c = pl[n-1]
    t.append(1 + t[n%c])


base = X.count("1")
basex = int(X, 2)
for n in range(N):
    if X[n] == "0":
        c = base + 1
        x = basex + 2**(N-n-1)
    else:
        c = base - 1
        x = basex - 2**(N-n-1)
    
    if c == 0:
        print(0)
    else:
        print(1 + t[x%c])

Submission status: Runtime Error

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

def n2(N):
  res = ''
  n=N
  while n>0:
    if n%2==0:
      res = '0' + res
    else:
      res = '1' + res
    n = n//2
  return res

def p(N):
  n=sum(int(x) for x in list(n2(N)))
  return n

N=int(input().rstrip('\n'))
X=[int(x) for x in list(input().rstrip('\n'))]
if all(x==0 for x in X):
  for x in range(N):
    print(0)
else:
  xm=sum((2**(N-y-1))*z for y,z in zip(range(N),X))
  for i in range(N):
    if X[i]==0:
      xn=xm+2**(N-i-1)
    else:
      xn=xm-2**(N-1-i)
    res = 0
    while 5572>573:
      xn=xn%p(xn)
      res += 1
      if xn==0:
        break
    print(res)

Submission status: Runtime Error

Solution code:
import itertools
import sys
input = sys.stdin.readline


def f(A):
    ans = 0
    X = int(A, 2)
    for i in itertools.count():
        pc = bin(X).count('1')
        X = X % pc
        ans += 1
        if X == 0:
            break
    print(ans)


N = int(input())
A = int(input().rstrip(), 2)
for i in itertools.count(start=N-1, step=-1):
    AA = bin(A ^ (1 << i))
    f(AA)
    if i == 0:
        break

Submission status: Runtime Error

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

import heapq
from collections import defaultdict, deque
from math import ceil, factorial, gcd
from itertools import accumulate, permutations
from copy import deepcopy

import bisect
# ----------

INF = float("inf")
MOD = 10 ** 9 + 7
# ----------

N = int(input())
X = input().strip()
L = list(X)

D = defaultdict(int)
D[0] = 0

def f(x, ans):
    ans += 1
    b = str(bin(x)[2:])
    c = b.count('1')
    m = x % c
    if m == 0:
        return ans
    return f(m, ans)


for i in range(1, 200001):
    D[i] = f(i, 0)


for i in range(N):
    LL = deepcopy(L)
    if L[i] == '1':
        LL[i] = '0'
    else:
        LL[i] = '1'
    x = ''.join(LL)
    n = int(x, 2)
    print(f(n, 0))

Submission status: Runtime Error

Solution code:
import bisect
import sys
import math
from collections import deque
from heapq import heappush, heappop

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))


INF = 1 << 29

DIV = (10**9) + 7
#DIV = 998244353

def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        finv[i] = finv[i-1]*inv[i] % mod

    class CONV:
        def __init__(self):
            self.fac = fac
            self.finv = finv
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % DIV) % DIV

    return CONV()


def cumsum(As):
    s = 0
    for a in As:
        s += a
        yield s


sys.setrecursionlimit(200005)


def dijkstra(G,start=0):
    heap = []
    cost = [INF]*len(G)
    heappush(heap,(0,start))
    while len(heap)!=0:
        c,n = heappop(heap)
        if cost[n] !=INF:
            continue
        cost[n]=c
        for e in G[n]:
            ec,v = e
            if cost[v]!=INF:
                continue
            heappush(heap,(ec+c,v))
    return cost


def main():
    cache={"0":0}
    def modPC(s):
        pc = sum([c == '1' for c in s])
        lpc = len(bin(pc)[2:])
        mod_now = 1
        ans = 0
        for cidx in range(0,len(s),lpc):
            part_s = s[max(len(s)-cidx-lpc,0):len(s)-cidx]
            ans+=(int(part_s,2)*mod_now)%pc
            ans=ans%pc
            mod_now = (mod_now*(2**(lpc)))%pc
        return ans%pc
    def f(s,cur=0):
        if s in cache:
            return cache[s]
        next_s = bin(modPC(s))[2:]
        ret = f(next_s,cur+1)+1
        cache[s]=ret
        return ret
    N=iRaw()
    Xs=sRaw()
    for n in range(N):
        xl = [x for x in Xs]
        xl[n]="1" if xl[n]=="0" else "0"
        print(f("".join(xl)))

main()

Submission status: Runtime Error

Solution code:
def resolve():
    #n=int(input())
    #a,b=map(int,input().split())
    #x=list(map(int,input().split()))
    #a=[list(map(lambda x:int(x)%2,input().split())) for _ in range(h)]

    def calc(x):#xは数字
        xn=x
        x=bin(x)[2:]
        cnt=sum(list(map(int,list(x))))
        return xn%cnt

    n=int(input())
    f=[]
    f.append(0)
    for i in range(1,2**18+1):
        f.append(f[calc(i)]+1)

    x=input()
    cnt=sum(list(map(int,list(x))))
    x=int(x,2)
    ans=[]
    for i in range(n):
        if x>>i&1:
            ans.append(f[(x-2**i)%(cnt-1)]+1)
        else:
            ans.append(f[(x+2**i)%(cnt+1)]+1)
    print(*ans[::-1],sep='\n')

if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

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

Y = int(X, 2)
Z = list(map(int,list(X)))
X_1 = bin(Y).count("1")
X_1m = X_1-1
X_1p = X_1+1
Ym = Y%X_1m
Yp = Y%X_1p


temp = []
for i in range(200010):
    ans = 0
    while i > 0:
        i %= bin(i).count("1")
        ans += 1
    temp.append(ans)

temp2p = []
temp2m = []
ansp = 1
ansm = 1
for i in range(200010):
    ansp %= X_1p
    ansm %= X_1m
    temp2p.append(ansp)
    temp2m.append(ansm)
    ansp *= 2
    ansm *= 2    

for i in range(N):
    if Z[i]==0:
        Xi = Yp + temp2p[(N-i-1)]
        Xi %= X_1p
        
        print(1+temp[Xi])
    else:
        Xi = Ym - temp2m[(N-i-1)]
        Xi %= X_1m
        print(1+temp[Xi])

Submission status: Runtime Error

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

n= int(input())
a=list(input())

v=a.count('1')

ans=[0]*n
A=[0]*n
# n以下の残り回数を記録
for i in range(n):
    x=i
    cnt=0
    while x>0:
        cnt+=1
        r = 0
        for j in range(10):
            if (x>>j)&1:
                r+=1
        x=x%r
    ans[i]=cnt

# 各桁をv＋１で割ったあまり
q = [0]*n
# 各桁をv-1で割ったあまり
r = [0]*n
for i in range(n):
    if a[i]=='1':
        if v!=0:
            q[i] = pow(2, n-i-1) % (v + 1)
        if v!=1:
            r[i] += pow(2, n-i-1) % (v - 1)
qq=sum(q)
rr=sum(r)

for i in range(n):
    if a[i]=='1':
        if v!=1:
            z = rr - pow(2,n-i-1)%(v-1)
            cnt = z % (v - 1)
            A[i] = 1 + ans[cnt]
    else:
        z=qq+pow(2,n-i-1)%(v+1)
        cnt=z%(v+1)
        A[i]=1+ans[cnt]

for i in A:
    print(i)

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
M = X.count("1")
List = []
for i in range(N):
  c = 1
  while i>0:
    i = i%bin(i).count("1")
    c += 1
  List.append(c)
for i in range(N):
  if X[i]=="0":
    R = X[:i]+"1"+X[i+1:]
    R = (int(R, 2))%(M+1)
  else:
    R = X[:i]+"0"+X[i+1:]
    R = (int(R, 2))%(M-1)
  print(List[R])

Submission status: Runtime Error

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

def popcount(n):
    ans = 0
    while True:
        i = bin(n).count("1")
        n = n % i
        ans += 1
        if n == 0:
            return ans
        
def hanten(XX, n):
    if XX[n] == "1":
        XX[n] = "0"
    else:
        XX[n] = "1"
    return int("".join(XX),2)

for i in range(N):
    XX = list(X)
    print(popcount(hanten(XX,i)))

Submission status: Runtime Error

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

if N == 1:
    if X == "1":
        print(0)
        exit()
    else:
        print(1)
        exit()

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

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