Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

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

Constraints

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

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

Input

Input is given from Standard Input in the following format:

N
X

Output

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

Sample Input 1

3
011

Sample Output 1

2
1
1

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

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

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

Sample Input 2

23
00110111001011011001110

Sample Output 2

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



Sample input:
3
011


Sample output:
2
1
1

Submission status: Runtime Error

Solution code:

import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby
from heapq import heapify, heappush, heappop

# sys.setrecursionlimit(5000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return map(lambda x: x + d, A)
def ldec(A, d=1): return map(lambda x: x - d, A)

N = n1()
X = int(s1(), 2)

def flip(n, i):
    return n ^ (1 << i)

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

dp = {}

def search(n):
    if n == 0:
        return 0

    if n in dp:
        return dp[n]

    m = n % popcount(n)
    t = search(m) + 1
    dp[n] = t
    return t


#for i in range(1, 10):
#    print(search(i))

buf = ""
for i in range(N-1, -1, -1):
    buf += search(flip(X, i)) + "\n"

print(ans)

Submission status: Runtime Error

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

def popcount(n):
    cnt = 0
    for i in range(n):
        g = len(bin(n))-2
        n = n%g
        cnt += 1
        if n == 0:
            break
    return cnt

for i in range(n):
    if x[i] == '1':
        x[i] = '0'
    else:
        x[i] = '1'
    a = int(x, 10)
    print(popcount(a))
    if x[i] == '1':
        x[i] = '0'
    else:
        x[i] = '1'

Submission status: Runtime Error

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

dp = [0] * (n+1)

for i in range(1,n+1):
    tmp = bin(i).count("1")
    dp[i] = dp[i%tmp] + 1

t = x.count('1')
po = []

for i in range(n):
    t1 = t
    if x[i] == '1':
        t1 -= 1
    else:
        t1 += 1
    po.append(t1)

t21 = 0
t22 = 0

for i in range(n):
    if x[i] == '1':
        t21 += pow(2, (n-i-1), t-1)
        t22 += pow(2, (n-i-1), t+1)
        t21 %= t-1
        t22 %= t+1

for i in range(n):
    if x[i] == '1':
        t3 = t21
    else:
        t3 = t22
    if x[i] == '1':
        t3 -= pow(2, (n-i-1), po[i])
    else:
        t3 += pow(2,(n-i-1), po[i])
    print(dp[t3%po[i]]+1)

Submission status: Runtime Error

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


N = int(input())
X = input()
X2 = int(X, 2)
popcount = popcount(X2)
prev = X[0]

for i in range(N-1, -1, -1):
    bit = X[N-i-1]
    if bit == prev:
        pop = popcount
    elif bit > prev:
        pop = popcount - 1
    else:
        pop = popcount + 1
    prev = bit
    ans = 1
    Y = X2 ^ (1 << i)
    Y %= pop
    while Y > 0:
        Y %= popcount(Y)
        ans += 1
    print(ans)

Submission status: Runtime Error

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


l = [0] * 2 * 100010
memo = [-1] * 2 * 100010

def popcount(num):
    return bin(num).count('1')

def get_cnt(now):
    cnt = 0
    tmp_list = []
    while True:
        if memo[now] != -1:
            #regist_memo(tmp_list, memo[now])
            return memo[now]
        else:
            tmp_list.append(now)
        now = now % popcount(now)
        cnt += 1
        if now == 0:
            break
    regist_memo(tmp_list, cnt)
    return cnt

def regist_memo(l, cnt):
    for tmp in l:
        memo[tmp] = cnt
        cnt = cnt -1

for i in range(1, n+1):
    # 反転させたbitを入れる
    now = x ^ (1 << n-i)
    cnt = get_cnt(now)
    l[i] = cnt

for i in range(1, n+1):
    print(l[i])

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from collections import Counter

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



n=int(input())
x=input()
d={}
j=[]
for i in range(n-):
  ans=0
  if x[i]=="1":
    y=x[:i]+"0"+x[i+1:]
  else:
    y=x[:i]+"1"+x[i+1:]
  c=int(y,2)
  a=int(y,2)

  while True:
    if a in d:
      j.append(d[a]+ans)
      print(d[a]+ans)
    b=count_ones_by_bin(a)
    if b==0 or a==0:
      d[c]=ans
      j.append(ans)
      print(couunt)
      break
    a%=b
    ans+=1

Submission status: Runtime Error

Solution code:
cnt = 0
def popcount(n):
	global cnt
	cnt += 1
	l = bin(n)[2:].count("1")
	if n % l == 0:
		return
	else:
		popcount(n%l)

p = [0]*10**6
for i in range(1,10**6):
	cnt = 0
	popcount(i)
	p[i] = cnt

for i in reversed(range(N)):
	X2 = X.copy()
	if X2[i]== "1":
		X2[i] = "0"
	else:
		X2[i] = "1"
	X3 = "".join(X2)
	#print(X3)
	print(p[int(X3,2)+1])

Submission status: Runtime Error

Solution code:
N = int(input())
X = input().strip()
C = X.count("1")
D = int(X, 2)
M = D % C
Mm, Mp = 0, D % (C+1)
if C > 0:
    Mm = D % (C-1)

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

for i in range(1, N+1):
    m = 0
    c = C
    if X[i-1] == "1":
        c -= 1
        if c == 0:
            print(0)
            continue
        m = Mm
        d = pow(2, N-i, c)
        d = (m-d+c) % c
    else:
        c += 1
        m = Mp
        d = pow(2, N-i, c)
        d = (m+d) % c

    print(p[d]+1)

Submission status: Runtime Error

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

def popcount(a):
    cnt = 0
    while True:
        y = bin(a).count("1")
        a %= y
        cnt += 1
        if n == 0:
            print(cnt)
            break

ans = 0
for i in range(len(X)):
    if X[i] == "1":
        X[i] = "0"
        Flag = True
    else:
        X[i] = "1"
        Flag = False
        
    x = "".join(X)
    n = int(x, 2)
    popcount(n)
            
    if Flag is True:
        X[i] = "1"
    else:
        X[i] = "0"

Submission status: Runtime Error

Solution code:
def popcount(x):
    x = x - ((x >> 1) & 0x55555555)

    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    return x & 0x0000007f

N = int(input())
X = int(input(),2)
counts = 0

for i in range(1,N+1,1):
    count = 0
    Xi = X ^ 2**(N-i)
    while Xi!=0:
        count+=1
        #popcount
        #Xi = Xi%bin(Xi).count("1")
        Xi = Xi % popcount(Xi)
    counts.append(count)

for k in counts:
    print(k)

Submission status: Runtime Error

Solution code:
# coding: utf-8
# hello worldと表示する
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
n=I()
lis=list(SI())

#s="".join(list(map(str,lis)))
#print(s)
#sys.exit()
#print(lis)
#sys.exit()
orig=0
for i in range(n):
    if lis[i]=="0":
        lis[i]=0
    else:
        lis[i]=1
orcount=sum(lis)
#beki=[1 for i in range(n+1)]
#for i in range(n):
    #beki[i+1]=beki[i]*2
#print(beki)
#print(lis)
m1=0
m2=0
m3=0
for i in range(n):
    if lis[i]==1:
        m1=(m1*pow(2,n-i-1,orcount-1))%mod
        #m2=(m2*pow(2,n-i-1,orcount))%mod
        m3=(m3*pow(2,n-i-1,orcount+1))%mod
'''for i in range(n):
    j=n-i-1
    if lis[i]==1:
        orig+=pow(2,j)'''
#print(orig)
dp=[0 for i in range(n+1)]
dp[1]=1
for i in range(1,n):
    #u=count1(i+1)
    count=0
    j=0
    while pow(2,j)<=i+1:
        if ((i+1)>>j) %2==1:
            count+=1
        j+=1
    z=1
    dp[i+1]=z+dp[(i+1)%count]
#print(dp)
for i in range(n):
    if lis[i]==0:
        #num=orig+pow(2,n-i-1)
        pr=orcount+1
        num=m3+pow(2,n-i-1,pr)
    else:
        #num=orig-pow(2,n-i-1)
        pr=orcount-1
        num=m1+pow(2,n-i-1,pr)
    #print(num,pr)
    if pr==0:
        print(0)
    else:
        print(1+dp[num%pr])

Submission status: Runtime Error

Solution code:
def pop_count(T):
    T = (T & 0x55555555) + ((T >> 1) & 0x55555555)
    T = (T & 0x33333333) + ((T >> 2) & 0x33333333)
    T = (T & 0x0F0F0F0F) + ((T >> 4) & 0x0F0F0F0F)
    T = (T & 0x00FF00FF) + ((T >> 8) & 0x00FF00FF)
    T = (T & 0x0000FFFF) + ((T >> 16) & 0x0000FFFF)
    return T


N = int(input())
X = input()
cnt = X.count("1")

if cnt == 0:
    for _ in range(N):
        print(1)
    exit()
if cnt == 1:
    if X[-1] == "0":
        res = 0
    else:
        res = 1
    for i, x in enumerate(X):
        if x == "1":
            print(0)
        else:
            print(res)
    exit()


res = [0]*21
for i in range(1, 19):
    tmp = 0
    x = i
    while x:
        cnt = pop_count(x)
        x %= cnt
        tmp += 1
    res[i] = tmp


cnt = X.count("1")
Xrev = X[::-1]
sum01 = 0
sum10 = 0
memo01 = [0] * N
memo10 = [0] * N

for i, x in enumerate(Xrev):
    val01 = pow(2, i, cnt + 1)
    val10 = pow(2, i, cnt - 1)
    if x == "1":
        sum01 += val01
        sum01 %= cnt + 1
        sum10 += val10
        sum10 %= cnt - 1
    memo01[i] = val01
    memo10[i] = val10
memo01.reverse()
memo10.reverse()

for i, x in enumerate(X):
    if x == "0":
        p = (sum01 + memo01[i]) % (cnt + 1)
        print(1 + res[p])
    else:
        p = (sum10 - memo10[i] + cnt - 1) % (cnt - 1)
        print(1 + res[p])

Submission status: Runtime Error

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

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

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

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

main()

Submission status: Runtime Error

Solution code:
def GCDC(A,B):
    Count = 0
    while A!=0:
        Count += 1
        A = A%B
        B = AX[A]
    return Count
  
N  = int(input())
X  = input()
BX = int(X,2)
LX = [int(T) for T in X]
PX = sum(LX)

AX = [0]*(N+1)
for T in range(0,N):
    AX[T] = sum([int(Q) for Q in format(T,'b')])
Pr = [0]*N
for T in range(0,N):
    if NX[T]==1:
        Num   = BX-pow(2,N-T-1)
        Pop   = PX-1
        Pr[T] = GCDC(Num,Pop)
    else:
        Num   = BX+pow(2,N-T-1)
        Pop   = PX+1
        Pr[T] = GCDC(Num,Pop)
print('\n'.join(str(X) for X in Pr))

Submission status: Runtime Error

Solution code:
# Template 1.0
import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n = INT()

x = input()

k = x.count('1')

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

def getMod(_str, n, k):

    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

init2 = getMod(x, n, k-1)
init1 = getMod(x,n,k+1)

dp = [0,1,1,2,1,2,1,3,1,2,1,2,1,2,2,3,1,2]

for i in range(18, n+2**17):
    dp.append(1+dp[int(i%bin(i).count('1'))])

# print(init1,init2)

for i in range(n):
    if(x[i]=='0'):
        new = (init1 + 2**(n-i-1)%(k+1))%(k+1)
        # print(new)
        print(1 + dp[new])
    else:
        new = (init2 - 2**(n-i-1)%(k-1))%(k-1)
        print(1 + dp[new])

Submission status: Runtime Error

Solution code:
def f(n):
    if n == 0:
        return 0
    elif n in d:
        return d[n]
    else:
        popcount = str(bin(n)).count('1')
        d[n] = max(1, f(n % popcount) + 1)
        return d[n]

n = int(input())
x = list(map(str, (input())))
X = int(''.join(x), 2)
d = {}
for i in range(n):
    if x[i] == '1':
        xx = X - 2 ** (n-i)
    else:
        xx = X + 2 ** (n-i)
    xx = int(s, 2)
    print(f(xx))

Submission status: Runtime Error

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

n = int(input())
x = list(input())
popcount = x.count('1')
stock = [1] * (n + 1)

for i in range(1, n + 1):
    stock[i] = stock[i - 1] * 2


for i in range(n):
    tmp = x.copy()
    tmp2 = popcount
    if tmp[i] == '1':
        tmp[i] = '0'
        tmp2 -= 1
    else:
        tmp[i] = '1'
        tmp2 += 1
    num = 0
    if tmp[i] == '0':
        for i in range(n):
            num += tmp[i] * stock[i]
    
    if tmp2 == 0:
        print(0)
    elif num>0 andnum % tmp2 == 0:
        print(1)
    elif tmp[n - 1] == '1' and tmp2 % 2 == 0 and tmp2 > 2:
        print(3)
    else:
        print(2)

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
# N = 2 * 10 ** 5
# X = "10"*(10**5)
cnt = X.count('1')

base = int(X, 2)
if cnt == 1:
    base_m1 = 0
else:
    base_m1 = base % (cnt - 1)
base_p1 = base % (cnt + 1)

c = dict()
for i in range(N):

    if (X[i] == '1') and (cnt != 1):
        bins = (base_m1 - 2 ** (N - i - 1)) % (cnt - 1)
        nc = cnt - 1
    elif (X[i] == '1') and (cnt == 1):
        bins = 0
        nc = 0
    else:
        bins = (base_p1 + 2 ** (N - i - 1)) % (cnt + 1)
        nc = cnt + 1

    c[i] = 0
    while True:
        if nc == 0:
            break
        n = bins % nc
        c[i] += 1
        if n == 0:

            break

        bins = n
        nc = bin(n).count('1')

print("\n".join([c[i] for i in range(N)]))

Submission status: Runtime Error

Solution code:
# coding: utf-8

import sys

sys.setrecursionlimit(10000)


def bi(x, n_digit):
    output = ""
    for i in range(n_digit-1, -1, -1):
        if x >= 2**i:
            x -= 2**i
            output += "1"
        else:
            output += "0"
    return output


def popcount(bi_n):
    output = 0
    for c in bi_n:
        if c == "1":
            output += 1
    return output


def main():
    N = int(input())
    bi_X = input()

    fs = [None] * 25

    def rec(x):
        pop_x = popcount(bi(x, 25))
        r = x % pop_x
        if r == 0:
            return 1
        elif r < 25 and fs[r] is not None:
            return 1 + fs[r]
        else:
            return 1 + rec(r)

    for i in range(1, 25):
        fs[i] = rec(i)
    fs[0] = 0

    pop_X = popcount(bi_X)
    qp = pop_X+1
    qm = pop_X-1

    bi_qp = [None] * N
    bi_qm = [None] * N
    bi_qp[0] = 1 % qp
    bi_qm[0] = 1 % qm
    bi_qp[1] = 2 % qp
    bi_qm[1] = 2 % qm
    for i in range(2, N):
        bi_qp[i] = ((bi_qp[1])*(bi_qp[i-1])) % qp
        bi_qm[i] = ((bi_qm[1])*(bi_qm[i-1])) % qm

    rp = 0
    rm = 0
    for i in range(N):
        p = N-1-i
        coo = int(bi_X[i])
        rp = (rp + (((coo % qp) * bi_qp[p]) % qp)) % qp
        rm = (rm + (((coo % qm) * bi_qm[p]) % qm)) % qm

    for i in range(N):
        if bi_X[i] == "0":
            ri = (rp + bi_qp[N-1-i]) % qp
            if ri < 25:
                print(1 + fs[ri])
            else:
                pop_ri = popcount(bi(ri, 25))
                print(2 + fs[ri % pop_ri])
        else:
            ri = (rm - bi_qm[N-1-i]) % qm
            if ri < 25:
                print(1 + fs[ri])
            else:
                pop_ri = popcount(bi(ri, 25))
                print(2 + fs[ri % pop_ri])



main()
# print(main())

Submission status: Runtime Error

Solution code:
def main(N, X):
    lst = list(map(int, list(X)))
    num = lst.count(1)  # 初期状態で1を持つ数．

    def func(x):    # xは10進数
        lst = list(bin(x)[2:])
        amari =  x % lst.count('1')
        return amari

    d = {}
    for i in range(1, N):
        d[i] = func(i)


    # 反転させるので num + 1 か， num - 1 で割る場合しか存在しない．
    plus = []   # num + 1 で各桁 (2 ** n) を割った値を保存
    minus = []  # num - 1 で各桁 (2 ** n) を割った値を保存

    p = 1
    m = 1
    for n in range(N):
        p %= (num + 1)
        plus.append(p)
        m %= (num - 1)
        minus.append(m)
        p *= 2
        m *= 2

    o = int(X, 2)   # originalの 'o'
    amari_plus = o % (num + 1)
    amari_minus = o % (num - 1)

    for i in range(N):
        if lst[i] == 0:
            amari = (amari_plus + plus[N - i - 1]) % (num + 1)
        else:
            amari = (amari_minus + (num - 1) - minus[N - i - 1]) % (num - 1)
        ans = 1
        while amari != 0:
            amari = d[amari]
            ans += 1
        print(ans)




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

Submission status: Runtime Error

Solution code:
def func(Y):
    m = 0
    Y = int(Y, 2)
    while True:
        m += 1
        Y = Y % format(Y, 'b').count('1')
        if Y == 0:
            break
    return m
N = int(input())
X = '0b' + str(input())
for i in range(N):
    Y = X & ~pow(2, n) ｜ ~(X & pow(2, n))
    print(func(Y))

Submission status: Runtime Error

Solution code:
def fast_powmod(n, m):
    pow2 = 2
    result = 1
    while n > 0:
        if n % 2 == 1:
            result = (result * pow2) % m
        pow2 = (pow2 * pow2) % m
        n >>= 1

    return result

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

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

res = dict()
res[1] = 1
res[2] = 1
for i in range(3, 2 * 10**5 + 1):
    val = i % popcnt3(i)
    if val == 0:
        res[i] = 1
    else:
        res[i] = res[val] + 1

count = 0
for i in x:
    if i == "1":
        count += 1

x = x[::-1]
small = 0
big = 0
for i in range(len(x)):
    if x[i] == "1":
        small += fast_powmod(i, count - 1)
        big += fast_powmod(i, count + 1)

try:
    small %= count - 1
except:
    small = 0

    
big %= count + 1

anse = []
for i in range(len(x)):
    if x[i] == "1":
        done = False
        ans = 0
        cur = small - fast_powmod(i, count - 1)
        cur %= count - 1
        if cur == 0:
            anse.append(1)
        else:
            anse.append(res[cur] + 1)
    else:
        done = False
        ans = 0
        cur = big + fast_powmod(i, count + 1)
        cur %= count + 1
        if cur == 0:
            anse.append(1)
        else:
            anse.append(res[cur] + 1)


for i in anse[::-1]:
    print(i)
                
        
        
# print(small, big)

Submission status: Runtime Error

Solution code:
n=int(input())
x=list(input())
y=0
lis=[0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2]
for i in range(n):
    y+=int(x[i])

＃print(y)

for i in range(n):
    tempx=x
    tempx[i]=str(int(x[i]) ^ 1)
    if tempx[i]=='1':
        tempy=y+1
    else:
        tempy=y-1
    if i>0:
        tempx[i-1]=str(int(tempx[i-1]) ^ 1)

    #print(tempx,x)
    tempx="".join(tempx)

    #print(tempx)
    cnt=0

    while True:
        if int(tempx)==0:
            print(cnt)
            break
        tempx=format(int(tempx,2)%tempy,'b')
        #print(len(tempx))
        tempy=0
        #print(tempx,'koko')
        #print(type(tempx),len(tempx))
        for j in range(len(tempx)):
            tempy+=int(tempx[j])
        cnt+=1

Submission status: Runtime Error

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

d = [0]*(2**n)
d[0] = 1
d[1] = 1
d[2] = 2
i = 2
for _ in range(2**n):
    ii = 0
    i += 1
    for k in range((1 << (i-1)), 1 << i):
        if k == (1 << (i-1)):
            d[k-1] = 1
        else:
            d[k-1] += d[ii] + 1
            ii += 1

mod = [0]*(2**n)
for i in range(n):
    mod[i] = (i+1) % d[i]

for i in range(n):
    if int(x[i]):
        x = x[:i] + '0' + x[i+1:]
    else:
        x = x[:i] + '1' + x[i+1:]
    j = int(x, 2)
    cnt = 0
    while j != 0:
        j = mod[j-1]
        cnt += 1
    print(cnt)

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
X_list = []
for i in range(N):
    X_list.append(int(X[i]))


import math
def solve(x):
    count = 0
    while x != 1 or :
        tmp = int(math.log2(x))
        tmp += 1
        for i in range(tmp):
            if (x >> i) & 1 == 1:
                count += 1
        x = x%count
    return x

def solve2(x):
    tmp = X_list.copy()
    if tmp[x] == 1:
        tmp[x] = 0
    else:
        tmp[x] = 1
    num = 1
    ans = 0
    for i in range(N-1,-1,-1):
        ans += tmp[i]*num
        num = num*2
        
    return ans   

for i in range(N):
    tmp = solve2(i)
    ans = solve(tmp)
    print(ans)

Submission status: Runtime Error

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

map_dic = {
    '0': '1',
    '1': '0'
}
MAX_0101 = int('0x' + '5'*50000, 16)
MAX_0011 = int('0x' + '3'*50000, 16)
MAX_0000_1111 = int('0x' + '0f'*25000, 16)
MAX_0000_0000_1111_1111 = int('0b' + '0000000000001111'*12500, 2)
MASK_RES = int('0b' + '1'*18, 2)


def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)
    https://qiita.com/zawawahoge/items/8bbd4c2319e7f7746266 より
    '''
    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & MAX_0101)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & MAX_0011) + ((x >> 2) & MAX_0011)
    x = (x + (x >> 4)) & MAX_0000_1111  # 8bitごと
    x = (x + (x >> 8))
    x = (x + (x >> 16))
    x = (x + (x >> 32))
    x = (x + (x >> 64)) & MAX_0000_0000_1111_1111
    x = (x + (x >> 128))
    x = (x + (x >> 256))
    x = (x + (x >> 512))
    x = (x + (x >> 1024))
    x = (x + (x >> 2048))
    x = (x + (x >> 4096))
    x = (x + (x >> 8192))
    x = (x + (x >> 16384))
    x = (x + (x >> 32768))
    x = (x + (x >> 65536))
    x = (x + (x >> 131072))
    return x & MASK_RES


def f(x):
    cnt = 0
    while x > 0:
        # print(x, popcount(x), bin(x), "cnt=", cnt)
        x %= popcount(x)
        cnt += 1
    return cnt


for i in range(N):
    x_str = x[:i] + map_dic[x[i]] + x[i+1:]
    x_val = int(x_str, 2)
    print(f(x_val))

Submission status: Runtime Error

Solution code:
def popcount(n):
    ans = 0
    while (n > 0):
        ans += n % 2
        n = n // 2
    return ans


N = int(input())



X = int(input(), 2)

for i in range(N):
    Xi = X ^ (1 << (N-i-1))
    ans = 0
    while (xi > 0):
        Xi = Xi % popcount(Xi)
        ans += 1
    print(ans)

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'])
POPCOUNT_TABLE16 = [0] * 2**16
for index in range(len(POPCOUNT_TABLE16)):
    POPCOUNT_TABLE16[index] = (index & 1) + POPCOUNT_TABLE16[index >> 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 popcnt5(v):
    return (POPCOUNT_TABLE16[v & 0xffff] +
            POPCOUNT_TABLE16[(v >> 16) & 0xffff] +
            POPCOUNT_TABLE16[(v >> 32) & 0xffff] +
            POPCOUNT_TABLE16[(v >> 48)])


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


def division_binary_shift_m(a, b, m):
    """
    :param a: dividend
    :param b: divisor
    :param m: maximum bit capacity
    :return: quotient
    """
    if a < b:
        return 0
    if b == 0:
        raise ZeroDivisionError

    q = 0
    sb = b << m
    rem = a  # remainder (init is dividend)
    while rem >= b:
        while sb > rem:
            sb = sb >> 1
            m = m - 1

        q = q + (1 << m)
        rem = rem - sb

    return q


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

Submission status: Runtime Error

Solution code:
import sys

def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))
def RN(N): return [input().strip() for i in range(N)]


def main():
    N = II()
    Xstr = str(input())
    X = int(Xstr)


    for i in range(N):
        Xi = Xstr
        if Xstr[i] == "0":
            Xi = Xi[:i] + '1' + Xi[i+1:]
        elif Xstr[i] == "1":
            Xi = Xi[:i] + '0' + Xi[i+1:]
        
        n = 0
        for j in range(N):
            if Xi[j] == "1":
                n += 2**(N-1-j)

        n10 = n
        n2 = int(bin(n))
        ans = 0
        while True:
            n2str = str(n2)
            kazu1 = n2str.count("1")
            n10 = n10 % kazu1
            ans += 1
            if n10 == 0:
                break
            n2 = bin(n10)
        print(ans)




if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()

X = list(map(int, list(input())))
bit_num = sum(x==1 for x in X)
bp = [0]*N
bm = [0]*N
for i in range(N):
    if X[i]:
        bp[i] = pow(2, N-1-i, bit_num+1)
        bm[i] = pow(2, N-1-i, bit_num-1)
flag = sum(X) == 1
ans = [0]*N
for i in range(N):
    if X[i]:
        if flag:
            ans[i] = 0
            continue
        s = sum(bm)
        s -= bm[i]
        b = bit_num-1
        s %= b
        cnt = 1
        tmp = s
        nex = list(map(int, "{:b}".format(s)))
        b = sum(x==1 for x in nex)
        while tmp:
            for j in range(len(nex)):
                if nex[-(j+1)]:
                    tmp += pow(2, j, b)
                    tmp %= b
            nex = list(map(int, "{:b}".format(tmp)))
            b = sum(x==1 for x in nex)
            cnt += 1
    else:
        s = sum(bp)
        b = bit_num+1
        s += pow(2, N-i-1, bit_num+1)
        s %= b
        cnt = 1
        tmp = s
        nex = list(map(int, "{:b}".format(s)))
        b = sum(x==1 for x in nex)
        while tmp:
            for j in range(len(nex)):
                if nex[-(j+1)]:
                    tmp += pow(2, j, b)
                    tmp %= b
            nex = list(map(int, "{:b}".format(tmp)))
            b = sum(x==1 for x in nex)
            cnt += 1
    ans[i] = cnt

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