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:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


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):
        # print(y)
        c = y.count('1')
        r = 0
        for b in y:
            b = int(b)
            r *= 2
            r += b % c
        r %= c
        if r == 0:
            return 1

        return 1 + f(bin(r)[2:])

    X = [x for x in X]
    for i in range(N):
        b = X[i]
        if X[i] == '1':
            X[i] = '0'
        else:
            X[i] = '1'
        # print(X)
        print(f(''.join(X)))
        X[i] = b


def main():
    N = read_int()
    X = read_str()
    print(slv(N, X))
    # 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:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
import random
from collections import deque
from decimal import *
import queue

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	X = inputStr()
	X_lin = list(X)

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

		oct = int(tmpX, 2)

		ans_tmp = 0
		while True:
			if oct == 0:
				break
			tmp = popcnt5(oct)
			oct = oct % tmp
			ans_tmp += 1
		ans.append(ans_tmp)

	for i in ans:
		print(i)

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


#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Runtime Error

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

memo = dict()


def f(n, c1, cnt):
    cnt += 1
    m = n % c1
    memo[n] = m
    if m == 0:
        return cnt
    else:
        return f(m, bin(m).count("1"), 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 = int(input())
X = input()
Xi = int(X, 2)

c0 = X.count('1')
Xp = Xi % (c0 + 1)
Xm = Xi % (c0 - 1)

for i, x in enumerate(X):
    if x == '1':
        if c0 == 1:
            print(0)
            continue
        y = (Xm - pow(2, N - 1 - i, c0 - 1)) % (c0 - 1)
    else:
        y = (Xp + pow(2, N - 1 - i, c0 + 1)) % (c0 + 1)

    ans = 1
    while y:
        y %= bin(y).count('1')
        ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
def popcount(x):
    return bin(x)[2:].count("1")

def f(x):
    cnt=0
    while(x>0):
        x%=popcount(x)
        cnt+=1
    return cnt

n=int(input())
s=input()
d=s.count("1")
s=s[::-1]
toaddm=1
toaddM=1
m=0
M=0
for i in range(n):
    if s[i]=="1":
        m+=toaddm
        M+=toaddM
        m%=d-1
        M%=d+1
    toaddm*=2
    toaddm%=d-1
    toaddM*=2
    toaddM%=d+1
toaddm=-1
toaddM=1
res=[None for i in range(n)]
for i in range(n):
    if s[i]=="1":
        res[i]=f((m+toaddm)%(d-1))+1
    else:
        res[i]=f((M+toaddM)%(d+1))+1
    toaddm*=2
    toaddm%=d-1
    toaddM*=2
    toaddM%=d+1
for i in res[::-1]:
    print(i)

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
S = len(str(X))

k = [0,1,1,2,1,2,1,2,1,2,1,2,1,2,2,3,1,2] #17まで

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

for i in range(S):
    if X[i] == "1":
        waru = c-1
    else:
        waru = c+1
    #print(waru)
    atai = 0
    for j in range(S):
        if i != j:
            atai += 2**(S-1-j)*int(X[j])
        else:
            atai += 2**(S-1-j)* ((int(X[j])+1)%2)

    nex = atai % waru
    print(1+k[nex])

Submission status: Runtime Error

Solution code:
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())
x=int(input(),2)

A=[]
for i in range(n):
    num=x^(2**i)
    cnt=0
    while num!=0:
        num %=popcount(num)
        cnt +=1
    A.append(cnt)

for i in A[::-1]:
    print(i)

Submission status: Runtime Error

Solution code:
def popcount(n,ans):
	if n==0: return ans
	ne = n%str(bin(n)).count("1")
	ans = popcount(ne,ans+1)
	return ans


n = int(input())
s = input()
d = str(bin(int(s,2))).count("1")
for i in range(n):
	if s[i] == "1":
		temp_d = d-1
		temp = int(s[:i] + "0" + s[i+1:],2)
	else:
		temp_d = d+1
		temp = int(s[:i] + "1" + s[i+1:],2)
	next_temp = temp%temp_d
	print(popcount(next_temp,1))

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline

n = int(input())
y = str(input())
ones = 0
for i in y:
    if i == '1': ones += 1
x = int(y, 2)

def get(z):
    ret = 0
    while z > 0:
        if z % 2 == 1:
            ret += 1
        z //= 2
    return ret

out = []
for i in range(n):
    tmp = (1 << i) * -1
    o = ones - 1
    if y[n - i - 1] == '0':
        tmp = 1 << i
        o = ones + 1

    tmp = tmp + x
    if tmp == 0:
        out.append(0)
    cnt = 1
    tmp %= o
    while tmp > 0:
        tmp %= get(tmp)
        cnt += 1

    out.append(cnt)

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

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
import random
from collections import deque
from decimal import *
import queue

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	X = inputStr()
	X_lin = list(X)

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

		oct = int(tmpX, 2)

		ans_tmp = 0
		while True:
			if oct == 0:
				break
			tmp = popcnt5(oct)
			oct = oct % tmp
			ans_tmp += 1
		ans.append(ans_tmp)

	for i in ans:
		print(i)

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


#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
import collections
n = int(raw_input())
x = int(raw_input(),2)
mem = [-1] * (n+1)
mem[0] = 0
def f(x):
	if mem[x] != -1:
		return mem[x]
	cc=  collections.Counter(bin(x))
	if x % cc['1'] == 0: 
		mem[x] = 1
		return 1
	mem[x] = 1 + f(x % cc['1'])
	return 1 + f(x % cc['1'])

for i in range(n - 1, -1, -1):
	print f(x ^ (1 << i))

Submission status: Runtime Error

Solution code:
def popcount(n):
    count = 0
    while n:
        if n & 1:
            count += 1
        n >>= 1
    return count


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

for n in range(N):
    x = X ^ (1 << N-n-1)
    count = 0
    while True:
        x = x % popcount(x)
        count += 1
        if not x:
            break
    print(count)

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

for i in range(n):
  y = list(x)
  if y[i] == '0':
    y[i] = '1'
    c = cnt+1
  else:
    y[i] = '0'
    c = cnt-1
  z = int(''.join(y),2)
  print(calc(z%c)+1)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from collections import *

def f(i):
    if X[i]=='0':
        nex = (d[p+1]+pow(2, N-1-i, p+1))%(p+1)
    elif X[i]=='1':
        nex = (d[p-1]-pow(2, N-1-i, p-1))%(p-1)
    
    res = 1
    
    while nex>0:
        pc = 0
        
        for i in range(20):
            if (nex>>i)&1:
                pc += 1
        
        nex %= pc
        res += 1
    
    return res

N = int(input())
X = input()[:-1]

if X=='0'*N:
    for i in range(N):
        print(1)
    exit()
    
p = 0

for Xi in X:
    if Xi=='1':
        p += 1

d = defaultdict(int)

for i in [p-1, p, p+1]:
    for j in range(N):
        if X[j]=='1':
            d[i] += pow(2, N-1-j, i)

for i in range(N):
    print(f(i))

Submission status: Runtime Error

Solution code:
import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def popcount(x):
    x = x - ((x >> 1) & 0x55555555)
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    return x & 0x0000007f

def solve():
    n = ni()
    X = list(map(int, list(ns())))
    p = sum(X)
    pl, ps = p+1, p-1

    g = [-1] * (n+5)
    g[0] = 0
    for i in range(1, n+5):
        g[i] = g[i % popcount(i)] + 1
    ql = qs = 0
    for x in X:
        ql = (ql * 2 + x) % pl
        if ps > 0:
            qs = (qs * 2 + x) % ps
    vl = vs = 1
    ans = [0]*n
    for i in range(n-1, -1, -1):
        if X[i]:
            if ps > 0:
                ans[i] = g[(qs-vs)%ps] + 1
        else:
            ans[i] = g[(ql+vl)%pl] + 1
        vs = vs * 2 % ps
        vl = vl * 2 % pl
    prn(ans)
    return

solve()

Submission status: Runtime Error

Solution code:
def popcount(x):
  S = format(x,'b')
  cnt = 0
  for s in S:
    if s=='1':
      cnt+=1
  return cnt
def solve():
  N = int(input())
  X = input()
  num = 0
  pcnt = 0
  for i, x in enumerate(X):
    if x=='1':
      pcnt += 1
      num += 2**(N-i-1)
  for i, x in enumerate(X):
    ans = 1
    if x=='1':
      n1 = (num-2**(N-i-1))%(pcnt-1)
    else:
      n1 = (num+2**(N-i-1))%(pcnt+1)
    while n1 != 0:
      pc = popcount(n1)
      n1 = n1%pc
      ans +=1
    print(ans)
solve()

Submission status: Runtime Error

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

l = 2*10**5 + 5
A = [0] * l
for i in range(1,l):
    ab = format(i, "b")
    abo = ab.count("1")
    A[i] = i % abo

B = [-1] * l
B[0] = 0
# print(A[:10])

def dd(y):
    # print(y)
    if B[y] == -1:
        return dd(A[y])+1
    else:
        return B[y]

for i in range(1, l):
    # print(dd(i))
    B[i] = dd(i)

# print(B[:10000])

m = x.count("1")
m0 = m-1
m1 = m+1
M0 = [1]
M1 = [1]
for i in range(l):
    M0.append((M0[-1]*2) % m0)
    M1.append((M1[-1]*2) % m1)

n0 = 0
n1 = 0
for i in range(n):
    if x[n-1-i] == "1":
        n0 = (n0 + M0[i]) % m0
        n1 = (n1 + M1[i]) % m1

for i in range(n):
    nn = 0
    if x[i] == "1":
        nn = (n0 - M0[n-i-1]) % m0
    else:
        nn = (n1 + M1[n-i-1]) % m1
    print(B[nn]+1)

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
Xn = int(X, 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


memo = [-1] * (2 * 10 ** 5 + 1)
for i in range(N):
    d = 1 << (N - i - 1)
    if X[i] == '0':
        n = Xn + d
    else:
        n = Xn - d

    cnt = 0
    ni = -1
    while n:
        p = popcount(n)
        n = n % p
        if ni == -1:
            ni = n

        if memo[n] != -1:
            cnt += memo[n]
            break

        cnt += 1

    print(cnt)
    memo[ni] = cnt

Submission status: Runtime Error

Solution code:
n,x=int(input()),input()
g=int(x,2)
c=pow(2,n-1)
j=x.count("1")

for b in x:
    if b=="1":
        p=g-c
        q=j-1
    else:
        p=g+c
        q=j+1
    p%=q
    ret=1
    while p:
        p%=bin(p).count("1")
        ret+=1
    c//=2
    print(ret)

Submission status: Runtime Error

Solution code:
from functools import lru_cache
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)


@lru_cache(None)
def popcount(n):
    return list(bin(n)[2:]).count("1")


@lru_cache(None)
def f(n, cnt):
    _tmp = n % popcount(n)
    if _tmp == 0:
        return cnt + 1
    else:
        return f(_tmp, cnt+1)


def main():
    N = int(input().strip())
    X = list(input().strip())
    for i in range(N):
        if X[i] == "0":
            X[i] = "1"
            _tmp = int("".join(X), 2)
            X[i] = "0"
        else:
            X[i] = "0"
            _tmp = int("".join(X), 2)
            X[i] = "1"
        print(f(_tmp, 0))
    return


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

n = int(input())
x = [int(item) for item in list(input().rstrip())]
x.reverse()

ones = x.count(1)
aug = ones + 1
dim = ones - 1

modaug = 0
moddim = 0
for i, item in enumerate(x):
    if item == 1:
        modaug += pow(2, i, aug)
        modaug %= aug
        moddim += pow(2, i, dim)
        moddim %= dim

cnt = [-1] * (2*10**5 + 1)
cnt[0] = 0; cnt[1] = 1
for i in range(1, 2*10**5 + 1):
    val = i
    num = bin(val).count("1")
    cnt[i] = cnt[val % num] + 1

ans = []
for i, item in enumerate(x):
    if item == 0:
        tmp = modaug + pow(2, i, aug)
        tmp %= aug
    else:
        tmp = moddim - pow(2, i, dim)
        tmp %= dim
    ans.append(cnt[tmp] + 1)

ans.reverse()
for item in ans:
    print(item)

Submission status: Runtime Error

Solution code:

N = int(input())

X = input()

o = 0
cnt = 0
for i in X:
    o *= 2
    if i == "1":
        o += 1
        cnt += 1

orev = [o % (cnt+1) , o % (cnt-1)]

for i in range(N):

    nb = int(X[i])

    if nb == 0:
        mod = cnt+1
        now = (orev[0] + pow(2,N-1-i,mod)) % mod

        ans = 1
        while now != 0:
            s = format( now , 'b' )
            one = 0
            for j in s:
                if j == "1":
                    one += 1
            now %= one
            ans += 1

        print (ans)

    else:
        mod = cnt-1
        now = (orev[1] - pow(2,N-1-i,mod)) % mod

        ans = 1
        while now != 0:
            s = format( now , 'b' )
            one = 0
            for j in s:
                if j == "1":
                    one += 1
            now %= one
            ans += 1

        print (ans)

Submission status: Runtime Error

Solution code:
N = int(input())
X = list(input())
P = X.count("1")
P1 = 0
P2 = 0
for i in range(N):
    if X[i] == "1":
        P1 += pow(2,N-i-1,P-1)
        P1 %= P-1
        P2 += pow(2,N-i-1,P+1)
        P2 %= P+1
for i in range(N):
    count = 1
    if X[i] == "0":
        cur = P2+pow(2,N-i-1,P+1)
        cur %= P+1
    else:
        cur = P1-pow(2,N-1-i,P-1)
        cur %= P-1
    while cur > 0:
        mod = bin(cur).count("1")
        cur %= mod
        count += 1
    print(count)

Submission status: Runtime Error

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

P = S.count('1')
Rp = X % (P+1)
Rn = X % (P-1)


@lru_cache(None)
def popcnt(x):
    return bin(x).count('1')

mask = 1 << N
for i in range(N-1, -1, -1):
    mask >>= 1
    
    x = X ^ mask
    if x == 0:
        print(0)
        continue

    if X & mask:
        p = P-1
        x = (Rn - pow(2, i, p)) % p
    else:
        p = P+1
        x = (Rp + pow(2, i, p)) % p

    cnt = 1
    while x:
        x %= popcnt(x)
        cnt += 1
    print(cnt)

Submission status: Runtime Error

Solution code:
def find(x,ones):
    total = 0
    n = len(x)
    for i in range(n):
        total += int(x[i])*pow(2,n-i-1,ones)
        total %= ones

    return total

def solve(x,mod):
    x %= mod
    moves = 1
    while x != 0:
        x = x%(bin(x)[2:].count('1'))
        moves += 1

    return moves

def main():
    n = int(input())
    x = input()
    ones = x.count('1')
    less = find(x,ones-1)
    more = find(x,ones+1)
    for i in range(n):
        if x[i] == '0':
            print(solve(more+pow(2,n-i-1,ones+1),ones+1))
        else:
            if ones-1 == 0:
                print(0)
            else:
                print(solve(less-pow(2,n-i-1,ones-1),ones-1))


main()

Submission status: Runtime Error

Solution code:
from copy import copy


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

for index, i in enumerate(X):
    X_i = copy(X)
    X_i[index] = abs(i - 1)
    X_i = [y * (2 ** (len(X_i) - 1 - x)) for x, y in enumerate(X_i)]
    X_i = bin(sum(X_i))
    count = 0
    while True:
        count += 1
        popcount = X_i.count("1")
        X_i = int(X_i, 2) % popcount
        if X_i == 0:
            break
        X_i = bin(X_i)
    print(int(count))

Submission status: Runtime Error

Solution code:
def function(n,k):
  s=list(bin(n)[2:])
  c=s.count("1")
  k+=1
  if n%c==0:
    return k
  else:
    return function(n%c,k)
N=int(input())
X=list(input())
for i in range(N):
  if X[i]=="1":
    X[i]="0"
  else:
    X[i]="1"
  print(function(int("".join(X),2),0))
  if X[i]=="1":
    X[i]="0"
  else:
    X[i]="1"

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    mem = defaultdict(lambda : None)
    mem[0] = 0
    cnt = [0]
    for _ in range(20):
        cnt = [x+i for i in range(2) for x in cnt]
    def dfs(x):
        if mem[x] is not None:
            return mem[x]
        p = cnt[x]
        res = dfs(x%p)+1
        mem[x] = res
        return res
    n = I()
    x = list(map(int, input()))
    cnt_x = sum(x)
    s = 0
    p = 1
    for i in range(n):
        s += x[-i-1]*p
        p <<= 1
    p >>= 1
    for i in range(n):
        x = s^p
        k = cnt_x-1 if s&p else cnt_x+1
        print(dfs(x%k)+1)
        p >>= 1
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:

n = int(input())
s=input()
p=0
c=0
for i in range(n):
    if s[i]=='1':
        p+=2**(n-i-1)
        c+=1
for i in range(n):
    k=p
    z=c
    if s[i]=='0':
        k+=2**(n-i-1)
        z+=1
    else:
        k-=2**(n-i-1)
        z-=1
    l=1
    while k%z>0:
        k%=z
        z=bin(k).count('1')
        l+=1
    print(l)

Submission status: Runtime Error

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from scipy.sparse.csgraph import floyd_warshall
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations, combinations_with_replacement
from heapq import heappop, heappush, heapify
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def main():
    n = int(input())
    x = list(input())
    for i in range(n):
        x[i] = int(x[i])
    A = 0
    for i in range(n):
        A += x[i]*pow(2,n-i-1)
    B = sum(x)
    for i in range(n):
        if x[i] == 0:
            AA = A + pow(2,n-i-1)
            BB = B + 1
        else:
            AA = A - pow(2,n-i-1)
            BB = B - 1
        ans = 1
        while AA%BB:
            AA = AA%BB
            AAA = copy.deepcopy(AA)
            BB = 0
            while AAA != 0:
                BB += AAA%2
                AAA //= 2
            ans += 1
        print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from functools import lru_cache


@lru_cache(maxsize=1000000)
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


@lru_cache(maxsize=1000000)
def f(x, n=0):
    if x == 0:
        return n
    return f(x % popcount(x), n + 1)


def resolve():
    n = int(input())
    x = int(input(), 2)
    for i in range(n):
        print(f(x ^ (1 << (n - i - 1))))


if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

Solution code:
def main():
    n = int(input())
    bit = input()[::-1]
    count = bit.count("1")
    count_plus = count+1
    count_minus = count-1
    pow_plus = [1 % count_plus]
    pow_minus = [1 % count_minus]
    for i in range(n):
        pow_plus.append(pow_plus[-1]*2 % count_plus)
    for i in range(n):
        pow_minus.append(pow_minus[-1]*2 % count_minus)

    bit_plus = 0
    bit_minus = 0

    for i in range(n):
        if bit[i] == "1":
            bit_plus = (bit_plus+pow_plus[i]) % count_plus
    for i in range(n):
        if bit[i] == "1":
            bit_minus = (bit_minus+pow_minus[i]) % count_minus
    ans = []
    for i in range(n):
        if bit[i] == "1":
            bit_ans = (bit_minus-pow_minus[i]) % count_minus
            count = count_minus
            if count_minus == 0:
                ans.append(0)
                continue
        else:
            bit_ans = (bit_plus+pow_plus[i]) % count_plus
            count = count_plus
        cnt = 1
        while bit_ans:
            b = str(bin(bit_ans)).count("1")
            bit_ans = bit_ans % b
            cnt += 1
        ans.append(cnt)
    for i in ans[::-1]:
        print(i)


main()

Submission status: Runtime Error

Solution code:
def find(x,ones):
    total = 0
    n = len(x)
    for i in range(n):
        total += int(x[i])*pow(2,n-i-1,ones)
        total %= ones

    return total

def solve(x,mod):
    if mod == 0:
        return 0
    x %= mod
    moves = 1
    while x != 0:
        x = x%(bin(x)[2:].count('1'))
        moves += 1

    return moves

def main():
    n = int(input())
    x = input()
    ones = x.count('1')
    less = find(x,ones-1)
    more = find(x,ones+1)
    for i in range(n):
        if x[i] == '0':
            print(solve(more+pow(2,n-i-1,ones+1),ones+1))
        else:
            print(solve(less-pow(2,n-i-1,ones-1),ones-1))


main()

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    X = input()
    MOD = 0
    for elem in X:
        if elem == '1':
            MOD += 1
    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
    MODP1 = MOD + 1
    MODM1 = MOD - 1
    POWEROFTWOP1 = [1]
    if MODM1 != 1:
        POWEROFTWOM1 = [1]
    else:
        POWEROFTWOM1 = [0]
    for i in range(N-1):
        POWEROFTWOP1.append((POWEROFTWOP1[-1] * 2) % MODP1)
        POWEROFTWOM1.append((POWEROFTWOM1[-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
        cnt = 1
        while anscur != 0:
            ans2 = bin(anscur)[2:]
            oneCount = 0
            for elem in ans2:
                if elem == '1':
                    oneCount += 1
            anscur = anscur % oneCount
            cnt += 1
        ans += str(cnt)
        if i != N-1:
            ans += '\n'
    print(ans)
                    
main()

Submission status: Runtime Error

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
x=list(input())
cnt=Counter(x)
# print(x)
# print(math.log2(2*10**5))

def wari(now):
    tmp=cnt["1"]
    if flag=="1":
        tmp-=1
    else:
        tmp+=1
    now%=tmp
    if now==0:
        return 1
    ans=1
    while now:
        cnt2=Counter(bin(now))
        now%=cnt2["1"]
        ans+=1
    return ans

for i in range(n):
    flag=x[i]
    if flag=="0":
        x[i]="1"
    else:
        x[i]="0"
    now=int("".join(x),2)
    # print(now)
    print(wari(now))
    x[i]=flag

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
d = [0] * n
t = x.count('1')
a = 0
b = 0
for i in range(n):
    a *= 2
    b *= 2
    if x[i] == '1':
        a += 1
        b += 1
    a %= t + 1
    b %= t - 1
for i in range(n):
    if x[i] == '1':
        d[i] = (b - pow(2, n - i - 1, t - 1)) % (t - 1)
    else:
        d[i] = (a + pow(2, n - i - 1, t + 1)) % (t + 1)
if t == 1:
    for i in range(n):
        if x[i] == '1':
            print(0)
        else:
            p = d[i]
            for p in d:
                ans = 1
                while p > 0:
                    p %= bin(p).count('1')
                    ans += 1
                print(ans)
else:
    for p in d:
        ans = 1
        while p > 0:
            p %= bin(p).count('1')
            ans += 1
        print(ans)

Submission status: Runtime Error

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
X=input()
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

F=[0]*(n+1)
F[1]=1
F[2]=1
for i in range(3,n+1):
  F[i]=1+F[i%popcount(i)]

ct=X.count("1")
if ct==0:
  for _ in range(n):
    print(1)
else:
  a,b=0,0
  for i in range(n):
    if X[n-1-i]=="1":
      a=(a+pow(2,i,ct-1))%(ct-1)
      b=(b+pow(2,i,ct+1))%(ct+1)
  for i in range(n):
    if X[i]=="0":
      print(F[(b+pow(2,n-1-i,ct+1))%(ct+1)]+1)
    else:
      print(F[(a-pow(2,n-1-i,ct-1))%(ct-1)]+1)

Submission status: Runtime Error

Solution code:
def find(x,ones):
    if ones == 0:
        return False
    total = 0
    n = len(x)
    for i in range(n):
        total += int(x[i])*pow(2,n-i-1,ones)
        total %= ones

    return total

def solve(x,mod):
    x %= mod
    moves = 1
    while x != 0:
        x = x%(bin(x)[2:].count('1'))
        moves += 1

    return moves

def main():
    n = int(input())
    x = input()
    ones = x.count('1')
    less = find(x,ones-1)
    more = find(x,ones+1)
    for i in range(n):
        if x[i] == '0':
            print(solve(more+pow(2,n-i-1,ones+1),ones+1))
        else:
            print(solve(less-pow(2,n-i-1,ones-1),ones-1))


main()