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 = list(input())[::-1]

num = 0
pop_num = 0
for i in range(N):
    if x[i] == "1":
        num += 2 ** i
        pop_num += 1

def popcnt(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
x = x[::-1]
import sys
sys.setrecursionlimit(10**8)

def calc(i,depth,n):
    if depth == 0:
        if x[i] == "1":
            tmp = (num - 2 ** (N - i)) % (pop_num - 1)
            return calc(i,depth+1,tmp)
        else:
            tmp = (num + 2 ** (N - i)) % (pop_num + 1)
            return calc(i,depth+1,tmp)
    else:
        if n == 0: return depth
        return calc(i,depth+1, n % popcnt(n))
        

for i in range(N):
    print(calc(i,0,0))

Submission status: Runtime Error

Solution code:
N = int(input())
x = list(input())[::-1]

num = 0
pop_num = 0
for i in range(N):
    if x[i] == "1":
        num += 2 ** i
        pop_num += 1

def popcnt(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
x = x[::-1]
import sys
sys.setrecursionlimit(10**10)

def calc(i,depth,n):
    if depth == 0:
        if x[i] == "1":
            tmp = (num - 2 ** (N - i)) % (pop_num - 1)
            return calc(i,depth+1,tmp)
        else:
            tmp = (num + 2 ** (N - i)) % (pop_num + 1)
            return calc(i,depth+1,tmp)
    else:
        if n == 0: return depth
        return calc(i,depth+1, n % popcnt(n))
        

for i in range(N):
    print(calc(i,0,0))

Submission status: Runtime Error

Solution code:
N=int(input())
X=input()
Y=int(X,2)

J=X.count("1")

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

if J>1:
    B=[0]*N
    B[0]=1
    for j in range(2,N+1):
        B[-j]=(B[-(j-1)]*2)%(J-1)


H=[0]*N
Q,R=divmod(Y,J)
for i in range(N):
    if X[i]=="0":
        S=(R+A[i]-Q)%(J+1)
    else:
        if J==1:
            continue
        S=(R-B[i]+Q)%(J-1)
        
    I=1
    while S>0:
        S=S%bin(S).count("1")
        I+=1
    H[i]=I

print("\n".join(map(str,H)))

Submission status: Runtime Error

Solution code:
N = int(input())
x = list(input())[::-1]

num = 0
pop_num = 0
for i in range(N):
    if x[i] == "1":
        num += 2 ** i
        pop_num += 1

def popcnt(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

def calc(i,depth,n):
    if depth == 0:
        if x[N-i] == "1":
            tmp = (num - 2 ** (N - i)) % (pop_num - 1)
            return calc(i,depth+1,tmp)
        else:
            tmp = (num + 2 ** (N - i)) % (pop_num + 1)
            return calc(i,depth+1,tmp)
    else:
        if n == 0: return depth
        return calc(i,depth+1, n % popcnt(n))
        

for i in range(1,1+N):
    print(calc(i,0,0))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2000)

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

def f(n):
    t = int(n,2) % list(n).count('1')
    if t == 0:
        return 1
    else:
        return f(str(bin(t))) + 1

for i in range(n):
    xb = list(x)
    xb[i] = '0' if xb[i] == '1' else '1'
    print(f(''.join(xb)))

Submission status: Runtime Error

Solution code:
N = int(input())
x = input()
#print(int(x,2))

def popcount(X,ones,count): 
 
    if ones==0:
        return count
    else:
      
        X=X%ones
        
        count+=1
 
        ones=str(bin(X)).count("1")
        
        return popcount(X,ones,count)
 
GroundOnes=x.count("1")
GroundX=int(x,2)
 
CaseOne= GroundX%(GroundOnes-1)
CaseZero= GroundX%(GroundOnes+1)

TwoPowerCaseOne=[]
TwoPowerCaseZero=[]

for j in range(N):
  TwoPowerCaseOne.append(2**(N-j-1) % (GroundOnes-1))
  TwoPowerCaseZero.append(2**(N-j-1) % (GroundOnes+1))
  
for i in range(N):
    
    #CaseOne
    if x[i]=="1":
        ones=GroundOnes-1
        X=CaseOne+TwoPowerCaseOne[i]
        
    #CaseZero
    else:
        ones=GroundOnes+1
        X=CaseZero+TwoPowerCaseZero[i]
            
 
    # print("for loop",i)
    # print("ones",ones)
    # print("new2bit",new2bit)
    # print(" ------ return --- ",popcount(X,ones,0))
    print(popcount(X,ones,0))

Submission status: Runtime Error

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

n = int(input())
x = input()
z = '1' * n
o = '0' * n
X = int(x, 2)

if (n = 1 and x == '1'):
  print(0)
  exit()

if (z == x):
  u = n - 1
  d = n - 1
elif (o == x):
  u = 1
  d = 1
else:
  tmp = len(list(filter(lambda x: x == '1', x)))
  u = tmp + 1
  d = tmp - 1


def popcount(i):
  return i % len(list(filter(lambda x: x == '1', format(i, 'b'))))


def solve(i, count):
  if (i <= 2 * 10**5 and ans[i] != 0):
    return count + ans[i]
  elif (i == 0):
    return count
  else:
    return solve(popcount(i), count + 1)


def solve2(i, div):
  if (i <= 2 * 10**5):
    return ans[i]
  else:
    return ans[i % div] + 1


ans = [0] * (2 * 10 ** 5 + 4)
_u = (2 * 10 ** 5) // u
U = X % u + (u * _u) + u
if(d != 0):
  _d = (2 * 10 ** 5) // d
  D = X % d + (d * _d) * 2 + d * 2
Us = [0] * (2 * 10 ** 5)
Ds = [0] * (2 * 10 ** 5)
for i in range(1, 2 * 10 ** 5 + 4):
  ans[i] = solve(i, 0)
Us[0] = 1 % u
if(d != 0):
  Ds[0] = 1 % d
for i in range(1, 2 * 10 ** 5):
  Us[i] = (Us[i - 1] * 2) % u
  if(d != 0):
    Ds[i] = (Ds[i-1] * 2) % d

for i in range(n):
  if(x[i] == '0'):
    print(solve2(U + Us[n-i-1], u))
  else:
    if (d == 0):
      print(0)
    else:
      print(solve2(D - Ds[n-i-1], d))

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
memo = {0:0}
for i in range(1, n+1):
    j = i
    a = 0
    while True:
        if j in memo:
            memo[i] = memo[j]+a
            break;
        else:
            b = 0
            k = j
            while k > 0:
                if k%2 == 1:
                    b += 1
                k //= 2
            j %= b
            a += 1
n1 = 0
for i in range(n):
    if x[i] == "1":
        n1 += 1
mup = [1]
mdown = [1]
for i in range(1, n):
    mup.append(mup[-1]*2%(n1+1))
    mdown.append(mdown[-1]*2%(n1-1))
mup.reverse()
mdown.reverse()
mmup = 0
mmdown = 0
for i in range(n):
    mmup = (mmup+mup[i]*int(x[i]))%(n1+1)
    mmdown = (mmdown+mdown[i]*int(x[i]))%(n1-1)
for i in range(n):
    if x[i] == "0":
        state = "up"
        n1i = n1+1
    else:
        state = "down"
        n1i = n1-1
    if state == "up":
        mm = (mmup+mup[i])%n1i
    else:
        mm = (mmdown-mdown[i])%n1i
    print(memo[mm]+1)

Submission status: Runtime Error

Solution code:
N=int(input())
X=input()
S=X.count('1')
S1=S+1
S2=S-1

i=0
while i<N:
    xx=list(X)
    if xx[i]=='0':
        xx[i]='1'
        A=int(''.join(xx),2)%S1
    else:
        xx[i]='0'
        A=int(''.join(xx),2)%S2
    count=1
    while A:
        count+=1
        A=A%(bin(A).count('1'))
    print(count)
    i+=1

Submission status: Runtime Error

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()


N=int(input())
X=input()
C=X.count("1")

lst=[]
lstcount=[]
for x in [C-1,C+1]:
    flg=0
    if C<=0:
        lst.append(0)
        lstcount.append(0)
    else:
        Z=0
        p=1
        for i in range(N):
            if X[-i-1]=="1":
                Z+=p
            p*=2
            if Z>=x:
                Z%=x
                flg=1
            if flg:
                p%=x
        lst.append(Z)
        lstcount.append(flg)
exit()
#print(lst)
fac1=[1]
fac2=[1]
C1=C-1
C2=C+1
for i in range(N):
    fac1.append(fac1[-1]*2%C1)
    fac2.append(fac2[-1]*2%C2)

for i in range(N):

    _C=C+(1 if X[i]=="0"  else -1 )
    if _C==0:
        print(0)
        continue
    if  X[i]=="0":
        lstidx=1
    else:
        lstidx=0

    idx=(N-1-i)

    value=lst[lstidx]+(fac2[idx] if  X[i]=="0" else fac1[idx])
    #print(lst[lstidx],value,_C)
    count=lstcount[lstidx]-1
    while value:
        count+=1
        value%=_C
        _C=0
        bit=value
        while bit:
            _C+=bit&1
            bit>>=1
    print(max(count,1))

Submission status: Runtime Error

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

n = int(input())
x = input()
z = '1' * n
o = '0' * n
X = int(x, 2)

if (z == x):
  u = n - 1
  d = n - 1
elif (o == x):
  u = 1
  d = 1
else:
  tmp = len(list(filter(lambda x: x == '1', x)))
  u = tmp + 1
  d = tmp - 1


def popcount(i):
  return i % len(list(filter(lambda x: x == '1', format(i, 'b'))))


def solve(i, count):
  if (i <= 2 * 10**5 and ans[i] != 0):
    return count + ans[i]
  elif (i == 0):
    return count
  else:
    return solve(popcount(i), count + 1)


def solve2(i, div):
  if (i <= 2 * 10**5):
    return ans[i]
  else:
    return ans[i % div] + 1


ans = [0] * (2 * 10 ** 5 + 4)
_u = (2 * 10 ** 5) // u
U = X % u + (u * _u) + u
if(d != 0):
  _d = (2 * 10 ** 5) // d
  D = X % d + (d * _d) * 2 + d * 2
Us = [0] * (2 * 10 ** 5)
Ds = [0] * (2 * 10 ** 5)
for i in range(1, 2 * 10 ** 5 + 4):
  ans[i] = solve(i, 0)
  
Us[0] = 1 % u
if(d != 0):
  Ds[0] = 1 % d
for i in range(1, 2 * 10 ** 5):
  Us[i] = (Us[i - 1] * 2) % u
  if(d != 0):
    Ds[i] = (Ds[i-1] * 2) % d

for i in range(n):
  if(x[i] == '0'):
    print(solve2(U + Us[n-i-1], u))
  else:
    if (d == 0):
      print(0)
    else:
      print(solve2(D - Ds[n-i-1], d))

Submission status: Runtime Error

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()


N=int(input())
X=input()
C=X.count("1")

lst=[]
lstcount=[]
for x in [C-1,C+1]:
    flg=0
    if C<=0:
        lst.append(0)
        lstcount.append(0)
    else:
        Z=0
        p=1
        for i in range(N):
            if X[-i-1]=="1":
                Z+=p
            p*=2
            if Z>=x:
                Z%=x
                flg=1
            if flg:
                p%=x
        lst.append(Z)
        lstcount.append(flg)

#print(lst)
fac1=[1]
fac2=[1]
C1=C-1
C2=C+1
for i in range(N):
    fac1.append(fac1[-1]*2%C1)
    fac2.append(fac2[-1]*2%C2)

for i in range(N):

    _C=C+(1 if X[i]=="0"  else -1 )
    if _C==0:
        print(0)
        continue
    if  X[i]=="0":
        lstidx=1
    else:
        lstidx=0

    idx=(N-1-i)

    value=lst[lstidx]+(fac2[idx] if  X[i]=="0" else fac1[idx])
    #print(lst[lstidx],value,_C)
    count=lstcount[lstidx]-1
    while value:
        count+=1
        value%=_C
        _C=0
        bit=value
        while bit:
            _C+=bit&1
            bit>>=1
    print(max(count,1))

Submission status: Runtime Error

Solution code:
def popcount(u):
    t = bin(u)
    h = t.count("1")
    return u % h 

n = int(input())
x = list(input())
c = x.count("1") + 1
d = c - 2

amaric = [1 % c]
amarid = [1 % d]
for i in range(n-1):
    amaric.append((amaric[-1]*2)%c)
    amarid.append((amarid[-1]*2)%d)

motoc = 0
motod = 0
for i in range(n):
    if x[i] == "1":
        motoc += amaric[n-1-i]
        motod += amarid[n-1-i]

for i in range(n):
    if x[i] == "0":
        op = motoc
        op += amaric[n-1-i]
        op %= c
    elif x[i] == "1":
        op = motod
        op -= amarid[n-1-i]
        op %= d
    cou = 1
    while True:
        if op == 0:
            break
        op = popcount(op)
        cou += 1
    print(cou)

Submission status: Runtime Error

Solution code:
from functools import lru_cache


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


@lru_cache(maxsize=None)
def rec(n):
    if n == 0:
        return 0
    else:
        return rec(n % popcnt(n)) + 1


n = int(input())
arr = input()

cnt = popcnt(int(arr, 2))
init_big = int(arr, 2) % (cnt + 1)
if cnt == 1:
    init_small = 0
else:
    init_small = int(arr, 2) % (cnt - 1)

li = []
for i in range(n):
    if arr[i] == "0":
        li.append((init_big + (1 << (n - i - 1))) % (cnt + 1))
    else:
        li.append((init_small - (1 << (n - i - 1))) % (cnt - 1))


ans = []

for x in li:
    ans.append(rec(x) + 1)

for i in range(n):
    x = arr[:i] + str(1 ^ int(arr[i])) + arr[i + 1:]
    if int(x, 2) == 0:
        ans[i] = 0

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

Submission status: Runtime Error

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

def f(n):
    t = int(n,2) % list(n).count('1')
    if t == 0:
        return 1
    else:
        return f(str(bin(t))) + 1

for i in range(n):
    xb = list(x)
    xb[i] = '0' if xb[i] == '1' else '1'
    print(f(''.join(xb)))

Submission status: Runtime Error

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

n = int(input())
x = input()
z = '1' * n
o = '0' * n
X = int(x, 2)

if (z == x):
  u = n - 1
  d = n - 1
elif (o == x):
  u = 1
  d = 1
else:
  tmp = len(list(filter(lambda x: x == '1', x)))
  u = tmp + 1
  d = tmp - 1


def popcount(i):
  return i % len(list(filter(lambda x: x == '1', format(i, 'b'))))


def solve(i, count):
  if (i <= 2 * 10**5 and ans[i] != 0):
    return count + ans[i]
  elif (i == 0):
    return count
  else:
    return solve(popcount(i), count + 1)


def solve2(i, div):
  if (i <= 2 * 10**5):
    return ans[i]
  else:
    return ans[i % div] + 1


ans = [0] * (2 * 10 ** 5 + 4)
_u = (2 * 10 ** 5) // u
U = X % u + (u * _u) + u
_d = (2 * 10 ** 5) // d
D = X % d + (d * _d) * 2 + d * 2
Us = [0] * (2 * 10 ** 5)
Ds = [0] * (2 * 10 ** 5)
for i in range(1, 2 * 10 ** 5 + 4):
  ans[i] = solve(i, 0)
  
Us[0] = 1 % u
if(d != 0):
  Ds[0] = 1 % d
for i in range(1, 2 * 10 ** 5):
  Us[i] = (Us[i - 1] * 2) % u
  if(d != 0):
    Ds[i] = (Ds[i-1] * 2) % d

for i in range(n):
  if(x[i] == '0'):
    print(solve2(U + Us[n-i-1], u))
  else:
    if (d == 0):
      print(0)
    else:
      print(solve2(D - Ds[n-i-1], d))

Submission status: Runtime Error

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()


N=int(input())
X=input()
C=X.count("1")

lst=[]
lstcount=[]
for x in [C-1,C+1]:
    flg=0
    if C<=0:
        lst.append(0)
        lstcount.append(0)
    else:
        Z=0
        p=1
        for i in range(N):
            if X[-i-1]=="1":
                Z+=p
            p*=2
            if Z>=x:
                Z%=x
                flg=1
            if flg:
                p%=x
        lst.append(Z)
        lstcount.append(flg)

#print(lst)
fac1=[1]
fac2=[1]
C1=C-1
C2=C+1
for i in range(N):
    fac1.append(fac1[-1]*2%C1)
    fac2.append(fac2[-1]*2%C2)

for i in range(N):

    _C=C+(1 if X[i]=="0"  else -1 )
    if _C==0:
        print(0)
        continue
    if  X[i]=="0":
        lstidx=1
    else:
        lstidx=0

    idx=(N-1-i)

    value=lst[lstidx]+(fac2[idx] if  X[i]=="0" else fac1[idx])
    #print(lst[lstidx],value,_C)
    count=lstcount[lstidx]-1
    while value:
        count+=1
        value%=_C
        _C=0
        bit=value
        while bit:
            _C+=bit&1
            bit>>=1
    print(count)

Submission status: Runtime Error

Solution code:

N=int(input())
x=input()

def popcount(X,ones,count): 
 
    if ones==0:
        return count
    else:
      
        X=X%ones
        
        count+=1
 
        ones=str(bin(X)).count("1")
        
        return popcount(X,ones,count)
 
GroundOnes=x.count("1")
GroundX=int(x,2)

CaseOne= GroundX%(GroundOnes-1)
CaseZero= GroundX%(GroundOnes+1)
 
for i in range(N):
    
    #CaseOne
    if x[i]=="1":
        ones=GroundOnes-1
        X=CaseOne-(2**(N-i-1))%ones
        
    #CaseZero
    else:
        ones=GroundOnes+1
        X=CaseZero+(2**(N-i-1))%ones
            
 
    # print("for loop",i)
    # print("ones",ones)
    # print("new2bit",new2bit)
    # print(" ------ return --- ",popcount(X,ones,0))
    print(popcount(X,ones,0))

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
B = str(input())

B_array = np.array(list(map(int, list(B))))
B_1 = B_array.sum()
mod_list_m1 = []
mod_list = []
mod_list_p1 = []
for i in range(N):
    mod_list.append((2**i) % (B_1))
    mod_list_m1.append((2**i) % (B_1-1))
    mod_list_p1.append((2**i) % (B_1+1))
mod_list = np.array(mod_list)[::-1]
mod_list_m1 = np.array(mod_list_m1)[::-1]
mod_list_p1 = np.array(mod_list_p1)[::-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)

for i in range(N):
    Z_array = B_array.copy()
    Z_array[i] = 1 if B_array[i] == 0 else 0
    if Z_array.sum() == 0:
        print(1)
        continue
    mod = Z_array.dot(mod_list_p1) % (B_1+1) if B_array[i] == 0 else Z_array.dot(mod_list_m1) % (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 = str(input())

B_array = np.array(list(map(int, list(B))))
B_1 = B_array.sum()
mod_list_m1 = []
mod_list = []
mod_list_p1 = []
for i in range(N):
    mod_list.append((2**i) % (B_1))
    mod_list_m1.append((2**i) % (B_1-1))
    mod_list_p1.append((2**i) % (B_1+1))
mod_list = np.array(mod_list)[::-1]
mod_list_m1 = np.array(mod_list_m1)[::-1]
mod_list_p1 = np.array(mod_list_p1)[::-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)

for i in range(N):
    Z_array = B_array.copy()
    Z_array[i] = 1 if B_array[i] == 0 else 0
    if Z_array.sum() == 0:
        print(1)
        continue
    mod = Z_array.dot(mod_list_p1) % (B_1+1) if B_array[i] == 0 else Z_array.dot(mod_list_m1) % (B_1-1)
    iter = 1
    if mod == 0:
        print(iter)
    else:
        print(calc_small(mod, iter))

Submission status: Runtime Error

Solution code:
LIM=200004
L=[0]*LIM

def bin_sum(Y):
    S=bin(Y)[2:]
    count=0
    for i in range(len(S)):
        count+=int(S[i])
    return count

def bin_sum2(Y):
    count=0
    for i in range(len(Y)):
        count+=int(Y[i])
    return count

for i in range(1,LIM):
    L[i]+=bin_sum(i)

def pop_num(N,b,L):
    if N==0:
        return 0
    v=N%b
    return pop_num(v,L[v],L)+1
    
M=[0]*200005
for i in range(1,200004):
    M[i]+=pop_num(i,L[i],L)
X=int(input())
Y=input()
d=bin_sum2(Y)
e=int(Y,2)%(d+1)
f=int(Y,2)%max(1,(d-1))
for i in range(X):
    if Y[i]=="0":
        b=d+1
        g=(e+2**(X-1-i))%d
    else:
        b=max(d-1,1)
        g=(f-2**(X-1-i)%b+b)%b
    if d==1:
        print(0)
    elif g==0:
        print(1)
    else:
        print(M[g]+1)

Submission status: Runtime Error

Solution code:
n = int(input())
x = list(input())
x=[1 if s=='1' else 0 for s in x]
sumx=sum(x)

neg=0
pos=0

for i in range(n):
    neg+=pow(2,(n-i-1),sumx-1)*x[i]
    neg%=sumx-1
    pos+=pow(2,(n-i-1),sumx+1)*x[i]
    pos%=sumx+1

pops=[]

for i in range(n):
    if x[i]==1:
        if sumx==1:
            pops.append(-1)
        else:
            pops.append((neg-pow(2,(n-i-1),sumx-1)+sumx-1)%(sumx-1))
    elif x[i]==0:
        pops.append((pos+pow(2,(n-i-1),sumx+1))%(sumx+1))

ans=[0]*(2*10**5+1)

for i in range(1,2*10**5+1):
    cnt=0
    tmp=i+0
    while tmp>0:
        cnt+=1
        b=bin(tmp)[2:]
        b=sum([1 if s=='1' else 0 for s in b])
        tmp%=b
    ans[i]=cnt

for p in pops:
    if p!=-1:
        print(ans[p]+1)
    else:
        print(0)

Submission status: Runtime Error

Solution code:
N = 23
B = "00110111001011011001110"

B_array = np.array(list(map(int, list(B))))
B_1 = B_array.sum()
mod_list_m1 = []
mod_list = []
mod_list_p1 = []
for i in range(N):
    mod_list.append((2**i) % (B_1))
    mod_list_m1.append((2**i) % (B_1-1))
    mod_list_p1.append((2**i) % (B_1+1))
mod_list = np.array(mod_list)[::-1]
mod_list_m1 = np.array(mod_list_m1)[::-1]
mod_list_p1 = np.array(mod_list_p1)[::-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)

for i in range(N):
    Z_array = B_array.copy()
    Z_array[i] = 1 if B_array[i] == 0 else 0
    if Z_array.sum() == 0:
        print(1)
        continue
    mod = Z_array.dot(mod_list_p1) % (B_1+1) if B_array[i] == 0 else Z_array.dot(mod_list_m1) % (B_1-1)
    iter = 1
    if mod == 0:
        print(iter)
    else:
        print(calc_small(mod, iter))

Submission status: Runtime Error

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

n = int(input())
x = input()
z = '1' * n
o = '0' * n
X = int(x, 2)

if (z == x):
  u = n - 1
  d = n - 1
elif (o == x):
  u = 1
  d = 1
else:
  tmp = len(list(filter(lambda x: x == '1', x)))
  u = tmp + 1
  d = tmp - 1


def popcount(i):
  return i % len(list(filter(lambda x: x == '1', format(i, 'b'))))


def solve(i, count):
  if (i <= 2 * 10**5 and ans[i] != 0):
    return count + ans[i]
  elif (i == 0):
    return count
  else:
    return solve(popcount(i), count + 1)


def solve2(i, div):
  if (i <= 2 * 10**5):
    return ans[i]
  else:
    return ans[i % div] + 1


ans = [0] * (2 * 10 ** 5 + 4)
_u = (2 * 10 ** 5) // u
U = X % u + (u * _u) + u
_d = (2 * 10 ** 5) // d
D = X % d + (d * _d) * 2 + d * 2
Us = [0] * (2 * 10 ** 5)
Ds = [0] * (2 * 10 ** 5)
for i in range(1, 2 * 10 ** 5 + 4):
  ans[i] = solve(i, 0)
  
Us[0] = 1 % u
Ds[0] = 1 % d
for i in range(1, 2 * 10 ** 5):
  Us[i] = (Us[i-1] * 2) % u
  Ds[i] = (Ds[i-1] * 2) % d

Submission status: Runtime Error

Solution code:
from functools import lru_cache


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


@lru_cache(maxsize=None)
def rec(n):
    if n == 0:
        return 0
    else:
        return rec(n % popcnt(n)) + 1


n = int(input())
arr = input()

cnt = popcnt(int(arr, 2))
init_big = int(arr, 2) % (cnt + 1)
init_small = int(arr, 2) % (cnt - 1)

li = []
for i in range(n):
    if arr[i] == "0":
        li.append((init_big + (1 << (n - i - 1))) % (cnt + 1))
    else:
        li.append((init_small - (1 << (n - i - 1))) % (cnt - 1))


ans = []

for x in li:
    ans.append(rec(x) + 1)

if int(arr, 2) == 1:
    ans[-1] = 0

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

Submission status: Runtime Error

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

n = int(input())
x = input()
z = '1' * n
o = '0' * n
X = int(x, 2)

if (z == x):
  u = n - 1
  d = n - 1
elif (o == x):
  u = 1
  d = 1
else:
  tmp = len(list(filter(lambda x: x == '1', x)))
  u = tmp + 1
  d = tmp - 1


def popcount(i):
  return i % len(list(filter(lambda x: x == '1', format(i, 'b'))))


def solve(i, count):
  if (i <= 2 * 10**5 and ans[i] != 0):
    return count + ans[i]
  elif (i == 0):
    return count
  else:
    return solve(popcount(i), count + 1)


def solve2(i, div):
  if (i <= 2 * 10**5):
    return ans[i]
  else:
    return ans[i % div] + 1


ans = [0] * (2 * 10 ** 5 + 4)
_u = (2 * 10 ** 5) // u
U = X % u + (u * _u) + u
_d = (2 * 10 ** 5) // d
D = X % d + (d * _d) * 2 + d * 2
Us = [0] * (2 * 10 ** 5 + 4)
Ds = [0] * (2 * 10 ** 5 + 4)
for i in range(1, 2 * 10 ** 5 + 4):
  ans[i] = solve(i, 0)
  
Us[0] = 1 % u
Ds[0] = 1 % d
for i in range(1, 2 * 10 ** 5 + 4):
  Us[i] = (Us[i-1] * 2) % u
  Ds[i] = (Ds[i-1] * 2) % d

for i in range(n):
  if(x[i] == '0'):
    print(solve2(U + Us[n-i-1], u))
  else:
    if (d == 0):
      print(0)
    else:
      print(solve2(D - Ds[n-i-1], d))

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
B = str(input())
B_array = np.array(list(map(int, list(B))))
B_1 = B_array.sum()
mod_list_m1 = []
mod_list = []
mod_list_p1 = []
for i in range(N):
    mod_list.append((2**i) % (B_1))
    mod_list_m1.append((2**i) % (B_1-1))
    mod_list_p1.append((2**i) % (B_1+1))
mod_list = np.array(mod_list)[::-1]
mod_list_m1 = np.array(mod_list_m1)[::-1]
mod_list_p1 = np.array(mod_list_p1)[::-1]

def calc_small(n, iter):
    
    iter += 1
    mod = n % np.array(list(map(int, list(bin(n)[2:])))).sum()
    if mod == 0:
        return iter
    else:
        return calc_small(mod, iter)

for i in range(N):
    Z_array = B_array.copy()
    Z_array[i] = 1 if B_array[i] == 0 else 0
    if Z_array.sum() == 0:
        print(1)
        continue
    mod = Z_array.dot(mod_list_p1) % (B_1+1) if B_array[i] == 0 else Z_array.dot(mod_list_m1) % (B_1-1)
    iter = 1
    if mod == 0:
        print(iter)
    else:
        print(calc_small(mod, iter))

Submission status: Runtime Error

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

n = int(input())
x = input()
z = '1' * n
o = '0' * n
X = int(x, 2)

if (z == x):
  u = n - 1
  d = n - 1
elif (o == x):
  u = 1
  d = 1
else:
  tmp = len(list(filter(lambda x: x == '1', x)))
  u = tmp + 1
  d = tmp - 1


def popcount(i):
  return i % len(list(filter(lambda x: x == '1', format(i, 'b'))))


def solve(i, count):
  if (i <= 2 * 10**5 and ans[i] != 0):
    return count + ans[i]
  elif (i == 0):
    return count
  else:
    return solve(popcount(i), count + 1)


def solve2(i, div):
  if (i <= 2 * 10**5):
    return ans[i]
  else:
    return ans[i % div] + 1


ans = [0] * (2 * 10 ** 5 + 4)
_u = (2 * 10 ** 5) // u
U = X % u + (u * _u) + u
_d = (2 * 10 ** 5) // d
D = X % d + (d * _d) * 2 + d * 2
Us = [0] * (2 * 10 ** 5)
Ds = [0] * (2 * 10 ** 5)
for i in range(1, 2 * 10 ** 5 + 4):
  ans[i] = solve(i, 0)
  
Us[0] = 1 % u
Ds[0] = 1 % d
for i in range(1, 2 * 10 ** 5 + 4):
  Us[i] = (Us[i-1] * 2) % u
  Ds[i] = (Ds[i-1] * 2) % d

for i in range(n):
  if(x[i] == '0'):
    print(solve2(U + Us[n-i-1], u))
  else:
    if (d == 0):
      print(0)
    else:
      print(solve2(D - Ds[n-i-1], d))

Submission status: Runtime Error

Solution code:
N = int(input())
B = str(input())
B_array = np.array(list(map(int, list(B))))
B_1 = B_array.sum()
mod_list_m1 = []
mod_list = []
mod_list_p1 = []
for i in range(N):
    mod_list.append((2**i) % (B_1))
    mod_list_m1.append((2**i) % (B_1-1))
    mod_list_p1.append((2**i) % (B_1+1))
mod_list = np.array(mod_list)[::-1]
mod_list_m1 = np.array(mod_list_m1)[::-1]
mod_list_p1 = np.array(mod_list_p1)[::-1]

def calc_small(n, iter):
    
    iter += 1
    mod = n % np.array(list(map(int, list(bin(n)[2:])))).sum()
    if mod == 0:
        return iter
    else:
        return calc_small(mod, iter)

for i in range(N):
    Z_array = B_array.copy()
    Z_array[i] = 1 if B_array[i] == 0 else 0
    if Z_array.sum() == 0:
        print(1)
        continue
    mod = Z_array.dot(mod_list_p1) % (B_1+1) if B_array[i] == 0 else Z_array.dot(mod_list_m1) % (B_1-1)
    iter = 1
    if mod == 0:
        print(iter)
    else:
        print(calc_small(mod, iter))

Submission status: Runtime Error

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

n = int(input())
x = input()
z = '1' * n
o = '0' * n
X = int(x, 2)

if (z == x):
  u = n - 1
  d = n - 1
elif (o == x):
  u = 1
  d = 1
else:
  tmp = len(list(filter(lambda x: x == '1', x)))
  u = tmp + 1
  d = tmp - 1


def popcount(i):
  return i % len(list(filter(lambda x: x == '1', format(i, 'b'))))


def solve(i, count):
  if (i <= 2 * 10**5 and ans[i] != 0):
    return count + ans[i]
  elif (i == 0):
    return count
  else:
    return solve(popcount(i), count + 1)


def solve2(i, div):
  if (i <= 2 * 10**5):
    return ans[i]
  else:
    return ans[i % div] + 1


ans = [0] * (2 * 10 ** 5 + 4)
_u = (2 * 10 ** 5) // u
U = X % u + (u * _u) + u
_d = (2 * 10 ** 5) // d
D = X % d + (d * _d) * 2 + d * 2
Us = [0] * (2 * 10 ** 5)
Ds = [0] * (2 * 10 ** 5)
for i in range(1, 2 * 10 ** 5 + 4):
  ans[i] = solve(i, 0)
  
Us[0] = 1 % u
Ds[0] = 1 % d
for i in range(1, 2 * 10 ** 5):
  Us[i] = (Us[i-1] * 2) % u
  Ds[i] = (Ds[i-1] * 2) % d

for i in range(n):
  if(x[i] == '0'):
    print(solve2(U + Us[n-i-1], u))
  else:
    if (d == 0):
      print(0)
    else:
      print(solve2(D - Ds[n-i-1], d))

Submission status: Runtime Error

Solution code:
LIM=200004
L=[0]*LIM

def bin_sum(Y):
    S=bin(Y)[2:]
    count=0
    for i in range(len(S)):
        count+=int(S[i])
    return count

def bin_sum2(Y):
    count=0
    for i in range(len(Y)):
        count+=int(Y[i])
    return count

for i in range(1,LIM):
    L[i]+=bin_sum(i)

def pop_num(N,b,L):
    if N==0:
        return 0
    v=N%b
    return pop_num(v,L[v],L)+1
    
M=[0]*200005
for i in range(1,200004):
    M[i]+=pop_num(i,L[i],L)
X=int(input())
Y=input()
d=bin_sum2(Y)+1
c=bin_sum2(Y)-1
e=int(Y,2)%d
f=int(Y,2)%c
for i in range(X):
    if Y[i]=="0":
        b=d
        g=(e+2**(X-1-i))%d
    else:
        b=c
        g=(f-2**(X-1-i)%c+c)%c
    if d==1:
        print(0)
    elif g==0:
        print(1)
    else:
        print(M[g]+1)