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:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from functools import lru_cache


@lru_cache(maxsize=2*10**5)
def f2(x):
    if x == 0: return 0
    y = bin(x).count("1")
    return 1 + f2(x % y)

def resolve():
    N = int(input())
    W = 16
    S = input()
    cnt0 = S.count("1")

    X = int(S, 2)

    dc = {}
    for k, v in (("0", 1), ("1", -1)):
        x = cnt0 + v
        dc[k] = (x, v, X % x)

    ans = []
    for i, si in enumerate(S):
        cnt, v, n = dc[si]

        if cnt == 0:
            ans.append(0)
            continue

        ni = N - i - 1
        n = (n + v * pow(2, ni, cnt)) % cnt

        ans.append(1+f2(n))

    print(*ans, sep="\n")


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
n=int(input())
s=input()
mod=s.count('1')
cur1,cur2=0,0
mu,md=mod+1,mod-1


for i in range(n):
    cur1+=(int(s[i])<<(n-i-1))%(mu)
    cur1%=(mod+1)
    if mod!=0:
        cur2+=(int(s[i])<<(n-i-1))%(md)
        cur2%=(mod-1)
for i in range(n):
    c=0
    if s[i]=='1':
        c=cur2-pow(2,n-i-1,md)
        c%=md
        
    else:
        c=cur1+pow(2,n-i-1,mu)
        c%=mu
    a=0
    x=c
    while x:
        a+=1
        x%=bin(x).count('1')
    print(a+1)

Submission status: Runtime Error

Solution code:
n=int(input())
s=input()
mod=s.count('1')
cur1,cur2=0,0
mu,md=mod+1,mod-1


for i in range(n):
    cur1+=(int(s[i])<<(n-i-1))%(mu)
    cur1%=(mod+1)
    if mod!=0:
        cur2+=(int(s[i])<<(n-i-1))%(md)
        cur2%=(mod-1)
for i in range(n):
    c=0
    if s[i]=='1':
        c=cur2+(md-(1<<(n-i-1))%(md))
        c%=md
        
    else:
        c=cur1+(1<<(n-i-1))%mu
        c%=mu
    a=0
    x=c
    while x:
        a+=1
        x%=bin(x).count('1')
    print(a+1)

Submission status: Runtime Error

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

dp=[-1]*(n+1)

dp[0]=0
dp[1]=1
co=[-1]*(n+1)

def fun(num,step):
    num2=num%sum(list(map(int,bin(num)[2:])))
    if dp[num2]!=-1:
        dp[num]=dp[num2]+step
    else:
        fun(num2,step+1)

for i in range(2,200001):
    fun(i,1)

num1=''.join(x)
num2=int(num1,2)
su = sum(list(map(int,x)))

for i in range(n):
    num4=num2
    su2=su
    if x[i]=='1':
        num4-=pow(2,(n-1-i))
        su2-=1
    else:
        num4+=pow(2,(n-1-i))
        su2+=1
    if su2 == 0:
        print('0')
    elif num4<=n:
        print(dp[num4])
    else:
        num3=num4%su2
        print(dp[num3]+1)

Submission status: Runtime Error

Solution code:
import sys

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("i8[:](i8,unicode_type,i8)", cache=True)
def solve(N, X, X_int):
    popcount_X = X.count("1")
    if popcount_X == 0:
        ans = np.ones(N, dtype=np.int64)
    elif popcount_X == 1:
        ans = np.ones(N, dtype=np.int64)
        ans[-1] = 2
        ans[int(X.index("1"))] = 0
    else:
        X_mod_popcount_X_p = X_int % (popcount_X + 1)
        X_mod_popcount_X_m = X_int % (popcount_X - 1)
        ans = np.zeros(N, dtype=np.int64)
        for i in range(N):
            if X[i] == "0":
                Y = X_mod_popcount_X_p + (2 ** (N - 1 - i)) % (popcount_X + 1)
                Y = Y % (popcount_X + 1)
            else:
                Y = X_mod_popcount_X_m - (2 ** (N - 1 - i)) % (popcount_X - 1)
                Y = Y + (popcount_X - 1)
                Y = Y % (popcount_X - 1)
            count = 1
            while Y > 0:
                popcount = 0
                tmp = Y
                while tmp > 0:
                    if tmp & 1:
                        popcount += 1
                    tmp >>= 1
                Y = Y % popcount
                count += 1
            ans[i] = count

    return ans


def main():
    N = int(input())
    X = input()

    ans = solve(N, X, int(X, 2))
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

B_1 = B.count("1")
mod_p1 = int(B,2) % (B_1+1)
if B_1 != 1:
    mod_m1 = int(B,2) % (B_1-1)

def calc_small(n, iter):
    iter += 1
    mod = n % bin(n).count("1")

    if mod == 0:
        return iter
    else:
        return calc_small(mod, iter)

p = pow(2,N)
for i in range(N):
    p = int(p / 2)
    if B_1 == 1 and int(B[i]) == 1:
        print(0)
        continue
    mod = (mod_m1 - p) % (B_1-1) if int(B[i]) == 1 else (mod_p1 + p) % (B_1+1)
    iter = 1
    if mod == 0:
        print(iter)
    else:
        print(calc_small(mod, iter))

Submission status: Runtime Error

Solution code:
N = int(input())
B = input()
B_1 = B.count("1")
mod_p1 = int(B,2) % (B_1+1)
if B_1 != 1:
    mod_m1 = int(B,2) % (B_1-1)

def calc_small(n, iter):
    iter += 1
    mod = n % bin(n).count("1")

    if mod == 0:
        return iter
    else:
        return calc_small(mod, iter)

p = pow(2,N)
for i in range(N):
  p /= 2
    if B_1 == 1 and int(B[i]) == 1:
        print(0)
        continue
    mod = (mod_m1 - p) % (B_1-1) if int(B[i]) == 1 else (mod_p1 + p) % (B_1+1)
    iter = 1
    if mod == 0:
        print(iter)
    else:
        print(calc_small(mod, iter))

Submission status: Runtime Error

Solution code:
N = int(input())
X = int(input(), 2)
def popcount(n):
  return bin(n).count("1")
max_n = int(("1" * N), 2)
dp = [0] * (max_n + 1)
for i in range(1, max_n+1):
  dp[i] =  dp[(i) % popcount(i)] + 1

for i in range(1, N+1):
  print(dp[X ^ 2**(N-i)])

Submission status: Runtime Error

Solution code:
N=int(input())
X=input()
Xnum=int(X,2)
popcount=X.count('1')
Xnum1=Xnum%(popcount-1)
Xnum0=Xnum%(popcount+1)
for i in range(N):
    if popcount==1 and X[i]=='1':
        print(0)
    if X[i]=='1':
        Xi = (Xnum1 - (2**(N-i-1)%(popcount-1)))%(popcount-1)
    else:
        Xi = (Xnum0 + (2**(N-i-1)%(popcount+1)))%(popcount+1)
    ans = 1
    while Xi!=0:
        Xi = Xi % bin(Xi).count('1')
        ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

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

memo = {0: 0}

def solve(X):
    x = X
    stack = deque([])
    while x:
        if x in memo:
            break
        stack.append(x)
        x = x % bin(x).count("1")
    cnt = memo[x] + 1
    while stack:
        x = stack.pop()
        memo[x] = cnt
        cnt += 1
    return cnt - 1



ans = []
px = x.count("1")

memo1 = [1 % (px - 1)] if px > 1 else []
memo2 = [1 % (px + 1)]
x1 = 0
x2 = 0

for i in range(n):
    if px > 1:
        memo1.append(memo1[-1] * 2 % (px-1))
    memo2.append(memo2[-1] * 2 % (px+1))

for i in range(n):
    if x[-i-1] == '1':
        x1 += memo1[i]
        x1 %= (px-1)
        x2 += memo2[i]
        x1 %= (px+1)

for i in range(n):
    if x[-i-1] == "1":
        if px > 1:
            ans.append(solve((x1-memo1[i])%(px-1)) + 1)
        else:
            ans.append(0)
    else:
        ans.append(solve((x2+memo2[i])%(px+1)) + 1)


for ansi in reversed(ans):
    print(ansi)

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 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

def my_pow(base, n, mod):
    if n == 0:
        return 1
    x = base
    y = 1
    while n > 1:
        if n % 2 == 0:
            x *= x
            n //= 2
        else:
            y *= x
            n -= 1
        x %= mod
        y %= mod
    return x * y % mod
MOD = 10 ** 9 + 7

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

def popcount(n):
    ret = 0
    while n > 0:
        if n % 2 == 1:
            ret += 1
        n //= 2
    return ret

ones = X.count('1')
A_1 = 0
A_2 = 0
d = 1
for a in X[::-1]:
    A_1 += (int(a) * d) % (ones - 1)
    A_2 += (int(a) * d) % (ones + 1)
    d *= 2

for i in range(N):
    ans = 1
    total = ones
    sumA = 0
    if X[i] == '0':
        total += 1
        if total != 0:
            sumA = A_2 + my_pow(2, N - i - 1, total)
    else:
        total -= 1
        if total != 0:
            sumA = A_1 - my_pow(2, N - i - 1, total)
    if total == 0:
        print(0)
        continue
    n = sumA % total
    while n != 0:
        n = n % popcount(n)
        ans += 1
    print(ans)

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 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

def my_pow(base, n, mod):
    if n == 0:
        return 1
    x = base
    y = 1
    while n > 1:
        if n % 2 == 0:
            x *= x
            n //= 2
        else:
            y *= x
            n -= 1
        x %= mod
        y %= mod
    return x * y % mod
MOD = 10 ** 9 + 7

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

def popcount(n):
    ret = 0
    while n > 0:
        if n % 2 == 1:
            ret += 1
        n //= 2
    return ret

ones = X.count('1')
A_1 = 0
A_2 = 0
d = 1
for a in X[::-1]:
    A_1 += (int(a) * d) % (ones - 1)
    A_2 += (int(a) * d) % (ones + 1)
    d *= 2

for i in range(N):
    ans = 1
    total = ones
    sumA = 0
    if X[i] == '0':
        total += 1
        sumA = A_2 + my_pow(2, N - i - 1, total)
    else:
        total -= 1
        sumA = A_1 - my_pow(2, N - i - 1, total)
    if total == 0:
        print(0)
        continue
    n = sumA % total
    while n != 0:
        n = n % popcount(n)
        ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math
from collections import deque
import itertools
import heapq
#import bisect
from fractions import Fraction
import copy
from functools import lru_cache
from collections import defaultdict
import pprint

#oo=list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
# ko=list("abcdefghijklmnopqrstuvwxyz")

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]

def ret(a):
    c=[None]*(len(a)-1)
    if len(a)==1:
        return a[0]
    elif len(a)==0:
        return 0
    for i in range(1,len(a)):
        c[i-1]=abs(a[i]-a[i-1])
    return ret(c)

def soinsubunkai(n):
    a = []
    i = 1
    while i*i <= n:
        if n % i == 0 and i!=1:
            a.append(i)
            n=n//i

        if n% i !=0 or i==1:
            i += 1
    nokori=[n]
    return a + nokori

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

def main():
    #l,r,d=map(int,input().split())
    n=int(input())
    s=input()
    ss=list(s)
    onecount=0
    for i in range(n):
        onecount+=int(ss[i])
    x=int(s, 2)
    o1=onecount-1
    o2=onecount+1
    MOD1=x%o1
    MOD2=x%o2
    for i in range(n):
        temp=2**(n-i-1)
        twoMOD1=temp%o1
        twoMOD2=temp%o2
        if int(ss[i])==1:
            f=MOD1-twoMOD1
            f%=o1
        else:
            f=MOD2+twoMOD2
            f%=o2
        div=1
        while True:
            if f==0:
                break
            one=bin(f).count("1")
            if one!=0:
                f=f%one
                div+=1
            else:
                break
        print(div)















if __name__ == "__main__":

    main()

Submission status: Runtime Error

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

if cnt1 > 1:
  x10mod_m = x10 % (cnt1-1)
  x10mod_p = x10 % (cnt1+1)
else:
  x10mod_m = 0
  x10mod_p = 0

ans = []
for i in range(n):
  add_val = add_val >> 1
  if x[i] == '1':
    if cnt1 == 1:
      print(0)
      continue
    cntx = cnt1-1
    mod = ( x10mod_m - pow(1,n-1-i,cntx) ) % cntx
  else:
    cntx = cnt1+1
    mod = ( x10mod_p + pow(1,n-1-i,cntx) ) % cntx
    
  cnt = 1
  mod = format(mod, 'b')
  
  while True:
    if mod == '0':
      break
    mod = format( int(mod,2) % mod.count('1'), 'b')
    cnt += 1
  print(cnt)

Submission status: Runtime Error

Solution code:
def dfs(n):
    if n == 0:return 0
    return dfs(n % format(n, "b").count("1")) + 1
n = int(input())
x = input()
c = x.count("1")
a = int(x, 2)
j, k = a % (c + 1), a % (c - 1)
if c == 1:
    for i in range(n):
        if x[i] == "1":
            print(0)
        elif i == n - 1:
            print(2)
        else:
            print(1)
else:
    for i in range(n):
        if x[i] == "1":print(dfs((k - pow(2, n - i - 1, c - 1)) % (c - 1)) + 1)
        else:print(dfs((j + pow(2, n - i - 1, c + 1)) % (c + 1)) + 1)

Submission status: Runtime Error

Solution code:

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

def popcount(ni):
    n_b = str(bin(ni))
    return n_b.count("1")

def ans(n,x):
    x_i = int(x, 2)
    x_orig = popcount(x_i)
    x_i_t = x_i % (x_orig+1)
    if x_orig > 0:
        x_i_b = x_i % (x_orig-1)
    solve = 0
    for i in range(n):
        x_count = x_orig
        if x[i] == "0":
            x_count += 1
            solve = x_i_t + pow(2,n-1-i,x_count)
        else:
            x_count -= 1
            solve = x_i_b - pow(2,n-1-i,x_count)
        count = 0

        if x_count != 0 :
            solve = solve % x_count
            count+=1

        while solve > 0:
            solve = solve % popcount(solve)
            count+=1

        print(count)

    
ans(n,x)

Submission status: Runtime Error

Solution code:

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

def popcount(ni):
    n_b = str(bin(ni))
    return n_b.count("1")

def ans(n,x):
    x_i = int(x, 2)
    x_orig = popcount(x_i)
    x_i_t = x_i % (x_orig+1)
    x_i_b = x_i % (x_orig-1)
    solve = 0
    for i in range(n):
        x_count = x_orig
        if x[i] == "0":
            x_count += 1
            solve = x_i_t + pow(2,n-1-i,x_count)
        else:
            x_count -= 1
            solve = x_i_b - pow(2,n-1-i,x_count)
        count = 0

        if x_count != 0 :
            solve = solve % x_count
            count+=1

        while solve > 0:
            solve = solve % popcount(solve)
            count+=1

        print(count)

    
ans(n,x)

Submission status: Runtime Error

Solution code:
n=int(input())
s=input()
mod=s.count('1')
cur1,cur2=0,0
mu,md=mod+1,mod-1

an=[0]
for i in range(1,31):
    a=0
    x=i
    while x:
        a+=1
        x%=bin(x).count('1')
    an.append(a)

for i in range(n):
    cur1+=(int(s[i])<<(n-i-1))%(mu)
    cur1%=(mod+1)
    if mod!=0:
        cur2+=(int(s[i])<<(n-i-1))%(md)
        cur2%=(mod-1)
for i in range(n):
    if s[i]=='1':
        c=cur2+(md-(1<<(n-i-1))%(md))
        c%=md
        print(an[c]+1)
    else:
        c=cur1+(1<<(n-i-1))%mu
        c%=mu
        print(an[c]+1)

Submission status: Runtime Error

Solution code:
import sys
n = int(input())
x = int(input(),2)
if bin(x).count('1')+1 >= 1000:
    sys.setrecursionlimit(bin(x).count('1')+1)

ans = [0]*(bin(x).count('1')+1)
for i in range(1,len(ans)):
    ans[i] = 1 + ans[i%bin(i).count('1')]
#print(ans)
l = []
for i in range(n):
    y = x^(1<<(n-i-1))
    t = y % bin(y).count('1')
    l.append(str(1+ans[t]))
    #print(1+ans[t])
print('\n'.join(l))

Submission status: Runtime Error

Solution code:
n=int(input())
s=input()
mod=s.count('1')
cur1,cur2=0,0
mu,md=mod+1,mod-1

an=[0]
for i in range(1,20):
    a=0
    x=i
    while x:
        a+=1
        x%=bin(x).count('1')
    an.append(a)

for i in range(n):
    cur1+=(int(s[i])<<(n-i-1))%(mu)
    cur1%=(mod+1)
    if mod!=0:
        cur2+=(int(s[i])<<(n-i-1))%(md)
        cur2%=(mod-1)
for i in range(n):
    if s[i]=='1':
        c=cur2+(md-(1<<(n-i-1))%(md))
        c%=md
        print(an[c]+1)
    else:
        c=cur1+(1<<(n-i-1))%mu
        c%=mu
        print(an[c]+1)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N = int(readline())
    X_bin = readline().strip()
    n = X_bin.count("1")
    X = int(X_bin, 2)

    X_pop_p = X % (n + 1)
    X_pop_m = X % (n - 1)
    
    def count(x):
        cnt = 1
        while x:
            x %= bin(x).count("1")
            cnt += 1
        return cnt
        
    ans = []
    for i in range(N):
        X_i = X ^ (1 << i)
        if X_i == 0:
            ans.append(0)
        else:
            if X_bin[-(i+1)] == "1":
                mod = (X_pop_m - pow(2, i, n - 1)) % (n - 1)
                ans.append(count(mod))
            else:
                mod = (X_pop_p + pow(2, i, n + 1)) % (n + 1)
                ans.append(count(mod))

    print("\n".join(map(str, ans[::-1])))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N = int(input())
S = list(input())
table = [0]*(N+3)
table[1] = 1
for i in range(2,N+3):
    num = i
    cnt = 0
    while num != 0:
        a = num % 2
        num = num // 2
        cnt += a
    p = i % cnt
    table[i] = table[p]+1
c = 0
for s in S:
    if s == "1":
        c += 1
ans = 0
plus = [0]*N
minus = [0]*N
p = 0
q = 0
for i in range(N):
    ss = S[N-1-i]
    p += int(ss)*pow(2,i,c+1)
    if c != 1:
        q += int(ss)*pow(2,i,c-1)
    p %= (c+1)
    q %= (c-1)
for i in range(N):
    ss = S[i]
    if ss == "0":
        ans = (p+pow(2,N-1-i,c+1))%(c+1)
        print(table[ans]+1)
    else:
        if c == 1:
            print(0)
        else:
            ans = (q-pow(2,N-1-i,c-1))%(c-1)
            print(table[ans]+1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)
def d(n):
 if n==0:return 0
 return d(n%bin(n).count("1"))+1
n=int(input())
x=input()
c=x.count("1")
a=int(x,2)
j,k=a%(c+1),a%(c-1)
for i in range(n):
 if x[i]=="1":print(d((k-pow(2,n-i-1,c-1))%(c-1))+1)
 else:print(d((j+pow(2,n-i-1,c+1))%(c+1))+1)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
N=int(sys.stdin.readline().strip())
X=sys.stdin.readline().strip()

cnt_of_one=0
for x in X:
    if x=="1": cnt_of_one+=1

cnt_of_one_plus_one=cnt_of_one+1
cnt_of_one_minus_one=cnt_of_one-1

amari_cnt_of_one_plus_one=0
amari_cnt_of_one_minus_one=0
for i,x in enumerate(X[::-1]):
    if x=="1":    #その桁の値が1の時だけ数を足す
        amari_cnt_of_one_plus_one+=pow(2,i,cnt_of_one_plus_one)
        amari_cnt_of_one_plus_one%=cnt_of_one_plus_one
        amari_cnt_of_one_minus_one+=pow(2,i,cnt_of_one_minus_one)
        amari_cnt_of_one_minus_one%=cnt_of_one_minus_one

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

def f(n):
    ret=0   #余りが0になるまでの割った回数
    while 0<n:
        n%=popcount(n)
        ret+=1
    return ret

for i,x in enumerate(X):
    keta=N-i-1
    if x=="0":
        syoki_amari=(amari_cnt_of_one_plus_one+pow(2,keta,cnt_of_one_plus_one))%cnt_of_one_plus_one
        if syoki_amari==0:
            print 1
        else:
            print 1+f(syoki_amari)
    elif x=="1":
        syoki_amari=(amari_cnt_of_one_minus_one-pow(2,keta,cnt_of_one_minus_one))%cnt_of_one_minus_one
        if syoki_amari==0:
            print 1
        else:
            print 1+f(syoki_amari)

Submission status: Runtime Error

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

def popcount(l):
    return bin(l).count("1")
def count(l):
    res = 0
    while l != 0:
        p = popcount(l)
        l %= p
        res += 1
    return res
m = popcount(x)
x_plus = x%(m+1)
x_minus = x%(m-1)
lis_plus = [0]*n
lis_minus = [0]*n
for i in range(n):
    if i == 0:
        lis_plus[i] = 1%(m+1)
        if m != 1:
            lis_minus[i] = 1%(m-1)
    else:
        lis_plus[i] = lis_plus[i-1]*2%(m+1)
        if m != 1:
            lis_minus[i] = lis_minus[i-1]*2%(m-1)
for i in range(n):
    if (x >> (n-i-1)) & 1:
        if m == 1:
            print(0)
        else:
            print(count((x_minus - lis_minus[-i-1])%(m-1)) + 1)
    else:
        print(count((x_plus + lis_plus[-i-1])%(m+1)) + 1)

Submission status: Runtime Error

Solution code:

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

def popcount(ni):
    n_b = str(bin(ni))
    return n_b.count("1")

def ans(n,x):
    x_i = int(x, 2)
    x_orig = popcount(x_i)
    x_i_t = x_i % (x_orig+1)
    x_i_b = x_i % (x_orig-1)
    solve = 0
    for i in range(n):
        x_count = x_orig
        if x[i] == "0":
            x_count += 1
            solve = x_i_t + pow(2,n-1-i,x_count)
        else:
            x_count -= 1
            solve = x_i_b - pow(2,n-1-i,x_count)
        count = 0

        if solve != 0 :
            solve = solve % x_count
            count+=1

        while solve > 0:
            solve = solve % popcount(solve)
            count+=1

        print(count)

    
ans(n,x)

Submission status: Runtime Error

Solution code:
import math
from copy import copy
di = {}
di[0] = 0
for i in range(1, 2*(10**5)+1):
    di[i] = 0
for i in range(1, 2*(10**5)+1):
    count = 0
    for j in range(int(math.log2(i))+4):
        if (i>>j)&1:
            count += 1
    di[i] = di[i%count] + 1
n = int(input())
x = list(input())
x.reverse()
count = 0
for i in x:
    if i =='1':
        count += 1
mod_p = count + 1
mod_m = count - 1
di_p = {}
di_m = {}
for i in range(n):
    di_p[i] = pow(2, i, mod_p)
    if mod_m >= 1:
        di_m[i] = pow(2, i, mod_m)
s_p = 0
s_m = 0
for i in range(n):
    if x[i] == '1':
        s_p += di_p[i]
        s_m += di_m[i]
    else:
        continue
for i in range(n-1, -1, -1):
    sm = copy(s_m)
    sp = copy(s_p)
    if x[i] == '1' and (mod_m == 0 or mod_m == -1):
        print(0)
    elif x[i] == '1':
        sm -= di_m[i]
        sm %= mod_m 
        print(di[sm]+1)
    else:
        sp += di_p[i]
        sp %= mod_p
        print(di[sp]+1)

Submission status: Runtime Error

Solution code:
def d(n):
 if n==0:return 0
 return d(n%bin(n).count("1"))+1
n=int(input())
x=input()
c=x.count("1")
a=int(x,2)
j,k=a%(c+1),a%(c-1)
for i in range(n):
 if x[i]=="1":print(d(k-pow(2,n-i-1,c-1)%(c-1))+1)
 else:print(d(j+pow(2,n-i-1,c+1)%(c+1))+1)

Submission status: Runtime Error

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

def popcount(l):
    return bin(l).count("1")
def count(l):
    res = 0
    while l != 0:
        p = popcount(l)
        l %= p
        res += 1
    return res
m = popcount(x)
x_plus = x%(m+1)
x_minus = x%(m-1)
lis_plus = []
lis_minus = []
for i in range(n):
    if i == 0:
        lis_plus.append(1%(m+1))
        if m != 1:
            lis_minus.append(1%(m-1))
    else:
        lis_plus.append(lis_plus[-1]*2%(m+1))
        if m != 1:
            lis_minus.append(lis_minus[-1]*2%(m-1))
for i in range(n):
    if (x >> (n-i-1)) & 1:
        if m == 1:
            print(0)
        else:
            print(count((x_minus - lis_minus[-i-1])%(m-1)) + 1)
    else:
        print(count((x_plus + lis_plus[-i-1])%(m+1)) + 1)

Submission status: Runtime Error

Solution code:

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

def popcount(ni):
    n_b = str(bin(ni))
    return n_b.count("1")

def ans(n,x):
    x_i = int(x, 2)
    x_orig = popcount(x_i)
    x_i_t = x_i % (x_orig+1)
    x_i_b = x_i % (x_orig-1)
    solve = 0
    n_i = 2**(n-1)
    for i in range(n):
        x_count = x_orig
        if x[i] == "0":
            x_count += 1
            solve = x_i_t + (n_i % x_count)
        else:
            x_count -= 1
            solve = x_i_b - (n_i % x_count) 
        n_i = n_i >> 1 
        count = 0

        if solve != 0 :
            solve = solve % x_count
            count+=1

        while solve > 0:
            solve = solve % popcount(solve)
            count+=1

        print(count)

    
ans(n,x)

Submission status: Runtime Error

Solution code:
N=int(input())
X=input()
Xnum=int(X,2)
popcount=X.count('1')
for i in range(N):
    if X[i]=='1':
        Xi = Xnum - 2**(N-i-1)
        popcount2=popcount-1
    else:
        Xi = Xnum + 2**(N-i-1)
        popcount2=popcount+1
    if popcount2==0: print(0)
    else:
        ans = 0
        while Xi!=0:
            Xi = Xi % popcount2
            popcount2 = bin(Xi).count('1')
            ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
from numba import jit

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

def popcount(ni):
    n_b = str(bin(ni))
    return n_b.count("1")

@jit
def ans(n,x):
    x_i = int(x, 2)
    x_orig = popcount(x_i)
    x_i_t = x_i % (x_orig+1)
    x_i_b = x_i % (x_orig-1)
    solve = 0
    n_i = 2**(n-1)
    for i in range(n):
        x_count = x_orig
        if x[i] == "0":
            x_count += 1
            solve = x_i_t + (n_i % x_count)
        else:
            x_count -= 1
            solve = x_i_b - (n_i % x_count) 
        n_i = n_i >> 1 
        count = 0

        if solve != 0 :
            solve = solve % x_count
            count+=1

        while solve > 0:
            solve = solve % popcount(solve)
            count+=1

        print(count)

    
ans(n,x)

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
x=input().rstrip()
p=x.count("1")
numx=0
for i in range(n):
    if x[-i-1]=="1":
        numx+=2**i
minus=numx%(p-1)
plus=numx%(p+1)

def popcnt(x):
    cnt=str(bin(x)).count("1")
    x%=cnt
    return x

for i in range(n):
    if x[i]=="0":
        amari=(plus+2**(n-i-1)%(p+1))%(p+1)
        ans=1
        while amari>=1:
            amari=popcnt(amari)
            ans+=1
        print(ans)
    else:
        if p==1:
            print(0)
            continue
        amari=(minus-2**(n-i-1)%(p-1))%(p-1)
        ans=1
        while amari>=1:
            amari=popcnt(amari)
            ans+=1
        print(ans)

Submission status: Runtime Error

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


B_1 = B.count("1")
mod_list_m1 = []
mod_list_p1 = []

mod_m1 = 0
mod_p1 = 0
for i in range(N):
  	if B_1 != 1:
        mm1 = (2**(N-i-1)) % (B_1-1)
        mod_list_m1.append(mm1)
        mod_m1 += int(B[i])*mm1
    mp1 = (2**(N-i-1)) % (B_1+1)
    mod_list_p1.append(mp1)
    mod_p1 += int(B[i])*mp1

def calc_small(n, iter):
    iter += 1
    mod = n % bin(n).count("1")

    if mod == 0:
        return iter
    else:
        return calc_small(mod, iter)

for i in range(N):
  	if B_1 == 1 and int(B[i]) == 1:
      	print(0)
        continue
    mod = (mod_m1 - mod_list_m1[i]) % (B_1-1) if int(B[i]) == 1 else (mod_p1 + mod_list_p1[i]) % (B_1+1)
    iter = 1
    if mod == 0:
        print(iter)
    else:
        print(calc_small(mod, iter))

Submission status: Runtime Error

Solution code:
import sys
n = int(input())
x = int(input(),2)
if bin(x).count('1')+1 > 1000:
    sys.setrecursionlimit(bin(x).count('1')+1)
    
ans = [0]*(bin(x).count('1')+1)
for i in range(1,len(ans)):
    ans[i] = 1 + ans[i%bin(i).count('1')]
#print(ans)
for i in range(n):
    y = x^(1<<(n-i-1))
    t = y % bin(y).count('1')
    print(1+ans[t])

Submission status: Runtime Error

Solution code:

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


def popcount(ni):
    n_b = str(bin(ni))
    return n_b.count("1")


def ans(n,x):
    x_i = int(x, 2)
    x_orig = popcount(x_i)
    solve = 0
    n_i = 2**(n-1)
    print(n_i)
    for i in range(n):
        x_count = x_orig
        if x[i] == "0":
            x_count += 1
            solve = (x_i % x_count) + (n_i % x_count)
        else:
            x_count -= 1
            solve = (x_i % x_count) - (n_i % x_count)
        n_i = n_i >> 1 
        count = 0

        if solve != 0 :
            solve = solve % x_count
            count+=1

        while solve > 0:
            solve = solve % popcount(solve)
            count+=1

        print(count)

    
ans(n,x)