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:
def popcount(x):
  S = format(x,'b')
  cnt = 0
  for s in S:
    if s=='1':
      cnt+=1
  return cnt
def solve():
  N = int(input())
  X = input()
  num = 0
  pcnt = 0
  for i, x in enumerate(X):
    if x=='1':
      pcnt += 1
      num += 2**(N-i-1)
  a = num//pcnt
  b = num%pcnt
  for i, x in enumerate(X):
    ans = 1
    if x=='1':
      n1 = (a+b-2**(N-i-1))%(pcnt-1)
    else:
      n1 = (b-a+2**(N-i-1))%(pcnt+1)
    while n1 >5:
      pc = popcount(n1)
      n1 = n1%pc
      ans +=1
    if n1==0:
      print(ans)
    elif n1==1:
      print(ans+1)
    elif n1==2:
      print(ans+1)
    elif n1==3:
      print(ans+2)
    elif n1==4:
      print(ans+1)
    elif n1==5:
      print(ans+2)
solve()

Submission status: Runtime Error

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

def calc(num, ans):
  a = ans
  n = format(num, 'b')
  cnt = n.count('1')
  if cnt == 0:
    a += 1
    print(a)
  mod = num % cnt
  if mod == 0:
    a += 1
    print(a)
  else:
    a += 1
    calc(mod, a)

n = int(X, 2)
for i in range(1, N+1):
  num = n
  if X[i-1] == '0':
    num += 2**(N-i)
    calc(num, 0)
  else:
    num -= 2**(N-i)
    calc(num, 0)

Submission status: Runtime Error

Solution code:
def popcount(y, n):
  now_n = n
  c = 0
  while(y!=0):
    y = y%now_n
    now_n = bin(y)[2:].count('1')
    c += 1
  return c
    
  

n = int(input())
x = input()
init_n = x.count('1')
intx = int(x, 2)
i2 = pow(2, n-1)
for i in range(n):
  now_n = 0
  now_x = 0
  if(x[i] == '1'):
    now_n = init_n -1
    now_x = intx - i2
  else:
    now_n = init_n +1
    now_x = intx + i2
  print(popcount(now_x, now_n))
  i2 = int(i2/2)

Submission status: Runtime Error

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


def arrayTo2(A):
    ans = 0
    l = len(A)
    for i in range(l):
        if (A[i] == '1'):
            ans += 2 ** (l-i-1)

    return ans


N = int(input())

popcountA = [0]*(2**N)
for i in range(1, 2**N-1):
    popcountA[i] = popcount(i)

print(popcountA)

X = input()

for i in range(N):
    Xi = []
    for j in range(N):
        if (i == j):
            if (X[i] == '0'):
                Xi.append('1')
            else:
                Xi.append('0')
        else:
            Xi.append(X[j])

    ans = 0
    n = arrayTo2(Xi)
    while (n > 0):
        n = n % popcountA[n]
        ans += 1

    print(ans)

Submission status: Runtime Error

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

for i in range(n):
    y=x[:]
    if x[i]=="1":
        y=y[:i]+"0"+y[(i+1):]
    else:
        y=y[:i]+"1"+y[(i+1):]
    
    k=0
    while y!="0b0":
        m=y.count("1")
        y=str(bin(int(y,2)%m))
        k+=1

    print(k)

Submission status: Runtime Error

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

li_x=[]
for num in range(n):
  num=2**num
  li_x.append(x^num)
  
li_x.reverse()

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

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

def popcount_rec(i):
  j=popcnt(i)
  k=i%j
  if k>0:
    return 1+popcount_rec(k)
  elif k<=0:
    return 1
  
for num in li_x:
  print(popcount_rec(num))

Submission status: Runtime Error

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

import sys
from io import StringIO
import unittest

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 + 1)
    amr2=[0]*((10**5)*2 + 1)
    bits=[False]*((10**5)*2 + 1)

    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:
"""
    こんにちは。これはクシャルです
    
    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("".join(q),2)
        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:
n = int(input())
x = list(input())

print(x)

B = 2**20 - 1

memo = [None for _ in range(2*n)]


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


def calc(p):
    cnt = 1
    p = p % popcount(p)
    tmp = p
    while tmp != 0:
        tmp = tmp % popcount(tmp)

        if memo[tmp] is not None:
            return memo[tmp] + cnt

        cnt += 1

    memo[p] = cnt
    return cnt


for i in range(n):
    tmp = x[:]
    tmp[i] = '1' if tmp[i] == '0' else '0'
    tmp = int(''.join(tmp), 2)
    print(calc(tmp))

Submission status: Runtime Error

Solution code:
import sys #追加

n=int(input())
sys.setrecursionlimit(10**5*2)

s=input()
x=int(s,2)
ans=[]

ans_memo=[0]*(2**(n+1))
#print(ans_memo)
ans_memo[1]=1
ans_memo[2]=1

def DEF(x,cnt):
    global ans_memo
    #print(x,cnt,ans_memo)
    if ans_memo[x]!=0:
        return ans_memo[x]
    if x==0:
        return 0    
    else:
        if x%(str(bin(x)).count("1"))==0:
            ans_memo[x]=1
            return 1
        else:
            tmp=DEF(x%(str(bin(x)).count("1")),cnt+1)+1
            ans_memo[x]=tmp
            return tmp

ans=[]

for i in range(n):
    tmp=2**(n-i-1)
    tmp_num=x
    #1の時
    if tmp&tmp_num:
        tmp_num-=tmp
        #print(bin(tmp_num),n-i-1)
        ans.append(DEF(tmp_num,0))
        
    else:
        tmp_num+=tmp
        #print(bin(tmp_num),n-i-1)
        ans.append(DEF(tmp_num,0))

#print(ans_memo)

for item in ans:
    print(item)

Submission status: Runtime Error

Solution code:
N = int(input())
X = int('0b' + input(), 0)

for i in range(N-1, -1, -1):
  xx = X ^ (1 << i)
  c = 0
  while xx > 0:  
    x = xx - ((xx >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x += (x >> 8)
    x += (x >> 16)
    x += (x >> 32)
    x &= 0x0000007f
    xx %= x
    c += 1
  else:
    print(c)

Submission status: Runtime Error

Solution code:
import sys
input = lambda:sys.stdin.readline().rstrip()
from collections import defaultdict
sys.setrecursionlimit(10**7)

def solve(k, cnt):  
    S = str(bin(k)).count("1") 
    L = k % S
    if L == 0:
        return 1
    cnt += solve(L,cnt)
    return cnt 

N = int(input())
P = input()
Df = int(P,2)
for i in range(N-1):
    cnt = 1
    if P[i] == "1":
        tmp = Df - 2**(N-i-1)
    else:
        tmp = Df + 2**(N-i-1)    
    #print(tmp, bin(tmp))
    print(solve(tmp,cnt))
    
cnt = 1
if P[-1] == "1":
    tmp = Df - 1
else:
    tmp = Df + 1
print(solve(tmp,cnt))
#print(solve(N,cnt))

Submission status: Runtime Error

Solution code:
import sys

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

# one = X.count("1")
Number = int(X,2)

def popcount(num,c):
    one = bin(num).count("1")
    next = num % one
    if next == 0:
        return c
    else:
        return popcount(next,c+1)

for i in range(N):
    if X[i] == "0":
        tmp = Number + 2 ** (N - (i + 1))
    else:
        tmp = Number - 2 ** (N - (i + 1))
    
    print(popcount(tmp,1))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
def popcount(x):
    ret = 0
    for i in range(len(x)):
        if x[i] == '1':
            ret += 1

    return ret

def main():
    n = int(input())
    x_init = input()
    pcnt_init = popcount(x_init)

    for i in range(n):
        if x_init[i] == '1':
            x = x_init[:i] + '0' + x_init[(i+1):]
            pcnt = pcnt_init - 1
        else:
            x = x_init[:i] + '1' + x_init[(i+1):]
            pcnt = pcnt_init + 1

        cnt = 1
        while True:
            x_num = int(x, 2) % pcnt
            if x_num == 0:
                break
            else:
                cnt += 1
                x = format(x_num, 'b')
                pcnt = popcount(x)
        print(cnt)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!

mm = {}

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

def f(n):
    n%=popcorn(n)
    return n
    
def nf(n,count):
    if(n == 0):
        return count
    else:
        n%=popcorn(n)
        return nf(n,count+1)


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

Submission status: Runtime Error

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


def solve(N: int, X: str):
    def pc(n):
        return bin(n).count("1")
    
    popsc = [0] * 25
    for i in range(1,25):
        p = 0
        t = i
        k = -1
        while(k!= 0):
            p+=1
            k_ = t % pc(t)
            t = k
            k = k_
        popsc[i] = p
    # print(popsc)
    # for ai, bi in zip(range(25),popsc):
        # print(ai,bi)

    x = int(X, 2)
    for i in range(N):
        if X[i] == "0":
            temp = (x + 2**(N-i-1))
        else:
            temp = (x - 2**(N-i-1))
        
        if temp > 24:
            temp = temp % bin(temp).count("1")
            p = 1
        else:
            temp = temp
            p = 0
        print(popsc[temp]+p)

    
    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:
a = input()
N = input()
for i in range(len(N)):
    n = list(N)
    if N[i] =="0":
        n[i] = "1"
    else:
        n[i] = "0"
    #print((*n))
    n = int("".join(n),2)        
    s = 0
    while True:
        n = n % sum(list(map(int,bin(n)[2:])))
        s = s + 1
        if n > 0:
            continue
        break
    print(s)

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    X = list(input())

    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

    # X = ['']*N
    # for i in range(N):
    #     X[i] = str(random.randint(0, 1))
    # print("".join(X))
    C = X.count("1")

    dp = [0]*N
    dp[0] = 0
    for i in range(1, N):
        k = i % popcount(i)
        dp[i] = 1 + dp[k]

    # def solve(n, d):

    for i in range(N):
        if X[i] == "0":
            X[i] = '1'
            print(dp[int((''.join(X)), 2) % (C+1)] + 1)
            #tmp = dp[int((''.join(X)), 2) % (C+1)] + 1
            X[i] = '0'
        else:
            if C == 1:
                print(0)
                continue
            X[i] = '0'
            print(dp[int((''.join(X)), 2) % (C-1)] + 1)
            #tmp = dp[int((''.join(X)), 2) % (C-1)] + 1
            X[i] = '1'


main()
# print(dp)

Submission status: Runtime Error

Solution code:
N = int(input())
X = list( i for i in str(input()))


def nisin(a, I):
  a = a.copy()
  if a[I] == '0':
    a[I] =  '1'
  elif a[I] == '1':
    a[I] = '0'
    
  return int(''.join(a), 2)

def solve(kazu):
  cnt = 0
  
  while True:
    cnt += 1
    kazu2 = format(kazu,'b')
    c = kazu2.count('1')
    if kazu % c == 0:
      break
    kazu = kazu % c
  return cnt

for i in range(N):
  print(solve(nisin(X, i)))

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
f = [0]*(N+1)
for i in range(1, N):
    a = sum(list(map(int, bin(i)[2:])))
    f[i] = f[i%a]+1

for i in range(N):
    if X[i] == '1':
        x = int(X[0:i]+'0'+X[i+1:], 2)
    else:
        x = int(X[0:i]+'1'+X[i+1:], 2)
    a = sum(list(map(int, bin(x)[2:])))
    print(f[x%a]+1)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n = int(input())
x = list(input())
y = x.count("1")
s, t = y - 1, y + 1
p = [1] * 20
for i in range(1, 20):
    p[i] = p[i - 1] * 2
p.sort(reverse = True)
a, b, u, v = 1 / 2, 1 / 2, 0, 0
m1, m2 = [0] * n, [0] * n
for i in range(1, n + 1):
    a += a
    a %= s
    b += b
    b %= t
    m1[i - 1] = a
    m2[i - 1] = b
    if x[-i] == "1":
        u += a
        v += b
ans = [1] * n
for i in range(1, n + 1):
    if x[-i] == "1":
        j = (u - m1[i - 1]) % s
    else:
        j = (v + m2[i - 1]) % t
    if not j == 0:
        while not j == 0:
            ans[-i] += 1
            l = j
            cnt = 0
            for k in p:
                if l == 0:
                    break
                if k <= l:
                    cnt += 1
                    l -= k
            j = j % cnt
for i in ans:
    print(i)

Submission status: Runtime Error

Solution code:
k = int(input())
x = list(str(input()))
p = [0] * 1000
C = [0] * 1000

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):
    temp = x[:]
    if temp[i] == "0":
        temp[i] = "1"
    else:
        temp[i] = "0"
    num = int("".join(temp),2)
    c = 1
    num %= bin(num).count("1")
    if num == 0:
        c -= 1
    print(c+C[num]+1)

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

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

Submission status: Runtime Error

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

def popcnt1(n):
    return bin(n).count("1")
def answer(X):
  c = int(''.join(X),2)
  ans = 0
  while True:
    ans += 1
    pct = popcnt1(c)
    c = c%pct
    if c == 0:
      break
  return ans
def xor(s):
  if s == '0':
    return '1'
  else:
    return '0'

x[0] = xor(x[0])
print(answer(x))
for i in range(1,N):
  x[i] = xor(x[i])
  x[i-1] = xor(x[i-1])
  print(answer(x))

Submission status: Runtime Error

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

x_1 = x.count('1')
flag = 0
if(x_1 == 0):
    flag = 1
if(x_1 == 1):
    flag = 2

data = [0 for i in range(n+1)]
data[0] = 0
for i in range(1,n+1):
    i_str = format(i,'b')
    ne = i % (i_str.count('1'))
    data[i] = data[ne] + 1

up = [0 for i in range(n)]
do = [0 for i in range(n)]

d = 1
for i in range(n):
    up[i] = d % (x_1 + 1)
    d *= 2
d = 1
if(flag == 0):
    for i in range(n):
        do[i] = d % (x_1 - 1)
        d *= 2

upp = 0
dow = 0

for i in range(n):
    if(x[n-i-1] == '1'):
        upp += up[i]
        upp %= (x_1+1)
        dow += do[i]
        dow %= (x_1-1)


for i in range(n):
    if(x[i] == '0'):
        sam = upp + up[n-i-1]
        sam %= (x_1+1)
        print(data[sam]+1)
    elif(flag == 0):
        sam = dow - do[n-i-1]
        sam %= (x_1-1)
        print(data[sam]+1)
    elif(flag == 2):
        print('0')

Submission status: Runtime Error

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

pop = [0]*(N+1)
amari = [0]*(N+1)
for i in range(1,N+1):
    pop[i]=pop[i-(i&(-i))]+1
    amari[i] = amari[i%pop[i]]+1

cnt1 = 0
for i in range(N):
    if X[i]=="1":
        cnt1+=1
Y = cnt1+1
Z = cnt1-1

baseY = 0
baseZ = 0
for i in range(N):
    K = int(X[N-1-i])
    if K==1:
        baseY += pow(2,i,Y)
        baseZ += pow(2,i,Z)
baseY = baseY%Y
baseZ = baseZ%Z


for i in range(N):
    if X[i]=="0":
        out = (baseY + pow(2,N-1-i,Y))%Y
        print(amari[out]+1)
    elif X[i]=="1":
        out = (baseZ - pow(2,N-1-i,Z))%Z
        print(amari[out]+1)

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
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(x, 2)
y = k(x,n)
for i in range(n):
    an = 0
    if 2**i &x:
        z = x-2**i
        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:
#create date: 2020-07-11 21:18

import sys
stdin = sys.stdin

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def popcount(m):
    res = 0
    while m:
        if m & 1:
            res += 1
        m //= 2
    return res
def f(m):
    cnt = 0
    while m:
        #print("test", m)
        m = m % popcount(m)
        cnt += 1
    return cnt

def main():
    n = ni()
    x = ns()
    pop0 = x.count("1") + 1
    pop1 = x.count("1") - 1
    y0 = 0; y1 = 0
    for i, xi in enumerate(x):
        r = n - i - 1
        if xi == "1":
            y0 += pow(2, r, pop0)
            y1 += pow(2, r, pop1)
            y0 %= pop0
            y1 %= pop1

    for i, xi in enumerate(x):
        r = n - i - 1
        if xi == "0":
            m = (y0 + pow(2, r, pop0)) % pop0
            print(f(m) + 1)
        else:
            m = (y1 - pow(2, r, pop1)) % pop1
            print(f(m) + 1)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n = 2 * 10 ** 5
k = int(input())
x = list(str(input()))
p = [0] * 100
C = [0] * 100

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

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

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

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
popcount_X = X.count('1')
numX = int(X, 2)
a, b = numX % (popcount_X + 1), numX % (popcount_X - 1)
for i, x in enumerate(X, 1):
    if x == '1' and popcount_X == 1:
        print(0); continue
    ans = 1
    if x == '1':
        temp = (b - pow(2, N - i, popcount_X - 1)) % (popcount_X - 1)
    else:
        temp = (a + pow(2, N - i, popcount_X + 1)) % (popcount_X + 1)
    while temp:
        p = format(temp, 'b').count('1')
        temp %= p
        ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
X = list(input())
X = [int(x) for x in X]
X.reverse()

def popcnt0(n):
    c = 0
    for i in range(64):
        c += (n >> i) & 1
    return c
  
#最初にNまでの表を作る
D = [0 for _ in range(N+1)]
D[1] = 1
for i in range(2, N+1):
  D[i] = D[i % popcnt0(i)] + 1
  
#次に、Xの１のカウントを求める
ct_1 = 0
for x in X:
  if x == 1:
    ct_1 += 1

#ct_1-1による2^n mod
B = [0 for _ in range(N)]
j = 1
for i in range(N):
  B[i] = j
  j *= 2
  j %= ct_1 - 1 
  
#ct_1+1による2^n mod
C = [0 for _ in range(N)]
j = 1
for i in range(N):
  C[i] = j
  j *= 2
  j %= ct_1 + 1 

#X mod ct_1-1 と、X mod ct_1+1 を求める
s = 0
t = 0
for i in range(N):
  s += X[i] * B[i]
  t += X[i] * C[i]
  s %= ct_1-1
  t %= ct_1+1

X.reverse()
#print(X)
#print(D,B,C)
i = N-1
#各場合の1回目の操作後の数を計算して、Dをつかって答えを出す
for x in X:
  if x == 1:
    k = (s - B[i]) % (ct_1-1)
  else:
    k = (t + C[i]) % (ct_1+1)
  i -= 1
  print(D[k]+1)

Submission status: Runtime Error

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

Submission status: Runtime Error

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


def fx(x):
    xbin = bin(x)
    popcount = xbin.count("1")
    return (x % popcount)


for i in range(N):
    fn = 0
    if X[i] == "0":
        Xi = int(X, 2) + 2 ** (N - i - 1)
    else:
        Xi = int(X, 2) - 2 ** (N - i - 1)

    while True:
        Xi = fx(Xi)
        fn += 1
        if Xi == 0:
            break
        else:
            pass

    print(fn)

Submission status: Runtime Error

Solution code:
def popcount(n):
    if n == 0:
        return 0
    n2 = n
    diver = 0
    while n2 != 0:
        if n2 % 2 == 1:
            diver += 1
        n2 = n2 // 2
    return diver


N = int(input())
X_in = input()
X_len = len(X_in)
X_d_r = list(X_in.lstrip('0'))[::-1]
X = 0
for i, c in enumerate(X_d_r):
    if c == '1':
        X += (1 << i)
# print('X in dec is ', X)
n_one = X_in.count('1')
for i in range(X_len-1, -1, -1):
    # print(i, X_in[-i-1])
    if X_in[-i-1] == '0':
        X_tmp = X + (1 << i)
        p = 1
    else:
        X_tmp = X - (1 << i)
        p = -1
    # print('x_tmp', X_tmp)
    X_tmp = X_tmp % (n_one + p)
    ans = 1
    while X_tmp != 0:
        X_tmp = X_tmp % popcount(X_tmp)
        ans += 1
    print(ans)

Submission status: Runtime Error

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

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

def solve(num):
    cnt=0
    now=num
    for i in range(100):
        if now==0:
            break
        now%=p(now)
        cnt+=1
    return cnt

decx=int(x, 2)

init_p = p(decx)

for i in range(n):
    now_x=decx
    if x[i]=="0":
        now_p=init_p+1
        now_x+=pow(2,n-1-i)
    else:
        now_p=init_p-1
        now_x-=pow(2,n-1-i)

    now_x%=now_p

    print(solve(now_x)+1)

Submission status: Runtime Error

Solution code:
N = int(input())
X = list(input())
X = [int(x) for x in X]
X.reverse()

def popcnt0(n):
    c = 0
    for i in range(64):
        c += (n >> i) & 1
    return c
  
#最初にNまでの表を作る
D = [0 for _ in range(N+1)]
D[1] = 1
for i in range(2, N+1):
  D[i] = D[i % popcnt0(i)] + 1
  
#次に、Xの１のカウントを求める
ct_1 = 0
for x in X:
  if x == 1:
    ct_1 += 1

#ct_1-1による2^n mod
B = [0 for _ in range(N)]
j = 1
for i in range(N):
  B[i] = j
  j *= 2
  j %= ct_1 - 1 
  
#ct_1+1による2^n mod
C = [0 for _ in range(N)]
j = 1
for i in range(N):
  C[i] = j
  j *= 2
  j %= ct_1 + 1 

#X mod ct_1-1 と、X mod ct_1+1 を求める
s = 0
t = 0
for i in range(N):
  s += X[i] * B[i]
  t += X[i] * C[i]
  s %= ct_1-1
  t %= ct_1+1

X.reverse()
print(X)
#print(D,B,C)
i = N-1
#各場合の1回目の操作後の数を計算して、Dをつかって答えを出す
for x in X:
  if x == 1:
    k = (s - B[i]) % (ct_1-1)
  else:
    k = (t + C[i]) % (ct_1+1)
  i -= 1
  print(D[k]+1)

Submission status: Runtime Error

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

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

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

    return K * x

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

popcount = [0] * (10**6)
for i in range(10**6):
    popcount[i] = format(i, 'b').count('1')

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

def f(num, cnt):
    if num == 0:
        return cnt
    return f(num % popcount[num], cnt+1)

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

Submission status: Runtime Error

Solution code:
N=int(input())
X=input()
XX=0
for i in range(N):
    XX+=int(X[N-i-1])*2**i
#print(XX)

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

def change(x,j):
    if int(x[j]):
        return XX-2**(N-1-j)
    else:
        return XX+2**(N-1-j)

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

def F(t):
    n=t
    if n<19:
        return table[n]
    else:
        n%=popcnt5(n)
        return table[n]+1

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

for i in range(N):
    #print(change(X,i))
    print(F(change(X,i)))

Submission status: Runtime Error

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

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

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

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

        x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
        x = x + (x >> 8) # 16bitごと
        x = x + (x >> 16) # 32bitごと
        x = x + (x >> 32) # 64bitごと = 全部の合計
        return x & 0x0000007f
  
    def f(x):
        temp = x
        count = 0
        while temp > 0:
            temp = temp % popcount(temp)
            count += 1
        return count
    
    ans = [0]*N
    for i in range(0, N):
        xi = X ^ (1 << i)
        ans[N-i-1] = f(xi)
    for a in ans:
        print(a)

main()