Problem:


Score : 400 points

Problem Statement

Let \mathrm{popcount}(n) be the number of 1s in the binary representation of n.
For example, \mathrm{popcount}(3) = 2, \mathrm{popcount}(7) = 3, and \mathrm{popcount}(0) = 0.

Let f(n) be the number of times the following operation will be done when we repeat it until n becomes 0: "replace n with the remainder when n is divided by \mathrm{popcount}(n)." (It can be proved that, under the constraints of this problem, n always becomes 0 after a finite number of operations.)

For example, when n=7, it becomes 0 after two operations, as follows:

\mathrm{popcount}(7)=3, so we divide 7 by 3 and replace it with the remainder, 1.

\mathrm{popcount}(1)=1, so we divide 1 by 1 and replace it with the remainder, 0.

You are given an integer X with N digits in binary.
For each integer i such that 1 \leq i \leq N, let X_i be what X becomes when the i-th bit from the top is inverted.
Find f(X_1), f(X_2), \ldots, f(X_N).

Constraints

1 \leq N \leq 2 \times 10^5

X is an integer with N digits in binary, possibly with leading zeros.

Input

Input is given from Standard Input in the following format:

N
X

Output

Print N lines. The i-th line should contain the value f(X_i).

Sample Input 1

3
011

Sample Output 1

2
1
1

X_1 = 7, which will change as follows: 7 \rightarrow 1 \rightarrow 0. Thus, f(7) = 2.

X_2 = 1, which will change as follows: 1 \rightarrow 0. Thus, f(1) = 1.

X_3 = 2, which will change as follows: 2 \rightarrow 0. Thus, f(2) = 1.

Sample Input 2

23
00110111001011011001110

Sample Output 2

2
1
2
2
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
3



Sample input:
3
011


Sample output:
2
1
1

Submission status: Runtime Error

Solution code:
N = int(input())

cnt = [0] * 6 * 10000 + 1

for x in range(1, 100):
    for y in range(1, 100):
        for z in range(1, 100):
            cnt[x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x] += 1

for i in range(1, N + 1):
    print(cnt[i])

Submission status: Runtime Error

Solution code:
# 数のbitに含まれる1の数をカウント
def bitsoncount(x):
    return bin(x).count('1')

def solve(x):
    global ans
    bx = bitsoncount(x)
    if bx == 0:
        return ans
    else:
        ans += 1
        x = x % bx
        solve(x)


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

Xb = bitsoncount(int(X, 2))
X0 = int(X, 2) % (Xb-1)
X1 = int(X, 2) % (Xb+1)

for x, i in zip(X, reversed(range(N))):
    x = int(x)
    if x == 0:
        temp = (X1 + pow(2, i, Xb+1)) % (Xb+1)
        ans = 1
    else:
        if Xb - 1 == 0:
            print(0)
            continue
        temp = (X0 - pow(2, i, Xb-1)) % (Xb-1)
        ans = 1
    
    solve(temp)
    print(ans)

Submission status: Runtime Error

Solution code:
# 数のbitに含まれる1の数をカウント
def bitsoncount(x):
    return bin(x).count('1')

def solve(x):
    global ans
    bx = bitsoncount(x)
    if bx == 0:
        return ans
    else:
        ans += 1
        x = x % bx
        solve(x)


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

Xb = bitsoncount(int(X, 2))
X0 = int(X, 2) % (Xb-1)
X1 = int(X, 2) % (Xb+1)

for x, i in zip(X, reversed(range(N))):
    x = int(x)
    if x == 0:
        temp = (X1 + pow(2, i, Xb+1))
        ans = 1
    else:
        if Xb - 1 == 0:
            print(0)
            continue
        temp = (X0 - pow(2, i, Xb-1))
        ans = 1
    
    solve(temp)
    print(ans)

Submission status: Runtime Error

Solution code:
from sys import stdin,stdout
def INPUT():return list(int(i) for i in stdin.readline().split())
def inp():return stdin.readline()
def out(x):return stdout.write(x)
import math
###############################################################################\
def power(a,p,m):
    res=1
    while(p>0):
        if p&1:
            res=(res*a)%m
        a=(a*a)%m
        p//=2
    return res%m
n=int(input())
s=input()
A=list(int(i) for i in s)
R=[]
for i in range(n-1,-1,-1):
    R.append(A[i])
one=0
for e in A:
    if e==1:
        one+=1
max=one+1
min=one-1
ansmax=0
ansmin=0
#print(one)
for i in range(n):
    ansmax=(ansmax+power(2,i,max)*(R[i]))%max
    ansmin=(ansmin+power(2,i,min)*R[i])%min
def popcount(z):
    ans=0
    while(z!=0):
        if z%2==1:
            ans+=1
        z//=2
    return ans
#print(ansmax,ansmin)
B=[]
for i in range(n):
    if R[i]==1:
        r=(ansmin-power(2,i,min))%min
        count=1
        while(r!=0):
            count+=1
            r=r%popcount(r)
        B.append(count)
        #print(count)
    else:
        r=(ansmax+power(2,i,max))%max
        count=1
        while(r!=0):
            count+=1
            r=r%popcount(r)
        B.append(count)
B.reverse()
for ele in B:
    print(ele)

Submission status: Runtime Error

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

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

def popcount(n):
    cnt = 0
    while n > 0:
        cnt += n & 1
        n //= 2
    return cnt
def f(n):
    cnt = 0
    while n != 0:
        n = n % popcount(n)
        cnt += 1
    return cnt

ones = X.count('1')
MOD1 = ones + 1
MOD2 = ones - 1
pow1 = [1] * (len(X) + 1)
pow2 = [0] * (len(X) + 1)
if MOD2 != 0:
    pow2[0] = 1
    for i in range(1, len(X) + 1):
        pow1[i] = (pow1[i - 1] * 2) % MOD1
        pow2[i] = (pow2[i - 1] * 2) % MOD2
else:
    for i in range(1, len(X) + 1):
        pow1[i] = (pow1[i - 1] * 2) % MOD1

X1, X2 = 0, 0
for i in range(N):
    if X[i] == '1':
        X1 += (2 * X1 + 1) % MOD1 
        X2 += (2 * X2 + 1) % MOD2
X1 %= MOD1
if MOD2 != 0:
    X2 %= MOD2

for i in range(N):
    d = N - i - 1
    if X[i] == '0':
        x = (X1 + pow1[d]) % MOD1
        print(f(x) + 1)
    else:
        if MOD2 != 0:
            x = (X2 - pow2[d]) % MOD2
            print(f(x) + 1)
        else:
            print(0)

Submission status: Runtime Error

Solution code:
import sys

N = int(sys.stdin.readline().strip())
X = sys.stdin.readline().strip()

def f(num):
    if num == 0:
        return 0
    elif num == 1 or num == 2:
        return 1
    
    b = bin(num)
    popcnt = b.count('1')
    
    if num % popcnt == 0:
        return 1
    elif popcnt == 0:
        return 0
    else:
        return f(num % popcnt) + 1

nX = int(X, 2)
pcnt = X.count('1')

nXp = nX%(pcnt+1)
if not pcnt == 1:
    nXm = nX%(pcnt-1)
delta = 2**(N-1)
for i in range(0, N):
    if X[i] == '0':
        print(f((nXp + (delta%(pcnt+1)))%(pcnt+1)) + 1)
    else:
        if pcnt == 1:
            print(0)
            continue
        print(f((nXm - (delta%(pcnt-1)))%(pcnt-1)) + 1)
        

    delta = int(delta/2)

Submission status: Runtime Error

Solution code:
import sys

N = int(sys.stdin.readline().strip())
X = sys.stdin.readline().strip()

def f(num):
    if num == 0:
        return 0
    elif num == 1 or num == 2:
        return 1
    
    b = bin(num)
    popcnt = b.count('1')
    
    if num % popcnt == 0:
        return 1
    else:
        return f(num % popcnt) + 1

nX = int(X, 2)
pcnt = X.count('1')

nXp = nX%(pcnt+1)
if not pcnt == 1:
    nXm = nX%(pcnt-1)
delta = 2**(N-1)
for i in range(0, N):
    if X[i] == '0':
        print(f((nXp + (delta%(pcnt+1)))%(pcnt+1)) + 1)
    else:
        print(f((nXm - (delta%(pcnt-1)))%(pcnt-1)) + 1)
        if pcnt == 1:
            print(0)
            continue
            
    delta = int(delta/2)

Submission status: Runtime Error

Solution code:
import sys

N = int(sys.stdin.readline().strip())
X = sys.stdin.readline().strip()

def f(num):
    if num == 0:
        return 0
    elif num == 1 or num == 2:
        return 1
    
    b = bin(num)
    popcnt = b.count('1')
    
    if num % popcnt == 0:
        return 1
    else:
        return f(num % popcnt) + 1

nX = int(X, 2)
pcnt = X.count('1')
nXp = nX%(pcnt+1)
nXm = nX%(pcnt-1)
delta = 2**(N-1)
for i in range(0, N):
    if X[i] == '0':
        if pcnt + 1 == 0:
            print(0)
            continue
        print(f((nXp + (delta%(pcnt+1)))%(pcnt+1)) + 1)
    else:
        print(f((nXm - (delta%(pcnt-1)))%(pcnt-1)) + 1)
        if pcnt - 1 == 0:
            print(0)
            continue
    delta = int(delta/2)

Submission status: Runtime Error

Solution code:
import sys
#dp = { 0:0, 1:1, 2:1 }
N = int(sys.stdin.readline().strip())
X = sys.stdin.readline().strip()

def f(num):
    if num == 0:
        return 0
    elif num == 1 or num == 2:
        return 1
    
    b = bin(num)
    popcnt = b.count('1')
    
    if num % popcnt == 0:
        return 1
    else:
        return f(num % popcnt) + 1

nX = int(X, 2)
pcnt = X.count('1')
nXp = nX%(pcnt+1)
nXm = nX%(pcnt-1)
delta = 2**(N-1)
for i in range(0, N):
    if X[i] == '0':
        # print(nXp, delta, pcnt+1)
        print(f((nXp + (delta%(pcnt+1)))%(pcnt+1)) + 1)
    else:
        # print(nXm, delta, pcnt-1)
        print(f((nXm - (delta%(pcnt-1)))%(pcnt-1)) + 1)
    delta = int(delta/2)

Submission status: Runtime Error

Solution code:
def index_replace_bin_to_number(number,index):
  number = [number[i] for i in range(len(number))]
  if number[index] == '0':
    number[index] = '1'
  elif number[index] == '1':
    number[index] = '0'
  return int(''.join(number),2)
def popcount(number):
  count =0
  while True:
    number = number%bin(number).replace('0b','').count('1')
    if number == 0:
      break
    else:
      count += 1
  return count+1
times = int(input())
bin_number = input()
for i in range(times):
  number = index_replace_bin_to_number(bin_number,i)
  count = popcount(number)
  print(count)

Submission status: Runtime Error

Solution code:
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby
from heapq import heapify, heappush, heappop

# sys.setrecursionlimit(5000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return map(lambda x: x + d, A)
def ldec(A, d=1): return map(lambda x: x - d, A)

popcount = lambda x: bin(x).count("1")
bitflip = lambda x, n: x ^ (1 << n)
bitflip2 = lambda x, n: x ^ (1 << (len(bin(x))-2 - (n+1)))
bits = lambda x, n = 0: bin(x)[2:].zfill(n)

N = n1()
X = list(map(int, list(s1())))

rt = [0, 0]
t = 1
p = X.count(1)
for i in range(N-1, -1, -1):
    if X[i] == 1:
        rt[0] = (rt[0] + t) % (p - 1)
        rt[1] = (rt[1] + t) % (p + 1)
    t *= 2

for i in range(N):
    if X[i] == 1 and p == 1:
        print(0)
        continue

    if X[i] == 0:
        t = (rt[1] + 2**(N-i-1)) % (p + 1)
    else:
        t = (rt[0] - 2**(N-i-1)) % (p - 1)

    ans = 1
    while t > 0:
        t %= popcount(t)
        ans += 1
    
    print(ans)

Submission status: Runtime Error

Solution code:
def popcount(x):
    return bin(x).count("1")

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



one_cnt=popcount(X)

modp=X%(one_cnt+1)
modm=X%(one_cnt-1) if one_cnt-1!=0 else 0

for i in range(n):
    if s[i]=="1":
        if cnt==1:
            print(0)
            continue
        else:
            num=(modm-pow(2,n-i-1,one_cnt-1))%(one_cnt-1)
    else:
        num=(modp+pow(2,n-i-1,one_cnt+1))%(one_cnt+1)


    cnt=1
    while num!=0:
        num=num%popcount(num)
        cnt+=1
    print(cnt)

Submission status: Runtime Error

Solution code:
n=int(input())

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

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

one_cnt=popcount(X)

modp=X%(one_cnt+1)
modm=X%(one_cnt-1) if cnt-1!=0 else 0

for i in range(n):
    if s[i]==1:
        if cnt==1:
            print(0)
            continue
        else:
            num=(modm-pow(2,n-i-1,one_cnt-1))%(one_cnt-1)
    else:
        num=(modp+pow(2,n-i-1,one_cnt+1))%(one_cnt+1)

    if num==0:
        print(1)
    else:
        cnt=1
        while 1:
            num=num%popcount(num)
            cnt+=1
            if num==0:
                print(cnt)
                break

Submission status: Runtime Error

Solution code:
n=int(input())

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

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

one_cnt=popcount(X)

modp=X%(one_cnt+1)
modm=X%(one_cnt-1)

for i in range(n):
    if s[i]==1:
        num=(modm-pow(2,n-i-1,one_cnt-1))%(one_cnt-1)
    else:
        num=(modp+pow(2,n-i-1,one_cnt+1))%(one_cnt+1)

    if num==0:
        print(1)
    else:
        cnt=1
        while 1:
            num=num%popcount(num)
            cnt+=1
            if num==0:
                print(cnt)
                break

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# 標準入力を取得
N = int(input())
X = int(input(), 2)

# メイン処理


def popcount(n: int) -> int:
    return bin(n).count("1")


popcount_X = popcount(X)
x_minus = X % (popcount_X - 1)
x_plus = X % (popcount_X + 1)
for n in range(1, N + 1):
    if (X >> (N - n)) & 1:
        if popcount_X == 1:
            print(0)
            continue
        x = (x_minus - 2**(N - n)) % (popcount_X - 1)
    else:
        x = (x_plus + 2**(N - n)) % (popcount_X + 1)
    c = 1
    while x != 0:
        x %= popcount(x)
        c += 1
    print(c)

Submission status: Runtime Error

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


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


x_10 = int(x, 2)
p = popcount(x)
r_p1 = x_10 % (p + 1)
r_m1 = x_10 % (p - 1)
# print("x_10 ={0}, p = {1}, r_p1 = {2}, r_m1 = {3}".format(x_10, p, r_p1, r_m1))

for i in range(n):
    out = 1
    # print("x[i] = {0}".format(x[i]))
    if x[i] == '1':
        if p == 1:
            m, out = 0, 0
        else:
            m = (r_m1 - ((2 ** (n - i - 1)) % (p - 1))) % (p - 1)
    else:
        m = (r_p1 + ((2 ** (n - i - 1)) % (p + 1))) % (p + 1)
    while m > 0:
        # print("m = {0}".format(m))
        m = m % popcount(format(m, 'b'))
        out += 1
    print(out)

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
p=x.count('1')

#愚直に解く関数を定義
def solve(n):
    count=0
    while n:
        popcount=bin(n).count('1')
        n%=popcount
        count+=1
    return count+1

#popcount(x)が0,1だった場合に対応
if p==0:
    for i in range(n):
        print(1)
    exit()
elif p==1:
    exit(1)
    z=x.index('1')
    for i in range(n):
        if i==z:
            print(0)
        else:
            tmp=(pow(2,z,p+1)+pow(2,i,p+1))%(p+1)
            print(solve(tmp))
    exit()


#2^i mod(p+1),2^i mod(p-1)のリストを作成
a,b=[],[]
for i in range(n):
    a.append(pow(2,i,p+1))
    b.append(pow(2,i,p-1))

#x mod(p+1),x mod(p-1)を計算
a1,b1=0,0
for i in range(n):
    if x[-1-i]=='1':
        a1+=a[i]
        b1+=b[i]

#本計算
for i in range(n):
    if x[i]=='1':
        tmp=(b1-b[-1-i])%(p-1)
    else:
        tmp=(a1+a[-1-i])%(p+1)
    print(solve(tmp))

Submission status: Runtime Error

Solution code:
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby
from heapq import heapify, heappush, heappop

# sys.setrecursionlimit(5000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return map(lambda x: x + d, A)
def ldec(A, d=1): return map(lambda x: x - d, A)

N = n1()
X = int(s1(), 2)

def flip(n, i):
    return n ^ (1 << i)

popcount = lambda x: bin(x).count("1")
bits = lambda x, n = 0: bin(x)[2:].zfill(n)

dp = {}

def search(n):
    if n == 0:
        return 0

    if n in dp:
        return dp[n]

    m = n % popcount(n)
    t = search(m) + 1
    dp[n] = t
    return t

#for i in range(N-1, -1, -1):
#    print(search(flip(X, i)))

p = popcount(X)
r1 = X % (p + 1)
r2 = X % (p - 1) if p > 1 else 0

for i in range(N-1, -1, -1):
    Y = flip(X, i)

    if Y == 0:
        print(1)
        continue

    b = bits(X, N)[i]
    if b == 0:
        t = (r1 + 1 << i) % (p + 1)
    else:
        t = (r2 - 1 << i) % (p - 1)

    print(search(Y))

Submission status: Runtime Error

Solution code:

import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby
from heapq import heapify, heappush, heappop

# sys.setrecursionlimit(5000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return map(lambda x: x + d, A)
def ldec(A, d=1): return map(lambda x: x - d, A)

N = n1()
X = int(s1(), 2)

def flip(n, i):
    return n ^ (1 << i)

popcount = lambda x: bin(x).count("1")
bits = lambda x, n = 0: bin(x)[2:].zfill(n)

dp = {}

def search(n):
    if n == 0:
        return 0

    if n in dp:
        return dp[n]

    m = n % popcount(n)
    t = search(m) + 1
    dp[n] = t
    return t

#for i in range(N-1, -1, -1):
#    print(search(flip(X, i)))

p = popcount(X)
r1 = X % (p + 1)
r2 = X % (p - 1)

for i in range(N-1, -1, -1):
    Y = flip(X, i)

    if Y == 0:
        print(1)
        continue

    b = bits(X, N)[i]
    if b == 0:
        t = (r1 + 2**i) % (p + 1)
    else:
        t = (r2 - 2**i) % (p - 1)

    print(search(Y))

Submission status: Runtime Error

Solution code:
import copy
import math
N = int(input())
X = input()
X2 = copy.deepcopy(X)
L = [0,1]+["None"]*((2**N)+10)


def f(n):
    global L

    if L[n] == "None":
        pop = str(bin(n)).count("1")
        L[n] = f(n%pop) + 1
        return(L[n])

    else:
        return L[n]



for p in range(N):
    Xi = int(X,2) ^ 2**(N-p-1)  #XORで１つだけbit反転
    print(f(Xi))

Submission status: Runtime Error

Solution code:
def popcount(num):
    return num.count('1')

def sinsuu(num):
    return int(num, 2)


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

for i in range(n):
    if i < n-1 :
        if x[i] == '1':
            y = x[:i] + '0' + x[i+1:]
        else:
            y = x[:i] + '1' + x[i+1:]
    else:
        if x[i] == '1':
            y = x[:i] + '0' 
        else:
            y = x[:i] + '1' 
    a = sinsuu(y)
    ans = [0]
    for i in ans:
        b = a % popcount(y)
        ans.append(i+1)
        if b ==0:
            break  
        a = b
        y = bin(b)
        y = y[2:]
    print(ans[-1])

Submission status: Runtime Error

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

pop_X = sum(map(int,list(X)))
X_10 = int('0b'+X,2)
r_0 = X_10%(pop_X+1)
zero_flag = False
if pop_X == 1:
    zero_flag = True
else:
    r_1 = X_10%(pop_X-1)

diff = 2 ** (N-1)
for i in range(N):
    if X[i]=='0':
        r = (r_0+diff%(pop_X+1))%(pop_X+1)
    else:
        if zero_flag:
            print(0)
            break
        else:
            r = (r_1-diff%(pop_X-1))%(pop_X-1)
    count = 1
    while True:
        if r == 0:
            break
        pop = sum(map(int,list(bin(r)[2:])))
        r = r % pop
        count += 1
        
    print(count)
    diff = int(diff/2)

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
​
pop_X = sum(map(int,list(X)))
X_10 = int('0b'+X,2)
r_0 = X_10%(pop_X+1)
zero_flag = False
if pop_X == 1:
    zero_flag = True
else:
    r_1 = X_10%(pop_X-1)
​
diff = 2 ** (N-1)
for i in range(N):
    if X[i]=='0':
        r = (r_0+diff%(pop_X+1))%(pop_X+1)
    else:
        if zero_flag:
            print(0)
            break
        else:
            r = (r_1-diff%(pop_X-1))%(pop_X-1)
    count = 1
    while True:
        if r == 0:
            break
        pop = sum(map(int,list(bin(r)[2:])))
        r = r % pop
        count += 1
        
    print(count)
    diff /= 2

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):
        return bin(n).count("1")

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

    for j in range(n):
        if X[j] == "0":
            cnt = cnt_init + 1
            x = int(X, 2) + pow(2, n - j - 1, cnt)
        else:
            cnt = cnt_init - 1
            x = int(X, 2) - pow(2, n - j - 1, cnt)

        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:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import copy
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


def pop_count(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 f(x):
    if x == 0:
        return 0
    return f(x % pop_count(x)) + 1


def solve():
    N = Scanner.int()
    S = Scanner.string()
    pc = sum([s == '1' for s in S])
    ans = [0 for _ in range(N)]
    for b in range(2):
        npc = pc
        if b == 0:
            npc += 1
        else:
            npc -= 1
        r0 = 0
        for i in range(N):
            r0 = ((r0 * 2) + int(S[i])) % npc
        k = 1
        for i in reversed(range(N)):
            if int(S[i]) == b:
                r = r0
                if b == 0:
                    r = (r + k) % npc
                else:
                    r = (r - k + npc) % npc
                ans[i] = f(r) + 1
            k = (k * 2) % npc
    print(*ans, sep='\n')


def main():
    sys.setrecursionlimit(1000000)
    # sys.stdin = open("sample.txt")
    # T = Scanner.int()
    # for _ in range(T):
    #     solve()
    # print('YNeos'[not solve()::2])
    solve()


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import copy
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


def pop_count(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 f(x):
    if x == 0:
        return 0
    return f(x % pop_count(x)) + 1


def solve():
    N = Scanner.int()
    S = Scanner.string()
    pc = sum([s == '1' for s in S])
    ans = [0 for _ in range(N)]
    for b in range(2):
        npc = pc
        if b == 0:
            npc += 1
        else:
            npc -= 1
        r0 = 0
        for i in range(N):
            r0 = ((r0 * 2) + int(S[i])) % npc
        k = 1
        for i in reversed(range(N)):
            if int(S[i]) == b:
                r = r0
                if b == 0:
                    r = (r + k) % npc
                else:
                    r = (r - k + npc) % npc
                ans[i] = f(r) + 1
            k = (k * 2) % npc
    print(*ans, sep='\n')


def main():
    # sys.setrecursionlimit(1000000)
    # sys.stdin = open("sample.txt")
    # T = Scanner.int()
    # for _ in range(T):
    #     solve()
    # print('YNeos'[not solve()::2])
    solve()


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def pop(x):
    binary = []
    while True:
        if x == 1:
            binary.append(x)
            break
        q,mod = divmod(x,2)
        binary.append(mod)
        x = q
    return sum(binary)

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

pop_X = sum(X)
X_10 = sum([X[i]*2**(N-i-1) for i in range(N)])

answer = []
for i in range(N):
    count = 0
    Xi_10 = X_10 + 2**(N-i-1) if X[i]==0 else X_10 - 2**(N-i-1)
    pop_Xi = pop_X + 1 if X[i]==0 else pop_X -1
    while True:
        r = Xi_10 % pop_Xi
        count+= 1
        if r == 0:
            break
        Xi_10 = r
        pop_Xi = pop(r)
    answer.append(count)

for i in range(N):
    print(answer[i])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import copy
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


def pop_count(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 solve():
    N = Scanner.int()
    S = Scanner.string()
    p = sum([s == '1' for s in S])
    MAX = 200010
    counter = [0 for _ in range(MAX)]
    for i in range(MAX):
        n = i
        cnt = 0
        while n > 0:
            j = pop_count(n)
            n %= j
            cnt += 1
        counter[i] = cnt
    for i in range(N):
        if S[i] == '1':
            pc = p - 1
        else:
            pc = p + 1
        n = 1
        x = 0
        for j in reversed(range(N)):
            s = S[j]
            if i == j:
                if s == '1':
                    s = '0'
                else:
                    s = '1'
            x += int(s) * n
            x %= pc
            n *= 2
            n %= pc
        print(counter[x] + 1)


def main():
    # sys.setrecursionlimit(1000000)
    # sys.stdin = open("sample.txt")
    # T = Scanner.int()
    # for _ in range(T):
    #     solve()
    # print('YNeos'[not solve()::2])
    solve()


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

c = x.count('1')
cp = c+1
cn = c-1

rp = [0] * n
if cp > 1:
    rp[0] = 1
rn = [0] * n
if cn > 1:
    rn[0] = 1
for i in range(1, n):
    rp[i] = (rp[i-1] * 2) % cp
    rn[i] = (rn[i-1] * 2) % cn

xp = 0
xn = 0
for i in range(n):
    xx = x[i]
    if xx == '1':
        xp = (xp + rp[n-i-1]) % cp
        xn = (xn + rn[n-i-1]) % cn

for i in range(n):
    o = 1
    if x[i] == '1':
        xx = (xn-rn[n-i-1]) % cn
    else:
        xx = (xp+rp[n-i-1]) % cp
    while xx > 0:
        cc = bin(xx)[2:].count('1')
        xx = xx % cc
        o += 1
    print(o)

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
val = int(X,2)
C = X.count("1")

# xをpopcountで割ったあまりに置き換える
def f(x):
  if x==0: return 0
  return 1 + f(x % bin(x).count("1"))

# 初回のpopcountでの割り方は、(C+1) or (C-1)
Y = val%(C+1)
if C-1 != 0:
  Z = val%(C-1)
else:
  Z = 0

for i in range(N):
  if X[i] == "1":
    if Z - 1 == 0:
      print(0)
      continue
    k = (Z - pow(2,N-i-1,C-1)) % (C-1)
  else:
    k = (Y + pow(2,N-i-1,C+1)) % (C+1)
  print(f(k)+1)