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("")
def pop(n):
    i=0
    while(n>0):
        if(n%2==1):
            i+=1
        n=int(n/2)
    return i
listx=[]
for i in range(n):
    listx+=[int(x[n-1-i])]
tt=0
for i in range(n):
    tt+=listx[i]*2**i

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

        



    print(c)

Submission status: Runtime Error

Solution code:
import math
n = int(input())
x = input()
ct = x.count("1")
for i in range(n):
    res = 0
    if x[i] == "0":
        y = 1
        t = ct + 1
    else:
        y = 0
        t = ct - 1
    s = x[:i] + str(y) + x[i + 1:]
    a = int(s, 2)
    while True:
        a %= t
        res += 1
        t = bin(a).count("1")
        if a == 0:
            break
    print(res)

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 f[x]

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 toggleKthBit(n, k): 
  return (n ^ (1 << (k-1))) 

def popcount(x):
    x -= (x >> 1) & 0x5555555555555555
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    return ((x * 0x0101010101010101) & 0xffffffffffffffff ) >> 56
N = int(input())
X = int(input())

ans = -1
for i in range(N, 0, -1):
  count = 0
  ans = toggleKthBit((int(str(X), 2)), i)
  while ans != 0:
    ans = ans % popcount(ans)
    count += 1
  print(count)

Submission status: Runtime Error

Solution code:
import numpy as np


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 main(N, X):
    check = "0"*N
    for i in range(N):
        check = check[:i]+"1"+check[i+1:]
        x = int(X, 2)
        if int(check, 2) & x == int(check, 2):
            x -= int(check, 2)
        else:
            x += int(check, 2)
        count = 0
        while True:
            if x == 0b0:
                print(count)
                break
            x = x % popcount(x)
            count += 1
        check = "0"*N


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

main(N, X)

Submission status: Runtime Error

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

sys.setrecursionlimit(20000000)

def yn(b):
    print("Yes" if b==1 else "No")
    return

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

def resolve():
    readline=sys.stdin.readline

    n=int(readline())
    x=readline().rstrip()

    #pc=[0]*(10**5+1)
    #for i in range(1,10**5):
    #    pc[i]=count_ones_by_bin(i)
    amr1=[0]*((10**5)*2 + 5)
    amr2=[0]*((10**5)*2 + 5)
    bits=[False]*((10**5)*2 + 5)

    bcnt=0
    j=0
    for i in x:
        if int(i)==1:
            bcnt += 1
            bits[j]=True
        j+=1

    base1=0
    base2=0
    for i in range(n):
        jo=n-i-1
        amr1[i]=pow(2,jo,bcnt+1)
        amr2[i]=pow(2,jo,bcnt-1)
        if bits[i]==True:
            base1+=amr1[i]
            base2+=amr2[i]
    for i in range(n):
        ans=0
        if bits[i]==True: #1->0
            base=(base2-amr2[i])%(bcnt-1)
        else:
            base=(base1+amr1[i])%(bcnt+1)
        ans+=1
        while base > 0:
            pp=count_ones_by_bin(base)
            base=base%pp
            ans+=1
        print(ans)
    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Runtime Error

Solution code:
from collections import defaultdict
N = int(input())
X = list(input())
d = defaultdict(int)

for i in range(1, N):
    c = 0
    k = format(i, "b")
    for j in k:
        if j == "1":
            c += 1
    d[i] = i % c

n = 0
for i in X:
    if i == "1":
        n += 1

p = 1
total1 = 0
total2 = 0
for i in X[::-1]:
    if i == "1":
        total1 += p % (n+1)
        total2 += p % (n-1)
    p *= 2

total1 %= (n+1)
total2 %= (n-1)
Ans = []
p = 1
for i in X[::-1]:
    c = 1
    if i == "0":
        start = total1
        start += p % (n+1)
        start %= (n+1)
    else:
        start = total2
        start -= p % (n-1)
        start += n - 1
        start %= (n-1)
    if start == 0:
        Ans.append(c)
    else:
        while(True):
            start = d[start]
            c += 1
            if start == 0:
                break
        Ans.append(c)
    p *= 2

for i in Ans[::-1]:
    print(i)

Submission status: Runtime Error

Solution code:
k = int(input())
x = list(str(input()))
p = [0] * 1000
C = [0] * 1000
o = x.count("1")

for i in range(1000):
    p[i] = bin(i).count("1")

for i in range(1000):
    if i == 0:
        C[i] == 0
    else:
        C[i] = i%p[i] + C[i%p[i]]


for i in range(k):
    f = 0
    temp = x[:]
    if temp[i] == "0":
        f = 1
        temp[i] = "1"
    else:
        temp[i] = "0"
        f = -1
    num = int("".join(temp),2)
    c = 1
    num %= (o+f)
    if num == 0:
        c -= 1
    print(c+C[num]+1)

Submission status: Runtime Error

Solution code:
arr=[0,1,1,2]
n=2*(10**5)+100
for i in range(4,n):
    b=bin(i)[2:]
    k=b.count('1')
    arr.append(arr[i%k]+1)
    #print(b,arr[i])
n=int(input())
z=input()
l=z.count('1')
l1=l+1
l2=l-1
ans1=0
ans2=0
for i in range(n):
    if(z[i]=='1'):
        u=pow(2,n-1-i,l1)
        ans1=(ans1+u)%l1
        if l2!=0:
            ans2=(ans2+pow(2,n-1-i,l2))%l2
for i in range(n):
    if z[i]=='0':
        p=ans1+pow(2,n-1-i,l1)
        p%=l1
        print(1+arr[p])
    else:
        p=ans2+pow(2,n-1-i,l2)
        p%=l2
        print(1+arr[p])

Submission status: Runtime Error

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

xs = int(x, 2)

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

for i in range(n):
    x2 = x
    tmp_count = count
    if x[i] == "0":
        x2 = x[:i] + "1" + x[(i+1):]
        tmp_count += 1
    else:
        x2 = x[:i] + "0" + x[(i+1):]
        tmp_count -= 1

    xs2 = int(x2, 2)

    tmp_xs = (xs2 % tmp_count)
    tmp_xs = int(tmp_xs)

    res = 1

    while tmp_xs > 0:
        xss = bin(tmp_xs)
        cnt = 0
        for j in range(len(xss)):
            if xss[j] == "1":
                cnt += 1
        tmp_xs = (tmp_xs % cnt)
        res += 1

    print(res)

Submission status: Runtime Error

Solution code:
from functools import lru_cache


@lru_cache(maxsize=None)
def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    x = x + (x >> 64)
    return x & 0x0000007f


@lru_cache(maxsize=None)
def rec(n):
    if n == 0:
        return 0
    else:
        return rec(n % popcnt(n)) + 1


n = int(input())
arr = input()

li = []

for i in range(n):
    tmp = arr[:i] + str(1 ^ int(arr[i])) + arr[i + 1:]
    li.append(int(tmp, 2))

for x in li:
    print(rec(x))

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
ans = [0]*(10**5+1)

for i in range(1,10**5+1):
    s = format(i, 'b')
    c = s.count('1')
    a = i%c
    ans[i] += 1
    ans[i] += ans[a] 

one_cnt = x.count('1')
numx = int(x,2)
for i in range(n):
    temp = one_cnt
    if x[i]=='0':
        temp += 1
        num = numx + 2**(n-1-i)
    else:
        temp -= 1
        num = numx - 2**(n-1-i)
    print(ans[num%temp]+1)

Submission status: Runtime Error

Solution code:
"""
    こんにちは。これはクシャルです
    
    Author : thekushalghosh (クシャル)
    Team   : CodeDiggers
 
    I prefer Python language over the C++ language :p :D
        
    Visit my website : thekushalghosh.github.io
"""
import sys,math,cmath,time,itertools
start_time = time.time()
##########################################################################
################# ---- THE ACTUAL CODE STARTS BELOW ---- #################
a = [0] * (100000 + 1)
for i in range(1,100000):
    q = bin(i).replace("0b","")
    a[i] = a[i % q.count("1")] + 1
    
def solve():
    global a
    n = inp()
    s = insr()
    q = list(s)
    w = q.count("1")
    for i in range(n):
        if q[i] == "0":
            q[i] = "1"
            w = w + 1
        else:
            q[i] = "0"
            w = w - 1
        qw = int(s[:i] + q[i] + s[i + 1:],2)
        if w == 0:
            print(0)
        else:
            print(a[qw % w] + 1)
        if q[i] == "0":
            q[i] = "1"
            w = w + 1
        else:
            q[i] = "0"
            w = w - 1
    
################## ---- THE ACTUAL CODE ENDS ABOVE ---- ##################
##########################################################################
 
def main():
    global tt
    if not ONLINE_JUDGE:
        sys.stdin = open("input.txt","r")
        sys.stdout = open("output.txt","w")
    t = 1
    for tt in range(t):
        solve()
    if not ONLINE_JUDGE:
        print("Time Elapsed :",time.time() - start_time,"seconds")
        sys.stdout.close()
    
#---------------------- USER DEFINED INPUT FUNCTIONS ----------------------#
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    return(input().strip())
def invr():
    return(map(int,input().split()))
 
#------------------ USER DEFINED PROGRAMMING FUNCTIONS ------------------#
def counter(a):
    q = [0] * max(a)
    for i in range(len(a)):
        q[a[i] - 1] = q[a[i] - 1] + 1
    return(q)

def counter_elements(a):
    q = dict()
    for i in range(len(a)):
        if a[i] not in q:
            q[a[i]] = 0
        q[a[i]] = q[a[i]] + 1
    return(q)

def string_counter(a):
    q = [0] * 26
    for i in range(len(a)):
        q[ord(a[i]) - 97] = q[ord(a[i]) - 97],1
    return(q)
 
def factors(n):
    q = []
    for i in range(1,int(n ** 0.5) + 1):
        if n % i == 0: q.append(i); q.append(n // i)
    return(list(sorted(list(set(q)))))
 
def prime_factors(n):
    q = []
    while n % 2 == 0: q.append(2); n = n // 2
    for i in range(3,int(n ** 0.5) + 1,2):
        while n % i == 0: q.append(i); n = n // i
    if n > 2: q.append(n)
    return(list(sorted(q)))

def transpose(a):
    n,m = len(a),len(a[0])
    b = [[0] * n for i in range(m)]
    for i in range(m): 
        for j in range(n): 
            b[i][j] = a[j][i]
    return(b)

#-----------------------------------------------------------------------#
        
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
    input = sys.stdin.readline
main()

Submission status: Runtime Error

Solution code:
def resolve():
    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)
resolve()

Submission status: Runtime Error

Solution code:
N=int(input())
X=input()
def fx(n,c):
    if c==0:
        return 0
    b=n%c
    if b==0:
        return 1
    if b==1 or b==2:
        return 2
    t=bin(b).count("1")
    return fx(b,t)+1
c=X.count("1")
n=int(X,2)
lp=[1]*N
lm=[1]*N
for i in range(N-2,-1,-1):
    lp[i]=2*lp[i+1]%(c+1)
    lm[i]=2*lm[i+1]%(c-1)
np=n%(c+1)
if c>1:
    nm=n%(c-1)
else:
    nm=1
for i in range(N):
    if X[i]=="0":
        print(fx(np+lp[i],c+1))
    else:
        print(fx(nm-lm[i],c-1))

Submission status: Runtime Error

Solution code:
n = int(input())
x = str(input())
kosu1 = 0
kazu = 0
for i in range(n):
    kazu += 2 ** (n - i - 1) * int(x[i])
    if x[i] == '1':
        kosu1 += 1
if kosu1 ==1:
    kazup = kazu % (kosu1 + 1)
    magic17 = [0, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 2, 3, 1, 2]
    box = [0] * (kosu1 + 1)

    amarip = [1] * n
    amarim = [1] * n
    for i in range(1, n):
        amarip[i] = (amarip[i - 1] * 2) % (kosu1 + 1)
    for i in range(n):
        if x[i] == '1':
            print(0)
        else:
            a = (kazup + amarip[n - 1 - i]) % (kosu1 + 1)
            # print(2121,a)
            if a <= 17:
                print(magic17[a] + 1)
            else:
                num = 0
                for i in range(len(str(bin(a)) - 2)):
                    if str(bin(a))[-1 - i] == 1:
                        num += 1
                print(magic17[a % num] + 1)
else:
    kazup = kazu %(kosu1 + 1)
    kazum = kazu %(kosu1 - 1)
    magic17 = [0,1,1,2,1,2,1,2,1,2,1,2,1,2,2,3,1,2]
    box = [0] * (kosu1 +1)

    amarip = [1] * n
    amarim = [1] * n
    for i in range(1,n):
        amarip[i] = (amarip[i - 1]*2) % (kosu1 + 1)
        amarim[i] = (amarim[i - 1]*2) % (kosu1 - 1)
    for i in range(n):
        if x[i] == '1':
            a = (kazum - amarim[n-1-i]) % (kosu1 - 1)
            #print(a,kazup,kazum,amarip,amarim,kosu1)
            if a <= 17:
                print(magic17[a]+1)
            else:
                num = 0
                for i in range(len(str(bin(a))-2)):
                    if str(bin(a))[-1-i] == 1:
                        num += 1
                print(magic17[a%num] + 1)
        else:
            a = (kazup + amarip[n - 1 - i]) % (kosu1 + 1)
            #print(2121,a)
            if a <= 17:
                print(magic17[a] + 1)
            else:
                num = 0
                for i in range(len(str(bin(a)) - 2)):
                    if str(bin(a))[-1 - i] == 1:
                        num += 1
                print(magic17[a % num] + 1)

Submission status: Runtime Error

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue
import numpy as np
# sympy as syp(素因数分解とか)
Mod = 1000000007
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1] 
for i in range(2, 10**5 + 1):
    fact.append((fact[-1] * i) % Mod)
    inv.append((-inv[Mod % i] * (Mod // i)) % Mod)
    factinv.append((factinv[-1] * inv[-1]) % Mod)
    
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % p
    
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[y] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)
import string
def main():  #startline-------------------------------------------
    n = int(input())
    x = input()
    xint = int(x,2)
    def countbin(i): #f(x)を求める関数
        bin_i = bin(i)
        popcount = bin_i.count("1")
        cnt = 0
        while i != 0:
            i = i % popcount
            cnt += 1
            popcount = bin(i).count("1")
        return cnt
    for i in range(len(x)):
        if x[i] == "0":
            print(countbin(xint + 2 ** (n - i - 1)))
        else:
            print(countbin(xint - 2 ** (n - i - 1)))

if __name__ == "__main__":
    main() #endline===============================================

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)

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

d = [0] * (2*10**5+1)
for i in range(2*10**5+1):
    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:
from decimal import *

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

xs = int(x, 2)

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

for i in range(n):
    x2 = x
    tmp_count = count
    if x[i] == "0":
        x2 = x[:i] + "1" + x[(i+1):]
        tmp_count += 1
    else:
        x2 = x[:i] + "0" + x[(i+1):]
        tmp_count -= 1

    xs2 = int(x2, 2)

    tmp_xs = (xs2 % tmp_count)
    tmp_xs = int(tmp_xs)

    res = 1

    while tmp_xs > 0:
        xss = bin(tmp_xs)
        cnt = 0
        for j in range(len(xss)):
            if xss[j] == "1":
                cnt += 1
        tmp_xs = (tmp_xs % cnt)
        res += 1

    print(res)

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

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)

	XX_lin = []
	for i in X_lin:
		if i == "0":
			XX_lin.append("1")
		else:
			XX_lin.append("0")

	ans = []
	mem = {}
	for i in range(N):
		tmpX = copy.deepcopy(X_lin)
		tmpX[i] = XX_lin[i]

		oct = int("".join(tmpX), 2)

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

		else:
			while True:
				if oct == 0:
					break
				tmp = gmpy2.popcount(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)

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

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

Submission status: Runtime Error

Solution code:
n=int(input())
x=str(input())
for i in range(n):
    if x[i]=='0':
        tmp=x[:i]+'1'+x[(i+1):]
    elif x[i]=='1':
        tmp=x[:i]+'0'+x[(i+1):]
    cnt=0
    while True:
        r=int(tmp,2)%tmp.count('1')
        tmp='{:b}'.format(r)
        cnt+=1
        if tmp=='0':
            print(cnt)
            break

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000000)

n = int(input())
x = input()
value = [0, 1]
for i in range(2, 2 * (10 ** 5) + 1):
    ans = 1
    i = i % bin(i).count('1')
    value.append(ans + value[i])

for i in range(n):
    t = x[:i] + ('0' if x[i] == '1' else '1') + x[i + 1:]
    ans = 1
    t = (int(t, 2) % (t.count('1')))
    print(ans + value[t])

Submission status: Runtime Error

Solution code:
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)
    count = 1
    while True:
        x = f(x)
        if x == 0:
            result.append(count)
            break
        count += 1

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

Submission status: Runtime Error

Solution code:
n = int(input())
q = input()
r = list(q)
p = [1,1,2,1,2,1,0]
ans = [0 for i in range(n)]
def k(x,n):
    ans = 0
    for i in range(n):
        if x&1:
            ans += 1
        x = x>>1
    return ans
x = int(q, 2)
y = k(x,n)
for i in range(n):
    an = 0
    if r[n-i-1]=='1':
        z = x-2**i
        if y-1 == 0:
            ans[i] = 0
        else:
            z = z%(y-1)
            while z:
                u = k(z,10)
                z = z%u
                an += 1
            ans[i] = an+1
    else:
        z = x + 2**i
        z = z%(y+1)
        while z:
            u = k(z,10)
            z = z%u
            an += 1
        ans[i] = an+1
ans.reverse()
for i in range(n):
    print(ans[i])

Submission status: Runtime Error

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

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'))]
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
  for y in range(100000):
    xn=xn%p(xn)
    res += 1
    if xn==0:
      break
  print(res)

Submission status: Runtime Error

Solution code:
def toggleKthBit(n, k): 
  return (n ^ (1 << (k-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
N = int(input())
X = int(input())

ans = -1
for i in range(N, 0, -1):
  count = 0
  ans = toggleKthBit((int(str(X), 2)), i)
  while ans != 0:
    ans = ans % popcount(ans)
    count += 1
  print(count)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
# Coding is about expressing your feeling, and
# there is always a better way to express your feeling_feelme
import sys
import math
# sys.stdin=open('input.txt','r')
# sys.stdout=open('output2.txt','w')
from sys import stdin,stdout
from collections import deque,defaultdict
from math import ceil,floor,inf,sqrt,factorial,gcd,log2
from copy import deepcopy
ii1=lambda:int(stdin.readline().strip())
is1=lambda:stdin.readline().strip()
iia=lambda:list(map(int,stdin.readline().strip().split()))
isa=lambda:stdin.readline().strip().split()
mod=int(1e9 + 7)
def invert(number,k):
    # m = (m) | (m - 1)
    mask=1<<(k-1)
    # print(mask)
    res = number ^ mask
    return res
def fun(num):
    count=0
    while num>=0:
        a=bin(num).count('1')
        ans=num%a
        num=ans
        count+=1
        if num==0:
            break
    print(count)

n=ii1()
s=is1()
ss='0b'+s
nums=int(ss,2)
for i in range(n):
    ans=invert(nums,n-i)
    # print(ans)
    fun(ans)

Submission status: Runtime Error

Solution code:
from functools import lru_cache


@lru_cache(maxsize=None)
def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


@lru_cache(maxsize=None)
def rec(n):
    if n == 0:
        return 0
    else:
        return rec(n % popcnt(n)) + 1


n = int(input())
arr = input()

li = []

for i in range(n):
    tmp = arr[:i] + str(1 ^ int(arr[i])) + arr[i + 1:]
    li.append(int(tmp, 2))

for x in li:
    print(rec(x))

Submission status: Runtime Error

Solution code:
def toggle_nth_bit(num: int, n: int):
    return num ^ (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

N = int(input())
X = input()
f = 0
count = 1
for i in range(N-1, -1, -1):
    f = toggle_nth_bit(int(X, 2), i)
    while f % popcount(f) != 0:
        f = f % popcount(f)
        count += 1
    print(count)
    count = 1

Submission status: Runtime Error

Solution code:
from functools import lru_cache

n = int(input())
x = input()
x10 = int(x, 2)
lenx = len(x)

maxbit = x.count("1")

box = [0] * (maxbit + 1)

@lru_cache(maxsize=None)
def f(i):
  cnt = 1
  while i > 0:
    if box[i] != 0:
      return box[i] + cnt
    i %= bin(i).count("1")
    cnt += 1
  return cnt

xlist = []

for i in range(lenx):
  if x[i] == "0":
    t = x10 + 2 ** (lenx - 1 - i)
  else:
    t = x10 - 2 ** (lenx - 1 - i)
  t %= (maxbit - 1) 
  ans = f(t)
  box[t] = ans
  print(ans)

Submission status: Runtime Error

Solution code:
def pop(x):
    c = 0
    for i in range(1 << 7):
        b = sum(i == '1' for i in format(x,'b'))
        x = x%b
        c += 1
        if x == 0:
            break
    return c

n = int(input())
x = input()
for i in range(n):
    a = x[:i] + '1' + x[i+1:] if x[i] == '0' else x[:i] + '0' + x[i+1:]
    print(pop(int(a,2)))

Submission status: Runtime Error

Solution code:
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

N = int(input())
X = int(input(),2)
for i in range(N-1,-1,-1):
    j = X^1<<i
    cnt = 0
    while j > 0:
        j %= popcount(j)
        cnt += 1
    print(cnt)

Submission status: Runtime Error

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

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 
    x = x + (x >> 8) 
    x = x + (x >> 16) 
    x = x + (x >> 32) 
    return x & 0x0000007f
  
def func(n, c):
  next = n%popcount(n)
  c+=1
  if ans[next]!=-1:
    return ans[next]+c
  if next == 0:
    return c
  else:
    return func(next, c)

ma = "11111111111111111111111"
maint = int(ma, 2)+1
n=int(input())
x=input()
ans = [-1]*maint
for i in range(1, maint):
  ans[i] = func(i, 0)

for i in range(n):
  temp=list(x)
  if x[i]=="0":
    temp[i]="1"
  else:
    temp[i]="0"
  itemp = int("".join(temp), 2)
  #print(itemp)
  print(ans[itemp])

Submission status: Runtime Error

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

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":
        change="0"
    else:
        change="1"
    X_copy=X.copy()
    X_copy[i]=change
    nowbin="".join(X_copy)
    #print(int(nowbin, 2))
    print(calc(int(nowbin, 2),0))