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())

def popcount(n):
    bin_n = bin(n)[2:]
    count = 0
    for i in bin_n:
        count += int(i)
    return count

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

lst = [0 for i in range(n+1)]
for i in range(1, n+1):
    num = i%popcount(i)
    lst[i] = lst[num] + 1

plus = [0 for i in range(n)]
minus = [0 for i in range(n)]
plus[0] = 1
minus[0] = 1
for i in range(1, n):
    plus[i] = (plus[i-1]*2) % (cnt+1)
    minus[i] = (minus[i-1]*2) % (cnt-1)

origin = int(''.join(x), base=2)
amariplus = origin % (cnt+1)
amariminus = origin % (cnt-1)

for i in range(n):
    if x[i] == '0':
        amari = (amariplus + plus[n-i-1]) % (cnt+1)
        print(lst[amari] + 1)
    else:
        amari = (amariminus - minus[n-i-1]) % (cnt-1)
        print(lst[amari] + 1)

Submission status: Runtime Error

Solution code:
import sys
import math
import statistics
import itertools
from collections import deque
n=int(input())
x=str(input())
ans_lis =[0]*10000000

def p(s):
    ans=0
    for i in range(int(math.sqrt(s))+1):
        if s>>i&1:
            ans+=1
    return ans
def o(d):
    i=0
    while d!=0:
        i+=1
        q=p(d)
        d%=q
    return i

lis=[]
for i in range(n):
    num=x[i]
    lis.append(num)



lisss=lis
for g in range(n):
    
    if lisss[g]=='0':
        lisss[g]='1'
    
    else:
        lisss[g]='0'
    ans=0
   
    for j in range(n):
        if lisss[j]=='1':
            jj=int(j)
            ans+=2**(n-jj-1)
    print(o(ans))
    if lisss[g]=='0':
        lisss[g]='1'
    
    else:
        lisss[g]='0'

Submission status: Runtime Error

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():
    N = in_n()
    X = in_s()
    nx = int(X, 2)

    ans = [0] * N

    oc = X.count('1')
    mx = nx % (oc - 1)
    px = nx % (oc + 1)

    print(oc, px, mx)

    tn = 1 << N - 1
    for i in range(N):

        if X[i] == '0':
            a = (px + tn % (oc + 1)) % (oc + 1)
        else:
            a = (mx - tn % (oc - 1)) % (oc - 1)

        count = 1
        while a:
            a = a % bin(a).count('1')
            count += 1

        ans[i] = count
        tn = tn >> 1

    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()

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 + 1

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)))

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    X = input()
    MOD = sum(map(lambda x: x == '1',X))
    lowNumber = []
    for i in range(MOD):
        anscur = i
        cnt = 1
        while anscur != 0:
            oneCount = bin(x).count('1')
            anscur %= oneCount
            cnt += 1
        lowNumber.append(cnt)
    if MOD == 0:
        print("1" + "\n1" * (N-1))
        return 0
    if MOD == 1 and X[-1] == '1':
        print("2\n" * (N-1) + "0")
        return 0
    if MOD == 1 and X[-1] == '0':
        ans = ''
        for i in range(N):
            if X[i] == '1':
                ans += '0'
            elif i != N-1:
                ans += '1'
            else:
                ans += '2'
            if i != N-1:
                ans += '\n'
        print(ans)
        return 0
    MODP1 = MOD + 1
    MODM1 = MOD - 1
    POWEROFTWOP1 = [0] * 200001
    POWEROFTWOM1 = [0] * 200001
    POWEROFTWOP1[0] = 1
    POWEROFTWOM1[0] = 1
    for i in range(1,N):
        POWEROFTWOP1[i] = (POWEROFTWOP1[i-1] * 2) % MODP1
        POWEROFTWOM1[i] = (POWEROFTWOM1[i-1] * 2) % MODM1
    xMODP1 = 0
    xMODM1 = 0
    for i in range(N):
        if X[i] == '1':
            xMODP1 += POWEROFTWOP1[N - i - 1]
            xMODP1 %= MODP1
            xMODM1 += POWEROFTWOM1[N - i - 1]
            xMODM1 %= MODM1
    ans = ""
    for i in range(N):
        if X[i] == '0':
            anscur = xMODP1
            anscur += POWEROFTWOP1[N - i - 1]
            anscur %= MODP1
        if X[i] == '1':
            anscur = xMODM1
            anscur -= POWEROFTWOM1[N - i - 1]
            anscur %= MODM1
        ans += str(lowNumber[anscur])
        if i != N-1:
            ans += '\n'
    print(ans)
                    
main()

Submission status: Runtime Error

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
X = input()
def popcount(n):
    cnt = 0
    while n:
        n %= "{:b}".format(n).count("1")
        cnt += 1
    return cnt

pl = [0]*(N+1)
for i in range(N+1):
    pl[i] = popcount(i)
bn = X.count("1")

modp = [0]*N
modm = [0]*N

for i in range(N):
    if X[i] == "1":
        modp[i] = pow(2, N-1-i, bn+1)
        modm[i] = pow(2, N-1-i, bn-1)

sp = sum(modp)
sm = sum(modm)
ans = [0]*N
for i in range(N):
    if X[i] == "1":
        if bn == 1:
            ans[i] = 0
            continue
        s = sm
        s -= modm[i]
        s %= bn-1
        ans[i] = pl[s]+1
    else:
        s = sp
        s += pow(2, N-1-i, bn+1)
        s %= bn+1
        ans[i] = pl[s]+1

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

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())
orig=0
for i in range(n):
    if lis[i]=="0":
        lis[i]=0
    else:
        lis[i]=1
orcount=sum(lis)
m1=0
m3=0
if orcount==1:
    for i in range(n):
        if lis[i]==1:
            m3=(m3+pow(2,n-i-1,orcount+1))
elif orcount>1:
    for i in range(n):
        if lis[i]==1:
            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
        if pr!=0:
            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:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
X = input()
def popcount(n):
    cnt = 0
    while n:
        n %= "{:b}".format(n).count("1")
        cnt += 1
    return cnt

pl = [0]*(N+1)
for i in range(N+1):
    pl[i] = popcount(i)
bn = X.count("1")

modp = [0]*N
modm = [0]*N

for i in range(N):
    if X[i] == "1":
        modp[i] = pow(2, N-1-i, bn+1)
        modm[i] = pow(2, N-1-i, bn-1)

sp = sum(modp)
sm = sum(modm)
ans = [0]*N
for i in range(N):
    if X[i] == "1":
        if bn == 1:
            ans[i] = 0
            continue
        s = sp
        s -= modm[i]
        s %= bn-1
        ans[i] = pl[s]+1
    else:
        s = sm
        s += pow(2, N-1-i, bn+1)
        s %= bn+1
        ans[i] = pl[s]+1

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

Submission status: Runtime Error

Solution code:
import itertools
import sys
import numba
from numba import njit
i8 = numba.int64
input = sys.stdin.readline


@njit((i8, ), cache=True)
def f(A):
    ans = 0
    n = int(A, 2)
    while n != 0:
        pc = bin(n).count('1')
        n = n % pc
        ans += 1
    return ans


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

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

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    X = input()
    MOD = sum(map(lambda x: x == '1',X))
    lowNumber = []
    for i in range(MOD):
        anscur = i
        cnt = 1
        while anscur != 0:
            ans2 = bin(anscur)[2:]
            oneCount = sum(map(lambda x: x == '1',ans2))
            anscur %= oneCount
            cnt += 1
        lowNumber.append(cnt)
    if MOD == 0:
        print("1" + "\n1" * (N-1))
        return 0
    if MOD == 1 and X[-1] == '1':
        print("2\n" * (N-1) + "0")
        return 0
    if MOD == 1 and X[-1] == '0':
        ans = ''
        for i in range(N):
            if X[i] == '1':
                ans += '0'
            elif i != N-1:
                ans += '1'
            else:
                ans += '2'
            if i != N-1:
                ans += '\n'
        print(ans)
        return 0
    MODP1 = MOD + 1
    MODM1 = MOD - 1
    POWEROFTWOP1 = [0] * 200001
    POWEROFTWOM1 = [0] * 200001
    POWEROFTWOP1[0] = 1
    POWEROFTWOM1[0] = 1
    for i in range(1,N):
        POWEROFTWOP1[i] = (POWEROFTWOP1[i-1] * 2) % MODP1
        POWEROFTWOM1[i] = (POWEROFTWOM1[i-1] * 2) % MODM1
    xMODP1 = 0
    xMODM1 = 0
    for i in range(N):
        if X[i] == '1':
            xMODP1 += POWEROFTWOP1[N - i - 1]
            xMODP1 %= MODP1
            xMODM1 += POWEROFTWOM1[N - i - 1]
            xMODM1 %= MODM1
    ans = ""
    for i in range(N):
        if X[i] == '0':
            anscur = xMODP1
            anscur += POWEROFTWOP1[N - i - 1]
            anscur %= MODP1
        if X[i] == '1':
            anscur = xMODM1
            anscur -= POWEROFTWOM1[N - i - 1]
            anscur %= MODM1
        ans += str(lowNumber[anscur])
        if i != N-1:
            ans += '\n'
    print(ans)
                    
main()

Submission status: Runtime Error

Solution code:

def cal_cnt(num):
  cnt = 0
  for bit in format(num, 'b'):
    if bit == '1':
      cnt += 1

  return cnt


def main():
  n = int(input())
  src = input()
  base = int(src, 2)
  base_cnt = 0
  for bit in src:
    if bit == '1':
      base_cnt += 1

  basep = base % (base_cnt + 1)
  basem = base % (base_cnt - 1)

  memo = tuple(map(cal_cnt, range(n)))

  dp = [None] * n
  dp[0] = 0

  def f(num, cnt):
    if num < n and dp[num] is not None:
      return dp[num]

    nxt = num % cnt
    res = 1 + f(nxt, memo[nxt])
    if num < n:
      dp[num] = res

    return res


  for i in range(n - 1, -1, -1):
    num = None

    if src[n - i - 1] == '0':
      mod = base_cnt + 1
      num = ((basep + pow(2, i, mod)) % mod)
    else:
      mod = base_cnt - 1
      num = ((basem - pow(2, i, mod)) % mod)

    print(1 + f(num, memo[num]))


main()

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())
orig=0
for i in range(n):
    if lis[i]=="0":
        lis[i]=0
    else:
        lis[i]=1
orcount=sum(lis)
m1=0
m3=0
if orcount==1:
    for i in range(n):
        if lis[i]==1:
            m3=(m3+pow(2,n-i-1,orcount+1))
elif orcount>1:
    for i in range(n):
        if lis[i]==1:
            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:
n = int(input())
x = input()

outf = {}
res = []

dec_d = {}
def get_dec(bin):
  if bin in dec_d.items():
    return dec_d[bin]
  s = 0
  seed = 2 ** (len(bin)-1)
  for el in bin:
    if el == '1':
      s += seed
    seed = seed // 2
  dec_d[bin] = s
  return s

bin_d = {}
def get_bin(dec):
  if dec in bin_d.items():
    return bin_d[dec]
  s = ''
  while dec > 0:
    if dec % 2 == 1:
      s = s + '1'
    else:
      s = s + '0'
    dec = dec // 2
  bin_d[dec] = s
  return s

pop_d = {}
def popcount(n):
  if n in pop_d.items():
    return pop_d[n]
  out = 0
  while n > 0:
    if n % 2 == 1:
      out += 1
    n = n // 2
  pop_d[n] = out
  return out

init_pop_cnt = popcount(get_dec(x))

for i in range(n):
  if x[i] == '0':
    lx = x[:i] + '1' + x[i+1:]
    ip = init_pop_cnt + 1
  else:
    lx = x[:i] + '0' + x[i+1:]
    ip = init_pop_cnt - 1
  x_dec = get_dec(lx)
  res.append(x_dec)

  kp = []
  f = 0

  # calc first op
  kp.append(x_dec)
  f += 1
  x_dec = x_dec % ip

  # calc f
  while x_dec > 0:
    st = get_bin(x_dec)
    if st in outf.items():
      f += outf[st]
      break
    kp.append(x_dec)
    f += 1
    pc = popcount(x_dec)
    x_dec = x_dec % pc

  # keep
  lf = f
  for k in kp:
    st = get_bin(k)
    outf[st] = lf
    lf -= 1


for i in res:
  st = get_bin(i)
  print(outf[st])

Submission status: Runtime Error

Solution code:
N = int(input())
X = list(input())
anslist = []

def popcount(n):
  X = list(bin(n)[2:])
  Xdict = {0:0, 1:0}
  for i in X:
    if i == '0':
      Xdict[0] += 1
    else:
      Xdict[1] += 1
  return Xdict[1]

def f(n):
  flg = True
  count = 1
  _popcount = popcount(n)
  while flg:
    if n % _popcount == 0:
      flg = False
    else:
      n = n % _popcount
      _popcount = popcount(n)
      count += 1
  return count
      
for i in range(N):
  Xtmp = X.copy()
  if Xtmp[i] == '0':
    Xtmp[i] = '1'
  else:
    Xtmp[i] = '0'
  Xi = ''.join(Xtmp)   
  Xi = int(Xi, 2)
  anslist.append(f(Xi))

for num in anslist:
  print(num)

Submission status: Runtime Error

Solution code:
def set_bit(n):
    count = 0
    for i in str(n):
        if i == '1':
            count += 1
    return count

def bin_decimal(n):
    base1 = 1
    dec_val = 0
    l = len(n)
    for i in range(l-1,-1,-1):
        if(n[i] == '1'):
            dec_val += base1
        base1 *= 2
    return dec_val
    
def popcount(x,i):
    s = list(x)
    if s[i] == '0':
        s[i] = '1'
    else:
        s[i] = '0'
    t = "".join(s)
    
    count = 0
    ans = -1
    while(ans!=0):
        ans = bin_decimal(str(t))%set_bit(t)
        
        count += 1
        t = bin(ans).replace("0b", "")
    return count 
n = int(input())
x = input()

for i in range(n):
    print(popcount(x,i))

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    X = input()
    MOD = sum(map(lambda x: x == '1',X))
    for i in range(MOD):
        anscur = i
        cnt = 1
        while anscur != 0:
            ans2 = bin(anscur)[2:]
            oneCount = sum(map(lambda x: x == '1',ans2))
            anscur %= oneCount
            cnt += 1
        lowNumber.append(cnt)
    if MOD == 0:
        print("1" + "\n1" * (N-1))
        return 0
    if MOD == 1 and X[-1] == '1':
        print("2\n" * (N-1) + "0")
        return 0
    if MOD == 1 and X[-1] == '0':
        ans = ''
        for i in range(N):
            if X[i] == '1':
                ans += '0'
            elif i != N-1:
                ans += '1'
            else:
                ans += '2'
            if i != N-1:
                ans += '\n'
        print(ans)
        return 0
    MODP1 = MOD + 1
    MODM1 = MOD - 1
    POWEROFTWOP1 = [0] * 200001
    POWEROFTWOM1 = [0] * 200001
    POWEROFTWOP1[0] = 1
    POWEROFTWOM1[0] = 1
    for i in range(1,N):
        POWEROFTWOP1[i] = (POWEROFTWOP1[i-1] * 2) % MODP1
        POWEROFTWOM1[i] = (POWEROFTWOM1[i-1] * 2) % MODM1
    xMODP1 = 0
    xMODM1 = 0
    for i in range(N):
        if X[i] == '1':
            xMODP1 += POWEROFTWOP1[N - i - 1]
            xMODP1 %= MODP1
            xMODM1 += POWEROFTWOM1[N - i - 1]
            xMODM1 %= MODM1
    ans = ""
    for i in range(N):
        if X[i] == '0':
            anscur = xMODP1
            anscur += POWEROFTWOP1[N - i - 1]
            anscur %= MODP1
        if X[i] == '1':
            anscur = xMODM1
            anscur -= POWEROFTWOM1[N - i - 1]
            anscur %= MODM1
        ans += str(lowNumber[anscur])
        if i != N-1:
            ans += '\n'
    print(ans)
                    
main()

Submission status: Runtime Error

Solution code:
n = int(input())
q = input()
r = list(q)
ans=[]
for i in range(n):
    ans.append(0)
def k(x,n):
    ans = 0
    for i in range(n):
        if x&1:
            ans += 1
        x = x>>1
    return ans
x = int(q, 2)
y = k(x,n)
for i in range(n):
    an = 0
    if r[n-i-1]=='1':
        z = x-2**i
        if y-1 == 0:
            ans[i] = 0
        else:
            z = z%(y-1)
            while z:
                u = k(z,10)
                z = z%u
                an += 1
            ans[i] = an+1
    else:
        z = x + 2**i
        z = z%(y+1)
        while z:
            u = k(z,10)
            z = z%u
            an += 1
        ans[i] = an+1
ans.reverse()
for i in range(n):
    print(ans[i])

Submission status: Runtime Error

Solution code:
from functools import lru_cache
N=int(input())
X=int(input(),2)

def popcount(n):
    ret = 0
    while n > 0:
        ret += (n & 1)
        n >>= 1
    return ret

@lru_cache(maxsize = None)
def f(n):
    x = n % popcount(n)
    if x > 0:
        return 1+f(x)
    else:
        return 1

ans = []
for i in range(N):
    ans.append(f(X ^ (1<<i)))
for i in reversed(ans):
    print(i)

Submission status: Runtime Error

Solution code:
N = int(input())
X = list(map(int, input().split()))
anslist = []

def popcount(n):
  X = list(bin(n)[2:])
  Xdict = {0:0, 1:0}
  for i in X:
    if i == '0':
      Xdict[0] += 1
    else:
      Xdict[1] += 1
  return Xdict

def f(n):
  flg = True
  count = 1
  popcount = popcount(n)
  while flg:
    if n % popcount == 0:
      flg = False
    else:
      n = n % popcount
      popcount = popcount(n)
  return count
      
for i in range(N):
  if X[i] == 0:
    X[i] = 0
    ''.join(X)
  else:
    X[i] = 1
    ''.join(X)
  anslist.append(f(int(X)))

for num in anslist:
  print(num)

Submission status: Runtime Error

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
X = input()
def popcount(n):
    cnt = 0
    while n:
        n %= "{:b}".format(n).count("1")
        cnt += 1
    return cnt
pl = [0]*(N+1)
for i in range(N+1):
    pl[i] = popcount(i)
bn = X.count("1")

modp = [0]*N
modm = [0]*N

for i in range(N):
    if X[i] == "1":
        modp[i] = pow(2, N-1-i, bn+1)
        modm[i] = pow(2, N-1-i, bn-1)

ans = [0]*N
for i in range(N):
    if X[i] == "1":
        if bn == 1:
            ans[i] = 0
            continue
        s = sum(modm)
        s -= modm[i]
        s %= bn-1
        ans[i] = pl[s]+1
    else:
        s = sum(modp)
        s += pow(2, N-1-i, bn+1)
        s %= bn+1
        ans[i] = pl[s]+1

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

Submission status: Runtime Error

Solution code:
import sys
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(sys.stdin.readline())
def ria(): return list(map(int, sys.stdin.readline().split()))
def ws(s): sys.stdout.write(s); sys.stdout.write('\n')
def wi(n): sys.stdout.write(str(n)); sys.stdout.write('\n')
def wia(a, sep=' '): sys.stdout.write(sep.join([str(x) for x in a])); sys.stdout.write('\n')


def main():
    n = ri()
    x = rs()

    k = int(x, 2)
    d = x.count('1')
    if d > 0:
        k0 = k % (d-1)
    k1 = k % (d+1)

    f = [0] * (n + 1)
    for i in range(1, n+1):
        f[i] = f[i % bin(i).count('1')] + 1

    for i in range(n):
        if x[i] == '1':
            dd = d - 1
            if dd == 0:
                wi(0)
                continue
            wi(f[k0 - pow(2, n-i-1, dd)] + 1)
        else:
            dd = d + 1
            wi(f[k1 + pow(2, n - i - 1, dd)] + 1)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

def f(x):
    count = 0
    while x != 0:
        count += 1
        x %= popcount(x)
    return count

N = int(input())
X = "0b"+input()
intX = int(X, 2)
popcountX = X.count("1")

f_table = [f(N+1)] + [f(i+1) for i in range(N)]  # 1 回やれば絶対この中に入る

for i in range(1, N+1):
    if X[i+1] == "0":
        diff = pow(2, N-i)
        popcount = popcountX + 1
    else:
        diff = -pow(2, N-i)
        popcount = popcountX - 1
    res = (intX + diff) % popcount
    ans = f_table[res-1]
    print(ans)

Submission status: Runtime Error

Solution code:
import sys

def L(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI():return list(map(int,sys.stdin.readline().rstrip().split()))
def LS():return list(sys.stdin.readline().rstrip().split())


sys.setrecursionlimit(1000000)

def cnt_1_inv_at(index, X, orgCnt):
    _x = list(X[:])
    # print(_x)
    if _x[index] == '0':
        _x[index] = '1'
        return (_x, orgCnt + 1)
    else:
        _x[index] = '0'
        return (_x, orgCnt - 1)

def func(n, r, X):
    global _cnt

    _cnt += 1
    _r = n % r
    if _r == 0:
        return
    else:
        # print(_r)
        # print("bin:",bin(_r).replace('0b',''))
        pop = sum(1 if i =='1' else 0 for i in bin(_r).replace('0b','')[:])
        # print("pop=",pop)
        func(_r, pop, X)

def solver(N,X):
    global _cnt
    # print(N,X)
    org1Cnt = sum(1 if i =='1' else 0 for i in X[:])
    # print(org1Cnt)
    # print(cnt_1_inv_at(0,X,org1Cnt))

    for i in range(0,N):
        # print("i=",i)
        _cnt = 0
        (_x, cnt) = cnt_1_inv_at(i, X, org1Cnt)
        n = int("".join(_x),2)
        # print(_x, cnt, "".join(_x), n)

        func(n, cnt, _x)

        # print("Ans=",_cnt)
        print(_cnt)


def main():

    N = I()
    X = L()

    solver(N,X)

if __name__ == '__main__':
    main()

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)))

Submission status: Runtime Error

Solution code:
import copy
from functools import lru_cache
n = int(input())
x = list(input())

popcount = [-1]*(n+1)
popcount[0] = 0
for i in range(1, n+1):
    if popcount[i] == -1:
        i_bin = str(bin(i))
        i_bin_one = i_bin.count("1")
        next_idx = i % i_bin_one
        popcount[i] = popcount[next_idx] + 1

#print(popcount)

x_lis = []
for i in range(n):
    x_copy = copy.copy(x)
    if x[i] == "1":
        x_copy[i] = "0"
    else:
        x_copy[i] = "1"
    x_lis.append("".join(x_copy))

for xi in x_lis:
    xi_int = int(xi, 2)
    xi_one = xi.count("1")  # たかだかｎ
    nxi_idx = xi_int % xi_one  # たかだかｎで割るのであまりはｎ以下
    if nxi_idx > n:
        print(-1)
    else:
        print(popcount[nxi_idx] + 1)

Submission status: Runtime Error

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

def popcount(x):
    count = 0
    while x != 0:
        count += x&1
        x = x>>1
    return count


pv = []
for i in range(n):
    pv.append(popcount(i))

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

x = int(s, 2)
ans = []
for i in range(n):
    y =  x
    p = pcnt
    if (x >> i) & 1 == 1:
        p -= 1
        y -= 2**i
    else:
        y += 2**i
        p += 1
    count = 1
    y = y % p
    while y != 0:
        y = y % pv[y]
        count += 1

    ans.append(count)

for i in range(n):
    print(ans[n - 1 - i])

Submission status: Runtime Error

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

def f(x):
    count = 0
    while x != 0:
        count += 1
        x %= popcount(x)
    return count

N = int(input())
X = "0b"+input()
X10 = int(X, 2)
popcountX = X.count("1")

f_table = [f(N)] + [f(i+1) for i in range(N-1)]  # 1 回やれば絶対この中に入る

for i in range(1, N+1):
    if X[i+1] == "0":
        diff = pow(2, N-i)
        popcount = popcountX + 1
    else:
        diff = -pow(2, N-i)
        popcount = popcountX - 1
    res = (X10+ diff) % popcount
    ans = f_table[res-1]
    print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

def getInts():
    return [ int(x) for x in input().split() ]

def complement(c):
    if c=='1':
        return '0'
    else:
        return '1'

H = {}

P = {}
def pop(n):
    if n in P:
        return P[n]
    c = "{0:b}".format(n).count('1')
    P[n] = c
    return c

def toZero(n):
    if n==0:
        return 0
    if n==1:
        return 1
    if n in H:
        return H[n]
    r = 1 + toZero(n%pop(n))
    H[n] = r
    return r

[N] = getInts()
X = input()
X = list(X)
for i in range(N):
    X[i] = complement(X[i])
    print(X)
    n = int("".join(X),2)
    print(toZero(n))
    X[i] = complement(X[i])

Submission status: Runtime Error

Solution code:


n=int(input())

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

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

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
X = input()
#N = 2 * 100000
#X = "0" * N
def hanten(a,i):
    if a[i] == "0":
        return(a[:i] + "1"+ a[i+1:],1)
    else:
        return(a[:i] + "0"+ a[i+1:],-1)

#def hanten(num, n):
#    return num ^ (1 << n)
num = X.count("1")

for i in range(N):
    hantened ,t = hanten(X,i)
    hantened = int(hantened,2)
    hantened = hantened % (num + t)
    cnt = 1
    while (hantened > 0):
        hantened = hantened % bin(hantened).count("1")
        cnt += 1
    print(cnt)