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

memo = dict()
memo["0"] = 0

def f(x):
    if x in memo:
        return memo[x]
    val = int(x, 2) % x.count("1")
    v = bin(val)[2:]
    memo[x] = f(v) + 1
    return memo[x]
    
ans = []
for i in range(N):
    if X[i] == "0":
        x = X[:i] + "1" + X[i+1:]
    else:
        x = X[:i] + "0" + X[i+1:]
    ans.append(f(x))

for v in ans:
    print(v)

Submission status: Runtime Error

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


def read():
    N = int(input().strip())
    X = input().strip()
    return N, X


def strdiv(X, k, d):
    P = 0
    q = 0
    for i in range(len(X)):
        q <<= 1
        if i == k:
            q |= 1-int(X[i])
        else:
            q |= int(X[i])
        p, q = divmod(q, d)
        # 商
        P <<= 1
        P |= p
    return P, q


def solve(N, X):
    B = sum([1 for a in X if a == "1"])
    if B == 0:
        return 0
    for k in range(N):
        if X[k] == "0":
            b = (B + 1)
        else:
            b = (B - 1)
        ans = 0
        x = X
        q = 1
        while q > 0:
            p, q = strdiv(x, k, b)
            ans += 1
            x = bin(q)[2:]
            b = sum([1 for a in x if a == "1"])
            k = -1
        print(ans)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Runtime Error

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

k=0
for i in range(N):
  if X[i]=="1":
    k+=1

A=int(X,2)
#apは0->1の時の一回目の変換の値。
ap=A%(k+1)
am=A%(k-1)

popc_list=[-1]*(k+3)

def F(num):
  if num==0:
    return 0
  if popc_list[num]!=-1:
    return popc_list[num]
  
  popc=0
  for i in range(10000000):
    if num>>i==1:
      popc+=1
    if num>pow(2,i):
      break
  popc_list[num]=F(num%popc)+1
  return popc_list[num]
  

for i in range(N):
  if X[i] == "0":
    print(F((ap+pow(2,N-i,k+1))%(k+1))+1)
  else:
    print(F((am+pow(2,N-i,k-1))%(k-1))+1)

Submission status: Runtime Error

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

popcount = [0] * 30
co = [0] * 30
for i in range(1,30):
    a = bin(i)[2:]
    cnt = a.count('1')
    popcount[i] = i % cnt

for i in range(1,30):
    cnt = 1
    nex = popcount[i]
    while nex != 0:
        nex = popcount[nex]
        cnt += 1
    co[i] = cnt

for i in range(N):
    x = X.copy()
    x[i] = '1' if x[i] == '0' else '0'
    x = ''.join(x)
    num = x.count('1')
    if num == 0:
        print(0)
        break
    pop = int(x,2) % num
    ans = co[pop] + 1
    print(ans)

Submission status: Runtime Error

Solution code:
def popcount(n):
    cnt = 0
    while True:
        answer = divmod(n, 2)
        if answer[1] == 1:
            cnt += 1
        n = answer[0]
        if n == 0:
            break
    return cnt

def f(n):
    cnt = 0
    while True:
        cnt += 1
        n = n % popcount(n)
        if n == 0:
            break
    return cnt

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

N = int(input())
X = input()
x10 = int(X,2)
for i in reversed(range(N)):
    n = toggle_nth_bit(x10, i)
    print(f(n))

Submission status: Runtime Error

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

for i in range(n):
	x = list(s)
	if x[i] == "0":
		x[i] = "1"
	else:
		x[i] = "0"
	x = "".join(x)
	
	count = x.count("1")
	x = "0b"+x
	inte = int(x,2)
	q,r = divmod(inte,count)
	total = 0
	while r != 0:
		co1 = str(bin(r)).count("1")
		q,r = divmod(r,co1)
		total += 1
	print(total + 1)
		# count = x.count("1")
		# x = "0b"+x
		# inte = int(x,2)
		# q,r = divmod(inte,count)

Submission status: Runtime Error

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

def calc(S, L):
    cnt = 0
    for i in range(L):
        if S[i] == "1":
            cnt += 1

    a_1 = 1
    r_1 = [0] * (L+1)
    for i in reversed(range(L)):
        r_1[i] = (r_1[i+1] + int(S[i]) * a_1) % cnt
        a_1 = (a_1 * 2) % cnt

    return r_1[0]

def calc_first(S, L):
    cnt = 0
    for i in range(L):
        if S[i] == "1":
            cnt += 1

    a_1 = 1
    a_2 = 1
    r_1 = [0] * (L+1)
    r_2 = [0] * (L+1)
    for i in reversed(range(L)):
        r_1[i] = (r_1[i+1] + int(S[i]) * a_1) % (cnt+1)
        r_2[i] = (r_2[i+1] + int(S[i]) * a_2) % (cnt-1)

        a_1 = (a_1 * 2) % (cnt + 1)
        a_2 = (a_2 * 2) % (cnt - 1)

    for i in range(L):
        if S[i] == "0":
            ans = (r_1[0] - r_1[i] + r_1[i+1] + pow(2, N-i-1, (cnt+1))) % (cnt+1)
        else:
            ans = (r_2[0] - r_2[i] + r_2[i+1]) % (cnt-1)

        cnt_ans = 1
        while ans > 0:
            ans = calc(str(bin(ans))[2:], len(str(bin(ans))[2:]))
            cnt_ans += 1
        print(cnt_ans)

calc_first(X, N)

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
import sys
#import resource
sys.setrecursionlimit(10 ** 9)
#resource.setrlimit(resource.RLIMIT_STACK, (-1, -1))

mm = {}

def popcorn(n):
    n = bin(n)
    return n.count("1")

def f(n):
    n%=popcorn(n)
    return n
    
def nf(n,count):
    if(n == 0):
        return count
    elif(n in mm):
        count += mm[n]-1
        return count
    else:
        n%=popcorn(n)
        return nf(n,count+1)


n = int(input())
a = input()
moto = int(a,2)
for i in range(n-1,0-1,-1):
    if(a[n-1-i] == "0"):
        k=moto+2**i
    else:
        k=moto-2**i
    mo = f(k)
    if(mo in mm):
        print(mm[mo])
        continue
    else:
        count = nf(mo,1)
        print(count)
        mm[mo]=count

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
cnt=0
X=int(x,2)
for i in range(n):
  if x[i]=='1':
    cnt+=1

def func(n):
  lst=[1,1,2,1,2,1,2,1,2,1,2,1,2,2,3,1,2,1,2,1]
  return lst[n-1]
    
for i in range(1,n+1):
  Cnt=cnt
  y=X
  if x[i]=='1':
    Cnt-=1
    y-=2**(n-i)
  else:
    y+=2**(n-i)
  if y>20:
    Cnt2=y%Cnt
    print(1+func(Cnt2))
  else:
    print(func(y))

Submission status: Runtime Error

Solution code:

array = []

def func(x, cnt):
    mod = x % cnt
    if array[mod] != -1:
        return array[mod]
    c = bin(mod).count('1')
    ret = func(mod, c)
    array[mod] = ret
    return ret + 1

n = int(input())
x = input()
array = [-1] * (n + 1)
array[0] = 0
bit = 1 << (n-1)
cnt = x.count('1')
xx = int(x, base=2)

for _ in range(n):
    flag = 1 if xx & bit else -1
    print(func(xx - flag *  bit, cnt - flag * 1) + 1)
    bit >>= 1

# if __name__ == "__main__":
#     resolve()

Submission status: Runtime Error

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


def calc(n,count):
    popcount=bin(n).count("1")
    next_n=n%popcount
    #print(next_n)
    if next_n==0:
        return count+1
    else:
        return calc(next_n, count+1)


for i in range(N):
    if X[i]=="1":
        now=X_int-2**(N-1-i)
    else:
        now=X_int+2**(N-1-i)

    #print(int(nowbin, 2))
    print(calc(now,0))

Submission status: Runtime Error

Solution code:
from collections import defaultdict

hist = defaultdict(int)

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

def f(n):
    pc = 0
    prove = 1
    for i in range(N):
        if n & (prove << i):
            pc += 1
    return n % pc

result = []
prove = 1
for i in range(N):
    x = X ^ (prove << i)
    route = [x]
    count = 1
    # print(x, end=" ")
    while True:
        # print("->", end="")
        x = f(x)
        # print(x, end="")
        if hist[x]:
            count += hist[x]
            x = 0
        if x == 0:
            result.append(count)
            for r in route:
                hist[r] = count
                count -= 1
            break
        route.append(x)
        count += 1
    # print()

# print(hist)

print(*result[::-1], sep='\n', end='')

Submission status: Runtime Error

Solution code:
from functools import lru_cache
n = int(input())
x = input()

def popcount(n):
    a = bin(n)
    return a[2:].count("1")

@lru_cache(maxsize=None)
def func(n, cnt=0):
    cnt += 1
    n = n % popcount(n)
    if n == 0:
        return cnt
    else:
        return func(n, cnt)

for i in range(n):
    a = list(x)
    a[i] = '1' if a[i] == '0' else '0'
    a = "".join(a)
    print(func(int(a,2)))

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
import sys
import resource
sys.setrecursionlimit(10 ** 9)
resource.setrlimit(resource.RLIMIT_STACK, (-1, -1))

mm = {}

def popcorn(n):
    n = bin(n)
    return n.count("1")

def f(n):
    n%=popcorn(n)
    return n
    
def nf(n,count):
    if(n == 0):
        return count
    elif(n in mm):
        count += mm[n]-1
        return count
    else:
        n%=popcorn(n)
        return nf(n,count+1)


n = int(input())
a = input()
moto = int(a,2)
for i in range(n-1,0-1,-1):
    if(a[n-1-i] == "0"):
        k=moto+2**i
    else:
        k=moto-2**i
    mo = f(k)
    if(mo in mm):
        print(mm[mo])
        continue
    else:
        count = nf(mo,1)
        print(count)
        mm[mo]=count

Submission status: Runtime Error

Solution code:
def cal_nums(number):
    cp = number
    cnt = 0
    pos = 0
    while(1):
        if (cp >> pos) == 0:
            break
        cnt += ((cp>>pos)&1)
        pos += 1
    
    cnt_cp = cnt
    mul = 2
    while(cnt < number):
        cnt *= mul
        mul = mul << 1

    return (number - cnt // mul) % cnt_cp

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

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

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

def map_int_input():
    return map(int, input())

MII = map_int_input

def MII_split():
    return map(int, input().split())

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

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

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

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

for i in range(1, N + 1):
    tmp = 1 << N - i
    X_i = X ^ tmp
    # print(f'{X_i=}')

    popcount = bin(X_i).count("1")
    it_num = X_i // popcount
    ans = 1
    for j in range(it_num):
        X_i = X_i % popcount
        if X_i == 0:
            break
        popcount = bin(X_i).count("1")
        ans += 1
    print(ans)

Submission status: Runtime Error

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


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


# dp = [0] * 1000000
for i in range(n - 1, -1, -1):
    num = (2 ** i) ^ x
    ans = 0
#   bit_count_init = popcount(num)
#    if dp[bit_count_init] != 0:
#        print(dp[bit_count_init])
#        continue
    while True:
        bit_count = popcount(num)
        num = num % bit_count
#        if dp[num] != 0:
#            print(a)
        ans += 1
        if num == 0:
            print(ans)
#            dp[bit_count_init] = ans
            break

Submission status: Runtime Error

Solution code:
N = int(input())

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

X = input()
X = int('0b' + X, 0)
res = 1 << N-1
for i in range(N):
    now = X ^ res
    #print(now, res)
        
    a = bin(now)
    #print(a)
    cnt = 0
    for j in range(2, len(a)):
        if a[j] == '1':
            cnt += 1
    b = now%cnt
    #print(now, cnt, b)
    ans = 1
    while b > 0:
        b = dic[b]
        ans += 1
    print(ans)
    
    res = res >> 1

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
if n == 1:
    if x[0] == "0":
        print("0")
    else:
        print("1")
else:

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

f = dict()

def function(x):
    # global f
    # if x in f:
    #     return f[x]
    cnt = 0
    for i in range(len(str(bin(x)))-2):
        if (x>>i) & 1 == 1:
            cnt += 1
    if x % cnt == 0:
        # f[x] = 1
        return 1
    else:
        # f[x] = function(x % cnt) + 1
        return function(x % cnt) + 1

for i in range(N):
    if i == N-1:
        if X[i] == '1': 
            x = X[:i] + '0'
        else:
            x = X[:i] + '1'
    else:
        if X[i] == '1': 
            x = X[:i] + '0' + X[i+1:]
        else:
            x = X[:i] + '1' + X[i+1:]
    # print(x, int(x, 2))
    print(function(int(x, 2)))
# print(f)

Submission status: Runtime Error

Solution code:
def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f

def f(n):
  count = 0
  while n:
    count += 1
    n %= popcount(n)
  return count

def turn(bn, n):
  bn_turned = bn
  if bn[n] == "1":
    bn_turned = bn_turned[:n] + "0" + bn_turned[n+1:]
  else:
    bn_turned = bn_turned[:n] + "1" + bn_turned[n+1:]
  return int(bn_turned, 2)

N = int(input())
X = input()
for i in range(N):
  print(f(turn(X, i)))

Submission status: Runtime Error

Solution code:
N = int(input())
X = int(input(),2)
l = [0]+[-1]*(N)

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 n in range(1,N+1):
    l[n] = l[n%popcount(n)]+1
a = [0]*N
for i in range(N):
    x = X^(1<<i)
    a[N-1-i] = l[x] if x<=N else l[x%popcount(x)]+1
for x in a:
    print(x)

Submission status: Runtime Error

Solution code:

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


def popcount(X):
    return X.count("1")
for i in range(N):
    ans=0
    hantei=1
    C=list(X)
    if X[i]==0:
        C[i]="1"
    else:
        C[i]="0"
    while hantei>0:
        p=popcount(C)
        c=''.join(C)
        c=bin(int(c,2)%p)[2:]
        ans+=1
        hantei=int(c,2)
        C=list(c)
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
import math
sys.setrecursionlimit(10**9)
from functools import lru_cache

import heapq

def input():
    return sys.stdin.readline().rstrip()

@lru_cache()
def tc(n):
     y =n
     count =0
     while y:
         if y%2==1:
             count +=1
         y=y//2
     ans =n % count
     if ans ==0:
         return 1
     else:
         return tc(ans) +1



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

    for i in range(N-1, -1, -1):
        t = 2 ** i ^ X
        print(tc(t))









if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():

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

    for i in range(N):
        n_bin = X.copy()
        if n_bin[i] == "1":
            n_bin[i] = "0"
        else:
            n_bin[i] = "1"
        n_bin = "".join(n_bin)
        cnt = 0
        while n_bin != "0":
            popcount = n_bin.count("1")
            n = int(n_bin, 2) % popcount
            n_bin = bin(n)[2:]
            cnt += 1

        print(cnt)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
for i in range(n):
    a=x
    if a[i]=="0":
        a=a[:i] + "1" + a[i+1:]
    else:
         a=a[:i] + "0" + a[i+1:]
    a2=int(a,2)
    b=list(a).count("1")
    b=a2%b
    c=1
    while b!=0:
        pb=list(bin(b)).count("1")
        b=b%pb
        c+=1
    print(c)

Submission status: Runtime Error

Solution code:
from functools import lru_cache

N = int(input())
X = input()
x = int(X, 2)
y = X.count('1')
x1 = x % (y+1)
x2 = x % (y-1)

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

d = [0] * (2*10**5+5)
for i in range(2*10**5+5):
    d[i] = f(i)

for i in range(N):
    if x >>(N - i - 1) & 1:
        # print(f(x-pow(2, N-i-1)))
        print(d[(x2 - pow(2, N - i - 1, y-1)) % (y-1)] + 1)
    else:
        # print(f(x+pow(2, N-i-1)))
        print(d[(x1 + pow(2, N - i - 1, y+1)) % (y+1)] + 1)

Submission status: Runtime Error

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

def pow_k(x, n):
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x

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

counter = x.count('1')
number = int(''.join(x), 2)

def f(num, cnt):
    if num == 0:
        return cnt
    popcount = format(num, 'b').count('1')
    return f(num % popcount, cnt+1)

for i in range(n):    
    if x[i] == '0':
        m = number + pow_k(2, n-i-1)
        print(f(m % (counter+1), 1))
    if x[i] == '1':
        m = number - pow_k(2, n-i-1)
        print(f(m % (counter-1), 1))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
import random
from collections import deque
from decimal import *
import queue

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	X = inputStr()
	X_lin = list(X)

	ans = []
	mem = {}
	for i in range(N):
		tmpX = X_lin
		if X[i] == "1":
			tmpX = X[:i] + "0" + X[i+1:]
		else:
			tmpX = X[:i] + "1" + X[i+1:]

		oct = int(tmpX, 2)

		ans_tmp = 0
		if oct in mem:
			ans_tmp = mem[oct]

		else:
			while True:
				if oct == 0:
					break
				tmp = popcnt5(oct)
				oct = oct % tmp
				ans_tmp += 1
				if oct == 0:
					break
				if oct in mem:
					ans_tmp += mem[oct]
					break

		if oct in mem:
			pass
		else:
			mem[oct] = ans_tmp

		ans.append(ans_tmp)

	for i in ans:
		print(i)

POPCOUNT_TABLE16 = [0] * 2**16
for index in range(len(POPCOUNT_TABLE16)):
    POPCOUNT_TABLE16[index] = (index & 1) + POPCOUNT_TABLE16[index >> 1]

def popcnt5(v):
    return (POPCOUNT_TABLE16[ v        & 0xffff] +
            POPCOUNT_TABLE16[(v >> 16) & 0xffff] +
            POPCOUNT_TABLE16[(v >> 32) & 0xffff] +
            POPCOUNT_TABLE16[(v >> 48)         ])

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
def f(n, count):
    binary = list(bin(n))[2:]
    popcount = 0
    for b in binary:
        if b == '1':
            popcount += 1
    count += 1
    if n%popcount == 0:
        return count
    else:
        return f(n%popcount, count)
        
N = int(input())
X = list(input())

fn = dict([(i, 0) for i in range(1, N+1)])

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