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:
def resolve():
    #n=int(input())
    #a,b=map(int,input().split())
    #x=list(map(int,input().split()))
    #a=[list(map(lambda x:int(x)%2,input().split())) for _ in range(h)]

    def calc(x):#xは数字
        xn=x
        x=bin(x)[2:]
        cnt=sum(list(map(int,list(x))))
        if xn%cnt==0:
            return 1
        else:
            return calc(xn%cnt)+1
    
    n=int(input())    
    x=input()
    cnt=sum(list(map(int,list(x))))
    x=int(x,2)
    ans=[]
    for i in range(n):
        if x>>i&1:
            ans.append(calc(x-2**i))
        else:
            ans.append(calc(x+2**i))
    print(*ans[::-1],sep='\n')

if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

sys.setrecursionlimit(20000000)

def yn(b):
    print("Yes" if b==1 else "No")
    return

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

def resolve():
    readline=sys.stdin.readline

    n=int(readline())
    x=readline().rstrip()

    #pc=[0]*(10**5+1)
    #for i in range(1,10**5):
    #    pc[i]=count_ones_by_bin(i)
    amr1=[0]*((10**5)*2 + 5)
    amr2=[0]*((10**5)*2 + 5)
    bits=[False]*((10**5)*2 + 5)

    bcnt=0
    j=0
    for i in x:
        if int(i)==1:
            bcnt += 1
            bits[j]=True
        j+=1

    base1=0
    base2=0
    for i in range(n):
        jo=n-i-1
        amr1[i]=pow(2,jo,bcnt+1)
        amr2[i]=pow(2,jo,bcnt-1)
        if bits[i]==True:
            base1+=amr1[i]
            base2+=amr2[i]
    for i in range(n):
        ans=0
        if bits[i]==True: #1->0
            if (bcnt-1)==0:
                base=0
            else:
                base=(base2-amr2[i])%(bcnt-1)
        else:
            base=(base1+amr1[i])%(bcnt+1)
        ans+=1
        while base > 0:
            pp=count_ones_by_bin(base)
            base=base%pp
            ans+=1
        print(ans)
    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Runtime Error

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

counter = sum(list(map(int, x)))
number = int(''.join(x), 2)

def f(num, cnt):
    if num == 0:
        return cnt
    popcount = sum(list(map(int, format(num, 'b'))))
    return f(num % popcount, cnt+1)

for i in range(n):    
    if x[i] == '0':
        m = number + pow(2, n-i-1)
        print(f(m % (counter+1), 1))
    if x[i] == '1':
        m = number - pow(2, n-i-1)
        print(f(m % (counter-1), 1))

Submission status: Runtime Error

Solution code:
n=int(input())
x=int(input(),2)
A=[0]*(n+1)
A[1]=1
def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
 
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x = x + (x >> 8) 
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f
for i in range(2,n+1):
  k=popcount(i)
  A[i]=A[i%k]+1
for i in range(n):
  y= x^(1<<(n-1-i))
  p=popcount(y)
  if p==0:
    print(0)
  else:  
    print(A[y%(popcount(y))]+1)
n=int(input())
x=int(input(),2)
A=[0]*(n+1)
A[1]=1
def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x = x + (x >> 8) 
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f
for i in range(2,n+1):
  k=popcount(i)
  A[i]=A[i%k]+1
for i in range(n):
  y= x^(1<<(n-1-i))
  p=popcount(y)
  if p==0:
    print(0)
  else:  
    print(A[y%(popcount(y))]+1)

Submission status: Runtime Error

Solution code:
import copy

N = int(input())
G = list(input())

memo = {}


def count_one(num):
    if num in memo:
        return memo[num]
    else:
        v = bin(num)[2:].count('1')
        memo[num] = v
        return v


one_count = 0
for x in G:
    if x == '1':
        one_count += 1

for i in range(N):
    #print(' i : ' + str(i))
    ans = 0
    X = copy.deepcopy(G)
    tmp = one_count
    if X[i] == '1':
        X[i] = '0'
        tmp -= 1
    else:
        X[i] = '1'
        tmp += 1
    base_10 = int(''.join(X), 2)
    while True:
        base_10 %= tmp
        ans += 1
        if base_10 == 0:
            print(ans)
            break
        tmp = count_one(base_10)
        # print(tmp)

Submission status: Runtime Error

Solution code:
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n=int(input())
x=input()
m=int(x,2)
c=x.count("1")
l=[1]*(2*10**5+2)
for i in range(1,2*10**5+1):
    l[i]=l[i%str(bin(i)).count("1")]+1
deka=0
for i in range(n):
    if x[i]=="1":
        deka+=pow(2,n-i-1,c+1)
        deka%=c+1
tiisa=0
if c!=1:
    for i in range(n):
        if x[i]=="1":
            tiisa+=pow(2,n-i-1,c-1)
            tiisa%=c-1

for i in range(n):
    if x[i]=="0":
        nex=(deka+pow(2,n-i-1,c+1))%(c+1)
    else:
        nex=(tiisa-pow(2,n-i-1,c-1))%(c-1)
    if nex==0:
        print(1)
    else:
        print(l[nex])

Submission status: Runtime Error

Solution code:
## coding: UTF-8
#N = 23
#S = '00110111001011011001110'
N = int(input())
S = input()
P = int(S, 2)

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 count(N):
    warareru = N
    waru = popcount(N)
    counter = 0
    while warareru > 0:
        warareru = warareru % waru
        waru = popcount(warareru)
        counter += 1
    return counter


ans = [0]
for i in range(1, 2*10**5+10):
    ans.append(count(i))
#print(ans[:100])

C = popcount(P)
ret = []
for i in range(N):
    new = []
    for j in range(N):
        if(j != i):
            new.append(S[j])
        else:
            if(S[j] == '0'):
                new.append('1')
                count = C + 1
            else:
                new.append('0')
                count = C - 1
    ten = int(''.join(new), 2)
    res = ans[ten%count] + 1
    ret.append(res)

for i in range(N):
    print(ret[i])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

def main():
  n = int(input())
  x = input()
  count = 0
  sub = 1
  last = [None]*n
  for i in range(n):
    if x[i] == "1":
      count += 1
            
  if count == 0:
    for i in range(n):
      print(1)
      sys.exit()
  if count == 1:
    if x[-1] == "1":
      for i in range(n-1):
        print(2)
        print(0)
        sys.exit()
    else:
      for i in range(n-1):
        if x[i] == "1":
          print(0)
        else:
          print(1)
          print(2)
          sys.exit()

  sub1, sub2 = 1, 1
  num1, num2 = 0, 0
  for i in range(n):
    last[i] = [sub1, sub2]
    if x[n-i-1] == "1":
      num1 += sub1
      num2 += sub2
      num1 %= count-1
      num2 %= count+1
    sub1 *= 2
    sub2 *= 2
    sub1 %= count-1
    sub2 %= count+1
            
    
    
  key = [0]*(2**18+1)
  for i in range(1, 2**18):
    c = 0
    for j in range(18):
      if (i>>j)&1:
        c += 1
    judge = i%c
    key[i] = key[judge] + 1

  for i in range(n):
    if x[i] == "1":
      judge = (num1+count-1-last[n-1-i][0])%(count-1)
      print(1+key[judge])
    else:
      judge = (num2+last[n-1-i][1])%(count+1)
      print(1+key[judge])

if __name__ == "__main__":
  main()

Submission status: Runtime Error

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

def popcnt1(n):
    return bin(n).count("1")
def answer(X):
  c = X
  ans = 0
  while True:
    ans += 1
    pct = popcnt1(c)
    c = c%pct
    if c == 0:
      break
  return ans

x = x^(2**(N-1))
#print(bin(x))
print(answer(x))
for i in range(N-1):
  x = x^(2**(N-1-i)+2**(N-2-i))
  #print(bin(2**(N-1-i)+2**(N-2-i)))
  #print(bin(x))
  print(answer(x))

Submission status: Runtime Error

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

xre = x[::-1]

cou = x.count('1')
basepl = int(x, 2) % (cou+1)
basemi = int(x, 2) % (cou-1)

li = [0]*n
pl = 1
mi = 1
for i in range(n):
    if xre[i] == '0':
        li[i] = (basepl + pl)  % (cou+1)
    else:
        li[i] = (basepl + mi)  % (cou-1)
    mi = (mi * 2)% (cou-1)
    pl = (pl * 2)% (cou+1)

def f(n):
    m = n
    k = 1
    while m > 0:
        co = str(bin(m)).count('1')
        m = m % co
        k +=1
    return k

for x in li[::-1]:
    print(f(x))

Submission status: Runtime Error

Solution code:
def main():
    n = int(input())
    x = int(input(), 2)
    
    def popcount(n):
        n = format(n, 'b')
        return n.count('1')
    
    l = len(bin(x))
    for i in range(n):
        x2 = 1 << l-1-i
        x2 = x^x2 
        ans = 0
        while x2 != 0:
            x2 = x2 % popcount(x2)
            ans += 1
        print(ans)
    
    
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
x = str(input())
kosu1 = 0
kazu = 0
for i in range(n):
    kazu += 2 ** (n - i - 1) * int(x[i])
    if x[i] == '1':
        kosu1 += 1
if kosu1 ==1:
    kazup = kazu % (kosu1 + 1)
    magic17 = [0, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 2, 3, 1, 2]
    box = [0] * (kosu1 + 1)

    amarip = [1] * n
    amarim = [1] * n
    for i in range(1, n):
        amarip[i] = (amarip[i - 1] * 2) % (kosu1 + 1)
    for i in range(n):
        if x[i] == '1':
            print(0)
        else:
            a = (kazup + amarip[n - 1 - i]) % (kosu1 + 1)
            # print(2121,a)
            if a <= 18:
                print(magic17[a] + 1)
            else:
                num = 0
                for i in range(len(str(bin(a)) - 2)):
                    if str(bin(a))[-1 - i] == 1:
                        num += 1
                print(magic17[a % num] + 1)
else:
    kazup = kazu %(kosu1 + 1)
    kazum = kazu %(kosu1 - 1)
    magic17 = [0,1,1,2,1,2,1,2,1,2,1,2,1,2,2,3,1,2,1]
    box = [0] * (kosu1 +1)

    amarip = [1] * n
    amarim = [1] * n
    for i in range(1,n):
        amarip[i] = (amarip[i - 1]*2) % (kosu1 + 1)
        amarim[i] = (amarim[i - 1]*2) % (kosu1 - 1)
    for i in range(n):
        if x[i] == '1':
            a = (kazum - amarim[n-1-i]) % (kosu1 - 1)
            #print(a,kazup,kazum,amarip,amarim,kosu1)
            if a <= 18:
                print(magic17[a]+1)
            else:
                num = 0
                for i in range(len(str(bin(a))-2)):
                    if str(bin(a))[-1-i] == 1:
                        num += 1
                print(magic17[a % num] + 1)
        else:
            a = (kazup + amarip[n - 1 - i]) % (kosu1 + 1)
            if a <= 18:
                print(magic17[a] + 1)
            else:
                num = 0
                for i in range(len(str(bin(a)) - 2)):
                    if str(bin(a))[-1 - i] == 1:
                        num += 1
                print(magic17[a % num] + 1)

Submission status: Runtime Error

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

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

p = [-1 for _ in range(2*(10**5)+1)]
cnt = x.count('1')

def calc(a):
  #print('a=',a)
  if p[a] != -1:
    return p[a]
  else:
    if a == 0:
      ret = 0
    else:
      b = bin(a).count('1')
      ret = 1+calc(a%b)
    p[a] = ret
    return ret

x0 = int(x,2)%(cnt-1)
x1 = int(x,2)%(cnt+1)
for i in range(n):
  xx = pow(2,n-i-1)
  y = list(x)
  if y[i] == '0':
    print(calc((x1+xx%(cnt+1))%(cnt+1))+1)
  else:
    print(calc((x0-xx%(cnt-1))%(cnt-1))+1)

Submission status: Runtime Error

Solution code:
import sys
N = int(input())
X = int(input(), 2)
x_popcount = sum(map(int, bin(X)[2:]))
x_popcounts = [x_popcount - 1, x_popcount + 1]
X_per_popcounts = [X % x_popcounts[0], X % x_popcounts[1]]
mods = [0, 0]
ans = [0]*N

if X == 0:
    for i in range(N-1):
        print(1)
    print(0)
    sys.exit()

def f(n):
    cnt = 0
    while n != 0:
        popcount = sum(map(int, bin(n)[2:]))
        n = n % popcount
        cnt += 1
    return cnt

flg = X & 1 ^ 1
mods[0] = (-1) % x_popcounts[0]
mods[1] = 1 % x_popcounts[1]
tmp = (X_per_popcounts[flg] + mods[flg]) % x_popcounts[flg]
ans[0] = f(tmp) + 1

for i in range(1, N):
    flg = (X>>i) & 1 ^ 1
    mods[0] = (mods[0] * 2) % (x_popcounts[0])
    mods[1] = (mods[1] * 2) % (x_popcounts[1])
    tmp = (X_per_popcounts[flg] + mods[flg]) % x_popcounts[flg]
    ans[i] = f(tmp) + 1


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

Submission status: Runtime Error

Solution code:
def f(x):
    X = len(x)
    mod = x.count('1')
    mod2 = format(mod, 'b')
    M = len(mod2)
    for i in range(X-M+1):
        if x[i:i+M] >= mod2:
            nx = int(x[i:i+M],2) % mod
            nx2 = format(nx, 'b')
            if i+M==X:
                x = '0' * (i+M-len(nx2)) + nx2
            else:
                x = '0' * (i+M-len(nx2)) + nx2 + x[i+M:]
        elif i+M==X:
            break
        elif x[i:i+M+1] >= '0'+mod2:
            nx = int(x[i:i+M+1],2) % mod
            nx2 = format(nx, 'b')
            if i+M==X-1:
                x = '0' * (i+M+1-len(nx2)) + nx2
            else:
                x = '0' * (i+M+1-len(nx2)) + nx2 + x[i+M+1:]
        # print(x)
    for i in range(X):
        if x[i] == '1':
            x = x[i:]
            break
    else:
        x = '0'
    return x

N = int(input())
X = input()
# print(X)
for i in range(N):
    if i==0:
        x = str(1-int(X[i])) + X[i+1:]
    elif i==N-1:
        x = X[:i] + str(1-int(X[i]))
    else:
        x = X[:i] + str(1-int(X[i])) + X[i+1:]
    ans = 0
    while x!='0':
        x = f(x)
        ans += 1
    print(ans)

Submission status: Runtime Error

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


def sousa(num, ans):
    num_b = format(num, 'b')
    cnt_s = num_b.count("1")
    num %= cnt_s
    if num == 0:
        print(ans)
    else:
        sousa(num, ans + 1)


for i in range(n):
    temp = list(x)
    if temp[i] == "1":
        temp[i] = "0"
    else:
        temp[i] = "1"
    temp = int("".join(temp), 2)
    sousa(temp, 1)

Submission status: Runtime Error

Solution code:
n = int(input())
s = input()[::-1]
cnt = s.count('1')

p1 = sum(pow(2, i, cnt+1) * (s[i] == '1') for i in range(n))
m1 = sum(pow(2, i, cnt-1) * (s[i] == '1') for i in range(n))

def op(n):
    popcnt = bin(n).count('1')
    return n%popcnt

pre = [0]*100000
for i in range(1,100000):
    pre[i] = pre[op(i)] + 1

def solve(i):
    t = list(s[::-1])
    t[i-1] = '1' if t[i-1]=='0' else '0'
    x = int(''.join(t), 2)

    if s[-i] == '0':
        r = (p1 + pow(2, n-i, cnt+1))%(cnt+1)
    else:
        if cnt == 1:
            return 1
        r = (m1 - pow(2, n-i, cnt-1))%(cnt-1)
    return 1 + pre[r]

for i in range(n):
    print(solve(i+1))

Submission status: Runtime Error

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

k=0
for i in range(N):
  if X[i]=="1":
    k+=1

A=int(X,2)
#apは0->1の時の一回目の変換の値。
ap=A%(k+1)
am=A%(k-1)

popc_list=[-1]*(k+3)

def F(num):
  #print(str(num)+"called")
  if num==0:
    return 0
  if popc_list[num]!=-1:
    return popc_list[num]
  
  popc=0
  for s in bin(num):
    if s == "1":
      popc+=1
      
  popc_list[num]=F(num%popc)+1
  return popc_list[num]
  

for i in range(N):
  if X[i] == "0":
    print(F((ap+pow(2,N-1-i,k+1))%(k+1))+1)
  else:
    print(F((am-pow(2,N-1-i,k-1))%(k-1))+1)
"""
print(popc_list)
print(k)
"""

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)
N=int(input())
X=input()
X_int=int(X, 2)


def calc(n,count):
    popcount=bin(n).count("1")
    next_n=n%popcount
    #print(next_n)
    if next_n==0:
        return count+1
    else:
        return calc(next_n, count+1)


for i in range(N):
    if X[i]=="1":
        now=X_int-2**(N-1-i)
    else:
        now=X_int+2**(N-1-i)

    #print(int(nowbin, 2))
    print(calc(now,0))

Submission status: Runtime Error

Solution code:
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define FOR(i,k,n) for(int(i)=(k);(i)<(n);++(i))
#define rep(i,n) FOR(i,0,n)
#define all(v) begin(v),end(v)
#ifdef ONLINE_JUDGE
  #define debug(x)
  #define debug2(x,y)
  #define debug3(x,y,z)
  #define assert(e) if(!(e)){stod("");}
#else
  #define debug(x) std::cerr<<#x<<": "<<x<<"\n"
  #define debug2(x,y) std::cerr<<#x<<": "<<x<<", "<<#y<<": "<<y<<"\n"
  #define debug3(x,y,z) std::cerr<<#x<<": "<<x<<", "<<#y<<": "<<y<<", "<<#z<<": "<<z<<"\n"
#endif

using ll=long long;
using vi=std::vector<int>;
using vvi=std::vector<vi>;
using vll=std::vector<ll>;
using vvll=std::vector<vll>;
template<typename T> using vvec=std::vector<std::vector<T>>;
template<typename T>
auto make_v(size_t sz){return std::vector<T>(sz);}
template<typename T,typename... Ts>
auto make_v(size_t sz,Ts...ts){return std::vector<decltype(make_v<T>(ts...))>(sz,make_v<T>(ts...));}
template<typename T>
void fill_v(T&var,const T&x){var=x;}
template<typename V,typename T>
void fill_v(V&v,const T&x){for(auto&& w:v){fill_v(w,x);}}

template<typename T> std::ostream& operator<<(std::ostream&s,const std::vector<T>&v){
  int sz=v.size();s<<"\n";rep(i,sz){s<<v[i];if(i<sz-1){s<<"\t";}}s<<"\n";return s;}
template<typename T> std::ostream& operator<<(std::ostream&s,const std::vector<std::vector<T>>&v){
  for(auto&& w:v){s<<w;}return s;}
template<typename T> std::ostream& operator<<(std::ostream&s,const std::deque<T>&v){
  int sz=v.size();s<<"\n";rep(i,sz){s<<v[i];if(i<sz-1){s<<"\t";}}s<<"\n";return s;}
template<typename T> std::ostream& operator<<(std::ostream&s,const std::deque<std::deque<T>>&v){
  for(auto&& w:v){s<<w;}return s;}
template<typename T> std::ostream& operator<<(std::ostream&s, const std::set<T>&v){
  s<<"\n";for(auto&& elm:v){s<<elm<<"\t";}s<<"\n";return s;}

inline void scan(int&a){scanf("%d",&a);}
inline void scan(ll&a){scanf("%lld",&a);}
inline void scan(char&a){scanf(" %c",&a);}
inline void scan(double&a){scanf("%lf",&a);}
template<typename T>
inline void scan(std::vector<T>&v){for(auto&& sv:v){scan(sv);}}
template<typename First,typename...Args>
inline void scan(First&f,Args&...args){scan(f);scan(args...);}
inline void scan(std::string&s){char BUF[3000000];scanf(" %s",BUF);s=std::string(BUF);}
inline void print(int a){printf("%d\n",a);}
inline void print(ll a){printf("%lld\n",a);}
inline void print(double a){printf("%.12f\n",a);}
inline void print(std::string s){std::cout<<s<<"\n";}

using namespace std;

int naive(int x) {
  int ret = 0;
  while (0 < x) {
    x %= __builtin_popcount(x);
    ret += 1;
  }
  return ret;
}

void solve() {
  int m = 200005;
  vi preans(m, 0);
  ll debugsum = 0;
  rep (i, m) {
    preans.at(i) = naive(i);
    debugsum += preans[i];
  }
  //debug(debugsum);
  int n;
  scan(n);
  string x;
  scan(x);
  int pc = 0;
  rep (i, n) {
    if (x[i] == '1') {
      pc += 1;
    }
  }
  int pcp = pc + 1;
  int pcm = max(pc - 1, 1);
  debug2(pcp, pcm);
  vi pcp_r(m, 0);
  vi pcm_r(m, 0);
  pcp_r[0] = 1;
  pcm_r[0] = 1;
  rep (i, m - 1) {
    pcp_r.at(i + 1) = pcp_r.at(i) * 2 % pcp;
    pcm_r.at(i + 1) = pcm_r.at(i) * 2 % pcm;
  }
  int base_pcpr = 0;
  int base_pcmr = 0;
  for (int i = n - 1; i >= 0; --i) {
    if (x[n-1 - i] == '1') {
      base_pcpr = (base_pcpr + pcp_r.at(i)) % pcp;
      base_pcmr = (base_pcmr + pcm_r.at(i)) % pcm;
    }
  }
  debug2(base_pcpr, base_pcmr);
  vi ans(n);
  for (int i = n - 1; i >= 0; --i) {
    if (x[n-1 - i] == '1') {
      if (pc == 1) {
        ans[n-1 - i] = 0;
        continue;
      }
      int current_pcmr = (base_pcmr + pcm - pcm_r.at(i)) % pcm;
      ans[n-1 - i] = 1 + preans.at(current_pcmr);
    } else {
      int current_pcpr = (base_pcpr + pcp_r.at(i)) % pcp;
      ans[n-1 - i] = 1 + preans.at(current_pcpr);
    }
  }
  rep (i, n) {
    print(ans.at(i));
  }
}

int main() {
  solve();
  return 0;
}

Submission status: Runtime Error

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

for i in range(N):
    ans=0
    if Xdef[i]=='0':
        X=int(Xdef,2)+2**(N-i-1)
    else:
        X=int(Xdef,2)-2**(N-i-1)
    #print(X)
    while True:
        X=X%int(format(X,'b').count('1'))
        ans+=1
        if X==0:
            break
    print(ans)

Submission status: Runtime Error

Solution code:
def popcount(n):
    bin_num = bin(n)[2:]
    count1 = 0
    for i in bin_num:
            count1 += int(i)
    return count1

def f(n):
    count=0

    while(1):
        n=n%popcount(n)
        count=count+1
        if n==0:
            break

    return count


if __name__=="__main__":
    N = int(input())
    X=(input())

    for i in range(N):
        if X[i]=="0":
            s=list(X)
            s[i:i+1]="1"
            ss=",".join(s)
            print(f(int(ss.replace(",",""))))
        else:
            s=list(X)
            s[i:i+1]="0"
            ss=",".join(s)
            print(f(int(ss.replace(",",""))))

Submission status: Runtime Error

Solution code:
arr=[0,1,1,2]
n=4*(10**5)+100
for i in range(4,n):
    b=bin(i)[2:]
    k=b.count('1')
    arr.append(arr[i%k]+1)
    #print(b,arr[i])
n=int(input())
z=input()
l=z.count('1')
l1=l+1
l2=l-1
ans1=0
ans2=0
for i in range(n):
    if(z[i]=='1'):
        u=pow(2,n-1-i,l1)
        ans1=(ans1+u)%l1
        if l2!=0:
            ans2=(ans2+pow(2,n-1-i,l2))%l2
for i in range(n):
    if z[i]=='0':
        p=ans1+pow(2,n-1-i,l1)
        p%=l1
        print(1+arr[p])
    else:
        p=ans2-pow(2,n-1-i,l2)
        p%=l2
        print(1+arr[p])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2 * 10**5)

N = int(input())
X = [i for i in input()]
sum_X = X.count("1")


def f(n, p):
    res = int(n, 2) % p
    if res != 0:
        temp2 = format(res, "b")
        return f(temp2, temp2.count("1")) + 1
    return 1


for i in range(0, N):
    tempX = ""
    count = sum_X
    if X[i] == "0":
        count += 1
        X[i] = "1"
        tempX = "".join(X)
        X[i] = "0"
    else:
        count -= 1
        X[i] = "0"
        tempX = "".join(X)
        X[i] = "1"

    print(f(tempX, count))

Submission status: Runtime Error

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

def popcount(s):
  return s.count('1')

def f(s):
  sub = int(s, 2) % popcount(s)
  if sub:
    return 1 + f('{:b}'.format(sub))
  else:
    return 1

for n in range(N):
  s = list(X)
  s[n] = '0' if s[n] == '1' else '1'
  print(f(''.join(s)))

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
ct = x.count("1")
for i in range(n):
    res = 0
    if x[i] == "0":
        y = 1
        t = ct + 1
    else:
        y = 0
        t = ct - 1
    s = x[:i] + str(y) + x[i + 1:]
    a = int(s, 2)
    while True:
        a %= t
        res += 1
        t = bin(a).count("1")
        if a == 0:
            break
    print(res)