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 sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math
from collections import deque
import itertools
import heapq
#import bisect
from fractions import Fraction
import copy
from functools import lru_cache
from collections import defaultdict
import pprint

#oo=list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
# ko=list("abcdefghijklmnopqrstuvwxyz")

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]

def ret(a):
    c=[None]*(len(a)-1)
    if len(a)==1:
        return a[0]
    elif len(a)==0:
        return 0
    for i in range(1,len(a)):
        c[i-1]=abs(a[i]-a[i-1])
    return ret(c)

def soinsubunkai(n):
    a = []
    i = 1
    while i*i <= n:
        if n % i == 0 and i!=1:
            a.append(i)
            n=n//i

        if n% i !=0 or i==1:
            i += 1
    nokori=[n]
    return a + nokori

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

def main():
    #l,r,d=map(int,input().split())
    n=int(input())
    num=list(map(int,input()))
    onecount=sum(num)
    origone=sum(num)
    numint=[]
    for i in range(n):
        numint.append(str(num[i]))
    numint="".join(numint)
    numint=int(numint, 2)
    orignum=numint
    for i in range(n):

        onecount=origone
        numint=orignum
        num[i]=(num[i]-1)*(-1)
        if num[i]==0:
            onecount-=1
            numint-=2**(n-i-1)
        else:
            onecount+=1
            numint += 2 ** (n - i-1)
        tempone=onecount
        divcount=0
        temp=numint
        while True:
            divcount+=1
            temp=temp%tempone
            if temp==0:
                break
            else:
                temp2=bin(temp).count("1")
                tempone=temp2
        print(divcount)
        num[i] = (num[i] - 1) * (-1)













if __name__ == "__main__":

    main()

Submission status: Runtime Error

Solution code:
import sys

def get1(y):
    b = bin(y)
    cnt = 0
    for c in b:
        if c == '1':
            cnt += 1
    return cnt

n = int(input())
s = sys.stdin.readline().rstrip()

cnt1 = 0
for c in s:
    if c == '1':
        cnt1 += 1
for i in range(n):
    if s[i] == '0':
        cnt1_ = cnt1 + 1
        s_ = s[:i] + '1' + s[(i+1):]
    else:
        cnt1_ = cnt1 - 1
        s_ = s[:i] + '0' + s[(i+1):]
    x = int(s_, 2)
    x = x % cnt1_
    ans = 1
    while x > 0:
        x = (x % get1(x))
        ans += 1
    print(ans)

Submission status: Runtime Error

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

pop = []
num = X.count("1")
n = int("".join(map(str, X)), 2)


def f(n):
    count = 0
    while n != 0:
        a = str(bin(n))
        n %= a.count("1")
        count += 1
    return count


for i in range(num):
    ans = f(i)
    pop.append(ans)

for i in range(N):
    if X[i] == "1":
        a = n-pow(2, N-1-i)
        if a < num-1:
            print(pop[n])
        else:
            a %= num-1
            print(pop[a]+1)
    if X[i] == "0":
        a = n+pow(2, N-1-i)
        if a < num+1:
            print(pop[n])
        else:
            a %= num+1
            print(pop[a]+1)

Submission status: Runtime Error

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

d = {}
def find(s):
    n = int(s,2)
    num_1 = s.count("1")
    if n % num_1 == 0:
        return 1

    if n in d:
        return d[n]
    else:
        n = n % num_1
        return find(bin(n)[2:]) + 1
    


for i in range(n):
    if x[i] == "0":
        if i < n -1:
            tmp = x[:i] + "1" +x[i+1:]
        else:
            tmp = x[:i] + "1"
    else :
        if i < n -1:
            tmp = x[:i] + "0" +x[i+1:]
        else:
            tmp = x[:i] + "0"
    n_1 = tmp.count("1")
    a = find(tmp)
    d[int(tmp, 2)] = a
    print(a)

Submission status: Runtime Error

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
x = input()
b = []
c = [0, 1, 1]
for i in range(n+2):
    cnt = 0
    for j in range(7):
        if i >> j & 1:
            cnt += 1
    b.append(cnt)

for i in range(3, n+2):
    c.append(c[i % b[i]]+1)

ans = []
tmp1 = 0
tmp2 = 0
cnt = x.count("1")
for i in range(n):
    if x[i] == "1":
        tmp1 += pow(2, n-(i+1), cnt+1)
        tmp2 += pow(2, n-(i+1), cnt-1)

for i in range(n):
    if x[i] == "1":
        ans.append(c[(tmp2 - pow(2, n-(i+1), cnt-1)) % (cnt-1)]+1)
    else:
        ans.append(c[(tmp1 + pow(2, n-(i+1), cnt+1)) % (cnt+1)]+1)

for i in ans:
    print(i)

Submission status: Runtime Error

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


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

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

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

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


dp = [0] * 1000000
for i in range(n - 1, -1, -1):
    num = (2 ** i) ^ x
    ans = 0
    bit_count_init = bc(num)
    while True:
        bit_count = bc(num)
        if num == 0:
            print(ans)
            dp[bit_count_init] = ans
            break
        num %= bit_count
        ans += 1
        if dp[num] != 0:
            print(dp[num] + ans)
            break

Submission status: Runtime Error

Solution code:
N = int(input())
X = eval("0b" + input())

dp = [-1]*(N+5)
dp[0] = 0
dp[1] = 1
dp[2] = 1

for i in range(3,N+1):
    c = bin(i).count("1")
    dp[i] = dp[i%c] + 1

for i in range(N):
    x = X^(1<<(N-1-i))
    c = bin(x).count("1")
    a = x%c
    print(dp[a]+1)

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
xx = int(x, 2)
value = [0, 1]
count_1 = x.count('1')
for i in range(2, 2 * (10 ** 5) + 1):
    ans = 1
    i = i % bin(i).count('1')
    value.append(ans + value[i])

for i in range(n):
    print(int(t, 2))

Submission status: Runtime Error

Solution code:
import math
from copy import copy
di = {}
di[0] = 0
for i in range(1, 2*(10**6)+1):
    di[i] = 0
for i in range(1, 2*(10**6)+1):
    count = 0
    for j in range(int(math.log2(i))+2):
        if (i>>j)&1:
            count += 1
    di[i] = di[i%count] + 1
n = int(input())
x = list(input())
x.reverse()
count = 0
for i in x:
    if i =='1':
        count += 1
mod_p = count + 1
mod_m = count - 1
di_p = {}
di_m = {}
for i in range(n):
    di_p[i] = pow(2, i, mod_p)
    di_m[i] = pow(2, i, mod_m)
s_p = 0
s_m = 0
for i in range(n):
    if x[i] == '1':
        s_p += di_p[i]
        s_m += di_m[i]
for i in range(n-1, -1, -1):
    sm = copy(s_m)
    sp = copy(s_p)
    if x[i] == '1':
        sm -= di_m[i]
        sm %= mod_m 
        print(di[sm]+1)
    else:
        sp += di_p[i]
        sp %= mod_p
        print(di[sp]+1)

Submission status: Runtime Error

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

popc = [0] * ((1 << 19) + 1)
for bit in range(1, 1 << 19):
    opt = bin(bit).count('1')
    popc[bit] = bit % opt

f_list = [0] * ((1 << 19) + 1)
for i in range(1, 1 << 19):
    now = popc[i]
    cnt = 1
    while True:
        if now == 0:
            f_list[i] = cnt
            break
        now = popc[now]
        cnt += 1

N = getN()
X = input()
NX = len(X)
time = X.count('1')
t1 = time + 1
t2 = time - 1

lis_left_1 = [0] * NX

now = 1 % t1
lis_left_1[0] = now
for i in range(1, NX):
    now = (2 * now) % t1
    lis_left_1[i] = now

lis_left_2 = [0] * NX

now = 1 % t2
lis_left_2[0] = now
for i in range(1, NX):
    now = (2 * now) % t2
    lis_left_2[i] = now

left_mother_1 = 0
for i in range(NX):
    if int(X[i]) == 1:
        left_mother_1 += lis_left_1[NX - i - 1]

left_mother_2 = 0
for i in range(NX):
    if int(X[i]) == 1:
        left_mother_2 += lis_left_2[NX - i - 1]

for i in range(N):
    # 1が0に left_mother_2, t2
    if int(X[i]) == 1:
        opt_mom = left_mother_2
        opt_mom -= lis_left_2[NX - i - 1]
        opt_mom %= t2
        print(f_list[opt_mom] + 1)
    # 0が1に left_mother_1, t1
    else:
        opt_mom = left_mother_1
        opt_mom += lis_left_1[NX - i - 1]
        opt_mom %= t1
        print(f_list[opt_mom] + 1)

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
num=int(x, 2)
first_one_count=x.count("1")

def popcount(n):
    return bin(n)[2:].count('1')

pop_list=[]
for i in range(2*(10**5)):
    pop_list.append(popcount(i))

x_mae=["",x[0]]
for i in range(1,len(x)):
    x_mae.append(x_mae[-1]+x[i])
x_mae.append("")

x_re=list(reversed(x))
x_ushiro=["",x_re[0]]
for i in range(1,len(x)):
    x_ushiro.append(x_ushiro[-1]+x_re[i])
x_ushiro.append("")

for i in range(n):
    if x[i]=='0':
        target=x_mae[i]+"1"+x_ushiro[n-1-i]
        one_count=first_one_count+1
    else:
        target=x_mae[i]+"0"+x_ushiro[n-1-i]
        one_count=first_one_count-1
    target="0b"+target
    target=int(target,2)%one_count
    cnt=1
    while target>0:
        target=target%pop_list[target]
        cnt+=1
    print(cnt)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


# cache = {}
import functools


def main():
    n = int(input().strip())
    x_str = input().strip()

    for i in range(n):
        xii = "0" if x_str[i] == "1" else "1"
        xi_str = x_str[:i] + xii + x_str[i + 1:]
        xi = int(xi_str, 2)

        print(fc(xi))


@functools.lru_cache(maxsize=None)
def fc(n):
    n_bin = bin(n)
    c = len(n_bin[2:].replace('0', ''))
    if n % c == 0:
        return 1
    else:
        return fc(n % c) + 1


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin
N = int(stdin.readline().rstrip())
X = (stdin.readline().rstrip())
cnt = X.count("1")
 
X = list(X)
 
f = [0]*(2*10**5+1)
for i in range(1,2*10**5+1):
    f[i] = (i%bin(i).count("1"))
 
for i in range(1,N+1):
    tmp = X[:]
    if tmp[i-1] == "0":
        tmp[i-1] = "1"
        cnt_t = cnt + 1
    else:
        tmp[i-1] = "0"
        cnt_t = cnt - 1
    
    amari = int("".join(tmp),2) % cnt_t
    ans = 1
    while amari != 0:
        amari = f[amari]
        ans += 1
    print(ans)

Submission status: Runtime Error

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


def calc(i, count):
    r = i % bin(i).count("1")
    if r != 0:
        return calc(r, count + 1)
    else:
        return count + 1


for i in range(1, N + 1):
    a = X ^ 2 ** ((N - 1) - (i - 1))
    b = calc(a, 0)
    print(b)

Submission status: Runtime Error

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

def bit_count(bits):
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
    return (bits & 0x0000ffff) + (bits >> 16 & 0x0000ffff);


def pop_counter(n):
    return n % bit_count(n)


ans = 0
for n, i in enumerate(X):
    ans = 0
    if i == '1':
        tmp = int_X - pow(2, N - 1 - n)
    else:
        tmp = int_X + pow(2, N - 1 - n)
    while tmp != 0:
        tmp = pop_counter(tmp)
        ans += 1
    print(ans)

Submission status: Runtime Error

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

memo = dict()


def f(n, c1, cnt):
    cnt += 1
    if n in memo:
        return memo[n]
    m = n % c1
    if m == 0:
        return cnt
    else:
        cnt = f(m, bin(m).count("1"), cnt)
        memo[n] = cnt
        return cnt


cnt1_n = x.count("1")
for i in range(n):
    ch_bi = x[:i] + str(int(x[i]) ^ 1) + x[i + 1:]
    ch_cnt = cnt1_n + (-1 if int(x[i]) else 1)
    num = int(ch_bi, 2)

    print(f(num, ch_cnt, 0))

Submission status: Runtime Error

Solution code:
n = 100000
ans_count = [-1 for _ in range(n)]

for i in range(1,n+1):
    b = bin(i)
    b=list(b)
    a = b.count("1")
    f = i%a
    if f == 0:
        ans_count[i-1]=1
    else:
        ans_count[i-1] = ans_count[f-1]+1

ans_count = [0]+ ans_count

n= int(input())
inp = input()
x = list(inp)

org = int(inp, 2)
if "1" in x:      
    l = x.count("1")
else:
    l = 0


# for _ in range(n):
#     print(0)

for i in range(n):
    a = x[i]
    if a=="0":
        N = org+(2**(n-i-1))
        m= N%(l+1)
        print(ans_count[m]+1)
    else:
        if l ==1:
            print(0)
        else:
            N = org-(2**(n-i-1))
            m=N%(l-1)
            print(ans_count[m]+1)

Submission status: Runtime Error

Solution code:
def solve(numX,X):
    global ans
    ans += 1
    y = int(X,2)%numX
    if y == 0:
        return 0
    else:
        z = bin(y)[2:]
        solve(z.count("1"),z)

n = int(input())
X = input()
n = len(X)
ans = 0
numX = X.count("1")
for i in range(n):
    ans = 0
    tmpX = ""
    tmp = ""
    if X[i] == "0":
        tmpnumX = numX + 1
        tmp = "1"
    else:
        tmpnumX = numX - 1
        tmp = "0"
    if i == 0:
        tmpX = tmp + X[1:]
    elif i == n-1:
        tmpX = X[:i] + tmp
    else:
        tmpX = X[:i] + tmp + X[i+1:]
    solve(tmpnumX,tmpX)
    print(ans)

Submission status: Runtime Error

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

##wは二進数
def lk(w):
  coun = 0
  l = len(w)
  for i in range(l):
    coun += 2**(l-i-1)
    if coun >=10**5:
      break
  return coun


##
list_f = [0 for i in range(10**6+1)]
for i in range(1,10**6+1):
  bi = bin(i).count("1")
  if i%bi==0:
    list_f[i] =1
  else:
    amari = i%bi
    list_f[i] = 1+ list_f[amari]
#print(list_f[:20])

if int(x)==1:
  print(1)
  exit()
  
for i in range(0,n):
  if x[i]=="0":
    t = list(x)
    t[i]="1"
    t = "".join(t)
    t_bin= t.count("1")
    t_amari = lk(t)%t_bin
    if t_amari==0:
      print(1)
    else:
      print(list_f[t_amari]+1)
 
  else:
    t = list(x)
    t[i]="0"
    t = "".join(t)
    t_bin= t.count("1")
    t_amari = lk(t)%t_bin
#    print(1,t_amari)
    if t_amari==0:
      print(1)
    else:
      print(list_f[t_amari]+1)

Submission status: Runtime Error

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


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


# print(popcount(N))

POPCOUNT_TABLE16 = [0] * 2 ** 16
for index in range(len(POPCOUNT_TABLE16)):
    POPCOUNT_TABLE16[index] = (index & 1) + POPCOUNT_TABLE16[index >> 1]
def popcnt5(v):
    return (POPCOUNT_TABLE16[v & 0xffff] +
            POPCOUNT_TABLE16[(v >> 16) & 0xffff] +
            POPCOUNT_TABLE16[(v >> 32) & 0xffff] +
            POPCOUNT_TABLE16[(v >> 48)])


cnt = 0


def func(n):
    global cnt
    if n == 0:
        return cnt
    n = n % popcnt5(n)
    cnt += 1
    return func(n)


# print(func(7))

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


for i in range(N - 1, -1, -1):
    n = toggle_nth_bit(int(X, 2), i)
    ans = func(n)
    print(ans)
    cnt -= ans

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)

Submission status: Runtime Error

Solution code:

N = int(input())
X = input()
x = int(X,2)
inum = 0
def popcnt1(n):
    return bin(n).count("1")
    
# print(x)
inum = popcnt1(x)
# print(inum)
def func(x,p,num = 0):
    x = x%p
    p = popcnt1(x)
    # print(x,p)
    num += 1
    # print(num)
    if x == 0:
        return num
    else:
        return(func(x,p,num))

# base = func(x,inum)
# print(base)
for i in range(N):
    X2 = X
    if X[i] == "0":
        X2 = X2[:i]+"1"+X2[i+1:]
        X2 = int(X2,2)
        # print(X2)
        a = func(X2,inum+1,num = 0)
        print(a)
    else:
        X2 = X2[:i]+"0"+X2[i+1:]
        X2 = int(X2,2)
        # print(X2)
        a = func(X2,inum-1,num = 0)
        print(a)

Submission status: Runtime Error

Solution code:
CH = [0,1,1,2,1,2,1,2,1,2,1,2,1,2,2,3,1,2,1,2,1]
N = int(input())
X = input()
s = 0
a = 1
A = []
B = []
for x in X:
    if x == "1":
        s += 1
for i in range(N):
    A.append(a)
    a = a*2 %(s+1)
a = 1
for i in range(N):
    B.append(a)
    a = a*2 %(s-1)
num = int(X,2)
num1 = num%(s+1)
if s > 1:
    num2 = num%(s-1)
for i in range(N):
    if int(X[i])==1:
        p = s-1
        if p == 0:
            print(0)
            continue
        x = (num2-B[N-1-i])%p
        if x > 20:
            y = x%sum(map(int,list(bin(x))[2:]))
            print(2+CH[y])
        else:
            print(1+CH[x])
    else:
        p = s+1
        x = (num1+A[N-1-i])%p
        if x > 20:
            y = x%sum(map(int,list(bin(x))[2:]))
            print(2+CH[y])
        else:
            print(1+CH[x])

Submission status: Runtime Error

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def s(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 1
ans = 0
inf = float("inf")

n = k()
x = s()
po = int(x,2)
cnt = x.count("1")
a = 2**(n-1)
for i in range(n):
    ans = 0
    count = 0
    if x[i] == "0":
        ans = po+a
        count = cnt+1
    else:
        ans = po-a
        count = cnt-1
    a //= 2
    if ans % count == 0:
        print(1)
    elif ans % count == 1 or (ans%count) % 2 == 0:
        print(2)
    else:
        print(3)

Submission status: Runtime Error

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

for i in range(1,-(-n//2)+1):
    s = format(i, 'b')
    c = s.count('1')
    a = i%c
    ans[i] += 1
    ans[i] += ans[a] 

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
        num = numx - 2**(n-1-i)
    print(ans[num%temp]+1)

Submission status: Runtime Error

Solution code:

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

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

    lut = [0] * N
    lut[1] = 1
    for i in range(2, N):
        Xi = i % popcnt(i)
        lut[i] = lut[Xi] + 1

    dp = d+1
    dm = d-1
    mp = X % dp
    mm = X % dm if dm else 0
    # print(lut)
    # print(format(X, 'b'))
    
    ans = []
    for i in range(N):
        mask = 1 << (N-i-1)
        Xi = X ^ mask
        _ans = 0
        if Xs[i] == '1':
            if dm:
                m = (mm - pow(2, N-i-1, dm)) % dm
                _ans = lut[m] + 1
            # m = (mm - mask) % dm
        else:
            # m = (mp + mask) % dp
            m = (mp + pow(2, N-i-1, dp)) % dp
            _ans = lut[m] + 1
        # print(Xi, Xs[N-i-1], m)
        # print(format(Xi, 'b'))

        # Xi2 = Xi % dd
        # ans.append((Xi, Xi2))
        ans.append(_ans)
    print(*ans, sep='\n')

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import Counter

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

x1 = 0
for i in X:
    if i == '1':
        x1 += 1

for i in range(N):
    if X[i] == '1':
        tmp = - (1<<(N-i-1))
        tmp2 = -1
    else:
        tmp = (1<<(N-i-1))
        tmp2 = 1
    
    n = int(X, 2) + tmp
    n %= x1 + tmp2
    cnt = 1
    while n != 0:
        c = 0
        for j in bin(n):
            c += j=='1'
        n %= c
        cnt += 1
    print(cnt)

Submission status: Runtime Error

Solution code:
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
# from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
# import numpy as np
# sys.setrecursionlimit(int(pow(10,6)))

mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

try:
    sys.stdin = open("input.txt", "r")
    sys.stdout = open("out.txt", "w")
except:
    pass


# @lru_cache(None)

n=L()[0]
X=input()
if X=="0"*n:
    for i in range(n):
        print(1)
    exit()
if X=="1":
    print(0)
    exit()
curr=curr2=1
nao=mnao=0
bit=X.count("1")+1
bit2=X.count("1")-1
for i in range(n-1,-1,-1):
    if X[i]=="1":
        nao+=curr%bit
        nao%=bit
        mnao+=curr2%bit2
        mnao%=bit2
    curr*=2
    curr%=bit
    curr2*=2
    curr2%=bit2
for  i in range(n):
    FN=0
    if X[i]=="0":
        FN=nao
        ex=pow(2,n-i-1,bit)
        FN+=ex
        FN%=bit
    else:
        FN=mnao
        ex=pow(2,n-i-1,bit2)
        FN-=ex
        FN%=bit2
        if FN<0:
            FN+=bit2
    step=1
    while(FN):
        bitcnt=bin(FN).count("1")
        FN%=bitcnt
        step+=1
    print(step)

Submission status: Runtime Error

Solution code:
# coding: utf-8

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

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

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

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

N = int(input())
y = input(); x = 0

dic = dict()
dic[0] = 0
for i in range(1, N+1):
    cnt = popcount(i)
    b = i%cnt
    dic[i] = b

    if y[i-1] == '1':
        x += 1

X = int('0b' + y, 0)

res = 1 << N-1
for i in range(N):
    now = X ^ res
    nx = x
    if y[i] == '1':
        nx -= 1
    else:
        nx += 1
    #print(now, res)
        
    a = bin(now)
    #print(a)
    
    b = now%nx
    #print(now, nx, b)
    ans = 1
    while b > 0:
        b = dic[b]
        ans += 1
    print(ans)
    
    res = res >> 1

Submission status: Runtime Error

Solution code:
import math
from copy import copy
di = {}
di[0] = 0
for i in range(1, 2*(10**6):
    di[i] = 0
for i in range(1, 2*(10**6)):
    count = 0
    for j in range(int(math.log2(i))+2):
        if (i>>j)&1:
            count += 1
    di[i] = di[i%count] + 1
n = int(input())
x = list(input())
x.reverse()
count = 0
for i in x:
    if i =='1':
        count += 1
mod_p = count + 1
mod_m = count - 1
di_p = {}
di_m = {}
for i in range(n):
    di_p[i] = pow(2, i, mod_p)
    di_m[i] = pow(2, i, mod_m)
s_p = 0
s_m = 0
for i in range(n):
    if x[i] == '1':
        s_p += di_p[i]
        s_m += di_m[i]
for i in range(n):
    sm = copy(s_m)
    sp = copy(s_p)
    if x[i] == '1':
        sm -= di_m[i]
        sm %= mod_m 
        print(di[sm]+1)
    else:
        sp += di_p[i]
        sp %= mod_p
        print(di[sp]+1)

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
times = {}
times[0] = 0

for i in range(1,200000):
  bi = format(i, 'b')
  arr = list(map(int, bi))
  sbi = sum(arr)
  if i%sbi == 0:
    times[i] = 1
  else:
    times[i] = 1+times[i%sbi]
    
arr = list(map(int, X))
sbX = sum(arr)
X10 = int(X,2)
mo = [1,-1]
mo2 = [X10%(sbX+1),X10%(sbX-1)]

for i in range(N):
  waru = sbX+mo[int(X[i])]
  if waru == 0:
    print(0)
  else:
    print(times[(pow(2,(N-i-1),waru)+mo2[int(X[i])])%waru]+1)

Submission status: Runtime Error

Solution code:
def f(n):
    if n in memo:
        return memo[n]
    c=list(str(bin(n)))[2:].count('1')
    r=n%c
    if r>0:
        memo[n]=f(r)+1
    else:
        memo[n]=1
    return memo[n]

memo={0:0}
N=int(input())
X=list(input())
XC=X.count('1')
XN=int('0b'+''.join(X),2)
for i in range(N):
    if X[i]=='1':
        tx=(XN%(XC-1)-pow(2,N-i-1,XC-1))%(XC-1)
        if tx<0:
            tx+=XC-1
    else:
        tx=(XN%(XC+1)+pow(2,N-i-1,XC+1))%(XC+1)
    print(f(tx)+1)

Submission status: Runtime Error

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

#print(bin(X))
for n in range(N):
    tmp = (1 << ((N - 1) - n))
    X_n = X ^ tmp
    #print('\n')
    #print(format(X_n, 'b'))
    
    str_X_n = format(X_n, 'b')
    
    count_popcount = 0
    tmp_str = str_X_n
    while(1):
        #print(tmp_str)
        count_1 = tmp_str.count('1')
        #print('count_1')
        #print(count_1)
        amari = int(tmp_str, 2) % count_1
        #print('amari')
        #print(amari)
        if(amari == 0):
            count_popcount += 1
            break
        else:
            count_popcount += 1
            tmp_str = format(amari, 'b')
    print(count_popcount)

Submission status: Runtime Error

Solution code:
N = int(input())
x__ = list(input())
X = []
for i in range(N):
    x_ = x__[:]
    x_[i] = "1" if x_[i] == "0" else "0"
    X.append(int("".join(x_),2))


popcounts = [-1 for i in range(10**7)]
#print("ok")
for x in X:
    n = x
    cnt = 0
    while n != 0:
        #print(n)
        if popcounts[n] == -1:
            popcounts[n] = str(bin(n)).count("1")

        n = n%popcounts[n]
        cnt += 1
    print(cnt)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(5000)
n = int(input())
X = input()
pc = X.count('1')
nx = int(X, 2)
dp = [-1] * (2*10**5+1)
def f(n):
    if dp[n] > 0:
        return dp[n]
    pc = bin(n).count('1')
    nn = n%pc
    if nn == 0:
        return 1

    dp[n] = f(nn) + 1
    return dp[n]

for i in range(n-1, -1, -1):
    # ibit目を反転させる # つまりi**2を引く
    tmp = pow(2, i)
    if (nx>>i)&1:
        nx -= tmp
        r = nx%(pc-1)
        if r > 0:
            print(f(r) + 1)
        else:
            print(1)
        nx += tmp
    else:
        nx += tmp
        r = nx%(pc+1)
        if r > 0:
            print(f(r) + 1)
        else:
            print(1)
        nx -= tmp

Submission status: Runtime Error

Solution code:
n=int(input())
x=int(input(),2)
a=[-1]*(n+1)
for i in range(n+1):
    cnt=0
    j=i
    while i!=0:
        if a[i]==-1:
            i%=str(bin(i)).count("1")
            cnt+=1
        else:
            cnt+=a[i]
            i=0
    a[j]=cnt

for i in range(1,n+1):
    b=x^(1<<(n-i))
    b%=str(bin(b)).count("1")
    print(a[b]+1)