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 numpy as np
from typing import List, Tuple

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

def binary_mod(bits: List[int], div: int) -> int:
    val = 0
    for b in bits:
        val = (val * 2 + b) % div
    return val

def f(x):
    cnt = 0
    while x > 0:
        x = x % bin(x).count('1')
        cnt += 1
    return cnt

popcount = sum(X)
div1 = popcount + 1
div2 = popcount - 1

rem1 = binary_mod(X, div1)
rem2 = binary_mod(X, div2)

for i in range(N):
    if X[i] == 0:
        r = rem1 + pow(2, N - 1 - i, div1)
        print(f(r) + 1)
    else:
        r = (rem2 - pow(2, N - 1 - i, div2) + div2) % div2
        print(f(r) + 1)

Submission status: Runtime Error

Solution code:
def input_int():
    return map(int, input().split())

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

N=one_int()
S=one_str()

bit_count = S.count("1")

#bit数
calc_dict = {i:-1 for i in range(22000)}
res_dict =  {i:-1 for i in range(2*(10**5))}

res_dict = {i:-1 for i in range(1001)}
res_dict[0]=0

for i in range(1, 1001):
    if calc_dict[i]==-1:
        calc_dict[i] = bin(i).count("1")
    
    res_dict[i] = i%calc_dict[i]+1


bit_count = S.count("1")
for i in range(len(S)):
    if S[i]=="0":

        bit_count+=1
        num = int(S,2) + 2**(N-i-1)
        if num==0:
            print(0)
        else:
            print(res_dict[num%bit_count]+1)

#         print(mods(num, bit_count, 0))
        bit_count-=1
    else:

        bit_count-=1
        num = int(S,2) - 2**(N-i-1)
        if num==0:
            print(0)
        else:
            print(res_dict[num%bit_count]+1)
        bit_count+=1

Submission status: Runtime Error

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N = I()
X = list(input())

# xが0になるまで何回かかるか
def calc(x):
    n = len(x)
    c = x.count('1')
    now = 0
    for i in range(n):
        if x[i] == '1':
            now += 2**(n-1-i)
            now %= c
    if now == 0:
        return 1
    else:
        return calc(list(format(now,'b')))+1

count = X.count('1')

a = [1]*(N+1)
a[0] = 1%(count-1)
for i in range(1,N+1):
    a[i] = a[i-1]*2
    a[i] %= count-1

b = [1]*(N+1)
b[0] = 1%(count+1)
for i in range(1,N+1):
    b[i] = b[i-1]*2
    b[i] %= count+1

suma = 0
sumb = 0
for i in range(N):
    if X[i] == '1':
        suma += a[N-i-1]
        sumb += b[N-i-1]
        suma %= (count-1)
        sumb %= (count+1)

ans = [0]*N
for i in range(N):
    if X[i] == '1':
        val = (suma-a[N-i-1])%(count-1)
        if val == 0:
            ans[i] = 1
        else:
            ans[i] = calc(list(format(val,'b')))+1
    else:
        val = (sumb+b[N-i-1])%(count+1)
        if val == 0:
            ans[i] = 1
        else:
            ans[i] = calc(list(format(val,'b')))+1

for a in ans:
    print(a)

Submission status: Runtime Error

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

def dv(x):
    return '0b'+x

def countpop(x):
    c = 0
    while True:
        a=bin(x).count("1")
        b=x%a
        c+=1
        if b==0:
            break
        x=b
    return c
def bitnot(x,i):
    if x[i]=='1':
        return x[:i]+'0'+x[(i+1):]
    else:
        return x[:i]+'1'+x[(i+1):]


for i in range(N):
    x=int(dv(bitnot(X,i)),0)
    print(countpop(x))

Submission status: Runtime Error

Solution code:
N=int(input())
xstr = input()
X=[int(v) for v in xstr]
num = int(xstr,2)
s=sum(X)
m = 2*10**5+1
pre = [-1]*m
pre[0]=0
for i in range(1,m):
  ans = 0
  tmp = i
  while True:
    if pre[tmp]!=-1:
      pre[i]=ans+pre[tmp]
      break
    cnt = 0
    for j in range(100):
      if tmp>>j&1:
        cnt+=1
    ans+=1
    #if cnt==0: print(tmp)
    tmp = tmp%cnt
#print(pre)

for i in range(N):
  if X[i]==0:
    s2 = s+1
    n2 = num + 2**(N-1-i)
  else:
    s2 = s-1
    n2 = num - 2**(N-1-i)
  amari = n2%s2
  print(1+pre[amari])

Submission status: Runtime Error

Solution code:
a = [0]*(2*10**5+1)
for i in range(1,2*10**5):
  t=0
  j = i
  while j != 0:
    t+=j-(j>>1)*2
    j=j>>1
  a[i]+=t
n = int(input())
x = input()
cnt=0
for i in x:
  if i=='1':
    cnt+=1
d =int(x, 2)
for i in range(n):
  if x[i] =='1':
    e=d-2**(n-i-1)
    c = cnt-1
  else:
    e=d+2**(n-i-1)
    c= cnt+1
  if e%c ==0:
    print(1)
  else:
    ans=1
    e= e%c
    c = a[e]
    while c!=0:
      e=e%c
      c = a[e]
      ans+=1
    print(ans)

Submission status: Runtime Error

Solution code:
# coding: utf-8

import sys

sys.setrecursionlimit(10000)


def bi(x, n_digit):
    output = ""
    for i in range(n_digit-1, -1, -1):
        if x >= 2**i:
            x -= 2**i
            output += "1"
        else:
            output += "0"
    return output


def popcount(bi_n):
    output = 0
    for c in bi_n:
        if c == "1":
            output += 1
    return output


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

    fs = [None] * 20

    def rec(x):
        pop_x = popcount(bi(x, 18))
        r = x % pop_x
        if r == 0:
            return 1
        elif r < 20 and fs[r] is not None:
            return 1 + fs[r]
        else:
            return 1 + rec(r)

    for i in range(1, 20):
        fs[i] = rec(i)
    fs[0] = 0

    pop_X = popcount(bi_X)
    qp = pop_X+1
    qm = pop_X-1

    bi_qp = [None] * N
    bi_qp[0] = 1 % qp
    bi_qp[1] = 2 % qp
    for i in range(2, N):
        bi_qp[i] = ((bi_qp[1])*(bi_qp[i-1])) % qp
    
    if qm > 0:
        bi_qm = [None] * N
        bi_qm[0] = 1 % qm
        bi_qm[1] = 2 % qm
        for i in range(2, N):
            bi_qm[i] = ((bi_qm[1])*(bi_qm[i-1])) % qm

    rp = 0
    rm = 0
    for i in range(N):
        p = N-1-i
        coo = int(bi_X[i])
        rp = (rp + (((coo % qp) * bi_qp[p]) % qp)) % qp
        if qm > 0:
            rm = (rm + (((coo % qm) * bi_qm[p]) % qm)) % qm

    for i in range(N):
        if bi_X[i] == "0":
            ri = (rp + bi_qp[N-1-i]) % qp
            if ri < 20:
                print(1 + fs[ri])
            else:
                pop_ri = popcount(bi(ri, 18))
                print(2 + fs[ri % pop_ri])
        else:
            if qm > 0:
                ri = (rm - bi_qm[N-1-i]) % qm
                if ri < 20:
                    print(1 + fs[ri])
                else:
                    pop_ri = popcount(bi(ri, 18))
                    print(2 + fs[ri % pop_ri])
            else:
                print(0)


main()
# print(main())

Submission status: Runtime Error

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

ans_reduce,ans_add = 0,0
for i in range(n):
    if(one_num>1):
        ans_reduce = (ans_reduce+pow(2,n-i-1,one_num-1)*(1 if x[i] == '1' else 0))%(one_num-1)
    ans_add = (ans_add+pow(2,n-i-1,one_num+1)*(1 if x[i] == '1' else 0))%(1+one_num)

for i in range(n):
    now_one = one_num + (-1 if x[i] == '1' else 1)
    num = ((ans_reduce if x[i] == '1' else ans_add) + pow(2,n-i-1,now_one)*(-1 if x[i] == '1' else 1))%now_one
    ans = 1
    while(num!=0):
        ans += 1
        num = num % bin(num).count('1')
    print(ans)

Submission status: Runtime Error

Solution code:
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
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 S(): return input()
def LS(): return input().split()


INF = float('inf')


def popcnt(m):
    return bin(m).count('1')


def popcount(x):
    # 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 f(m):
    res = 0
    while m > 0:
        m = m % popcount(m)
        res += 1
    return res


# print(bin(1))
n = I()
# x = int(S(), 2)
x = S()
for i in range(n):
    xi = list(x)
    if xi[i] == '0':
        xi[i] = '1'
    else:
        xi[i] = '0'
    xi = int(''.join(xi), 2)
    # print(xi)
    print(f(xi))

Submission status: Runtime Error

Solution code:
N = int(input())
X = list(input())
def devide(n):
    global cnt
    ans = int(n, 2) % n.count("1")
#     print(int(n, 2),n.count("1"))
    if ans == 0:
        cnt += 1
        print(cnt)
    else:
        cnt += 1
        return devide(bin(ans))
    
for i in range(N):
    cnt = 0
    if X[i] == "0":
        X[i] = "1"
        nn= ''.join(X)
        devide(nn)
        X[i] = "0"
    else:
        X[i] = "0"
        nn= ''.join(X)
        devide(nn)
        X[i] = "1"

Submission status: Runtime Error

Solution code:
# coding: utf-8
# hello worldと表示する
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
n=I()
lis=list(SI())

#s="".join(list(map(str,lis)))
#print(s)
#sys.exit()
#print(lis)
#sys.exit()
orig=0
for i in range(n):
    if lis[i]=="0":
        lis[i]=0
    else:
        lis[i]=1
orcount=sum(lis)
#beki=[1 for i in range(n+1)]
#for i in range(n):
    #beki[i+1]=beki[i]*2
#print(beki)
#print(lis)
m1=0
m2=0
m3=0
for i in range(n):
    if lis[i]==1:
        if orcount==0:
            m1=0
            m3=0
        elif orcount==1:
            m1=0
            m3=(m3+pow(2,n-i-1,orcount+1))
        else:
            m1=(m1+pow(2,n-i-1,orcount-1))
            m3=(m3+pow(2,n-i-1,orcount+1))
m1=m1%(orcount-1)
m3=m3%(orcount+1)
#print(m1)
#print(m3)
#print(orig)
dp=[0 for i in range(n+1)]
dp[1]=1
for i in range(1,n):
    #u=count1(i+1)
    count=0
    j=0
    while pow(2,j)<=i+1:
        if ((i+1)>>j) %2==1:
            count+=1
        j+=1
    z=1
    dp[i+1]=z+dp[(i+1)%count]
#print(dp)
for i in range(n):
    if lis[i]==0:
        #num=orig+pow(2,n-i-1)
        pr=orcount+1
        num=m3+pow(2,n-i-1,pr)
    else:
        #num=orig-pow(2,n-i-1)
        pr=orcount-1
        num=m1-pow(2,n-i-1,pr)
    #print(num,pr)
    if pr==0:
        print(0)
    else:
        print(1+dp[num%pr])

Submission status: Runtime Error

Solution code:
from functools import lru_cache


result = 0
@lru_cache(maxsize=None)
def popcount(n):
    global result
   
    bin_n = bin(n)
    one = bin_n.count('1')
    tmp = n % one
    result += 1
    if tmp > 0:
        popcount(tmp)
    return(result)



N = int(input())
stri = input()

X = 0
for i in range(len(stri)):
    if stri[len(stri) -1 -i] == '1':
        X += 2 ** i

# print(popcount(1))
# print(1<<3)
# print(0b111 ^ 1<<2)
for i in range(len(stri)-1,-1,-1):
    tmpX = X ^ 1<<i
    # print(tmpX)
    print(popcount(tmpX))
    result = 0

Submission status: Runtime Error

Solution code:
# coding: utf-8

import sys

sys.setrecursionlimit(10000)


def bi(x, n_digit):
    output = ""
    for i in range(n_digit-1, -1, -1):
        if x >= 2**i:
            x -= 2**i
            output += "1"
        else:
            output += "0"
    return output


def popcount(bi_n):
    output = 0
    for c in bi_n:
        if c == "1":
            output += 1
    return output


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

    fs = [None] * 20

    def rec(x):
        pop_x = popcount(bi(x, 18))
        r = x % pop_x
        if r == 0:
            return 1
        elif r < 20 and fs[r] is not None:
            return 1 + fs[r]
        else:
            return 1 + rec(r)

    for i in range(1, 20):
        fs[i] = rec(i)
    fs[0] = 0

    pop_X = popcount(bi_X)
    qp = pop_X+1
    qm = pop_X-1

    bi_qp = [None] * N
    bi_qm = [None] * N
    bi_qp[0] = 1 % qp
    bi_qm[0] = 1 % qm
    bi_qp[1] = 2 % qp
    bi_qm[1] = 2 % qm
    for i in range(2, N):
        bi_qp[i] = ((bi_qp[1])*(bi_qp[i-1])) % qp
        bi_qm[i] = ((bi_qm[1])*(bi_qm[i-1])) % qm

    rp = 0
    rm = 0
    for i in range(N):
        p = N-1-i
        coo = int(bi_X[i])
        rp = (rp + (((coo % qp) * bi_qp[p]) % qp)) % qp
        rm = (rm + (((coo % qm) * bi_qm[p]) % qm)) % qm

    for i in range(N):
        if bi_X[i] == "0":
            ri = (rp + bi_qp[N-1-i]) % qp
            if ri < 20:
                print(1 + fs[ri])
            else:
                pop_ri = popcount(bi(ri, 18))
                print(2 + fs[ri % pop_ri])
        else:
            ri = (rm - bi_qm[N-1-i]) % qm
            if ri < 20:
                print(1 + fs[ri])
            else:
                pop_ri = popcount(bi(ri, 18))
                print(2 + fs[ri % pop_ri])



main()
# print(main())

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
ans = [0]*(-(-n//2)+1)

def f(x):
    c = 0
    while x:
        c += 1
        x = x % bin(x).count('1')
    return c

one_cnt = x.count('1')
numx = int(x,2)
for i in range(n):
    temp = one_cnt
    if x[i]=='0':
        temp += 1
        num = numx + 2**(n-1-i)
    else:
        temp -= 1 if temp>0 else 0
        num = numx - 2**(n-1-i)
    print(f(num%temp)+1)

Submission status: Runtime Error

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))

# ===CODE===

eps = 10 ** (-9)


def main():
    def popcounter(n):
        cnt = 0
        if n == 0:
            return 0
        for _ in range(INF):
            tmp = bin(n).count("1")
            n = n % tmp
            cnt += 1
            if n == 0:
                return cnt

    n = ni()
    x = input()
    x_1 = x.count("1")

    num = int(x, 2)
    num1 = num % (x_1 - 1)
    num0 = num % (x_1 + 1)

    ans = []
    for i in range(len(x)):
        if x[len(x) - 1 - i] == "1":
            tmp_n = (num1 - pow(2, i)) % (x_1 - 1)
        else:
            tmp_n = (num0 + pow(2, i)) % (x_1 + 1)
        ans.append(popcounter(tmp_n) + 1)

    l = len(ans)
    for i in range(l - 1, -1, -1):
        print(ans[i])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    n_ansl = [0]*(2*(10**5))
    for i in range(1,2*(10**5)):
    # for i in range(1,20):
        cnt = 0
        one_cnt = bin(i).count("1")
        rem = i
        while rem != 0:
            one_cnt = bin(rem).count("1")
            rem = rem%one_cnt   
            cnt += 1
        n_ansl[i] = cnt
 
    n = int(input())
    x = input()
    one_cnt = x.count('1')

    if one_cnt == 0:
        for i in range(n):
            print(1)
        exit()
    
    curr_2b_p = 1
    curr_2b_m = 1
    curr_sum_p1 = 0
    curr_sum_m1 = 0
    for i in range(n-1, -1, -1):
        if x[i] == '1':
            curr_sum_p1 += curr_2b_p
            curr_sum_m1 += curr_2b_m
            curr_sum_p1%=(one_cnt+1)
            if one_cnt > 1:
                curr_sum_m1%=(one_cnt-1)
        curr_2b_p*=2
        curr_2b_m*=2
        curr_2b%=one_cnt
        curr_2b_p%=(one_cnt+1)
        if one_cnt > 1:
            curr_2b_m%=(one_cnt-1)
 
        
 
    curr_2b_p = 1
    curr_2b_m = 1
    ansl = [0]*(n)
    for i in range(n-1, -1, -1):
        if x[i] == '1':
            diff = (-1)*curr_2b_m
            if one_cnt > 1:
                ans = (curr_sum_m1 + diff)%(one_cnt-1)
                ansl[i] = n_ansl[ans]+1
            else:
                ansl[i] = 0
        else:
            diff = curr_2b_p
            ans = (curr_sum_p1 + diff)%(one_cnt+1)
            ansl[i] = (n_ansl[ans]+1)
        curr_2b_p*=2
        curr_2b_m*=2
        curr_2b_p%=(one_cnt+1)
        if one_cnt > 1:
            curr_2b_m%=(one_cnt-1)
 
 
    # print(ansl)
    for a in ansl:
        print(a)
 
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import gmpy2

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

def dv(x):
    return '0b'+x

def countpop(x):
    c = 0
    while True:
        a=gmpy2.popcount(x)
        b=x%a
        c+=1
        if b==0:
            break
        x=b
    return c
def bitnot(x,i):
    if x[i]=='1':
        return x[:i]+'0'+x[(i+1):]
    else:
        return x[:i]+'1'+x[(i+1):]


for i in range(N):
    x=int(dv(bitnot(X,i)),0)
    print(countpop(x))

Submission status: Runtime Error

Solution code:

result = 0

def popcount(n):
    global result
   
    bin_n = bin(n)
    one = bin_n.count('1')
    tmp = n % one
    result += 1
    if tmp > 0:
        popcount(tmp)
    return(result)



N = int(input())
stri = input()

X = 0
for i in range(len(stri)):
    if stri[len(stri) -1 -i] == '1':
        X += 2 ** i

# print(popcount(1))
# print(1<<3)
# print(0b111 ^ 1<<2)
for i in range(len(stri)-1,-1,-1):
    tmpX = X ^ 1<<i
    # print(tmpX)
    print(popcount(tmpX))
    result = 0

Submission status: Runtime Error

Solution code:
N=int(input())
xstr = input()
X=[int(v) for v in xstr]
num = int(xstr,2)
s=sum(X)

pre = [-1]*101
pre[0]=0
for i in range(1,101):
  ans = 0
  tmp = i
  while True:
    if pre[tmp]!=-1:
      pre[i]=ans+pre[tmp]
      break
    cnt = 0
    for j in range(10):
      if tmp>>j&1:
        cnt+=1
    ans+=1
    tmp = tmp%cnt
#print(pre)

for i in range(N):
  if X[i]==0:
    s2 = s+1
    n2 = num + 2**(N-1-i)
  else:
    s2 = s-1
    n2 = num - 2**(N-1-i)
  amari = n2%s2
  print(1+pre[amari])

Submission status: Runtime Error

Solution code:
def popcount(n,ct):
    x2 = bin(n)
    x3 = x2.count("1")
    if n%x3==0:
        return ct + 1
    else:
        return popcount(n%x3,ct+1)
n = int(input())
x = input()
xt = x
for i in range(n):
    xt = list(x)
    if xt[i]=="0":
        xt[i] = "1"
    else:
        xt[i] = "0"
    xt = "".join(xt)
    x1 = int(xt,2)
    print(popcount(x1,0))

Submission status: Runtime Error

Solution code:
from collections import deque

n = int(input())
x = eval('0b' + 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 = bin(x).count("1")

for i in range(n):
    y = 0
    py = px
    if x & (1 << i):
        y = x - 2 ** i
        py -= 1
    else:
        y= x + 2 ** i
        py += 1
    ans.append(solve(y%py)+1)

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

Submission status: Runtime Error

Solution code:
n = int(input())
# for i in range(n):
#     print('0', end='')
# print(flush=True)
x_str = input()
x = int(x_str, base=2)
popcount = x_str.count('1')
y_zero = x % (popcount + 1)
y_one = x % (popcount - 1)
dp = [-1] * n
dp[0] = 0


def calc(y):
    if dp[y] != -1:
        return dp[y]
    dp[y] = 1 + calc(y % bin(y).count('1'))
    return dp[y]


ans = [0] * n
rem_zero = 1
rem_one = popcount - 2
for i in range(n):
    if x_str[n - 1 - i] == '0':
        ans[n - 1 - i] = 1 + calc((y_zero + rem_zero) % (popcount + 1))
    else:
        ans[n - 1 - i] = 1 + calc((y_one + rem_one) % (popcount - 1))
    rem_zero = rem_zero * 2 % (popcount + 1)
    rem_one = rem_one * 2 % (popcount - 1)
for i in range(n):
    print(ans[i])

Submission status: Runtime Error

Solution code:
for i in range(n):
    tempx=x
    tempx[i]=str(int(x[i]) ^ 1)
    #if tempx[i]=='1':
    #    tempy=y+1
    #else:
    #    tempy=y-1
    if i>0:
        tempx[i-1]=str(int(tempx[i-1]) ^ 1)

    #print(tempx,x)
    tempx=int("".join(tempx),2)

    #print(tempx)
    cnt=0

    while True:
        if int(tempx)==0:
            print(cnt)
            break
        tempx%=bin(tempx).count('1')
        #print(len(tempx))
        #tempy=
        #print(tempx,'koko')
        #print(type(tempx),len(tempx))

        cnt+=1

Submission status: Runtime Error

Solution code:
# coding: utf-8
# hello worldと表示する
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
n=I()
lis=list(SI())

#s="".join(list(map(str,lis)))
#print(s)
#sys.exit()
#print(lis)
#sys.exit()
orig=0
for i in range(n):
    if lis[i]=="0":
        lis[i]=0
    else:
        lis[i]=1
orcount=sum(lis)
#beki=[1 for i in range(n+1)]
#for i in range(n):
    #beki[i+1]=beki[i]*2
#print(beki)
#print(lis)
m1=0
m2=0
m3=0
for i in range(n):
    if lis[i]==1:
        m1=(m1+pow(2,n-i-1,orcount-1))
        #m2=(m2*pow(2,n-i-1,orcount))%mod
        m3=(m3+pow(2,n-i-1,orcount+1))
m1=m1%(orcount-1)
m3=m3%(orcount+1)
#print(m1)
#print(m3)
#print(orig)
dp=[0 for i in range(n+1)]
dp[1]=1
for i in range(1,n):
    #u=count1(i+1)
    count=0
    j=0
    while pow(2,j)<=i+1:
        if ((i+1)>>j) %2==1:
            count+=1
        j+=1
    z=1
    dp[i+1]=z+dp[(i+1)%count]
#print(dp)
for i in range(n):
    if lis[i]==0:
        #num=orig+pow(2,n-i-1)
        pr=orcount+1
        num=m3+pow(2,n-i-1,pr)
    else:
        #num=orig-pow(2,n-i-1)
        pr=orcount-1
        num=m1-pow(2,n-i-1,pr)
    #print(num,pr)
    if pr==0:
        print(0)
    else:
        print(1+dp[num%pr])

Submission status: Runtime Error

Solution code:
def input_int():
    return map(int, input().split())

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

N=one_int()
S=one_str()

bit_count = S.count("1")

#bit数
calc_dict = {i:-1 for i in range(22000)}
res_dict =  {i:-1 for i in range(2*(10**5))}

res_dict = {i:-1 for i in range(1001)}
res_dict[0]=0

for i in range(1, 1001):
    if calc_dict[i]==-1:
        calc_dict[i] = bin(i).count("1")
    
    res_dict[i] = i%calc_dict[i]+1




# def mods(N, m, count):
#     temp = N%m
#     count+=1
#     while temp!=0:

#         if temp in res_dict:
# #             print(count, temp, res_dict[temp])
# #             print("come")
# #             print()
#             return count+res_dict[temp]
        
#         if calc_dict[temp]==-1:
#             calc_dict[temp] = bin(temp).count("1")
            
#         temp = temp%calc_dict[temp]
#         count+=1

#     return count

bit_count = S.count("1")
for i in range(len(S)):
    if S[i]=="0":

        bit_count+=1
        num = int(S,2) + 2**(N-i-1)
#         print(num, bit_count)
        print(res_dict[num%bit_count]+1)
#         print(mods(num, bit_count, 0))
        bit_count-=1
    else:

        bit_count-=1
        num = int(S,2) - 2**(N-i-1)
        print(res_dict[num%bit_count]+1)
#         print(mods(num, bit_count, 0))
        bit_count+=1

Submission status: Runtime Error

Solution code:
import sys
import copy
from collections import deque
import collections
stdin = sys.stdin

mod = 10**9+7

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
x = ns()
dp = {}


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

def f(p):
    if p in dp:
        return dp[p]
    pop = popcount(p)
    r = p%pop
    if r > 0:
        dp[p] = f(r) + 1
    else:
        dp[p] = 1
    return dp[p]

for i in range(n):
    if x[i]=='0':
        tmp = x[:i] + '1' + x[i+1:]
    else:
        tmp = x[:i] + '0' + x[i+1:]
    
    print(f(int(tmp, 2)))

Submission status: Runtime Error

Solution code:
def popcount(x):
    c = str(x).count('1')
    return c


n = int(input())
a = input()

for i in range(1,n+1):
    b = int(a[:i-1] + str(int(a[i-1],2)^abs(1-int(a[i-1],2))^int(a[i-1],2)) + a[i:]) 
    print(b)
    intb = int(str(b),2)
    pop = popcount(b)
    count=0
    while intb:
        count+=1
        intb = intb%pop
        pop = popcount(intb)
    print(count)

Submission status: Runtime Error

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

up = True
n = int(X,2)
c = X.count('1')

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

Submission status: Runtime Error

Solution code:
def fast_powmod(n, m):
    pow2 = 2
    result = 1
    while n > 0:
        if n % 2 == 1:
            result = (result * pow2) % m
        pow2 = (pow2 * pow2) % m
        n >>= 1

    return result

def popcnt3(n):
    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

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

res = dict()
res[1] = 1
res[2] = 1
for i in range(3, 2 * 10**5 + 1):
    val = i % popcnt3(i)
    if val == 0:
        res[i] = 1
    else:
        res[i] = res[val] + 1

count = 0
for i in x:
    if i == "1":
        count += 1

x = x[::-1]
small = 0
big = 0
for i in range(len(x)):
    if x[i] == "1":
        small += fast_powmod(i, count - 1)
        big += fast_powmod(i, count + 1)

try:
    small %= count - 1
except:
    small = 0
big %= count + 1

anse = []
for i in range(len(x)):
    if x[i] == "1":
        done = False
        ans = 0
        if count - 1 == 0:
            anse.append(0)
        else:
            cur = small - fast_powmod(i, count - 1)
            cur %= count - 1
            if cur == 0:
                anse.append(1)
            else:
                anse.append(res[cur] + 1)
    else:
        done = False
        ans = 0
        cur = big + fast_powmod(i, count + 1)
        cur %= count + 1
        if cur == 0:
            anse.append(1)
        else:
            anse.append(res[cur] + 1)


for i in anse[::-1]:
    print(i)
                
        
        
# print(small, big)

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)

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

Submission status: Runtime Error

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

val0 = 0
val1 = 0
cnt = 0

for i in range(0,n):
    if s[i] == '1':
        cnt += 1

for i in range(0,n):
    if s[i] == '1':
        val0 += pow(2,n-i-1,cnt+1)
        val1 += pow(2,n-i-1,cnt-1)

def  countSetBits(n): 
    count = 0
    while (n): 
        count += n & 1
        n >>= 1
    return count

for i in range(0,n):
    ans = 0
    if s[i] == '0':
        vall = val0
        o = cnt + 1
        vall += pow(2,n-i-1,o)
        while vall != 0:
            vall = vall % (o)
            o = countSetBits(vall)
            ans += 1
    else:
        vall = val1
        o = cnt - 1
        vall -= pow(2,(n-i-1),o)
        while vall != 0:
            vall = vall % (o)
            o = countSetBits(vall)
            ans += 1
    print(ans)