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 copy
n = int(input())
k = input()
xnum = int(k,2)

def f(x):
    a = bin(x)
    a = a[2:]
    num = a.count('1')
    ans = 1
    hantei = x % num
    while hantei != 0:
        ans += 1
        a = bin(hantei)
        a = a[2:]
        num = a.count('1')
        hantei = hantei % num
    return ans

z = []
for i in range(n):
    y = copy.deepcopy(k)
    if y[i] == '1':
        ynum = xnum - 2 ** (n-i-1)
        z.append(ynum)
    else:
        ynum = xnum + 2 ** (n-i-1)
        z.append(ynum)

for j in z:
    ans = f(j)
    print(ans)

Submission status: Runtime Error

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

fn = dict()

def f(n, count):
    # binary = bin(n)[2:]
    popcount = bin(n).count('1')
    # for b in binary:
    #     if b == '1':
    #         popcount += 1
    count += 1
    if n%popcount == 0:
        return count
    else:
        if n in fn:
            return fn[n]
        else:
            x = f(n%popcount, count)
            fn[n%popcount] = x- count
            # fn[n] = x
            return x

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)
    ans = f(n, 0)
    fn[n] = ans
    print(ans)
    # print(fn)
# print(fn)

Submission status: Runtime Error

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


def popcnt(n):
    # n = str(n)
    return bin(n).count("1")

X_list = [0] + [0] * N

for i in range(0, N):

    if X[i] == "0":
        temp = "1"
    elif X[i] == "1":
        temp = "0"

    X_list[i + 1] = str(X[:i]) + str(temp) + str(X[i + 1:])
    X_list[i + 1] = int(X_list[i + 1], 2)
    X_list[i + 1] = bin(X_list[i + 1])

# print(X_list)


# print(X[:2])
# print(X[3:])
# print(X[2])

for i in range(1, N + 1):
    temp = X_list[i]
    count = 0

    x = int(temp, 2)
    y = popcnt(temp)

    # if int(temp, 2) != 0:
    #     temp = int(temp, 2) % popcnt(temp)
    #     count += 1

    while x != 0:
        print(x)
        # print(popcnt(temp))
        x = x % popcnt(x)
        count += 1

    # print("-----")
    print(count)

Submission status: Runtime Error

Solution code:
from functools import lru_cache


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


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


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

for i in range(n):
    x = arr[:i] + str(1 ^ int(arr[i])) + arr[i + 1:]
    print(rec(x))

Submission status: Runtime Error

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

d = {}
def find(s):
    n = int(s,2)
    num_1 = s.count("1")
    if n % num_1 == 0:
        return 1

    if n in d:
        return d[n]
    else:
        n = n % num_1
        d[n] = find(bin(n)[2:]) + 1
        return d[n]
    


for i in range(n):
    if x[i] == "0":
        if i < n -1:
            tmp = x[:i] + "1" +x[i+1:]
        else:
            tmp = x[:i] + "1"
    else :
        if i < n -1:
            tmp = x[:i] + "0" +x[i+1:]
        else:
            tmp = x[:i] + "0"
    n_1 = tmp.count("1")
    a = find(tmp)
    d[int(tmp, 2)] = a
    print(a)

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

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

for n in range(N):
  a = 0
  Y = X
  
  if Y[n]=="0":
    Y = Y[:n]+"1"+Y[n+1:]
  else:
    Y = Y[:n]+"0"+Y[n+1:]
  
  Y = int(Y,2)
  
  while Y!=0:
    a+=1
    Y%=popcount(Y)
  
  print(a)

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
a = []
s = int(x, 2)
k = x.count('1')
d = {}


for i in range(n):
    if int(x[i]) == 0:
        w = s + 2**(n-i-1)
        K = k + 1
    else:
        w = s - 2**(n-i-1)
        K = k - 1
    ans = 1
    S = w % K
    while S != 0:
        S = S % str(bin(S)).count('1')
        if S in d:
            ans += d[S]
        else:
            ans += 1
    d[w] = ans
    print(ans)

Submission status: Runtime Error

Solution code:
#!python3.8
# -*- coding: utf-8 -*-
# aising2020/aising2020_d
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))


def main():
    N = i2n()
    _X = i2s()
    X = int(_X, base=2)
    root_cnt = sum((X >> i) & 1 for i in range(N))
    #print(root_cnt)
    for i in range(N-1, -1, -1):
        d = 1 << i
        n = X ^ d
        #print(bin(d))
        #print(bin(n), n, root_cnt + (-1)**bool(X & d))
        n %= root_cnt + (-1)**bool(X & d)
        cnt = 1
        while n > 0:
            #print(n)
            n %= popcount(n)
            cnt += 1
        #print('#', cnt)
        print(cnt)
    return

def popcount(n):
    return sum((n >> i) & 1 for i in range(n.bit_length()))

main()

Submission status: Runtime Error

Solution code:

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

from collections import defaultdict
d = defaultdict(lambda: -1)

Xmemo = defaultdict(lambda: -1)
Xmemo[0]=0

def popcount(x):

    # 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 dfs(X):
    if Xmemo[X]==-1:
        if d[X]==-1:
            pc = popcount(X)
            d[X]=pc
        else:
            pc = d[X]

        if pc == 1:
            Xmemo[X]=1
            return 1
        Xmemo[X] = dfs(X%pc)+1

    return Xmemo[X]


for i in reversed(range(n)):
    print(dfs(X^(1<<i) ))

Submission status: Runtime Error

Solution code:
N = int(input())
X = int(input(), 2)
from numba import njit

@njit
def popcount(n, cnt, dic):
    if n in dic:
        kos = dic[n]
    else:
        cnt1 = 0
        for i in str(bin(n))[2:]:
            if i == "1":
                cnt1 += 1
        dic[n] = cnt1
        kos = cnt1
    dic2 = dic.copy()
    if n != 0:
        return popcount(n%kos, cnt+1, dic2)
    else:
        return cnt

for i in range(1, N+1):
    mask = 1<<N-i
    x = X ^ mask
    print(popcount(x, 0, {}))

Submission status: Runtime Error

Solution code:
n=int(input())
x=int(input(),2)
if x==1:
    print(0)
    exit()

def popcount(m,p):
    binst=format(m,'b')
    lis=list(binst)
    num=lis.count('1')
    nm=m%num
    p += 1
    if nm==0:
        return p
    else:
        return popcount(nm,p)
for i in range(n-1,-1,-1):
    t=x^(2**(i))
    print(popcount(t,0))

Submission status: Runtime Error

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

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

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

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

n=int(input())
popn=[0 for i in range(n+1)]
for i in range(1,n+1):
  popn[i]=i%popcount(i)
#print(popn)
ans=[0 for i in range(n)]
x=int(input(),2)
num=popcount(x)
for i in range(n):
  if (x>>n-i-1)&1==0:
    popc=num+1
  else:
    popc=num-1
  y=x^(1<<(n-i-1))
  #print(i,y,popc)
  cnt=1
  y=y%popc
  #print(i,y)
  flag=True
  if y==0:
    flag=False
  while flag:
    if popn[y]==0:
      flag=False
      cnt+=1
    else:
      y=popn[y]
      cnt+=1
  ans[i]=cnt
for i in ans:
  print(i)

Submission status: Runtime Error

Solution code:
a=int(input())
b=input()
c=int(b, 2)

pop1=bin(c).count("1")
pop=pop1+2

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

    t=t%m
    count+=1
  list1[i]+=count

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

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

    print(list1[s])

Submission status: Runtime Error

Solution code:
from collections import Counter

N = int(input())
Y = input()
X = int(Y,2)
cnt = bin(X).count('1')
for i in range(1,N+1):
  t = 0
  a = X ^ (1<<(N-i))
  if Y[i-1] == '1':
    b = cnt - 1
  else:
    b = cnt + 1
  a %= b
  t += 1
  while a > 0:
    b = bin(a).count('1')
    a %= b
    t += 1
  print(t)

Submission status: Runtime Error

Solution code:
from collections import defaultdict,deque
from sys import stdin,setrecursionlimit
import heapq,bisect,math,itertools,string,queue,copy
setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, stdin.readline().split()))

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

dp = [-1]*(N+3)

def rec(a):
    ico = str(bin(a)).count('1')
    b = a%ico
    if b == 0:
        dp[b] = 1
        return 1
    if dp[b] != -1:
        dp[a] = dp[b] + 1
        return dp[a]
    res = rec(b) +1
    return res

for i in range(N-1,-1,-1):
    han = pow(2,i)
    if xx & han:
        ans = rec(xx-han)
        print(ans)
    else:
        ans = rec(xx+han)
        print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
a = int('0b'+X, 0)
for i in range(N):
    count = 0
    ic = X.count('1')
    if X[i] == '0':
        ic += 1
        y = a+2**(N-i-1)
    if X[i] == '1':
        ic -= 1
        y = a-2**(N-i-1)
    while True:
        y = y%ic
        ic = str(bin(y)).count('1')
        count += 1
        if y == 0:
            print(count)
            break

Submission status: Runtime Error

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

memo = [0]


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


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

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

    tmp = int(tmp)

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

    print(1)

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

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
z=int('0b'+x)
cnt=0
X=int(x,2)
for i in range(n):
  if x[i]=='1':
    cnt+=1
    
def pop(m):
  return str(bin(m))[2:].count('1')

def func(m):
  cnt=0
  while m>0:
    m=m%pop(m)
    cnt+=1
  return cnt

table=[]
for i in range(n-1):
  table.append(func(i+1))
  
for i in range(n):
  y=X
  if x[i]=='1':
    y-=2**(n-i-1)
  else:
    y+=2**(n-i-1)
  if y>=n:
    print(1+table[(z%cnt)-1])
  else:
    print(table[y-1])

Submission status: Runtime Error

Solution code:
N = int(input().strip())
X = [int(v) for v in input().strip()]

store = [-1] * (2 ** N)

def popcount(bins):
    return sum(bins)


def f(bins):
    # print(bins)
    count = 0
    x = get_num(bins)
    while x != 0:
        if store[x] != -1:
            count += store
            break
        pc = popcount([int(v) for v in bins])
        x = x % pc
        bins = get_bin(x)
        count += 1
    return count


def get_bin(n):
    return bin(n)[2:]


def get_num(bins):
    bins = "".join([str(v) for v in bins])
    return int(bins, 2)


for i in range(N):
    # print(X)
    X[i] = int(not(X[i]))

    print(f(X))

    X[i] = int(not(X[i]))

Submission status: Runtime Error

Solution code:
import copy

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

def Base_n_to_10(X,n):
    out = 0
    for i in range(1,len(str(X))+1):
        out += int(X[-i])*(n**(i-1))
    return out#int out

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

for i in range(n):
    xx = copy.copy(x)
    if xx[i] == '1':
        xx[i] = '0'
    else:
        xx[i] = '1'

    c = 0
    xy = ''.join(xx)
    while True:
        po = popcount(xy)
        k = int(xy, 2) % po
        c += 1
        if k == 0:
            print(c)
            break
        else:
            xy = bin(k)[2:]

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)

now = 1 % t2
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:
        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:
N = int(input())
X = str(input())

def calc(num, cnt, ans):
  ans += 1
  if cnt == 0:
    return ans
  mod = num % cnt
  if mod == 0:
    return ans
  else:
    cnt = bin(mod).count('1')
    return(calc(mod, cnt, ans))

n = int(X, 2)
c = X.count('1')
a = n % (c+1)
b = n % (c-1)
for i in range(1, N+1):
  if X[i-1] == '0':
    print(calc(a+2**(N-i), c+1, 0))
  else:
    if c == 1:
      print(0)
    else:
      print(calc(b-2**(N-i), c-1, 0))

Submission status: Runtime Error

Solution code:
n=int(input())
m=input()
x=int(m,2)
li=list(m)
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

jpop=popcount(x)
jop=x%(jpop+1)
jom=x%(jpop-1)
jppp=jpop+1
jppm=jpop-1
for i in range(0,n):
  nijo=2**(n-i-1)
  if li[i]=="0":
    a=jop+nijo%jppp
    if a>jppp:
      a-=jppp
  else:
    a=jom-nijo%jppm
    if a<0:
      a+=jppm
  co=1
  if a==0:
    print(1)
    continue
  while a!=0:
    co+=1
    a%=popcount(a)
  print(co)

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
ans = [1 for _ in range(N)]

def popcount(n):
  c = 0
  n = str(bin(n))[2:]
  for _ in range(len(n)):
    if n[_] == '1':
      c += 1
  return c

l = 0
for k in range(N):
  if X[k] == '1':
    l+=1
firstpop = [l for _ in  range(N)]


start = []
if N == 1:
  if X[0] == '1':
    a = '0'
    firstpop[0] -= 1
  else:
    a = '1'
    firstpop[1] += 1
  ia = int(a, 2)
  start.append(ia)

if N > 1:
  if X[0] == '1':
    a = '0' + X[1:]
    firstpop[0] -= 1
  else:
    a = '1' + X[1:]
    firstpop[0] += 1
  ia = int(a, 2)
  start.append(ia)

  for k in range(1, N-1):
    if X[k] == '1':
      a = X[:k] + '0' + X[k+1:]
      firstpop[k] -= 1
    else:
      a = X[:k] + '1' + X[k+1:]
      firstpop[k] += 1
    ia = int(a, 2)
    start.append(ia)
  if X[-1] == '1':
    a = X[:-1] + '0'
    firstpop[-1] -= 1
  else:
    a = X[:-1] + '1'
    firstpop[-1] += 1
  ia = int(a, 2) 
  start.append(ia)

mp = l + 1
poplist = [0]
for _ in range(1, l+2):
  poplist.append(popcount(_))

for k in range(N):
  if firstpop[k] == 0:
    ans[k] = 0
  else:
    start[k] %= firstpop[k]



for k in range(len(start)):
  for count in range(10*5):
    if start[k] == 0:
      ans[k] += count
      break
    else:
      start[k] = start[k] % poplist[start[k]]
  


for k in range(N):
  print(ans[k])

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]*(C+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
        if p[n] > 0:
            p[i] += p[n]
            break

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 = (1 << (N-i)) % c
        d = (m-d+c) % c
    else:
        c += 1
        m = Mp
        d = (1 << (N-i)) % c
        d = (m+d) % c

    print(p[d]+1)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
def popcount(n):
    count = 0
    if n != 0:
        while n > 0:
            count += 1
            n = n % bin(n).count("1")
    return count


n = int(input())
a = input()
x = int(a,2)
c1 = bin(x).count("1")

for i in range(n):

    if a[i] == "0":
        c2 = c1 + 1
        ans = x + 2 ** (n - 1 - i)
    else:
        c2 = c1 - 1
        ans = x - 2 ** (n - 1 - i)
    ans = ans % c2


    ans = popcount(ans) + 1

    print(ans)

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 p[a] != -1:
    return p[a]
  else:
    if a == 0:
      ret = 0
    else:
      b = bin(a).count('1')
      ret = 1+calc(a%b)
    p[a] = ret
    return ret

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

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

Submission status: Runtime Error

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


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

Submission status: Runtime Error

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


def bit_count(bits):
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
    return (bits & 0x0000ffff) + (bits >> 16 & 0x0000ffff);


def pop_counter(n):
    return n % bit_count(n)


ans = 0
for n, i in enumerate(X):
    ans = 0
    tmp = int_X ^ pow(2, N - n - 1)
    while tmp != 0:
        tmp = pop_counter(tmp)
        ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n = int(readline())
lst1 = list(readline().rstrip().decode('utf-8'))


res = lst1.copy()
res = "".join(res)
ct = res.count("1")
res = int(res,2)
if ct == 0:
    for i in range(n):
        print(0)
    exit()
if ct == 1:
    amari_of_m = -1
else:
    amari_of_m = res%(ct-1)
amari_of_p = res%(ct+1)

def pow(n,p,mod): #繰り返し二乗法(nのp乗)
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod

def func(res):
    ans = 1
    while True:
        ct = 0
        for i in range(len(bin(res))):
            if res>>i&1:
                ct += 1
        if res%ct == 0:
            print(ans+1)
            return
        else:
            res %= ct
            ans += 1

for i in range(n):
    if lst1[i] == "1" and amari_of_m == -1:
        resres = 0
    else:
        resres = pow(2,n-i-1,ct-1) if lst1[i] == "1" else pow(2,n-i-1,ct+1)
    if lst1[i] == "1":
        resres = amari_of_m - resres
        resres %= ct-1
    else:
        resres = amari_of_p + resres
        resres %= ct+1
    if not resres:
        print(1)
    else:
        func(resres)

Submission status: Runtime Error

Solution code:
import numpy as np

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

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


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

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



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

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


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

Submission status: Runtime Error

Solution code:
# 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] * 20

    def rec(x):
        pop_x = popcount(bi(x, 20))
        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, 20):
        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 < 20:
                print(1 + fs[ri])
            else:
                pop_ri = popcount(bi(ri, 20))
                print(2 + fs[ri % pop_ri])
        else:
            ri = (rm - bi_qm[N-1-i]) % qm
            if ri < 20:
                print(1 + fs[ri])
            else:
                pop_ri = popcount(bi(ri, 20))
                print(2 + fs[ri % pop_ri])



main()
# print(main())

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(input())
X = input()
px = X.count('1')

def xmod(m):
    res = []
    mod = 1
    for s in reversed(X):
        res.append(mod)
        mod = (mod * 2) % m
    
    return list(reversed(res))

plus = xmod(px+1)
minus = xmod(px-1)
sp = sum(plus)
sm = sum(minus)

for i in range(N):
    if X[i] == '0':
        sum_ = (sp - plus[i]) % (px+1)
        if sum_ == 0:
            print(0)
        else:
            cnt = 0
            while sum_ == 0:
                cnt += 1
                sum_ = sum_ % popcpunt(sum_)
            print(cnt)
    else:
        sum_ = (sm - minus[i]) % (px-1)
        if sum_ == 0:
            print(0)
        else:
            cnt = 0
            while sum_ == 0:
                cnt += 1
                sum_ = sum_ % popcpunt(sum_)
            print(cnt)
      
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

Submission status: Runtime Error

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

dic = {0: 0, 1: 1, 2: 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 f(x):
    #print(x)
    if x in dic:
        #print("!", x, dic[x])
        return dic[x]
    else:
        next_x = x % popcount(x)
        ans = f(next_x) + 1
        dic[x] = ans
        return ans

for i in range(n):
    keta = n - i - 1
    bit = 2 ** keta
    trans_num = num ^ bit
    #print(bin(num), bin(bit), bin(trans_num))
    #print("ans", f(trans_num))
    print(f(trans_num))

Submission status: Runtime Error

Solution code:
from sys import stdin, stdout

int_in = lambda: int(stdin.readline())
arr_in = lambda: [int(x) for x in stdin.readline().split()]
mat_in = lambda rows: [arr_in() for _ in range(rows)]
str_in = lambda: stdin.readline().strip()
out = lambda o: stdout.write("{}\n".format(o))
arr_out = lambda o: out(" ".join(map(str, o)))
bool_out = lambda o: out("YES" if o else "NO")
tests = lambda: range(1, int_in() + 1)
case_out = lambda i, o: out("Case #{}: {}".format(i, o))


cache = {}
def popcount(n):
    if n in cache:
        return cache[n]
    pop = bin(n).count("1")
    result = popcount(n % pop) + 1
    cache[n] = result
    return result


def mod(x, y):
    power_of_two = [0] * len(x)
    power_of_two[0] = 1 % y
    for i in range(1, len(x)):
        power_of_two[i] = power_of_two[i - 1] * (2 % y)
        power_of_two[i] %= y
    result = 0
    i = 0
    j = n - 1
    while i < len(x):
        if x[j] == 1:
            result += power_of_two[i]
            result %= y
        i += 1
        j -= 1
    return result


def solve(n, x):
    cache[0] = 0
    ones = x.count(1)
    for i in range(n):
        # flip bits
        old = x[i]
        x[i] = 1 if old == 0 else 0

        curr_ones = ones + (1 if old == 0 else -1)
        next_num = mod(x, curr_ones)
        yield popcount(next_num) + 1
        
        # reset
        x[i] = old

if __name__ == "__main__":
    n = int_in()
    x = [int(y) for y in str_in()]
    result = solve(n, x)
    for item in result:
        out(item)

Submission status: Runtime Error

Solution code:

import sys
sys.setrecursionlimit(10 ** 7)
from functools import lru_cache

from collections import defaultdict
from copy import deepcopy

# ----------

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

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

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

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


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


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