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())
s = int(input(), 2)


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


def division_binary_shift(a, b):
    """
    a // b

    :param a: dividend
    :param b: divisor
    :return: quotient
    """
    if a < b:
        return 0
    if b == 0:
        raise ZeroDivisionError

    q = 0
    sq = 1
    ori_b = b
    while a >= b:
        b <<= 1
        if a >= b:
            sq <<= 1
        else:
            b >>= 1
            a -= b
            q += sq
            sq = 1
            b = ori_b

    return q


for i in range(n):
    ss = s ^ (1 << (n-i-1))
    c = 0
    t = popcount(ss)
    while ss - t*division_binary_shift(ss, t) != 0:
        ss -= t*division_binary_shift(ss, t)
        t = popcount(ss)
        c += 1
    # print(ss, popcount(ss), c)
    print(c+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))
if cnt > 1:
    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):
    if s[-i] == '0':
        r = (p1 + pow(2, n-i, cnt+1))%(cnt+1)
    else:
        if cnt == 1:
            return 0
        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()
d = {'1':1}

def popcount(x):
    x = x.lstrip('0')
    if x in d:
        return d[x]
    else:
        n1 = x.count('1')
        num = int(x, base=2)
        if num % n1 == 0:
            return 1
        else:
            return popcount(bin(num % n1)[2:]) + 1
    
def trans(x,n):
    if x[n] == '1':
        return x[:n] + '0' + x[n+1:]
    else:
        return x[:n] + '1' + x[n+1:]
    
for i in range(n):
    ix = trans(x,i)
    print(popcount(ix))

Submission status: Runtime Error

Solution code:
def popcount(x):
    # '''xの立っているビット数をカウントする関数
    # (xは64bit整数)
    # https://qiita.com/zawawahoge/items/8bbd4c2319e7f7746266'''

    # # 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
    return bin(x).count("1")

N = int(input())
X = input()
Xn = int(X, 2)
F = [-1] * (2**N+10)
F[0] = 0
F[1] = 1
popcounts = [-1] * (2**N+1)
for i in range(N):
    if X[i] == "1":
        y = Xn - 2**(N-i-1)
    else:
        y = Xn + 2**(N-i-1)
    cnt = 0
    yy = y
    while True:
        if F[y] == -1:
            if popcounts[y] == -1:
                popcounts[y] = popcount(y)
            y = y % popcounts[y]
            cnt += 1
            continue
        else:
            F[yy] = cnt + F[y]
            print(F[yy])
            break

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import math

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

def num_to_X(num):
    new_X = []
    new_N = int(math.log(num,2))+1
    for i in range(new_N):
        new_X.append(num>>i&1)
    return new_X[::-1]

def X_to_num(X):
    value = 0
    X = X[::-1]
    for i in range(len(X)):
        value += X[i]*pow(2,i)
    return value

def mode(X, mod):
    X = X[::-1]
    next_X = 0
    mod_2_i = 1
    for i in range(len(X)):
        next_X += X[i]*mod_2_i
        mod_2_i = (mod_2_i*2)%mod
    next_X = next_X%mod
    return next_X

def f(N, X, k):
    mod = sum(X)
    next_X = mode(X,mod)
    if next_X == 0:
        return k+1
    else:
        new_X = num_to_X(next_X)
        return f(len(new_X), new_X, k+1)

base_mod = sum(X)
# base_modが1なら, 操作は0回.
if base_mod == 1:
    for i in range(N):
        # 100 -> 000
        if X[i] == 1:
            print(0)
        # 100 -> 110
        elif i != N-1:
            print(1)
        # 100 -> 101
        else:
            print(2)

plus_amari = mode(X, base_mod+1)
# print(X_to_num(X), base_mod+1, X_to_num(X)%(base_mod+1), plus_amari)
minus_amari = mode(X, base_mod-1)
# print(X_to_num(X), base_mod-1, X_to_num(X)%(base_mod-1), minus_amari)

results = []
modplus_2_i = 1
modminus_2_i = 1
X_hanten = X[::-1]

# print('----')
# print(X)
# print('----')

for i in range(N):
    # modが増えるパターン
    if X_hanten[i] == 0:
        now_num = X_to_num(X)+pow(2,i)
        now_mod = base_mod+1
        amari = (plus_amari+modplus_2_i)%(base_mod+1)
    else:
        now_num = X_to_num(X)-pow(2,i)
        now_mod = base_mod-1
        amari = (minus_amari-modminus_2_i)%(base_mod-1)
#     print(now_num, now_mod, now_num%now_mod,amari)

    if amari != 0:
        new_X = num_to_X(amari)
        results.append(f(len(new_X),new_X,1))
    else:
        results.append(1)

    modplus_2_i = (modplus_2_i*2)%(base_mod+1)
    modminus_2_i = (modminus_2_i*2)%(base_mod-1)

# print('---')
for result in results[::-1]:
    print(result)

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
t=int(x,2)
c=x.count('1')
m=[0]*n
k=1
while k<n: m[k]=1; k*=2
def popcount(x):
  if x==0: return 0
  if m[x]: return m[x]
  return popcount(x%bin(x).count('1'))+1
for i in range(n):
  if int(x[i]):
    d=c-1
    if c<1: print(0)
    print(popcount((t-pow(2,n-i-1,d))%d)+1)
  else:
    d=c+1
    print(popcount((t+pow(2,n-i-1,d))%d)+1)

Submission status: Runtime Error

Solution code:
N=int(input())
X = input()
def popcount(string):
    cnt = 0
    for j in range(len(string)):
        if string[j] == "1":
            cnt += 1
    return cnt

for i in range(1,N+1):
    cnt = 0
    cnt_1 = 0
    sum = 0
    string = X
    #反転
    if string[i-1] =="1":
        string=string[:i-1]+ "0"+string[i:]
    else:
        string =string[:i-1]+ "1"+string[i:]
    #print(string)
    bin_num = int(string, 2)
    tmp = popcount(string)
    #print(bin_num,tmp)
    mod = 100
    while mod != 0:
        mod = int(bin_num) % tmp
        cnt+=1
        bin_num = "000"+format(mod, 'b')
        tmp = popcount(bin_num)
        bin_num = int(str(bin_num),2)
    print(cnt)
    #print(sum,cnt_1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict,deque
from sys import stdin,setrecursionlimit
import heapq,bisect,math,itertools,string,queue,copy
setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, stdin.readline().split()))

N = int(input())
X = int(input())
xx = int(str(X),2)

dp = [-1]*(N+3)

def rec(a):
    ico = str(bin(a)).count('1')
    b = a%ico
    if b == 0:
        dp[b] = 1
        return 1
    if dp[b] != -1:
        dp[a] = dp[b] + 1
        return dp[a]
    res = rec(b) +1
    return res

for i in range(N-1,-1,-1):
    han = 2**i
    if xx & han:
        ans = rec(xx-han)
        print(ans)
    else:
        ans = rec(xx+han)
        print(ans)

Submission status: Runtime Error

Solution code:

N = int(input())
X = input()
ans_dic = {}

for n in range(N):
    s = X[:n]
    if X[n] == "0":
        s += "1"
    else:
        s += "0"
    s += X[n+1:]
    first_num  = int(s, 2)
    ans = 0
    num_list = []
    while True:
        one = list(s).count("1")
        num = int(s, 2)
        if num in ans_dic:
            ans += ans_dic[num]
            ans_dic[first_num] = ans
            break

        num_list.append(num)
        amari = num % one
        if amari == 0:
            ans += 1
            for n in range(len(num_list)):
                ans_dic[num_list[n]] = ans - n
            break
        else:
            s = str(bin(amari))[2:]
            ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
import numba
from numba import njit
i8 = numba.int64

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

@njit((i8, ), cache=True)
def popcount(n):
    ret = 0
    while n:
        ret += n & 1
        n >>= 1
    return ret


@njit((i8, ), cache=True)
def f(n):
    t = 0
    while n:
        t += 1
        n %= popcount(n)
    return t

@njit((i8[:]), cache=True)
def main(X):

    popX = X.sum()
    MOD1 = popX + 1
    MOD2 = popX - 1
    if popX == 1:
        MOD2 = 1
    pow1 = np.ones_like(X)
    pow2 = np.ones_like(X)
    for n in range(1, len(X)):
        pow1[n] = 2 * pow1[n - 1] % MOD1
        pow2[n] = 2 * pow2[n - 1] % MOD2

    X1, X2 = 0, 0
    for x in X:
        X1 = (2 * X1 + x) % MOD1
        X2 = (2 * X2 + x) % MOD2

    ans = np.empty(N, np.int64)
    for i in range(N):
        x = X[N - 1 - i]
        if x == 0:
            nxt = (X1 + pow1[i]) % (popX + 1)
            ans[i] = 1 + f(nxt)
        elif x == 1:
            if popX == 1:
                ans[i] = 0
            else:
                nxt = (X2 - pow2[i]) % (popX - 1)
                ans[i] = 1 + f(nxt)
    return ans[::-1]

N = int(readline())
X = np.array(list(read().rstrip()), np.int64) - ord('0')
ans = main(X)
print('\n'.join(map(str, ans.tolist())))

Submission status: Runtime Error

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

def calc_n(x:str):
    de=sum([int(x[i])*2**(len(x)-i-1) for i in range(n)])
    ans=[]
    for i in range(len(x)):
        if x[i]=="0":
            ans.append(de+2**(n-i-1))
        else:
            ans.append(de-2**(n-i-1))
    return ans
  
def popcount(n:int, count:int=0):
    ans=n%list(bin(n)).count('1')
    if ans==0:
        return count+1
    else:
        return popcount(ans,count+1)

for i in calc_n(x):
    print(popcount(i))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from functools import lru_cache

import sys
sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, X):
    @lru_cache(maxsize=None)
    def f(y):
        c = bin(y).count('1')
        if c == 0:
            return 0
        r = y % c

        return 1 + f(r)

    C = X.count('1')
    cmr = 0
    cpr = 0
    for b in X:
        cmr *= 2
        cmr += int(b)
        cmr %= C - 1
        cpr *= 2
        cpr += int(b)
        cpr %= C + 1

    for i in range(N):
        t = 1
        b = 2 ** (N-i-1)
        if X[i] == '0':
            x = (cpr + b) % (C+1)
        else:
            if C-1 == 0:
                x = 0
            else:
                x = (cmr - b) % (C-1)
        while True:
            c = bin(x).count('1')
            # print(x, c)
            if c == 0:
                break
            x = x % c
            t += 1
        print(t)


def main():
    N = read_int()
    X = read_str()
    slv(N, X)

    # import random
    # N = 10**5
    # N *= 2
    # X = ''.join(random.choices('01', k=N))
    # print(slv(N, X))




if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    n = int(input())
    x = input()
    x = '0b'+x

    x = int(x,0)
    m = bin(x).count('1')
    # print(x)

    a = x%(m-1)
    b = x%(m+1)
    # exit()

    ans = dict()
    tmp_a = 1
    tmp_b = 1
    xx = [None] * n

    for i in range(n):
        if (x >> i) &1:
            y = (a - tmp_a)%(m-1)
        else:
            y = (b+tmp_b)%(m+1)
        tmp_a *= 2
        tmp_a %= (m-1)
        tmp_b *= 2
        tmp_b %= (m+1)
        # print(tmp_a,tmp_b)

        z = x ^ (1<<i) 
        t = z
        z %= bin(z).count('1')
        # y = z
        # print(t,z,y)

        cnt = 1
        c = y
        while y != 0:
            # if y in ans.keys():
            #     cnt += ans[y]
            #     break
            cnt += 1
            y = solve(y)
        ans[c] = cnt
        xx[i] = cnt
    
    for i in range(n-1,-1,-1):
        print(xx[i])

def solve(n):
    m = bin(n).count('1')
    return n%m

main()

Submission status: Runtime Error

Solution code:
from itertools import product
from math import log2

N = int(input())
X = input()
m = sum(list(map(int, X)))+1
n = int(log2(m)+1)
f = [0]

i = 0
for p in product([0,1], repeat=n):
    if i>0:
        a = sum(p)
        f.append(f[i%a]+1)
    i += 1

for i in range(N):
    if X[i] == '1':
        x = int(X[0:i]+'0'+X[i+1:], 2)
        a = m-2
    else:
        x = int(X[0:i]+'1'+X[i+1:], 2)
        a = m
    print(f[x%a]+1)

Submission status: Runtime Error

Solution code:
N = int(input())
X = str(input())
x_num_ = 0
x = 0
## 個数カウント
for i,Xi in zip(range(N)[::-1],X):
    x += int(Xi)
    x_num_ += int(Xi)*2**i
## popcount
def popcount(x):
    a = bin(x)[2:]
    b = 0
    for ai in a:
        b += int(ai)
    return b
n = int(2e5)
a = [0]*n
for i in range(n):
    a[i] = popcount(i+1)
##########
b = {0:1}
def f(x):
    ans = 0
    x_ = x%a[x-1]
    if x_ in b:
        ans += b[x_] + 1
    else:
        ans += f(x_) + 1
    return ans - 1
##########
for i,Xi in zip(range(N)[::-1],X):
    ans = 0
    if Xi == '1':
        x_num = (x_num_ - 2**i)%(x - 1)
    else:
        x_num = (x_num_ + 2**i)%(x + 1)
    if x_num in b:
        ans += b[x_num]
    else:
        b[x_num] = f(x_num) + 1
        ans += b[x_num]
    print(ans)

Submission status: Runtime Error

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

n = int("1"+X, 2)

popcounts = [0] * n
fs = [0] * n
fs[0] = 1

def popcount(n):
  if popcounts[n] ==0:
    popcounts[n] = bin(n).count("1")
  return popcounts[n]


def f(n):
  if fs[n] == 0:
    count = 1
    count += f(n%popcount(n))
    fs[n] = count
  return fs[n]

def turn(bn, n):
  bn_turned = bn
  if bn[n] == "1":
    bn_turned = bn_turned[:n] + "0" + bn_turned[n+1:]
  else:
    bn_turned = bn_turned[:n] + "1" + bn_turned[n+1:]
  return int(bn_turned, 2)


for i in range(N):
  print(f(turn(X, i))-1)

Submission status: Runtime Error

Solution code:


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


def main(N, X):
    check = "0"*N
    for i in range(N):
        check = check[:i]+"1"+check[i+1:]
        x = int(X, 2)
        if int(check, 2) & x == int(check, 2):
            x -= int(check, 2)
        else:
            x += int(check, 2)
        count = 0
        while True:
            if x == 0b0:
                print(count)
                break
            x = x % popcount(x)
            count += 1
        check = "0"*N


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

main(N, X)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
x = int(input().rstrip(),2)
#print(x)
anslist = []

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
def toggle_nth_bit(num: int, n: int):
    return num ^ (1 << n)


for i in range(n):
    '''
    b = list(x)
    if b[n-i] == '1':
        b[n-i] = '0'
    else:
        b[n-i] = '1'
    p = int(''.join(b),2)
    '''
    p = toggle_nth_bit(x,i)
    #print(p)
    ans = 0
    while True:
        if p == 0:
            break
        p = p%popcount(p)
        ans += 1
    anslist.append(ans)

for i in range(len(anslist)-1,-1,-1):
    print(anslist[i])

Submission status: Runtime Error

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

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
# Python3 implementation of the approach 

# Function to return the value of (str % k) 
def getMod(_str, n, k) : 

	# pwrTwo[i] will store ((2^i) % k) 
	pwrTwo = [0] * n 
	pwrTwo[0] = 1 % k 
	for i in range(1, n): 
		pwrTwo[i] = pwrTwo[i - 1] * (2 % k) 
		pwrTwo[i] %= k 

	# To store the result 
	res = 0
	i = 0
	j = n - 1
	while (i < n) : 

		# If current bit is 1 
		if (_str[j] == '1') : 

			# Add the current power of 2 
			res += (pwrTwo[i]) 
			res %= k 
			
		i += 1
		j -= 1

	return res 


bc = 0
for b in X:
    if b == '1':
        bc += 1

ans = []
for i in range(N):

    if X[i] == '0':
        t = "".join(X[:i]) + '1' + "".join(X[i+1:])
        k = bc
    else:
        t = "".join(X[:i]) + '0' + "".join(X[i+1:])
        k = bc-1
    
    m = getMod(t, N, k)
    cnt = 1

    while m != 0:
        t = popcount(m)
        m = m%t
        cnt += 1

    ans.append(cnt)

for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
import math
n = int(input())
s= input()
t=s.count("1")
bit=0
for i in range(n-1,-1,-1):
    if s[i]=="1":
        bit+=2**(n-1-i)
a=[0 for i in range(t+4)]
a[0]=0
a[1]=1
a[2]=1

for j in range(3,t+1):
    r=j
    cnt=0
    while (r != 0): 
        if(r % 2 == 1):  
            cnt += 1
        
        r //= 2
        
    a[j]=1+a[j%cnt]

bit1=bit%(t-1)
bit2=bit%(t+1)
for i in range(n):
    if s[i]=="0":
       
        print(1+a[(bit2+2**(n-1-i))%(t+1)])
    else:

        print(1+a[((bit1-2**((n-1-i))%(t-1))%(t-1))])

Submission status: Runtime Error

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

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

number = 0
now =len(s)
for i in range(len(s)):
    if(s[i]=='1'):
        number+=pow(2,now-1)
    now-=1
#print(number)
for i in range(n):
    #$print(str(n)+" "+str(i))
    ss = s
    cal = number
    ccnt = cnt
    if(s[i]=='0'):
        cal+=pow(2,n-i-1)
        ccnt+=1
    else:
        cal-=pow(2,n-i-1)
        ccnt-=1
    x = cal%ccnt
    #print(str(cal)+" "+str(ccnt))
    if(x==0):
        print(1)
    elif x%2==0:
        print(2)
    elif x==1:
        print(2)
    else:
        print(3)

Submission status: Runtime Error

Solution code:
# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
from collections import Counter
import queue
import copy
import bisect
import heapq
import itertools

def unko(abc):
    count = 0
    while True:
        b=bin(abc)
        pop = b.count("1")
        if(abc%pop==0):
            count+=1
            return count
        else:
            abc = abc%pop
            count+=1


sys.setrecursionlimit(10**7)
#N, Q = map(int, input().split())
#G = [list(input()) for i in range(H)]
#INF = V * 10001
#A = [int(i) for i in input().split()]
#AB = [list(map(int, input().split())) for _ in range(K)]

N = int(input())
XX = list(input())
temp= ""
xx = 0

for i in range(N):
    X= copy.deepcopy(XX)
    if(X[i]=="0"):
        X[i]="1"
    else:
        X[i]="0"
    temp = "".join(X)
    xx = int(temp, 2)
    print(unko(xx))

Submission status: Runtime Error

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

def ans(X):
    if X == 0: return 0
    X = X % (bin(X).count('1'))
    return 1+ans(X)

# test case injection
if False:
    import random
    X = ''.join(random.choice("1") for _ in range(2*10**5))
    N = len(X)
    # print(N, X)
    # exit(0)
else:
    N = int(input())
    X = input()

N = N-1

popcount = X.count('1')
X_int = int(X, 2)

import array

two_pow_mod_pc_plus = array.array('i', [0]*(N+1))
two_pow_mod_pc_minus = array.array('i', [0]*(N+1))

two_pow_mod_pc_plus[0] = 1 % (popcount+1)
two_pow_mod_pc_minus[0] = 1 % (popcount-1)

for i in range(1, len(two_pow_mod_pc_plus)):
    two_pow_mod_pc_plus[i] = (2*two_pow_mod_pc_plus[i-1]) % (popcount+1)

for i in range(1, len(two_pow_mod_pc_minus)):
    two_pow_mod_pc_minus[i] = (2*two_pow_mod_pc_minus[i-1]) % (popcount-1)

X_mod_pc_plus = X_int % (popcount+1)
X_mod_pc_minus = X_int % (popcount-1)

for i, x in enumerate(X):
    # if i % 1000 == 0: print(i)
    if x == '0':
        r = 1 + ans((X_mod_pc_plus + two_pow_mod_pc_plus[N-i]) % (popcount+1))
    else:
        if popcount == 1:
            print(0)
        else:
            r = 1 + ans((X_mod_pc_minus - two_pow_mod_pc_minus[N-i]) % (popcount-1))
    print(r)

Submission status: Runtime Error

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

c1 = x.count('1')
cc1 = int('0b' + x, 0) % (c1 - 1)
cc2 = int('0b' + x, 0) % (c1 + 1)

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

for i in range(n):
    if x[i] == '1':
        print(f((pow(2, n-i-1, c1-1) + cc1) % (c1 - 1)) + 1)
    else:
        print(f((pow(2, n-i-1, c1+1) + cc2) % (c1 + 1)) + 1)

Submission status: Runtime Error

Solution code:
# @author 

import sys

class DAnythingGoesToZero:
    def solve(self, tc=0):
        n = int(input())
        # n = 10 ** 5
        x = input().strip()
        cache = [-1] * (n + 1)
        cache[0] = 0
        for nb in range(n + 1):
            v = 0
            i = nb
            while cache[i] == -1:
                i %= bin(i).count('1')
                v += 1

            cache[nb] = v + cache[i]

        # print(cache[8191])

        def brem(N, D):
            n = len(N)
            R = 0
            for i in range(n - 1, -1, -1):
                R <<= 1
                R |= int(N[n - 1 - i])
                if R >= D:
                    R -= D
            return R

        x = list(x)
        ones = x.count('1')
        r1 = brem(x, ones + 1)
        r2 = brem(x, ones - 1) if ones != 0 else 0
        for i in range(n):
            if x[i] == '0':
                # print((r + pow(2, n - 1 - i, ones + 1)) % (ones + 1), '*')
                print(cache[(r1 + pow(2, n - 1 - i, ones + 1)) % (ones + 1)] + 1)
            else:
                print(cache[(r2 - pow(2, n - 1 - i, ones - 1)) % (ones - 1)] + 1)
            # x[i] = str(int(x[i]) ^ 1)
            # print(cache[brem(x, x.count('1'))] + 1)
            # x[i] = str(int(x[i]) ^ 1)

solver = DAnythingGoesToZero()
input = sys.stdin.readline

solver.solve()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from functools import lru_cache

import sys
sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, X):
    @lru_cache(maxsize=None)
    def f(y):
        c = bin(y).count('1')
        if c == 0:
            return 0
        r = y % c

        return 1 + f(r)

    C = X.count('1')
    cmr = 0
    cpr = 0
    for b in X:
        cmr *= 2
        cmr += int(b)
        cmr %= C - 1
        cpr *= 2
        cpr += int(b)
        cpr %= C + 1

    for i in range(N):
        t = 1
        b = 2 ** (N-i-1)
        if X[i] == '0':
            x = (cpr + b) % (C+1)
        else:
            x = (cmr - b) % (C-1)
        while True:
            c = bin(x).count('1')
            # print(x, c)
            if c == 0:
                break
            x = x % c
            t += 1
        print(t)


def main():
    N = read_int()
    X = read_str()
    slv(N, X)

    # import random
    # N = 10**5
    # N *= 2
    # X = ''.join(random.choices('01', k=N))
    # print(slv(N, X))




if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N=int(input())
Xl=list(map(int,list(input())))
#X=int(input())
#print(Xl)

def func(x):
  cnt=0
  while x>0:
    num1=0
    xcopy=x
    while xcopy:
      if xcopy&1:
        num1+=1
      xcopy>>=1
      
    #print(x,num1)
    x=x%num1
    cnt+=1
  return cnt

func_dic={}
for i in range(N):
  func_dic[i]=func(i)
#print(func_dic)

num1_X=Xl.count(1)
#print(num1_X)

mod_nminus=0
mod_nplus=0
for i in range(N):
  mod_nminus*=2
  mod_nplus*=2
  if Xl[i]==1:
    mod_nminus+=1
    mod_nplus+=1

  mod_nminus%=num1_X-1
  mod_nplus%=num1_X+1
#print(mod_nminus,mod_nplus)

answer_list=[]
modpow_plus=1
modpow_minus=1
for i in reversed(range(N)):
  if Xl[i]==0:
    mod=(mod_nplus+modpow_plus)%(num1_X+1)
    answer_list.append(func_dic[mod]+1)
  else:
    if num1_X-1==0:
      answer_list.append(0)
    else:
      mod=(mod_nminus-modpow_minus)%(num1_X-1)
      answer_list.append(func_dic[mod]+1)
  
  modpow_plus*=2  
  modpow_plus%=num1_X+1
  if num1_X-1>0:
    modpow_minus*=2
    modpow_minus%=num1_X-1
  
for i in reversed(range(N)):
  print(answer_list[i])

Submission status: Runtime Error

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

def rev(num, i):
  i = N - 1 - i
  return num ^ (1 << i)



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



for i in range(N):
  X = rev(X, i)
    
  fn = X
  cnt = 0
  
  while fn != 0:
    fn = fn % popcount(fn)
    cnt += 1
  print(cnt)
  
  X = rev(X, i)

Submission status: Runtime Error

Solution code:
from collections import defaultdict,deque
from sys import stdin,setrecursionlimit
import heapq,bisect,math,itertools,string,queue,copy
setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, stdin.readline().split()))

N = int(input())
X = int(input())
xx = int(str(X),2)

dp = [-1]*(xx+1)

def rec(a):
    ico = str(bin(a)).count('1')
    b = a%ico
    if b == 0:
        dp[b] = 1
        return 1
    if dp[b] != -1:
        dp[a] = dp[b] + 1
        return dp[a]
    res = rec(b) +1
    return res
    
for i in range(N-1,-1,-1):
    han = 2**i
    if xx & han:
        ans = rec(xx-han)
        print(ans)
    else:
        ans = rec(xx+han)
        print(ans)

Submission status: Runtime Error

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


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

def g(n, m):
    if n < 60:
        return (1 << n) % m
    else:
        t = n // 2
        return g(t, m) * g(n - t, m) % m


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

c = X.count('1')
t1 = [0] * N
t2 = [0] * N
for i in range(N):
    n = N - 1 - i
    t1[i] = g(n, c - 1)
    t2[i] = g(n, c + 1)

x1, x2 = 0, 0
for i in range(N):
    if X[i] == '1':
        x1 += t1[i]
        x2 += t2[i]

result = []
for i in range(N):
    if X[i] == '1':
        n = x1 - t1[i]
        n %= c - 1
    elif X[i] == '0':
        n = x2 + t2[i]
        n %= c + 1
    t = 1
    while n != 0:
        n %= popcount(n)
        t += 1
    result.append(t)
print(*result, sep='\n')

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
def main():
    n = int(input())
    s = int(input(), 2)
    pc0 = bin(s).count("1")
    ans = []
    for i in range(n):
        k = 1 << (n - 1 - i)
        x = k ^ s
        if x >= s:
            pc1 = pc0 + 1
        else:
            pc1 = pc0 - 1
        x %= pc1
        cnt = 1
        while x > 0:
            pc = bin(x).count("1")
            x %= pc
            cnt += 1
        ans.append(cnt)
    print("\n".join(str(y) for y in ans))
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
x_bin = list(input())
for i in range(n):
    x_cp = x_bin.copy()
    if x_bin[i] == '0':
        x_cp[i] = '1'
    else:
        x_cp[i] = '0'
    x = ""
    for j in range(len(x_bin)):
        x += x_cp[j]
    x_cnt = x.count('1')
    x = int(x, 2)
    cnt = 1
    if x % x_cnt == 0:
        print(cnt)
    else:
        while x % x_cnt > 0:
            cnt += 1
            x = x % x_cnt
            x_cnt = str(bin(x)).count("1")
        print(cnt)