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 sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain, product
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    N = ii()
    X = input()
    P = X.count('1')
    def popcount(n):
        return bin(n).count('1')
    def f(n, p=None):
        if n==0:
            return 0
        else:
            return f(n % popcount(n)) + 1
    Xi = int(X, 2)
    FP = Xi % (P+1)
    FN = Xi % (P-1)
    ans = []
    for i, b in enumerate(reversed(X)):
        if b=='0':
            ans.append(f((FP + pow(2, i, P+1))%(P+1)) + 1)
        else:
            ans.append(f((FN + pow(2, i, P-1))%(P-1)) + 1)
    print(*reversed(ans))



main()

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

N = int(input())
Xs = input()
Xint = eval("0b"+Xs)
X = list(map(int, list(Xs)))

def popcount(Xi):
    return Xi.count(1)

x_pc = popcount(X)
x_pc1 = x_pc + 1
x_pc2 = x_pc - 1
# print("Xs: {} x_pc1: {} x_pc2: {}".format(Xs, x_pc1, x_pc2))

x_mod1 = Xint % x_pc1
x_mod2 = Xint % x_pc2
# print("x_mod1: {} x_mod2: {}".format(x_mod1, x_mod2))

anss = []
for i in range(N):
    j = N - i - 1
    if X[i] == 0:
        # mod = (x_mod1 + (1 << j % x_pc1)) % x_pc1
        mod = (Xint + (1 << j)) % x_pc1
        anss.append(mod)
    else:
        # mod = (x_mod2 - (1 << j % x_pc2)) % x_pc2
        mod = (Xint - (1 << j)) % x_pc2
        anss.append(mod)

# print(anss)
# quit()
for Xi in anss:
    if Xi == 0:
        print(1)
        continue

    pc = bin(Xi).count("1")
    ans = 1
    while pc:
        pc = Xi % pc
        ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    X = input()
    
    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

    ans = []
   
    f = [0] * N
    # preprocess 1
    for i in range(1, N):
        pc = popcount(i)
        j =  i % pc
        f[i] = f[j] + 1
    
    # preprocess 2
    X_COUNT = X.count("1")
    X = tuple(map(int, tuple(X)))
    rem_plus = [0] * N
    rem_minus = [0] * N
    two_factor = 1
    for i in range(N):
        rem_plus[i] = two_factor
        two_factor *= 2
        two_factor %= (X_COUNT+1)

    if X_COUNT:
        two_factor = 1
        for i in range(N):
            rem_minus[i] = two_factor
            two_factor *= 2
            two_factor %= (X_COUNT-1)


    X_rem_plus = 0
    X_rem_minus = 0
    two_factor = 1
    for c in X[::-1]:
        X_rem_plus += two_factor*c
        X_rem_plus %= (X_COUNT+1)
        two_factor *= 2
        two_factor %= (X_COUNT+1)
    
    if X_COUNT:
        two_factor = 1
        for c in X[::-1]:
            X_rem_minus += two_factor*c
            X_rem_minus %= (X_COUNT-1)
            two_factor *= 2
            two_factor %= (X_COUNT-1)
    
    for i, c in enumerate(X):
        if c:
            if X_COUNT > 1:
                rem = X_rem_minus - rem_minus[N-1-i]
                rem %= (X_COUNT-1)
                ans.append(f[rem]+1)
            elif X_COUNT == 1:
                ans.append(1)
            else:
                ans.append(0)
        else:
            rem = X_rem_plus + rem_plus[N-1-i]
            rem %= (X_COUNT+1)
            ans.append(f[rem]+1)
   
    print(*ans, sep="\n")

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def popcount(x):
    x -= ((x>>1) & 0x5555555555555555)
    x = (x&0x3333333333333333) + ((x&0xCCCCCCCCCCCCCCCC)>>2)
    x = (x&0x0F0F0F0F0F0F0F0F) + ((x&0xF0F0F0F0F0F0F0F)>>4)
    
    x *= 0x0101010101010101

def main():
    N = int(input())
    X = input()
    
    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

    ans = []
   
    f = [0] * (N+1)
    # preprocess 1
    for i in range(1, N+1):
        pc = popcount(i)
        j =  i % pc
        f[i] = f[j] + 1
    
    # preprocess 2
    X_COUNT = X.count("1")
    X = tuple(map(int, tuple(X)))
    rem_plus = [0] * N
    rem_minus = [0] * N
    two_factor = 1
    for i in range(N):
        rem_plus[i] = two_factor
        two_factor *= 2
        two_factor %= (X_COUNT+1)

    if X_COUNT:
        two_factor = 1
        for i in range(N):
            rem_minus[i] = two_factor
            two_factor *= 2
            two_factor %= (X_COUNT-1)


    X_rem_plus = 0
    X_rem_minus = 0
    two_factor = 1
    for c in X[::-1]:
        X_rem_plus += two_factor*c
        X_rem_plus %= (X_COUNT+1)
        two_factor *= 2
        two_factor %= (X_COUNT+1)
    
    if X_COUNT:
        two_factor = 1
        for c in X[::-1]:
            X_rem_minus += two_factor*c
            X_rem_minus %= (X_COUNT-1)
            two_factor *= 2
            two_factor %= (X_COUNT-1)
    
    for i, c in enumerate(X):
        if c:
            if X_COUNT:
                rem = X_rem_minus - rem_minus[N-1-i]
                rem %= (X_COUNT-1)
                ans.append(f[rem]+1)
            else:
                ans.append(0)
        else:
            rem = X_rem_plus + rem_plus[N-1-i]
            rem %= (X_COUNT+1)
            ans.append(f[rem]+1)
   
    print(*ans, sep="\n")
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def popcount(x):
    x -= ((x>>1) & 0x5555555555555555)
    x = (x&0x3333333333333333) + ((x&0xCCCCCCCCCCCCCCCC)>>2)
    x = (x&0x0F0F0F0F0F0F0F0F) + ((x&0xF0F0F0F0F0F0F0F)>>4)
    
    x *= 0x0101010101010101

def main():
    N = int(input())
    X = input()
    
    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

    ans = []
   
    f = [0] * N
    # preprocess 1
    for i in range(1, N):
        pc = popcount(i)
        j =  i % pc
        f[i] = f[j] + 1
    
    # preprocess 2
    X_COUNT = X.count("1")
    X = tuple(map(int, tuple(X)))
    rem_plus = [0] * N
    rem_minus = [0] * N
    two_factor = 1
    for i in range(N):
        rem_plus[i] = two_factor
        two_factor *= 2
        two_factor %= (X_COUNT+1)

    if X_COUNT:
        two_factor = 1
        for i in range(N):
            rem_minus[i] = two_factor
            two_factor *= 2
            two_factor %= (X_COUNT-1)


    X_rem_plus = 0
    X_rem_minus = 0
    two_factor = 1
    for c in X[::-1]:
        X_rem_plus += two_factor*c
        X_rem_plus %= (X_COUNT+1)
        two_factor *= 2
        two_factor %= (X_COUNT+1)
    
    if X_COUNT:
        two_factor = 1
        for c in X[::-1]:
            X_rem_minus += two_factor*c
            X_rem_minus %= (X_COUNT-1)
            two_factor *= 2
            two_factor %= (X_COUNT-1)
    
    for i, c in enumerate(X):
        if c:
            if X_COUNT:
                rem = X_rem_minus - rem_minus[N-1-i]
                rem %= (X_COUNT-1)
                ans.append(f[rem]+1)
            else:
                ans.append(0)
        else:
            rem = X_rem_plus + rem_plus[N-1-i]
            rem %= (X_COUNT+1)
            ans.append(f[rem]+1)
   
    print(*ans, sep="\n")
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain, product
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    N = ii()
    X = list(input())
    P = X.count('1')
    def popcount(n):
        return bin(n).count('1')
    def f(n, p=None):
        if n==0:
            return 0
        if p is None:
            p = popcount(n)
        if isinstance(n, list):
            v = 0
            for b in n:
                v <<= 1
                v += int(b)
                v %= p
            return f(v) + 1
        else:
            return f(n % p) + 1

    for i in range(N):
        b = X[i]
        X[i] = '0' if b=='1' else '1'
        print(f(X, p=P+(1 if b=='0' else -1)))
        X[i] = b

main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain, product
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    N=ii()
    X=input()
    def popcount(n):
        if isinstance(n, str):
            return n.count('1')
        else:
            return bin(n).count('1')
    def f(n, p=None):
        if n==0:
            return 0
        if p is None:
            p = popcount(n)
        if isinstance(n, str):
            v = 0
            for b in n:
                v <<= 1
                v += int(b)
                v %= p
            return f(v) + 1
        else:
            return f(n % p) + 1

    P = popcount(X)
    for i in range(N):
        x = X[:i] + ('0' if X[i]=='1' else '1') + X[i+1:]
        print(f(x, p=P+(1 if X[i]=='0' else -1)))







main()

Submission status: Runtime Error

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


N = int(input())
X = input()
f = 0
count = 1
ans = 0
fi = 0
ori = X.count("1")
result = 0
xc0 = int(X,2) % (ori + 1)
xc1 = int(X,2) % (ori - 1) if ori > 1 else 0
for i in range(N-1, -1, -1):
    # print(i)
    fi = toggle_nth_bit(int(X, 2), i)
    # f = bin(toggle_nth_bit(int(X, 2), i))
    if X[i] == "1":
        result = ori - 1
        ans = (xc1 - pow(2, i,result)) % result
    else:
        result = ori + 1
        ans = (xc0 - pow(2, i,result)) % result

    # f = toggle_nth_bit(int(X, 2), i)
    if result == 0:
        # ans = fi % result
    # else:
        print(0)
        continue
    while ans > 0:
        # f = bin(fi)
        count += 1
        if ans == 1:
            break
        # ans = ans % popcount(ans)
        ans = ans % bin(ans).count("1")

        # print(f)
        # print(fi)
        # count += 1
        # print(count)
    # c.append(count)
    print(count)
    count = 1

# ans = str(bin(toggle_nth_bit(int(X,2), 0)))
# for i in c:
#     print(i)

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
x2 = int(x, 2)
c = x.count('1')

for i in range(n):
    # k = 1 << (n-i-1)
    k = 1
    if int(x[i]):
        y = x2 - k
        c1 = c-1
    else:
        y = x2 + k
        c1 = c+1
    if y == 0:
        print(0)
        continue
    surplus = y % c1
    cnt = 1

    while surplus:
        surplus %= bin(surplus).count('1')
        cnt += 1
    print(cnt)

Submission status: Runtime Error

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


original_popcount=x.count('1')
one_to_zero_p=original_popcount-1
zero_to_one_p=original_popcount+1
X=int(x,2)

f=[0]*n

for i in range(n):
    if x[i]=='1':
        f[i]=(X-pow(2,n-1-i))%one_to_zero_p
    else:
        f[i]=(X+pow(2,n-1-i))%zero_to_one_p

n_max=3*10**5
dp=[0]*n_max
for i in range(1,n+1):
    p=bin(i).count('1')
    nxt=i%p
    dp[i]=dp[nxt]+1

for i in f:
    if i==0:
        print(1)
    else:
        print(dp[i]+1)

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
x2 = int(x, 2)
c = x.count('1')

for i in range(n):
    # k = 1 << (n-i-1)
    if int(x[i]):
        y = x2 - k
        c1 = c-1
    else:
        y = x2 + k
        c1 = c+1
    if y == 0:
        print(0)
        continue
    surplus = y % c1
    cnt = 1

Submission status: Runtime Error

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


original_popcount=x.count('1')
one_to_zero_p=original_popcount-1
zero_to_one_p=original_popcount+1
X=int(x,2)

f=[0]*n

for i in range(n):
    if x[i]=='1':
        f[i]=(-2**(n-1-i)+X)%one_to_zero_p
    else:
        f[i]=(2**(n-1-i)+X)%zero_to_one_p

#print(f)

ans=[1]*n 

n_max=3*10**5
dp=[0]*n_max
for i in range(1,n+1):
    p=bin(i).count('1')
    nxt=i%p
    dp[i]=dp[nxt]+1

for i in f:
    if i==0:
        print(1)
    else:
        print(dp[i]+1)

Submission status: Runtime Error

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


original_popcount=x.count('1')
one_to_zero_p=original_popcount-1
zero_to_one_p=original_popcount+1
X=int(x,2)

f=[0]*n

for i in range(n):
    if x[i]=='1':
        f[i]=(2**(n-1-i)+X)%one_to_zero_p
    else:
        f[i]=(2**(n-1-i)+X)%zero_to_one_p

#print(f)

ans=[1]*n 

n_max=3*10**5
dp=[0]*n_max
for i in range(1,n+1):
    p=bin(i).count('1')
    nxt=i%p
    dp[i]=dp[nxt]+1

for i in f:
    if i==0:
        print(1)
    else:
        print(dp[i]+1)

Submission status: Runtime Error

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

for i in range(n):
    if int(x[i]):
        y = x[:i] + '0' + x[i+1:]
    else:
        y = x[:i] + '1' + x[i+1:]
    surplus = int(y, 2) % (y.count('1'))
    cnt = 1
    while surplus:
        surplus %= bin(surplus).count('1')
        cnt += 1
    print(cnt)

Submission status: Runtime Error

Solution code:
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
# from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
# import numpy as np
# sys.setrecursionlimit(int(pow(10,6)))

mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

try:
    sys.stdin = open("input.txt", "r")
    sys.stdout = open("out.txt", "w")
except:
    pass


# @lru_cache(None)

n=L()[0]
X=input()
if X=="0"*n:
    for i in range(n):
        print(1)
    exit()
if X=="1":
    print(0)
    exit()
curr=curr2=1
nao=mnao=0
bit=X.count("1")+1
bit2=X.count("1")-1
if bit==2:
    if X[n-1]=="1":
        for i in range(n):
            if X[i]=="0":
                print(2)
            else:
                print(1)
         exit()
    else:
        for i in range(n):
            if i==n-1:
                print(2)
            elif X[i]=="0":
                print(1)
            else:
                print(0)
        exit()

for i in range(n-1,-1,-1):
    if X[i]=="1":
        nao+=curr%bit
        nao%=bit
        mnao+=curr2%bit2
        mnao%=bit2
    curr*=2
    curr%=bit
    curr2*=2
    curr2%=bit2
print(curr,curr2,bit,bit2,nao,mnao)
for  i in range(n):
    FN=0
    if X[i]=="0":
        FN=nao
        ex=pow(2,n-i-1,bit)
        FN+=ex
        FN%=bit
    else:
        FN=mnao
        ex=pow(2,n-i-1,bit2)
        FN-=ex
        FN%=bit2
        if FN<0:
            FN+=bit2
    step=1
    # print(FN)
    while(FN):
        bitcnt=bin(FN).count("1")
        FN%=bitcnt
        step+=1
    print(step)

Submission status: Runtime Error

Solution code:
#20200711_D
N =  int(input())
X = input()
line = []
counter = 0


def popcount(n): #2進数を与えて1の数を10進数で返す
    return n.count("1")
popX =  popcount(X)

line.append(int(X,2) % (popX -1))
line.append(int(X,2) % (popX +1))
# print('int(X,2', int(X,2))
# print('line = ' , line)


for i in range(N):
    #print('i=' + str(i))
    counter = 0
    
    if X[i] == '0':
        Xi = '0b' + X[:i] + '1' + X[i+1:]
        s = 1
    else:
        Xi = '0b'  + X[:i] + '0' + X[i+1:]
        s = 0
    #print('Xi =' + Xi , 's = ' + str(s))
    
    if int(Xi, 0) == 0:
        print(counter)
    else:
        if s == 0:
            Xi = (line[0] - (2**(N-i-1) % (popX -1)))%(popX-1)
        else:
            Xi = (line[1] + (2**(N-i-1) % (popX +1)))%(popX+1)
        counter += 1
        #print(Xi)
    
        while Xi >0:
            Xi = Xi % popcount(bin(Xi))
            
            counter +=1
    
        #print( 'counter = ' + str(counter))
        print(counter)

Submission status: Runtime Error

Solution code:
#20200711_D
N =  int(input())
X = input()
line = []
counter = 0


def popcount(n): #2進数を与えて1の数を10進数で返す
    return n.count("1")
popX =  popcount(X)

line.append(int(X,2) % (popX -1))
line.append(int(X,2) % (popX +1))
# print('int(X,2', int(X,2))
# print('line = ' , line)


for i in range(N):
    #print('i=' + str(i))
    counter = 0
    
    if X[i] == '0':
        Xi = '0b' + X[:i] + '1' + X[i+1:]
        s = 1
    else:
        Xi = '0b'  + X[:i] + '0' + X[i+1:]
        s = 0
    #print('Xi =' + Xi , 's = ' + str(s))
    
    if int(Xi, 0) == 0:
        print(counter)
    else:
        if s == 0:
            Xi = (line[0] - (2**(N-i-1) % (popX -1)))%(popX-1)
        else:
            Xi = (line[1] + (2**(N-i-1) % (popX +1)))%(popX+1)
        counter += 1
        #print(Xi)
    
        while Xi >0:
            Xi = Xi % popcount(bin(Xi))
            
            counter +=1
    
        #print( 'counter = ' + str(counter))
        print(counter)

Submission status: Runtime Error

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

def division_count(n):
    k = 1
    while True:
        b = format(n, 'b')
        p = popcount(b)
        m = n % p
        if m == 0:
            break
        n = m
        k += 1
    return k

def invert_bit(b):
    return '0' if b=='1' else '1'

def invert_bits(b, i):
    c = list(b)
    c[i] = invert_bit(c[i])
    return "".join(c)

N = int(input())
bits = input()

for i in range(N):
    current_bits = int(invert_bits(bits, i), 2)
    print(division_count(current_bits))

Submission status: Runtime Error

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

def division_count(b):
    k = 1
    n = int(b, 2)
    while True:
        p = popcount(b)
        m = n % p
        if m == 0:
            break
        n = m
        k += 1
        b = format(n, 'b')
    return k

def invert_bit(b):
    return '0' if b=='1' else '1'

def invert_bits(b, i):
    c = list(b)
    c[i] = invert_bit(c[i])
    return "".join(c)

N = int(input())
bits = input()

for i in range(N):
    current_bits = invert_bits(bits, i)
    print(division_count(current_bits))

Submission status: Runtime Error

Solution code:
#関数リスト
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def bin2dec(target):
    out = 0
    index = 0
    while target > 0:
        out += (target % 10) * 2**index
        target //= 10
        index += 1
    return out

n = I()
x = I()

#２進数にした際の桁数
keta = [0] * (n+1)
keta[1] = 1
keta[2] = 1
for i in range(2, n+1):
    keta[i] = (i & 1) + keta[i>>1]

#操作回数
d = [0] * (n+1)
d[1] = 1
d[2] = 1
d[3] = 2
for i in range(2, n+1):
    amari = i % keta[i]
    d[i] = d[amari] + 1

num = bin2dec(x)
K = 0
for i in range(n):
    if (num >> i) & 1 == 1:
        K += 1

for i in range(n-1,-1,-1):
    temp1 = num >> i
    temp2 = num
    #bit反転
    if temp1 & 1 == 0:
        temp2 += 2**i
        if temp2 != 0:
            print(d[temp2 % (K+1)]+1)
        else:
            print(0)
    else:
        temp2 += 2**i - 2**(i+1)
        if temp2 != 0:
            print(d[temp2 % (K-1)]+1)
        else:
            print(0)

Submission status: Runtime Error

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

X_int = int(X,2)
popcount = X.count('1')

modp = X_int % (popcount + 1)
modm = X_int % (popcount - 1) if popcount != 0 else 0

for i in range(N):
    if X[i] == '0':
        x = (modp + pow(2, N - i - 1, popcount + 1)) % (popcount + 1)
    else:
        if popcount - 1 == 0:
            print(0)
            continue
        else:
            x = (modm - pow(2, N - i - 1, popcount - 1)) % (popcount - 1)
    cnt = 1
    while x != 0:
        x %= bin(x).count('1')
        cnt += 1
    print(cnt)

Submission status: Runtime Error

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

X_int = int(X,2)
popcount = X.count('1')

modp = X_int % (popcount + 1)
modm = X_int % (popcount - 1) if popcount != 0 else 0

for i in range(N):
    if X[i] == '0':
        x = (modp + pow(2, N - i - 1, popcount + 1)) % (popcount + 1)
    else:
        if popcount - 1 == 0:
            print(0)
            continue
        else:
            x = (modm + pow(2, N - i - 1, popcount - 1)) % (popcount - 1)
    cnt = 1
    while x != 0:
        x %= bin(x).count('1')
        cnt += 1
    print(cnt)

Submission status: Runtime Error

Solution code:
#関数リスト
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def bin2dec(target):
    out = 0
    index = 0
    while target > 0:
        out += (target % 10) * 2**index
        target //= 10
        index += 1
    return out

n = I()
x = I()

#２進数にした際の桁数
keta = [0] * (n+1)
keta[1] = 1
keta[2] = 1
for i in range(2, n+1):
    keta[i] = (i & 1) + keta[i>>1]

#操作回数
d = [0] * (n+1)
d[1] = 1
d[2] = 1
d[3] = 2
for i in range(2, n+1):
    amari = i % keta[i]
    d[i] = d[amari] + 1

num = bin2dec(x)
result = []


for i in range(0,n):
    temp1 = num >> i
    temp2 = num
    #bit反転
    if temp1 & 1 == 0:
        temp2 += 2**i
        result.append(d[temp2 % (n+1)])
    else:
        temp2 += 2**i - 2**(i+1)
        result.append(d[temp2 % (n-1)])

for i in reversed(result):
    print(i)

Submission status: Runtime Error

Solution code:
N = int(input())
X = str(input())
num_X = int(X,2)
bit_caunt = 0
for i in range(N):
    if X[i] == '1':
        bit_caunt += 1


b = num_X % (bit_caunt+1)
c = num_X % (bit_caunt-1)

for i in range(N):
    ans = 0
    if X[i] == '1':
        re_X = num_X - 2**(N-1-i)
        if re_X != 0:
            pop = bit_caunt - 1
            re_X = (c - 2**(N-1-i)%pop)%pop
            ans += 1
    else:
        re_X = num_X + 2**(N-1-i)
        if re_X != 0:
            pop = bit_caunt + 1
            re_X = (b + 2**(N-1-i)%pop)%pop
            ans += 1
         
    while re_X != 0:
        pop = bin(re_X).count('1')
        re_X %= pop
        ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
X = str(input())
num_X = int(X,2)
bit_caunt = 0
for i in range(N):
    if X[i] == '1':
        bit_caunt += 1


b = num_X % (bit_caunt+1)
c = num_X % (bit_caunt-1)

for i in range(N):
    ans = 0
    if X[i] == '1':
        re_X = num_X - 2**(N-1-i)
        if re_X != 0:
            pop = bit_caunt - 1
            re_X = (c + 2**(N-1-i)%pop)%pop
            ans += 1
    else:
        re_X = num_X + 2**(N-1-i)
        if re_X != 0:
            pop = bit_caunt + 1
            re_X = (b + 2**(N-1-i)%pop)%pop
            ans += 1
         
    while re_X != 0:
        pop = bin(re_X).count('1')
        re_X %= pop
        ans += 1
    print(ans)

Submission status: Runtime Error

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

memo = {}


def popcount(n):
    return bin(n).count('1')


def f(n):
    if n == 0:
        return 0
    if n in memo:
        return memo[n]
    memo[n] = 1 + f(n % popcount(n))
    return memo[n]


Xint = int(X, 2)
p = popcount(Xint)
x1 = Xint % (p - 1) if 1 < p else None
x2 = Xint % (p + 1)
ans = []
b = 1
bmod1 = b % (p - 1) if 1 < p else None
bmod2 = b % (p + 1)
for i in range(N):
    if X[-1 - i] == '1':
        if 1 < p:
            ans.append(1 + f((x1 - bmod1) % (p - 1)))
        else:
            ans.append(1)
    else:
        ans.append(1 + f((x2 + bmod2) % (p + 1)))
    b <<= 1
    bmod1 = bmod1 * 2 % (p - 1) if 0 < p else None
    bmod2 = bmod2 * 2 % (p + 1)
for a in reversed(ans):
    print(a)