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())
X = input()

source_one = X.count('1')
# print(count_one)

import collections

count = collections.defaultdict(int)
count[1] = 1
count[2] = 1
count_one = {}

# print(int(X, 2), X)

source_n = int(X, 2)

kijou = 2 ** N

for i in range(N):
    kijou //= 2
    if X[i] == '1':
        # bit = X[:i] + '0' + X[i+1:]
        one_count = source_one - 1
        original_n = source_n - kijou
    else:
        # bit = X[:i] + '1' + X[i + 1:]
        one_count = source_one + 1
        original_n = source_n + kijou
    # original_n = int(bit, 2)
    # print(original_n, bit, kijou)


    if original_n in count:
        print(count[n])
        continue
    if original_n % one_count == 0:
        count[n] = 1
        print(1)
        continue

    n = original_n
    n_list = []
    flag = 0

    while n % one_count != 0:
        count[original_n] += 1
        n = n % one_count
        n_list.append(n)

        if n in count_one:
            one_count = count_one[n]
        else:
            one_count = bin(n).count('1')
            count_one[n] = one_count
        # print(n, one_count)

        if n in count:
            count[original_n] += count[n]
            flag = 1
            break

    if not flag:
        count[original_n] += 1

    for idx, n in enumerate(n_list):
        if n in count:
            continue
        else:
            count[n] = count[original_n] - (idx + 1)
    print(count[original_n])

Submission status: Runtime Error

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

def f(N:int,s:int):
    bina=list(bin(N))
    array=bina[2:]
    c=0
    for i in array:
        if i=="1":
            c+=1
    p=N%c
    s+=1
    if p==0:
        return s
    else:
        return f(p,s)


N=int(input())
binary=input()
a="0b"+binary
binary=int(a,0)
for i in reversed(range(N):
    print(f(toggle_nth_bit(binary,i),0))

Submission status: Runtime Error

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

dic = {0: 0, 1: 1, 2: 1}

def popcount(c):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

def f(x):
    #print(x)
    if x in dic:
        #print("!", x, dic[x])
        return dic[x]
    else:
        next_x = x % popcount(x)
        ans = f(next_x) + 1
        dic[x] = ans
        return ans

for i in range(n):
    keta = n - i - 1
    bit = 2 ** keta
    trans_num = num ^ bit
    #print(bin(num), bin(bit), bin(trans_num))
    #print("ans", f(trans_num))
    print(f(trans_num))

Submission status: Runtime Error

Solution code:
N = int(input())
X = input().strip()
C = X.count("1")
D = int(X, 2)
Mm, Mp = 0, D % (C+1)
if C > 0:
    Mm = D % (C-1)

p = [0]*(2*10**5+2)
for i in range(1, len(p)):
    n = i
    while True:
        b = bin(n).count("1")
        if b <= 0:
            break
        p[i] += 1
        n = n % b

for i in range(1, N+1):
    c = C
    if X[i-1] == "1":
        c -= 1
        if c == 0:
            print(0)
            continue
        m = Mm
        d = pow(2, N-i, c)
        d = (m-d+c) % c
    else:
        c += 1
        m = Mp
        d = pow(2, N-i, c)
        d = (m+d) % c

    print(p[d]+1)

Submission status: Runtime Error

Solution code:

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

    popcount = {k:-1 for k in range(2**N)}
    popcount[0] = 0

    li = []
    for n in range(N):
        li.append(X ^ 1<<(N-n-1))

    for l in li:
        num = 0
        a = l
        while(True):
            num += 1
            b = bin(a).count('1')
            res = a % b
            # print(f"res = {res}")
            if popcount[res] > -1:
                popcount[l] = num + popcount[res]
                break
            elif res == 0:
                popcount[l] = num
                break
            a = res
    
    for l in li:
        print(popcount[l])
    



if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
X_list = []
for i in range(N):
    X_list.append(int(X[i]))


import math
def solve(x):
    count = 0
    while x != 1:
        tmp = int(math.log2(x))
        tmp += 1
        for i in range(tmp):
            if (x >> i) & 1 == 1:
                count += 1
        x = x%count
    return x

def solve2(x):
    tmp = X_list.copy()
    if tmp[x] == 1:
        tmp[x] = 0
    else:
        tmp[x] = 1
    num = 1
    ans = 0
    for i in range(N-1,-1,-1):
        ans += tmp[i]*num
        num = num*2
        
    return ans   

for i in range(N):
    tmp = solve2(i)
    ans = solve(tmp)
    print(ans)

Submission status: Runtime Error

Solution code:
def popcnt(n):
    return bin(n).count("1")
N = int(input())
L = [0]*(N+1)
for i in range(1,N+1):
    L[i] = L[i%popcnt(i)]+1
X = input()
M = X.count("1")+1
m = M-2
X = list(X)
XM = int(X[-1])
Xm = int(X[-1])
tM = 1
tm = 1
X.reverse()
for i in range(1,N):
    tM = tM*2%M
    tm = tm*2%m
    if X[i] == "1":
        XM = (XM + tM)%M
        Xm = (Xm + tm)%m
ans = []
tM = 1
tm = 1
for i in range(N):
    A = 0
    if X[i] == "0":
        A = (XM + tM)%M
    else:
        A = (Xm + m - tm)%m
    ans.append(A)
    tM = (tM*2)%M
    tm = (tm*2)%m
ans.reverse()
for a in ans:
    print(L[a]+1)

Submission status: Runtime Error

Solution code:
if __name__ == '__main__':
    n = int(input().strip())
    x = input().strip()

    pre_count = [1, 1, 2, 1, 2,
                 1, 2, 1, 2, 1,
                 2, 1, 2, 2, 2]

    for i in range(n):
        count = 1
        _x = list(x)
        _x[i] = "0" if _x[i] == "1" else "1"
        _x = int("".join(_x), 2)
        _x = int(_x % bin(_x).count("1"))
        if not _x == 0:
            count += pre_count[_x - 1]
        print(count)

Submission status: Runtime Error

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

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

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

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f

def reverse_bin(X, ind):
    ret = X[:ind]
    ret += "1" if X[ind] == "0" else "0"
    ret += X[ind + 1:]

    return ret

def main():
    N = int(input())
    X_str = input()
    X = int(X_str, 2)
    for i in range(len(X_str)):
        count = 0
        X_tr = reverse_bin(X_str, i)
        x = int(X_tr, 2)
        while x != 0:
            x = x % popcount(x)
            count += 1
        print(count)
    

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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


N = int(input())
X = input()
X2 = int(X, 2)
count = popcount(X2)
prev = X[0]

for i in range(N-1, -1, -1):
    bit = X[N-i-1]
    if bit == prev:
        pop = count
    elif bit > prev:
        pop = count - 1
    else:
        pop = count + 1
    prev = bit
    ans = 1
    Y = X2 ^ (1 << i)
    Y %= pop
    while Y > 0:
        Y %= popcount(Y)
        ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
    def popcount(x):
        x = x - ((x >> 1) & 0x55555555)

        x = (x & 0x33333333) + ((x >> 2) & 0x33333333)

        x = (x + (x >> 4)) & 0x0f0f0f0f
        x = x + (x >> 8)
        x = x + (x >> 16)
        return x & 0x0000007f

    N = int(input())
    X = int(input(),2)
    counts = []

    for i in range(1,N+1,1):
        count = 0
        Xi = X ^ 2**(N-i)
        while Xi!=0:
            count+=1
            #popcount
            #Xi = Xi%bin(Xi).count("1")
            Xi = Xi % popcount(Xi)
        counts.append(count)

    for k in counts:
        print(k)

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
p=x.count("1")
Ma=[1]+[0]*(n-1)
Mb=[1]+[0]*(n-1)
for i in range(1,n):
  Ma[i]=Ma[i-1]*2%(p-1)
  Mb[i]=Mb[i-1]*2%(p+1)
Sa=Sb=0
for i in range(n):
  if x[i]=="1":
    Sa+=Ma[n-1-i]
    Sb+=Mb[n-1-i]
for i in range(n):
  a=1
  if x[i]=="1":
    s=(Sa-Ma[n-1-i])%(p-1)
  else:
    s=(Sb+Mb[n-1-i])%(p+1)
  while(s>0):
    t=0
    r=s
    while(r>0):
      t+=r&1
      r//=2
    s%=t
    a+=1
  print(a)

Submission status: Runtime Error

Solution code:
A=[0] * N
for i in range(N):
    A[i]=int(X[-i])
A.reverse()
ans=0
for i in range(N-1,-1,-1):
    if A[i]==0:
        A[i]=1
        for j in range(N):
            ans+=(2**j)*A[j]
        q=0
        k=ans
        while k>0:
            a=bin(k)
            k=k%a.count('1')
            q+=1
        print(q)
        A[i]=0
        ans=0
    if A[i]==1:
        A[i]=0
        for j in range(N):
            ans+=(2**j)*A[j]
        q=0
        k=ans
        while k>0:
            a=bin(k)
            k=k%a.count('1')
            q+=1
        print(q)
        A[i]=1
        ans=0

Submission status: Runtime Error

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

c = X.count('1')

table = [0]*(2*pow(10,5))

for i in range(2*pow(10,5)):
    a = bin(i+1)
    z = a.count('1')
    table[i] = (i+1)%z

up = True

for i in range(N):
    Xi = list(X)
    if Xi[i] == '1':
        Xi[i] = '0'
        c -= 1
        up = False
    else:
        Xi[i] = '1'
        c += 1
        up = True
    
    if up:
        n = int(X,2) - pow(2,N-i)
    else:
        n = int(X,2) + pow(2,N-i)
    n = n % c
    ans = 1
    while n > 0:
        n = table[n-1]
        ans += 1
        
    print(ans)
    
    if up:
        c -= 1
    else:
        c += 1

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from functools import reduce, lru_cache
import collections, heapq, itertools, bisect
import math, fractions
import sys, copy

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline().rstrip())
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline().rstrip())
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

def main():
    N = I()
    X = S()
    original_popcount = X.count("1")

    upper_popcount = original_popcount + 1
    lower_popcount = original_popcount - 1

    if original_popcount == 0:
        for i in range(N):
            print(1)
        return

    # Xが0の可能性
    upper = [0] * N
    lower = [0] * N
    upper[-1] = 1 % upper_popcount
    lower[-1] = 1 % lower_popcount

    for i in range(1, N)[::-1]:
        upper[i-1] = (2 * upper[i]) % upper_popcount
        lower[i-1] = (2 * lower[i]) % lower_popcount

    mu = 0
    ml = 0
    for i in range(N):
        if X[i] == "1":
            mu = (mu + upper[i]) % upper_popcount
            ml = (ml + lower[i]) % lower_popcount

    for i in range(N):
        if X[i] == "0":
            m = (mu + upper[i]) % upper_popcount
        else:
            m = (ml - lower[i]) % lower_popcount

        ans = 1
        while m:
            tmp = m
            ones = 0
            while tmp:
                if tmp & 1 == 1:
                    ones += 1
                tmp //= 2
            m %= ones
            ans += 1

        print(ans)



if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
import copy
n = int(input())
k = input()
xnum = int(k,2)

def f(x):
    a = bin(x)
    a = a[2:]
    num = a.count('1')
    ans = 1
    hantei = x % num if num != 0 else hantei = 0
    while hantei != 0:
        ans += 1
        a = bin(hantei)
        a = a[2:]
        num = a.count('1')
        hantei = x % num if num != 0 else hantei = 0
    return ans

z = []
for i in range(n):
    y = copy.deepcopy(k)
    if y[i] == '1':
        ynum = xnum - 2 ** (n-i-1)
        z.append(ynum)
    else:
        ynum = xnum + 2 ** (n-i-1)
        z.append(ynum)

for j in z:
    ans = f(j)
    print(ans)

Submission status: Runtime Error

Solution code:
N = int(input().strip())
X = [int(v) for v in input().strip()]

store = [-1] * (2 ** N)


def popcount(bins):
    return sum(bins)


def f(bins):
    # print(bins)
    count = 0
    x = get_num(bins)
    while x != 0:
        if store[x] != -1:
            count += store
            break
        pc = popcount([int(v) for v in bins])
        x = x % pc
        bins = get_bin(x)
        count += 1
    return count


def get_bin(n):
    return bin(n)[2:]


def get_num(bins):
    bins = "".join([str(v) for v in bins])
    return int(bins, 2)


for i in range(N):
    # print(X)
    X[i] = int(not(X[i]))

    count = f(X)
    store[get_num(X)] = count
    print(count)

    X[i] = int(not(X[i]))

Submission status: Runtime Error

Solution code:
N = int(input())
X = int(input(),2)
 
def f(x, n):
  c = format(x, 'b').count("1")
  if x%c==0:
    return n+1
  else:
    return f(x%c, n + 1)
 
for i in range(N):
  print(f(X^(2**(N-1-i)),0))

Submission status: Runtime Error

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

number = bin(x).count('1')
# print(number)
def calc(im, p, order):
    result = im%p
    if result == 0:
        return order
    else:
        order += 1
        num = bin(result).count('1') 
        return calc(result,num, order)
for i in range(n-1,-1,-1):
    pop = number
    if x>>i & 1 == 1:
        y = x-2**i
        pop = number-1
    else:
        y = x + 2**i
        pop = number +1
    print(calc(y, pop, 1))

Submission status: Runtime Error

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


n=int(input())
X=str(input())

number=0
for i in range(n):
    if X[i]=='1':
        number+=1

base1=0
for i in range(n):
    if X[i]=='1':
        base1=(base1+pow(2,n-i-1,number+1))%(number+1)


base2=0
for i in range(n):
    if X[i]=='1':
        base2=(base2+pow(2,n-i-1,number-1))%(number-1)



def culc(x):
    bin_x=str(bin(x)[2:])
    one=0
    for i in range(len(bin_x)):
        if bin_x[i]=='1':
            one+=1
    return x%one
        



#dp[i](0<=i<=number)
dp=[-1]*(number+1)
dp[0]=0
def rec(x):
    if dp[x]>=0:
        return dp[x]
    else:
        dp[x]=rec(culc(x))+1
        return dp[x]





for i in range(n):
    #base1
    if X[i]=='0':
        temp=(base1+pow(2,n-i-1,number+1))%(number+1)
        ans=rec(temp)+1
        print(ans)
    #base2
    if X[i]=='1':
        temp=(base2-pow(2,n-i-1,number-1))%(number-1)
        ans=rec(temp)+1
        print(ans)

Submission status: Runtime Error

Solution code:
if __name__ == '__main__':
    n = int(input().strip())
    x = input().strip()

    pre_count = [1, 1, 2, 1, 2,
                 1, 2, 1, 2, 1,
                 2, 1, 2, 2, 2]

    for i in range(n):
        count = 0
        _x = list(x)
        _x[i] = "0" if _x[i] == "1" else "1"
        _x = int("".join(_x), 2)
        _x = int(_x % bin(_x).count("1"))
        if _x == 0:
            count = 1 + pre_count[_x]
        print(count)

Submission status: Runtime Error

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

Y = int(X, 2)
Z = list(map(int,list(X)))
X_1 = bin(Y).count("1")
X_1m = X_1-1
X_1p = X_1+1
if X_1m!=0:
    Ym = Y%X_1m
Yp = Y%X_1p


temp = []
for i in range(200010):
    ans = 0
    while i > 0:
        i %= bin(i).count("1")
        ans += 1
    temp.append(ans)

temp2p = []
temp2m = []
ansp = 1
ansm = 1
for i in range(200010):
    ansp %= X_1p
    ansm %= X_1m
    temp2p.append(ansp)
    temp2m.append(ansm)
    ansp *= 2
    ansm *= 2    

for i in range(N):
    if Z[i]==0:
        Xi = Yp + temp2p[(N-i-1)]
        Xi %= X_1p
        
        print(1+temp[Xi])
    else:
        if sum(Z)==1:
            print(0)
        else:
            Xi = Ym - temp2m[(N-i-1)]
            Xi %= X_1m
            print(1+temp[Xi])

Submission status: Runtime Error

Solution code:
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

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

for i in range(N):
  x_list = list(X)
  if x_list[i] == '0':
    x_list[i] = '1'
  else:
    x_list[i] = '0'
  x_changed = "".join(x_list)
  print(popcount(x_changed.encode()))
  #print(int(x_changed))
  #print(bin(int(x_changed)))

Submission status: Runtime Error

Solution code:
n=int(input())
m=input()
x=int(m,2)
li=list(m)
def popcount(x):
  return list(str(bin(x))).count("1")
def check(a):
  co=1
  while a!=0:
    co+=1
    a%=popcount(a)
  return co
jpop=popcount(x)
jop=x%(jpop+1)
jom=x%(jpop-1)
jppp=jpop+1
jppm=jpop-1
for i in range(0,n):
  nijo=2**(n-i-1)
  if li[i]=="0":
    a=jop+nijo%jppp
    if a>=jppp:
      a-=jppp
  else:
    a=jom-nijo%jppm
    if a<0:
      a+=jppm
  if a==0:
    print(1)
    continue
  print(check(a))

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
for i in range(n):
    num = x[:i]
    if x[i] == '0':
        num += '1'
    else:
        num += '0'
    num += x[i + 1:]
    #print(num)
    ans = 0
    #pop = num.count('1')
    #num = int(num, 2) % pop
    pop, hoge = num_cnt(num)
    num = hoge % pop
    num = bin(num)
    ans = 1
    #print(num)
    while int(num, 2) != 0:
        #pop = num.count('1')
        #num = int(num, 2) % pop
        pop, hoge = num_cnt(num)
        num = hoge % pop
        num = bin(num)
        ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
def f_n(n):
  ans = 0
  while n > 0:
    n = n%bin(n).count("1")
    ans += 1
  return ans
  
n = int(input())
x = int(input(), 2)
for i in range(n-1,0,-1):
  tmp = x
  print(f_n(((~(tmp & (1<<i))) & (1<<i)) | (tmp & ~(1<<i))))
print(f_n(((~(tmp & 1)) & 1) | (tmp & ~1)))

Submission status: Runtime Error

Solution code:
def pop(x):
    bin_x = format(x, 'b')
    return bin_x.count('1')

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

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

for n in range(N):
    newX = ''
    # if n ==0:
    #     newX = X[n:].replace('1', 'asd').replace('0', '1').replace('asd', '0') 
    # else:
    #     newX  = X[:0] +  X[n:].replace('1', 'asd').replace('0', '1').replace('asd', '0')
    # if(X[n] == '0'):
    #     X[n] = '1'
    # else:
    #     X[n]= '0'
    newX  = X[:n] +  X[n].replace('1', 'asd').replace('0', '1').replace('asd', '0')
    if(n!= N-1): 
        newX += X[n+1:]
    # newX = X[:n] +  X[n:].replace('1', 'asd').replace('0', '1').replace('asd', '0')
    # print('X[:n]' + str(X[:n]))
    # print(newX)
    print(fn(int(newX, 2)))
    # if(X[n] == '0'):
    #     X[n] = '1'
    # else:
    #     X[n]= '0'

Submission status: Runtime Error

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

import sys
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N = int(readline())
X = readline().decode().rstrip()

hoge = [pow(2, i) for i in range(N + 5)]
counts = [1 if i in hoge else -1 for i in range(N + 5)]

for i in range(N):
    cnt = X.count('1')

    tmp = 0
    X_ = list(X)
    m = 0
    if X[i] == "0":
        cnt += 1
        X_[i] = "1"
    else:
        X_[i] = "0"
        cnt -= 1

    X_ = "".join(X_)
    acc = 0
    for j, c in enumerate(X_[::-1]):
        if c == '1':
            acc += hoge[j]
    if acc > 2 * pow(10, 5):
        if acc % cnt == 0:
            print(1)
            continue
        else:
            acc %= cnt
            cnt = bin(acc).count('1')
            tmp += 1

    if counts[acc] != -1:
        print(counts[acc] + tmp)
    else:
        while True:
            if acc % cnt == 0:
                counts[acc] = 1
                print(counts[acc] + tmp)
                break
            elif counts[acc % cnt] != 0:
                counts[acc] = counts[acc % cnt] + 1
                print(counts[acc] + tmp)
                break

            acc %= cnt
            cnt = bin(acc).count('1')
            #print(acc, cnt)

Submission status: Runtime Error

Solution code:
import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
#from bisect import bisect_left as bl, bisect_right as br, insort
#from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
#from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var) : sys.stdout.write('\n'.join(map(str, var))+'\n')
def out(var) : sys.stdout.write(str(var)+'\n')
#from decimal import Decimal
#from fractions import Fraction
#sys.setrecursionlimit(100000)
#INF = float('inf')
mod = int(1e9)+7

n=int(data())
x=data()
c=x.count('1')
t1,t2=1,1
k1=0
k2=0
for i in range(n-1,-1,-1):
    if x[i]=='1':
        k1=(k1+t1)%(c+1)
        k2=(k2+t2)%(c-1)
    t1=(t1*2)%(c+1)
    t2=(t2*2)%(c-1)
ans=[]
t1,t2=1,1
for i in range(n-1,-1,-1):
    if x[i]=='1':
        k=(k2-t2+c-1)%(c-1)
    else:
        k=(k1+t1)%(c+1)
    cnt=1
    while k:
        k=k%(bin(k)[2:].count('1'))
        cnt+=1
    ans.append(cnt)
    t1 = (t1 * 2) % (c + 1)
    t2 = (t2 * 2) % (c - 1)
outl(ans[::-1])

Submission status: Runtime Error

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

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

def popcnt(n):
    return bin(n).count("1")

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from collections import Counter

def count_ones_by_bin(num):
    bin_num = bin(num)[2:]
    count = 0
    for i in bin_num:
            count += int(i)
    return count



n=int(input())
x=input()
d={}
j=[]
for i in range(n-):
  ans=0
  if x[i]=="1":
    y=x[:i]+"0"+x[i+1:]
  else:
    y=x[:i]+"1"+x[i+1:]
  c=int(y,2)
  a=int(y,2)

  while True:
    if a in d:
      j.append(d[a]+ans)
      print(d[a]+ans)
    b=count_ones_by_bin(a)
    if b==0 or a==0:
      d[c]=ans
      j.append(ans)
      print(count)
      break
    a%=b
    ans+=1

Submission status: Runtime Error

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

def popcount(i):
    c = 0
    while not i % format(i, 'b').count('1') == 0:
        c += 1
        i = i % format(i, 'b').count('1')
    return c

for i in range(N):
    x = X
    if x[i] == '0':
        x = x[:i] + '1' + x[i+1:]
    else:
        x = x[:i] + '0' + x[i+1:]
    print(popcount(int(x, 2))+1)

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
# = str(input())
# = map(int, input().split())
X = str(input())
Xlist = np.array(list(map(int, X)))
total = int(X, 2)
# = [int(input()) for i in range(N)]
# = [list(map(int, input().split())) for i in range(N)]
one = np.sum(Xlist)

print("test", 2**0)

if N == 1:
    if X == "1":
        print(0)
        exit()
    else:
        print(1)
        exit()

for i in range(N):
    count = 0
    joe = N-1-i
    check = int(total)
    if Xlist[i] == 1:
        div = one -1
        next = (check%div - (2**joe)%div)%div
        if next == 0:
            count += 1
            print(count)
        else:
            count += 1
            check = next
            while check > 0:
                b = bin(next)
                clist = list(map(int, b[2:]))
                clist = np.array(clist)
                div = np.sum(clist)
                if div == 0:
                    break
                next = check%div
                if next == 0:
                    count += 1
                    print(count)
                    break
                else:
                    count += 1
                    check = next

    else:
        div = one +1
        next = (total%div + (2**joe)%div)%div
        if next == 0:
            count += 1
            print(count)
        else:
            count += 1
            check = next
            while check > 0:
                b = bin(next)
                clist = list(map(int, b[2:]))
                clist = np.array(clist)
                div = np.sum(clist)
                if div == 0:
                    break
                next = check%div
                if next == 0:
                    count += 1
                    print(count)
                    break
                else:
                    count += 1
                    check = next

Submission status: Runtime Error

Solution code:
n=int(input())
m=input()
x=int(m,2)
li=list(m)
def popcount(x):
  return list(str(bin(num))).count("1")
def check(a):
  co=1
  while a!=0:
    co+=1
    a%=popcount(a)
  return co
jpop=popcount(x)
jop=x%(jpop+1)
jom=x%(jpop-1)
jppp=jpop+1
jppm=jpop-1
for i in range(0,n):
  nijo=2**(n-i-1)
  if li[i]=="0":
    a=jop+nijo%jppp
    if a>=jppp:
      a-=jppp
  else:
    a=jom-nijo%jppm
    if a<0:
      a+=jppm
  if a==0:
    print(1)
    continue
  print(check(a))

Submission status: Runtime Error

Solution code:
#import numpy as np 
#popcount=[0]*n
eight_1=[0,1,1,2,1,2,2,3]
eight_2=[0]*64
for i in range(8):
  for j in range(8):
    eight_2[i*8+j]=eight_1[i]+eight_1[j]
#eight_01=0
#eight_02=0
#eight_03=0
#print(eight_2)
"""for k in range(n):
  if eight_01==64:
    eight_02+=1
    eight_01=0
    if eight_02==64:
      eight_03+=1
      eight_02=0
  popcount[k]=eight_2[eight_01]+eight_2[eight_02]+eight_2[eight_03]
  eight_01+=1
f=[0]*n
"""
def popcount(s,n):
  r=0
  for i in range(n,64):
    b=int(s[i,i+64],2)
    r+= eight_2[b]
  return r
def f(n):
  if n=1:
    return 1
  s=bin(n)[1:]
  r=n%popcount(s,len(n))
  return f(r)
  
  
n=int(input())
x=input()
#x=np.array([y for y in x])
x_num=int(x,2)
#x_len=n
n+=1
#n_2=2**n
n+=-1
for m in range(n):
  if x[m]==1:
    r=x_num-2**(n-m)
  else:
    r=x_num+2**(n-m)
  
  print(f[r])

Submission status: Runtime Error

Solution code:
n = int(input())
x = list(input())
y = int(''.join(x), 2)

memo = [0]


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


for i in range(1, n):
    tmp = i % popcount(i)
    memo.append(memo[tmp] + 1)

B = 2**(n-1)
for d in x:
    tmp = y
    if d == '0':
        tmp += B
    else:
        tmp -= B

    tmp = int(tmp)

    if tmp == 0:
        print(0)
        B = B // 2
        continue

    tmp = tmp % popcount(tmp)
    print(memo[tmp] + 1)
    B = B // 2

Submission status: Runtime Error

Solution code:
# def popcount(x):
#     bitx = bin(x)
#     cnt = bitx.count('1')
#     return cnt

n = int(input())
x = list(input())
popcount = x.count('1')
stock = [1] * (n + 1)

for i in range(1, n + 1):
    stock[i] = stock[i - 1] * 2


for i in range(n):
    tmp = x.copy()
    tmp2 = popcount
    if tmp[i] == '1':
        tmp[i] = '0'
        tmp2 -= 1
    else:
        tmp[i] = '1'
        tmp2 += 1
    num = 0
    if tmp[i] == '0':
        for i in range(n):
            num += tmp[i] * stock[i]
    
    if tmp2 == 0:
        print(0)
    elif num>0 and num % tmp2 == 0:
        print(1)
    elif tmp[n - 1] == '1' and tmp2 % 2 == 0 and tmp2 > 2:
        print(3)
    else:
        print(2)

Submission status: Runtime Error

Solution code:
import math
from copy import copy
di = {}
di[0] = 0
for i in range(1, 2*(10**6)+1):
    di[i] = 0
for i in range(1, 2*(10**6)+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:
        print(1)
    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)