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 bc(x):
    n = 0
    while x:
        n += 1
        x &= x -1
    return n

def numChange(list, i):
    num = 0
    j = 0
    while True:
        if i < 0:
            break
        num += int(list[i]) * pow_r(2, j)
        i -= 1
        j += 1
    return num

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

def pow_r(x, n):
    if n == 0:
        return 1
    if n % 2 == 0:
        return pow_r(x ** 2, n // 2)
    else:
        return x * pow_r(x ** 2, (n - 1) // 2)

if __name__ == "__main__":
    n = int(input())
    x = input()
    xList = list(x)
    k = len(xList) - 1
    for i in range(n):
        xList[i] = str(int(xList[i]) ^ 1)
        xNum = numChange(xList, k)
        print(f(xNum))
        xList[i] = str(int(xList[i]) ^ 1)
def bc(x):
    n = 0
    while x:
        n += 1
        x &= x -1
    return n

def numChange(list, i):
    num = 0
    j = 0
    while True:
        if i < 0:
            break
        num += int(list[i]) * pow_r(2, j)
        i -= 1
        j += 1
    return num

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

def pow_r(x, n):
    if n == 0:
        return 1
    if n % 2 == 0:
        return pow_r(x ** 2, n // 2)
    else:
        return x * pow_r(x ** 2, (n - 1) // 2)

if __name__ == "__main__":
    n = int(input())
    x = input()
    xList = list(x)
    k = len(xList) - 1
    for i in range(n):
        xList[i] = str(int(xList[i]) ^ 1)
        xNum = numChange(xList, k)
        print(f(xNum))
        xList[i] = str(int(xList[i]) ^ 1)

Submission status: Runtime Error

Solution code:
def bitcount(N):  # 立ってるbitの数
    bitcnt = [0]
    for _ in range(N):
        bitcnt += [i + 1 for i in bitcnt]
    return bitcnt


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

num, cnt = int(x, 2), x.count('1')
lbit = bitcount(18)
for i in range(n):
    ans = 1
    if x[i] == '0':
        ctmp = cnt + 1
        tmp = num % ctmp + pow(2, n - (i + 1), ctmp)
    elif x[i] == '1':
        ctmp = cnt - 1
        tmp = num % ctmp - pow(2, n - (i + 1), ctmp)
    tmp %= ctmp
    ctmp = lbit[tmp]
    while tmp > 0:
        ans += 1
        tmp %= ctmp
        ctmp = lbit[tmp]
    print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
x_pop=format(x,'b').count('1')
f=[0]*(x_pop+1)
for i in range(1,x_pop+1):
    popcount=format(i,'b').count('1')
    f[i]=f[i%popcount]+1
# print(f)
for i in range(len(x)):
  popcount=x_pop
    if x[i]=='1':
        x_changed=x[:i]+'0'+x[i+1:]
        popcount-=1
    else:
        x_changed=x[:i]+'1'+x[i+1:]
        popcount+=1
    num_changed=int(x_changed,2)
    # print(x_changed,num_changed)
    if num_changed<popcount:
        print(f[num_changed])
    else:
        print(f[num_changed%popcount]+1)

Submission status: Runtime Error

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

N = int(input())
X = input()
Xn = int(X, 2)
binc = X.count("1")
ans = [-1] * (N)
ans[0] = 0
ans[1] = 1
for i in range(2, N):
    ans[i] = ans[i%count(i)] + 1

for i in range(N):
    if X[i] == "1":
        y = Xn - 2**(N-i-1)
        c = binc - 1
        if binc == 1:
            print(0)
            continue
    else:
        y = Xn + 2**(N-i-1)
        c = binc + 1
    y %= c
    print(ans[y] + 1)

Submission status: Runtime Error

Solution code:


n=int(input())

ans=[0]*n
for i in range(n):
    x=i
    cnt=0
    while x>0:
        cnt+=1
        r = 0
        for j in range(19):
            if (x>>j)&1:
                r+=1
            if x>>j==0:
                break
        x=x%r
    ans[i]=cnt

s=input()
l=[0]*(n+1)
rem=[0]*30
num=0
temp=0
k=1
for i in reversed(range(0,n)):
    if int(s[i]):
        num+=k
        temp+=1
    k<<=1
k=1
for i in reversed(range(1,n+1)):
    # num1=num^k
    if num1:
        l[i]+=1
        num1%=temp+(1 if num1>num else -1)
    l[i]+=ans[num1]
    k<<=1
for i in range(1,n+1):
    print(l[i])

Submission status: Runtime Error

Solution code:
n = int(input())
q = input()
r = list(q)
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(q, 2)
y = k(x,n)
for i in range(n):
    an = 0
    if r[n-i-1]=='1':
        z = x-2**i
        if y-1 == 0:
            ans[i] = 0
        else:
            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:
import itertools
import sys
input = sys.stdin.readline

AL = {}


def f(A):
    ans = 0
    n = int(A, 2)
    while n != 0:
        pc = bin(n).count('1')
        n = n % pc
        ans += 1
        if bin(n) in AL:
            ans += AL[n]
            break

    if A not in AL:
        AL[A] = ans
    print(ans)


N = int(input())
A = int(input().rstrip(), 2)

for i in range(N)[::-1]:
    AA = bin(A ^ (1 << i))
    f(AA)

# print(AL)