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 math
# from collections import defaultdict
import time
def steps(n,p):
  c = 0
  while n:
    c += 1
    n = n%p
    p = bin(n).count('1')
  return c

# n = 200000
# x = "1"*n
n = int(input())
x = input()
incs = [1]
decs = [1]
p = x.count('1')
for i in range(1,n):
  incs.append((incs[-1]*2)%(p+1))
  decs.append((decs[-1]*2)%(p-1))
num = int(x,2)
inc = num%(p+1)
dec = num%(p-1)
start = time.time()
k = -1
for i in range(n):
  cp = p
  if x[i] == '0':
    cp += 1
    new = (inc+incs[k])%cp
  else:
    cp -= 1
    new = (dec-decs[k])%cp
  k -= 1
  ans = steps(new,cp)
  if ans==0:
    ans=1
  print(ans)
  # steps(new,cp)
# print(time.time()-start)

Submission status: Runtime Error

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

def f(N:int,s:int):
    bina=list(bin(N))
    array=bina[2:]
    c=0
    for i in array:
        if i=="1":
            c+=1
    p=N%c
    s+=1
    if p==0:
        return s
    else:
        return f(p,s)


N=int(input())
binary=input()
a="0b"+binary
binary=int(a,0)
for i in reversed(range(0, 3)):
    print(f(toggle_nth_bit(binary,i),0))

Submission status: Runtime Error

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

pop = []
num = X.count("1")
n = int("".join(map(str, X)), 2)
mod_1 = n % (num+1)
mod_2 = n % (num-1)

def f(n):
    count = 0
    while n != 0:
        a = str(bin(n))
        n %= a.count("1")
        count += 1
    return count


for i in range(num+1):
    ans = f(i)
    pop.append(ans)

for i in range(N):
    if X[i] == "1":
        a = pow(2, N-1-i, num-1)
        print(pop[a+mod_2]+1)
    else:
        a = pow(2, N-1-i, num+1)
        print(pop[a+mod_1]+1)

Submission status: Runtime Error

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


def solve(N: int, X: str):
    def pc(n):
        return bin(n).count("1")

    def f(i):
        if i == 0 : return 0
        p = 0
        k = i
        while(k!= 0):
            t = k
            p+=1
            k = t % pc(t)
        return p
    
    ts = [f(i) for i in range(1024)]
    # ts = {}
    # for i in range(2*10**5+1):
        # ts[i] = f(i)
    # for i in range(2*10**5+1):
        # ts[i] = f(i)



    x = int(X, 2)
    px = X.count("1")
    for i, xi in enumerate(X):
        if xi == "0":
            temp = (x + 2**(N-i-1))
            l = px+1
        else:
            temp = (x - 2**(N-i-1))
            l = px-1

        if temp == 0:
            print(0)
        else:
            temp = temp % l
            if temp == 0:
                print(1)
            else:
                temp = temp % l
                print(ts[temp]+1)
    
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = next(tokens)  # type: str
    solve(N, X)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

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

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

def calc(a):
  #print('a=',a)
  if 0 <= a <= 2*(10**7) and  p[a] != -1:
    return p[a]
  else:
    if a == 0:
      ret = 0
    else:
      b = bin(a).count('1')
      ret = 1+calc(a%b)
    if 0 <= a <= 2*(10**7):
      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:
    if cnt == 1:
      print(1)
    else:
      xx = xx0[n-i-1]
      print(calc((x0-xx)%(cnt-1))+1)

Submission status: Runtime Error

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

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

DP[0] = 0
DP[1] = 1


def pop(n):
    Sum = 0
    for j in range(n):  # このループが一番のポイント
        if ((i >> j) & 1):
            Sum += 1
    return Sum


def dp(n):
    if DP[n] != -1:
        return DP[n]
    else:
        return dp(n % pop(n)) + 1


for i in range(2,2 * (10 ** 5) + 1):
    dp(i)

for i in range(N):
    Xi = X ^ 2 ** i
    print(dp(Xi%pop(Xi)))

Submission status: Runtime Error

Solution code:
def divbin(s,res):
  if int(s,2)==0:
    v=res
    return v
  # ss=int(s)
  val=int(s,2)
  count=bin(val).count("1")
  val%=count
  # t_str=bin(str(count))
  t_str=bin(val)
  t_str=t_str.replace("0b","")
  res+=1
  return divbin(t_str,res)

from copy import deepcopy
n=int(input())
x=input()

# c=str(bin(n))
# c=c.replace("0b","")
s=x
vv=int(s,2)
p=int(x)
cnt=bin(p).count("1")
x=list(x)
# print(cnt)
for i in range(len(x)):
  tmp=cnt
  ts=""
  vv-=2**(i-1)
  if x[i]=="1":
    vv-=2**(i-1)
  else:
    vv+=2**(i-1)
  # ans=0
  # global ans
  ts=bin(vv)
  ts=ts.replace("0b","")
  ans=0
  ans=divbin(ts,ans)
  print(ans)

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

def popn(n,res):
    for i in range(n):
        if n !=0:
            n = n % popcount(n)
            res += 1
        else:
            break
    return res    

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

y = int(x,2)
for i in range(n):    
    if x[i] =="0":
        z  = y+2**(n-1-i) 
    else:
        z = y- 2**(n-1-i)
    print(popn(z,0))

Submission status: Runtime Error

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


def countbits(n):
    res = 0
    while n:
        res += n % 2
        n //= 2
    return res


n = inp()
x = str_inp()
dp = collections.defaultdict(lambda: -1)
dp[0] = 0
bits_amount = 0
ans = []
for i in range(n):
    bits_amount += int(x[i])
minus_val = 0
plus_val = 0
if bits_amount != 0:
    for i in range(n):
        if int(x[i]):
            minus_val += pow(2, n - i - 1, bits_amount - 1)
            minus_val %= (bits_amount - 1)
if bits_amount != n:
    for i in range(n):
        if int(x[i]):
            plus_val += pow(2, n - i - 1, bits_amount + 1) % (bits_amount + 1)
            plus_val %= (bits_amount + 1)
for i in range(n):
    if int(x[i]):  # 1->0
        now_val = (minus_val - pow(2, n - i - 1, bits_amount - 1)) % (bits_amount - 1)
    else:
        now_val = (plus_val + pow(2, n - i - 1, bits_amount + 1)) % (bits_amount + 1)
    path = [now_val]
    while True:
        if dp[now_val] != -1:
            break
        now_val = now_val % countbits(now_val)
        path.append(now_val)
    tmp = dp[now_val]
    for j in range(1, len(path)):
        tmp += 1
        dp[path[len(path) - j - 1]] = tmp
    ans.append(dp[path[0]])
for i in ans:
    print(i + 1)

Submission status: Runtime Error

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

def popcount(num):
    count = 0
    while num:
        num &= num -1
        count += 1
    return count

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

base = f(Xint)
for i in range(len(X)-1,-1, -1):
  xi = Xint ^ (1 << i)
  print(f(xi))

Submission status: Runtime Error

Solution code:
def dfs(n):
    s = str(format(n, "b"))
    c = s.count("1")
    return l[n % c] + 1
n = int(input())
x = input()
xi = int(x, 2)
c = x.count("1")
l = [0]
for i in range(1, 2 ** n):
    l.append(dfs(i))
for i in range(n):
    k = 0
    if x[i] == "1":
        m = xi - pow(2, n - i - 1)
        c2 = c - 1
    else:
        m = xi + pow(2, n - i - 1)
        c2 = c + 1
    print(dfs(m))

Submission status: Runtime Error

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

cnt = X.count("1")
div = [0] * (cnt + 10)
for i in range(1, cnt + 10):
    for n in range(20):
        div[i] += i >> n & 1

memo = [-1] * (cnt + 10)
memo[0] = 0
for i in range(1, cnt + 10):
    memo[i] = memo[i % div[i]] + 1

res0 = 0
res1 = 0
for i in range(N):
    if X[i] == "1":
        res0 = (res0 + pow(2, N - i - 1, cnt + 1)) % (cnt + 1)
        res1 = (res1 + pow(2, N - i - 1, cnt - 1)) % (cnt - 1)

for i in range(N):
    if X[i] == "0":
        div = cnt + 1
        tmp = (res0 + pow(2, N - i - 1, div)) % div
    else:
        div = cnt - 1
        tmp = (res1 + div - pow(2, N - i - 1, div)) % div
    print(memo[tmp] + 1)

Submission status: Runtime Error

Solution code:
def popcount(n, bit):
    cnt = 0
    ch = []
    while n % bit != 0:
        n = n%bit 
        bit = bin(n).count('1')
        t = (n, bit)
        if memo.get(t):
            return cnt + memo[t]
        else:
            ch.append((t, bit, cnt))
        
        cnt += 1
        
    cnt += 1
    for t1, new1, cnt1 in ch:
        memo[(t1, new1)] = cnt - cnt1
        
    return cnt
    
n = int(input())
x = input()
cnt = x.count('1')
num = 0
for i in range(n):
    num += int(x[-(i + 1)]) * pow(2, i)

memo = dict()

for i in range(n):
    if x[i] == "1":
        temp = num - pow(2, n - i - 1)
        print(popcount(temp, cnt - 1))
    else:
        temp = num + pow(2, n - i - 1)
        print(popcount(temp, cnt + 1))

Submission status: Runtime Error

Solution code:
n = int(input())
m = input()
x = [int(i) for i in list(m)]

for i in range(n):
    l = x
    if l[i] == 0:
        l[i] == 1
    else:
        l[i] == 0
    r = l
    r.reverse()
    a = 0
    for i in range(n):
        a += 2**i * r[i]
    b = sum(r)
    count = 0
    while True:
        A = a % b
        count += 1
        if A == 0:
            break
        elif A == 1 or A == 2 or A == 4 or A == 6 or A == 8 or A == 10:
            count += 1
            break
        elif A == 3 or A == 5 or A == 7 or A == 9 or A == 11 or A == 13 or A == 14:
            count += 1
            break


    print(count)

Submission status: Runtime Error

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


def P(n):
    b = bin(n)
    l = len(b)
    r = 0
    for i in range(2, l):
        if b[i] == '1':
            r += 1
    return r


for i in range(n):
    c = x.copy()
    if c[i] == '0':
        c[i] = '1'
    else:
        c[i] = '0'
    u = int(''.join(c), 2)
    sum = 0
    for j in range(20000000):
        u = u % P(u)
        sum += 1
        if u == 0:
            break
    print(sum)

Submission status: Runtime Error

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

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

table=[0,1]+[-1 for i in range(219998)]
for i in range(2,220000):
    table[i]=table[i%popcnt5(i)]+1

table2=[0 for i in range(N)]
moto=0
for i in range(N):
    if X[i]=='1':
        moto+=1

plus=0  #もとの数字に1のときのmodをしたやつ
minus=0

for i in range(N):
    plus+=int(X[i])*pow(2,N-1-i,moto-1)
    minus+=int(X[i])*pow(2,N-1-i,moto+1)
    plus%=(moto-1)
    minus%=(moto+1)

for i in range(N):
    ans=0
    if X[i]=='1':
        ans=plus
        ans-=pow(2,N-1-i,moto-1)
        ans%=(moto-1)
    else:
        ans=minus
        ans+=pow(2,N-1-i,moto+1)
        ans%=(moto+1)
    print(table[ans]+1)

Submission status: Runtime Error

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

bit_caunt = [0]*(2**N+1)

for i in range(2**N):
    if 2**i >= 2**N:
        break
    bit_caunt[2**i] = 1
    
    for j in range(2**i+1,2**(i+1)):
        bit_caunt[j] = bit_caunt[j-2**i] + 1
        if j >= 2**N:
            break


for i in range(N-1,-1,-1):
    re_X = X^(2**i)#ビット反転した数
    ans = 0
    while re_X != 0:
        pop = bit_caunt[re_X]
        re_X = re_X % pop
        ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
x=
pop=[0]
a=1
b=0
count=1
for i in range(1,n):
    ni=0
    a=i
    while a:
        a&=(a-1)
        ni+=1
    pop.append(ni)
x1=0
for i in range(n):
    if int(x[i])&1:
        x1+=2**(n-1-i)
for i in range(n):
    xi=(2**(n-1)>>i)^x1
    count=1
    popi=0
    while a:
        a&=(a-1)
        popi+=1
    xi%=popi
    while xi:
        xi%=pop[xi]
        count+=1
    print(count)

Submission status: Runtime Error

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

def resCount(n):
    tmp = gmpy2.popcount(n)
    if tmp == 1:
        return 1
    else:
        return 1 + resCount(n % tmp)

for i in range(N):
    res, n = 1, int(X, 2) ^ (1<<(N-i-1))
    print(resCount(n))

Submission status: Runtime Error

Solution code:
nn=int(input())
n=int(input())
aa=n
moto=str(format(aa,'b')).count('1')
ans=[]
for i in range(l):
  a=n
  mm=moto
  if k[i]==0:
    a+=2**i
    mm+=1
  else:
    a-=2**i
    mm-=1
  cnt=0
  while a>0:
    a%=mm
    mm=str(format(a,'b')).count('1')
    cnt+=mm
  ans.append(cnt)
for aa in ans:
  print(aa)

Submission status: Runtime Error

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

def one(y):
    return sum(y[2:])

def popcount(y):
    ans = 0
    yint = int(y,2)
    while yint != 0:
        ans += 1
        count = one(bin(yint))
        yint = yint % count
    return ans

j = 0
for i in range(n):
    xAfter = x
    if xAfter[j] == "0":
        xAfter = x[:j] + '1' +x[j+1:]
    elif xAfter[j] == "1":
        xAfter = x[:j] + '0' +x[j+1:]
    ans = popcount(xAfter)
    print(ans)
    j += 1

Submission status: Runtime Error

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

popc = [0] * ((1 << 19) + 1)
for bit in range(1, 1 << 19):
    opt = bin(bit).count('1')
    popc[bit] = bit % opt

f_list = [0] * ((1 << 19) + 1)
for i in range(1, 1 << 19):
    now = popc[i]
    cnt = 1
    while True:
        if now == 0:
            f_list[i] = cnt
            break
        now = popc[now]
        cnt += 1

N = getN()
X = input()
NX = len(X)
time = X.count('1')
t1 = time + 1
t2 = time - 1

lis_left_1 = [0] * (NX + 1)

now = 1 % t1
lis_left_1[0] = now
for i in range(1, NX + 1):
    now = (2 * now) % t1
    lis_left_1[i] = now

lis_left_2 = [0] * (NX + 1)

if t2 > 0:
    now = 1 % t2
else:
    now = 0
lis_left_2[0] = now
for i in range(1, NX + 1):
    now = (2 * now) % t2
    lis_left_2[i] = now

left_mother_1 = 0
for i in range(NX):
    if int(X[i]) == 1:
        left_mother_1 += lis_left_1[NX - i - 1]

left_mother_2 = 0
for i in range(NX):
    if int(X[i]) == 1:
        left_mother_2 += lis_left_2[NX - i - 1]

for i in range(N):
    # 1が0に left_mother_2, t2
    if int(X[i]) == 1:
        if t2 == 0:
            print(0)
        opt_mom = left_mother_2
        opt_mom -= lis_left_2[NX - i - 1]
        opt_mom %= t2
        print(f_list[opt_mom] + 1)
    # 0が1に left_mother_1, t1
    else:
        opt_mom = left_mother_1
        opt_mom += lis_left_1[NX - i - 1]
        opt_mom %= t1
        print(f_list[opt_mom] + 1)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    def popcount(n):
        cnt = 0
        for b in range(5):
            cnt += (n >> b) & 1
        return cnt

    n = int(input())
    X = input()
    one = X.count("1")

    for i in range(n):
        x = list(X)
        cnt = one + 1 if x[i] == "0" else one - 1
        x[i] = "1" if x[i] == "0" else "0"
        x = int("".join(x), 2)
        res = 0
        while x:
            if res != 0:
                cnt = popcount(x)
            x %= cnt
            res += 1
        print(res)


if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from functools import reduce, lru_cache
import collections, heapq, itertools, bisect
import math, fractions
import sys, copy

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline().rstrip())
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline().rstrip())
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

def main():
    N = I()
    X = S()
    original_popcount = X.count("1")

    upper_popcount = original_popcount + 1
    lower_popcount = original_popcount - 1

    if original_popcount == 0:
        return

    # Xが0の可能性
    upper = [0] * N
    lower = [0] * N
    upper[-1] = 1 % upper_popcount
    lower[-1] = 1 % lower_popcount

    for i in range(1, N)[::-1]:
        upper[i-1] = (2 * upper[i]) % upper_popcount
        lower[i-1] = (2 * lower[i]) % lower_popcount

    mu = 0
    ml = 0
    for i in range(N):
        if X[i] == "1":
            mu = (mu + upper[i]) % upper_popcount
            ml = (ml + lower[i]) % lower_popcount

    for i in range(N):
        if X[i] == "0":
            m = (mu + upper[i]) % upper_popcount
        else:
            m = (ml - lower[i]) % lower_popcount

        ans = 1
        while m:
            tmp = m
            ones = 0
            while tmp:
                if tmp & 1 == 1:
                    ones += 1
                tmp //= 2
            m %= ones
            ans += 1

        print(ans)



if __name__ == '__main__':
    main()

Submission status: Runtime Error

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


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

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:
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
if X_1m!=0:
    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:
N = int(input())
X = int(input())
answer = [0]*N

def popcount(n,x):
    count = 0
    for i in range(n):
        if (x>>i) & 1 == 1:
            count += 1
    return(count)

keta = '0'+str(N)+'b'
prenum = str(format(N,keta))
import copy


for i in range(N):
    num = copy.deepcopy(prenum)
    if num[i] == '0':
        num = num[:i] + '1' + num[i+1:]
    else:
        num = num[:i] + '0' + num[i+1:]
    #print(num)
    count = 0
    tennum = int(num,2)
    result = 1
    while True:
        if result == 0:
            break
        
        popc = popcount(N,tennum)
        result = tennum%popc
        #print(N,tennum,popcount(N,tennum),result)
        tennum = result
        count += 1
    print(count)

Submission status: Runtime Error

Solution code:
from numba import jit

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

@jit('i4(i2)')
def pc(a):
    cnt = 0
    while a != 0:
        a = int(bin(a%a.count("1"))[2:], 2)
        cnt += 1
    return cnt

for i in range(n):
    print(pc(int(bin(x^2**(n-i-1))[2:], 2)))

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 main(N, X):
    check = "0"*N
    for i in range(N):
        check = check[:i]+"1"+check[i+1:]
        # print(f"check:{check}")
        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
            if x == 0b1:
                print(count+1)
                break
            if x == 0b10:
                print(count+1)
                break
            if x == 0b11:
                print(count+2)
                break
            if x == 0b100:
                print(count+2)
                break
            x = x % popcount(x)
            count += 1
        check = "0"*N


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

main(N, X)

Submission status: Runtime Error

Solution code:
'''Author- Akshit Monga'''
n=int(input())
x=input()
x=x[::-1]
ans1=0
ans2=0
c=x.count('1')
for i in range(0,n):
    if x[i]:
        ans1=(ans1+pow(2,i,c+1))%(c+1)
        ans2=(ans2+pow(2,i,c-1))%(c-1)
to_print=[]
for i in range(0,n):
    if x[i]=='1':
        if c==1:
            to_print.append(0)
            continue
        var=(ans2%(c-1)-pow(2,i,c-1))%(c-1)
        a = 1
        while var:
            var = var % bin(var).count('1')
            a += 1
        to_print.append(a)
    else:
        # print(ans1)
        var = (ans1%(c+1) + pow(2, i, c +1))%(c+1)
        # print(c+1)
        # print(var)
        a = 1
        while var:
            var = var % bin(var).count('1')
            a += 1
        to_print.append(a)
for i in to_print[::-1]:
    print(i)

Submission status: Runtime Error

Solution code:
n = int(input())
X = input()
n = len(X)
ans = 0
numX = X.count("1")
def solve(numX,X):
    global ans
    ans += 1
    y = int(X,2)%numX
    if y == 0:
        return 0
    else:
        z = bin(y)[2:]
        solve(z.count("1"),z)


for i in range(n):
    ans = 0
    tmpX = ""
    tmp = ""
    if X[i] == "0":
        tmpnumX = numX + 1
        tmp = "1"
    else:
        tmpnumX = numX - 1
        tmp = "0"
    if i == 0:
        tmpX = tmp + X[1:]
    elif i == n-1:
        tmpX = X[:i] + tmp
    else:
        tmpX = X[:i] + tmp + X[i+1:]
    solve(tmpnumX,tmpX)
    print(ans)

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 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):
        print(1)
        # 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:
#!/usr/bin/env python3
import sys


def solve(N: int, X: str):
    def pc(n):
        return bin(n).count("1")

    def f(i):
        if i == 0 : return 0
        p = 0
        k = i
        while(k!= 0):
            t = k
            p+=1
            k = t % pc(t)
        return p
    
    ts = [f(i) for i in range(64)]
    # ts = {}
    # for i in range(2*10**5+1):
        # ts[i] = f(i)
    # for i in range(2*10**5+1):
        # ts[i] = f(i)



    x = int(X, 2)
    px = X.count("1")
    for i, xi in enumerate(X):
        if xi == "0":
            temp = (x + 2**(N-i-1))
            l = px+1
        else:
            temp = (x - 2**(N-i-1))
            l = px-1

        if temp == 0:
            print(0)
        else:
            temp = temp % l
            if temp == 0:
                print(1)
            else:
                temp = temp % l
                print(ts[temp]+1)
    
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = next(tokens)  # type: str
    solve(N, X)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def popcount(x):
    x = bin(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 reverse_bin(X, ind):
    ret = X[:ind]
    ret += "1" if X[ind] == "0" else "0"
    ret += X[ind + 1:]

    return ret

def main():
    N = int(input())
    X_str = input()
    X = int(X_str, 2)
    for i in range(len(X_str)):
        count = 0
        X_tr = reverse_bin(X_str, i)
        x = int(X_tr, 2)
        while x != 0:
            x = x % popcount(x)
            count += 1
        print(count)
    

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin
from collections import deque
input = stdin.readline

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

q = deque([])
b = X.count("1")

for i in range(N):
    if X[i] == "0":
        X[i] = "1"
        q.append(["".join(X), b + 1])
        X[i] = "0"
    else:
        X[i] = "0"
        q.append(["".join(X), b - 1])
        X[i] = "1"

while q:
    n, b = q.popleft()
    n = int(n, 2)
    if b == 1 or n % b == 0:
        print(1)
    elif (n % b) % 2 == 0:
        print(2)
    else:
        print(3)