Problem:


Score : 400 points

Problem Statement

Let \mathrm{popcount}(n) be the number of 1s in the binary representation of n.
For example, \mathrm{popcount}(3) = 2, \mathrm{popcount}(7) = 3, and \mathrm{popcount}(0) = 0.

Let f(n) be the number of times the following operation will be done when we repeat it until n becomes 0: "replace n with the remainder when n is divided by \mathrm{popcount}(n)." (It can be proved that, under the constraints of this problem, n always becomes 0 after a finite number of operations.)

For example, when n=7, it becomes 0 after two operations, as follows:

\mathrm{popcount}(7)=3, so we divide 7 by 3 and replace it with the remainder, 1.

\mathrm{popcount}(1)=1, so we divide 1 by 1 and replace it with the remainder, 0.

You are given an integer X with N digits in binary.
For each integer i such that 1 \leq i \leq N, let X_i be what X becomes when the i-th bit from the top is inverted.
Find f(X_1), f(X_2), \ldots, f(X_N).

Constraints

1 \leq N \leq 2 \times 10^5

X is an integer with N digits in binary, possibly with leading zeros.

Input

Input is given from Standard Input in the following format:

N
X

Output

Print N lines. The i-th line should contain the value f(X_i).

Sample Input 1

3
011

Sample Output 1

2
1
1

X_1 = 7, which will change as follows: 7 \rightarrow 1 \rightarrow 0. Thus, f(7) = 2.

X_2 = 1, which will change as follows: 1 \rightarrow 0. Thus, f(1) = 1.

X_3 = 2, which will change as follows: 2 \rightarrow 0. Thus, f(2) = 1.

Sample Input 2

23
00110111001011011001110

Sample Output 2

2
1
2
2
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
3



Sample input:
3
011


Sample output:
2
1
1

Submission status: Runtime Error

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

def initMemo(n):
    memo = {}
    for i in range(1, n):
        memo[i] = popcount(i)
    return memo

def popcount(n):
    cnt = 0
    while n != 0:
        cnt += 1
        n = n % bin(n).count('1')
        if n in memo:
            cnt += memo[n]
            break
        
    return cnt

memo = initMemo(N)

for i in range(N):
    temp_X = [l for l in X]
    if temp_X[i] == '0':
        temp_X[i] = '1'
    else:
        temp_X[i] = '0'
    temp_X = ''.join(temp_X)
    
    n = int(temp_X, 2)
    
    output = popcount(n)
    print(output)

Submission status: Runtime Error

Solution code:
def popcount(s):
    ret = 0
    for c in s:
        if c == '1':
            ret += 1
    return ret


n = int(input())
x = input()
base = popcount(x)
base_int = int(x, 2)
memo = dict()

for i in range(n):
    if x[i] == '0':
        bb = base + 1
        bn = base_int + 2 ** (n - i - 1)
    else:
        bb = base - 1
        bn = base_int - 2 ** (n - i - 1)
    c = 0
    while True:
        a = bn % bb
        c += 1
        if a == 0:
            print(c)
            break
        else:
            bn = a
            bb = popcount(str(format(a, 'b')))

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")
if cnt != 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)
else:
    for i in range(n):
        if x[i] == "1":
            tmp1 += pow(2, n-(i+1), cnt+1)
    for i in range(n):
        if x[i] == "1":
            ans.append(0)
        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 = input()
cnt1 = x.count("1")
n = int(x, 2)

for i in range(N):
    if x[i] == "0":
        tmp = n + 2 ** (N - i - 1)
        tmp %= (cnt1 + 1)
    else:
        tmp = n - 2 ** (N - i - 1)
        tmp %= (cnt1 - 1)
    cnt = 1
    while tmp != 0:
        tmp %= bin(tmp).count("1")
        cnt += 1
    print(cnt)

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
a = []
s = int(x, 2)
k = x.count('1')



for i in range(n):
    if int(x[i]) == 0:
        S = s + 2**(n-i-1)
        K = k + 1
    else:
        S = s - 2**(n-i-1)
        K = k - 1
    ans = 1
    S = S % K
    while S != 0:
        S = S % str(bin(S)).count('1')
        ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
def popcount(n):
    count = 0
    if n != 0:
        while n > 0:
            count += 1
            n = n % bin(n).count("1")
    return count


n = int(input())

a = input()

x = int(a,2)
nlis = range(n)

c1 = bin(x).count("1")

for i in range(n):

    if a[i] == "0":
        c2 = c1 + 1
        ans = x + 2 ** (n - 1 - i)
    else:
        c2 = c1 - 1
        ans = x - 2 ** (n - 1 - i)
    ans = ans % c2


    ans = popcount(ans) + 1

    print(ans)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N = int(input())
    X = input()
    count_1 = X.count('1')
    X = int('0b'+X,0)
    if X == 1:
        print(0)
        sys.exit()

    memo = [-1] * (2**(N+1))

    def f(X):
        if memo[X]!=-1:
            return memo[X]
        x = X
        count = 0
        while x>=1:
            if x%2==1:
                count += 1
            x//=2
        if X%count == 0:
            memo[X] = 1
            return memo[X]
        else:
            memo[X] = f(X%count)+1
            return memo[X]

    for i in range(N-1,-1,-1):
        x = X^(1<<i)
        print(f(x))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import copy
n = int(input())
x = input()
x2 = list(copy.deepcopy(x))

def popcnt(n):
    return n.count("1")


for i in range(n):
    if x2[i] == "0":
        x2[i] = "1"
    else:
        x2[i] = "0"
    #x2.insert(0,'0')
    #x2.insert(1,"b")
    a = (''.join(x2))
    p = popcnt(a)
    xx = int(a,2)
    ans = 0
    print(p)
    for i in range(1,10**5):
        xx = int(bin(xx % p), 2)
        if xx == 0:
            print(i)
            break
        else:
            p = popcnt(str(xx))
        if p ==0:
            print(i+1)
            break

    x2 = list(copy.deepcopy(x))

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
# N = 2 * 10 ** 5
# X = "10"*(10**5)
cnt = X.count('1')

base = int(X, 2)
if cnt == 1:
    base_m1 = 0
else:
    base_m1 = base % (cnt - 1)
base_p1 = base % (cnt + 1)

c = dict()
for i in range(N):

    if (X[i] == '1') and (cnt == 1):
        bins = base_m1 - 2 ** (N - i - 1) % (cnt - 1)
        nc = cnt - 1
    else:
        bins = base_p1 + 2 ** (N - i - 1) % (cnt + 1)
        nc = cnt + 1

    c[i] = 0
    while True:
        if nc == 0:
            print(c[i])
            break
        n = bins % nc
        c[i] += 1
        if n == 0:
            print(c[i])
            break

        bins = n
        nc = bin(n).count('1')

Submission status: Runtime Error

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

c = X.count('1')

table = [0]*(2*pow(10,5))

for i in range(2*pow(10,5)):
    n = bin(i+1)
    z = n.count('1')
    table[i] = (i+1)%z

up = True

for i in range(N):
    Xi = list(X)
    if Xi[i] == '1':
        Xi[i] = '0'
        c -= 1
        up = False
    else:
        Xi[i] = '1'
        c += 1
        up = True
    
    n = int(''.join(Xi), 2)
    n = n % c
    ans = 1
    while n > 0:
        n = table[n-1]
        ans += 1
        
    print(ans)
    
    if up:
        c -= 1
    else:
        c += 1

Submission status: Runtime Error

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

def main():
    N = int(input())
    X = [None] * N
    l = list(input())
    Xc = 0
    for i in range(N):
        X[i] = int(l[i])
        Xc += X[i]

    ans1 = 0
    ans2 = 0
    for j in range(N):
        if X[j]==1:
            ans1 += pow(2,N-1-j,Xc+1)
            ans2 += pow(2,N-1-j,Xc-1)
    ans1 %= Xc+1
    ans2 %= Xc-1

    for i in range(N):
        if X[i]==0:# 0->1
            ans = (ans1 + pow(2,N-1-i)) % (Xc+1)
        else:# 1-> 0
            ans = (ans2 - pow(2,N-1-i)) % (Xc-1)
        count = 1
        while ans > 0:
            tmp = str(bin(ans)).count('1')
            ans %= tmp
            count += 1
        print(count)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**9)

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


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


bin_x = int(x, 2)


class calc:
    def __init__(self):
        self.popcount_list = [-1]*(10**7+1)
        self.popcount_list[0] = 0

    def solve(self, a):
        if self.popcount_list[a] != -1:
            return self.popcount_list[a]

        num_one = bc(a)
        new_a = a % num_one
        if new_a == 0:
            self.popcount_list[a] = 1
            return 1
        else:
            num = self.solve(new_a)
            self.popcount_list[a] = num+1
        return num+1


calc_d = calc()
ans = []
haita = 1
# print(n)
for i in range(n):
    tmp_x = bin_x ^ haita
    # print(tmp_x)
    ans_tmp = calc_d.solve(tmp_x)
    # print(ans_tmp)

    ans.append(ans_tmp)
    haita = haita << 1

# print(ans)
for i in reversed(ans):
    print(i)

Submission status: Runtime Error

Solution code:
import math
from copy import copy
di = {}
di[0] = 0
for i in range(1, 2*(10**3)+1):
    di[i] = 0
for i in range(1, 2*(10**3)+1):
    count = 0
    for j in range(int(math.log2(i))+4):
        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 popcount(num):
    bin_num = bin(num)[2:]
    count = 0
    for i in bin_num:
        count += int(i)
    return count


N = int(input())

AAA = []
for i in range(1, 2**N):
    AAA.append(AAA[i % popcount(i)] + 1)

X = int(input(), 2)

for i in range(N):
    Xi = X ^ (1 << (N-i-1))
    print(AAA[Xi])

Submission status: Runtime Error

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

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

l = [0] * N
for i in range(N):
    l[i] = 2 ** i

l.reverse()

def ten_to_2shin(num):
    result = "0b"
    for idx, v in enumerate(l):
        if num >= v:
            num -= v
            result += "1"
        else:
            result += "0"
    return result


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

def nishin_to_10sin(nishin):
    result = 0
    for i, v in enumerate(reversed(nishin)):
        if v == "1":
            result += 2**i
    return result


def x_suretu(start_x, n):
    tmp = list(start_x)
    b = start_x[n-1]
    rev_b = 0
    if b == "1":
        rev_b = "0"
    else:
        rev_b = "1"
    tmp[n-1] = rev_b
    return "".join(tmp)


def xnittuite_toku(x):
    n = nishin_to_10sin(x) % popcount(x)
    x = ten_to_2shin(n)
    result = 1
    while n != 0:
        result += 1
        n = n % popcount(ten_to_2shin(n))
    print(result)


for i in range(1, N+1):
    tmp = x_suretu(X, i)
    xnittuite_toku(x_suretu(X, i))

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)+10)]
cnt = x.count('1')

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

x0 = int(x,2)%(cnt-1)
x1 = int(x,2)%(cnt+1)
xx0 = [1]
for i in range(n+1):
  xx0.append((xx0[-1]*2)%(cnt-1))
xx1 = [1]
for i in range(n+1):
  xx1.append((xx1[-1]*2)%(cnt+1))

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

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

N = int(input())
X = input()
Xn = int(X, 2)
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 y>0:
        y %= popcount(y)
        cnt += 1
    print(cnt)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000000)
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 main():
    N = int(input())
    X = input()
    d = {}
    dd = {}
    x1 = X.count('1')
    xn = int(X, 2)
    dd[0] = 0
    def hoge(i):
        if i in dd:
            return dd[i]
        if i not in d:
            j = popcount(i)
            d[i] = i % j
            if d[i] == 0:
                dd[i] = 1
            else:
                dd[i] = 1 + hoge(d[i])
        return dd[i]
    if xn == 1:
        xn1 = 0
    else:
        xn1 = xn % (x1-1)
    xn2 = xn % (x1 + 1)
    for i in range(N):
        if X[i] == '1':
            t = xn1
            if xn1 == 0:
                print(0)
                continue
            t -= pow(2, N-1-i, x1-1)
            t %= (x1-1)
        else:
            t = xn2
            t += pow(2, N-1-i, x1+1)
            t %= (x1 + 1)
        if t == 0:
            print(1)
        else:
            print(1 + hoge(t))
main()

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
x = [int(x[i]) for i in range(len(x))]
ans = [0 for i in range(1<<n+1)]
def popc(n):
	ans = 0
	while(True):
		if n==0:
			break
		if n%2 == 1:
			ans += 1
		n = n//2
	return ans
def conv(a):
	ans = 0
	for i in range(len(a)):
		ans += (2**i)*a[-1*(i+1)]
	return ans

for i in range(n):
	tmp = x[:]
	tmp[i] = 0 if tmp[i] == 1 else 1
	num = conv(tmp)
	#print('num',num)
	popcount = sum(tmp)
	#print('popcount',popcount)
	tmp_list = [num]
	#print(tmp_list)
	if ans[num] != 0:
		print(ans[num])
		#print('++++++++++++++++')
		continue
	while(True):
		#print('ans[num]',ans[num])
		if ans[num] != 0:
			for j in tmp_list:
				if j == num:
					continue
				ans[j] += ans[num]
			break
		num = num%popcount
		for j in tmp_list:
			ans[j] += 1
		tmp_list.append(num)
		#print(tmp_list)
		if num == 0:
			break
		#print(ans)
		popcount = popc(num)
	print(ans[tmp_list[0]])
	#print('++++++++++++++++')
	#print(ans)

Submission status: Runtime Error

Solution code:
def main():
  from collections import deque
  import sys
  input = sys.stdin.readline
  T = int(input())
  for _ in range(T):
    N = int(input())
    KLR = [list(map(int,input().split())) for _ in range(N)]
    left = deque([])
    right = deque([])
    mid = deque([])
    for K,L,R in KLR:
      x = L - R
      if x==0:
        mid.append([K-1,L,R,x])
      elif x>0:
        left.append([K-1,L,R,x])
      else:
        right.append([K-1,L,R,x])

    left = sorted(left,key = lambda x:x[3],reverse = True)
    right = sorted(right, key = lambda x:x[3])
    flag = [False] * (N)
    ans = 0
    for klr in left:
      x = klr[0]
      for _ in range(N):
        if x<0:
          ans += klr[2]
          break
        if flag[x]:
          x -= 1
        else:
          flag[x] = True
          ans += klr[1]
          break
    flag = [False] * (N)
    for klr in right:
      x = klr[0] + 1
      for _ in range(N):
        if x>=N:
          ans += klr[1]
          break
        if flag[x]:
          x += 1
        else:
          flag[x] = True
          ans += klr[2]
          break
    for klr in mid:
      ans += klr[1]

    print(ans)
    
main()

Submission status: Runtime Error

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

mem = {}

def step(X):
    x = list(X)
    b = sum([s == "1" for s in x])
    return format(int(X, 2) % b, f"0{len(x)}b")


for i in range(0, N):
    x = list(X)
    x[i] = "1" if x[i] == "0" else "0"
    x = "".join(x)
    stack = [x]
    fn = 0
    while 1:
        x = step(x)
        stack.append(x)
        fn += 1
        if int(x, 2) == 0:
            for p, j in enumerate(stack[::-1]):
                mem[j] = fn - p
            break
    print(fn)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N = int(input())
x = input()
cnt_1 = x.count('1')
X = int(x, 2)

if cnt_1%2 == 1:
    if x[0] == '1':
        print(1)
    else:
        print(2)
    for i in range(1,N-1):
        t = x[n]
        if t == '1':
            print(2)
        else:
            print(1)
    if x[N-1] == '1':
        print(1)
    else:
        print(3)
else:
    for i in range(N):
        t = x[n]
        if t == '1':
            print(1)
        else:
            print(2)

Submission status: Runtime Error

Solution code:
from sys import stdin
from sys import setrecursionlimit
from collections import Counter, deque, defaultdict
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
import random
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

# popcount table
popcount = {}
popcount[0] = 0
def gpc(n):
    if n not in popcount:
        popcount[n] = bin(n).count("1")
    return popcount[n]

# mem rec
solutions = {}
def sol(Xk):
    # pc = popcount[Xk]
    pc = gpc(Xk)
    # print("Call {}, {}".format(Xk, pc))
    if Xk == 0:
        solutions[(Xk, 0)] = 0
        return 0
    elif (Xk, pc) in solutions:
        return solutions[Xk, pc]
    else:
        count = 1 + sol(Xk % pc)
        solutions[Xk, pc] = count
        return count

def main():
    from builtins import int, map
    N = int(input())
    X = input()
    
    # 余りが0からN - 1
    Xpc = X.count("1")
    iX = int(X, 2)
    rem_groups = [0] * N
    for k in range(1, N):
        # print(k, gpc(k), k % gpc(k))
        rem_groups[k] = k % gpc(k)

    # ans = [-1] * (N + 1)
    for k in range(N - 1, -1, -1):
        # f(k)を計算
        Xk = iX ^ (1 << k)
        Xkpc = Xpc
        if (iX & (1 << k)) >> k:
            Xkpc -= 1
        else:
            Xkpc += 1
        ans = rem_groups[Xk % Xkpc] + 1 + (0 if Xk % Xkpc == 0 else 1)
        # ans_sol = sol(Xk)
        # print(k, Xk, Xkpc, ans, ans_sol)
        print(ans)



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

    if m > 1:
        a = x%(m-1)
    b = x%(m+1)
    tmp_a = 1
    tmp_b = 1
    xx = []

    for i in range(n):
        if (x >> i) &1:
            if m == 1:
                xx.append(0)
                break
            else:
                y = (a - tmp_a)%(m-1)
        else:
            y = (b + tmp_b)%(m+1)
        tmp_a *= 2
        if m > 1:
            tmp_a %= (m-1)
        tmp_b *= 2
        tmp_b %= (m+1)

        cnt = 1
        while y != 0:
            cnt += 1
            y = solve(y)
        xx.append(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:
"""
    こんにちは。これはクシャルです
    
    Author : thekushalghosh (クシャル)
    Team   : CodeDiggers
 
    I prefer Python language over the C++ language :p :D
        
    Visit my website : thekushalghosh.github.io
"""
import sys,math,cmath,time
start_time = time.time()
##########################################################################
################# ---- THE ACTUAL CODE STARTS BELOW ---- #################
    
def solve():
    n = inp()
    s = insr()
    a = [0] * (n + 1)
    for i in range(1,n + 1):
        q = bin(i).replace("0b","")
        a[i] = a[i % q.count("1")] + 1
    w = s.count("1")
    qq = int(s,2)
    for i in range(n):
      qw = 0
        if s[i] == "0":
            qw = qw + (2 ** (n - i - 1))
            w = w + 1
        else:
            qw = qw - (2 ** (n - i - 1))
            w = w - 1
        if w == 0:
            print(0)
        else:
            print(a[(qq + qw) % w] + 1)
    
################## ---- THE ACTUAL CODE ENDS ABOVE ---- ##################
##########################################################################
 
def main():
    global tt
    if not ONLINE_JUDGE:
        sys.stdin = open("input.txt","r")
        sys.stdout = open("output.txt","w")
    t = 1
    for tt in range(t):
        solve()
    if not ONLINE_JUDGE:
        print("Time Elapsed :",time.time() - start_time,"seconds")
        sys.stdout.close()
    
#---------------------- USER DEFINED INPUT FUNCTIONS ----------------------#
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    return(input().strip())
def invr():
    return(map(int,input().split()))
 
#------------------ USER DEFINED PROGRAMMING FUNCTIONS ------------------#
def counter(a):
    q = [0] * max(a)
    for i in range(len(a)):
        q[a[i] - 1] = q[a[i] - 1] + 1
    return(q)
def counter_elements(a):
    q = dict()
    for i in range(len(a)):
        if a[i] not in q:
            q[a[i]] = 0
        q[a[i]] = q[a[i]] + 1
    return(q)
 
def string_counter(a):
    q = [0] * 26
    for i in range(len(a)):
        q[ord(a[i]) - 97] = q[ord(a[i]) - 97],1
    return(q)
 
def factors(n):
    q = []
    for i in range(1,int(n ** 0.5) + 1):
        if n % i == 0: q.append(i); q.append(n // i)
    return(list(sorted(list(set(q)))))
 
def prime_factors(n):
    q = []
    while n % 2 == 0: q.append(2); n = n // 2
    for i in range(3,int(n ** 0.5) + 1,2):
        while n % i == 0: q.append(i); n = n // i
    if n > 2: q.append(n)
    return(list(sorted(q)))
 
def transpose(a):
    n,m = len(a),len(a[0])
    b = [[0] * n for i in range(m)]
    for i in range(m): 
        for j in range(n): 
            b[i][j] = a[j][i]
    return(b)
#-----------------------------------------------------------------------#
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
    input = sys.stdin.readline
main()

Submission status: Runtime Error

Solution code:
N=int(input())
X=input()
x=X.count('1')
y=int(X,2)
for i in range(N):
    ans=0
    f=True
    if X[i]=='1':
        a=x-1
        b=y-(2**(N-i-1))
    else:
        a=x+1
        b=y+(2**(N-1-i))
    while f:
        ans+=1
        if b%a==0:
            break
        else:
            b%=a
            a=bin(b).count('1')
    print(ans)

Submission status: Runtime Error

Solution code:
def main():
  n = int(input())
  x = str(input())
  dp = [None for _ in range(2**n)]

  for i in range(n):
    if x[i] == "0":
      binary = x[:i] + "1" + x[i+1:]
    else:
      binary = x[:i] + "0" + x[i+1:]

    num, count = bin2num(binary)
    a = popcount(num, count)
    print(a)

def popcount(num, count):
  tmp = num % count
  if tmp == 0:
    return 1
  else:
    bi = str(bin(num))
    _, c = bin2num(bi)
    return popcount(tmp, c) + 1


def bin2num(binary):
  num = int(binary, 2)
  count = binary.count("1")
  return num, count

if __name__ == "__main__":
  main()

Submission status: Runtime Error

Solution code:
LIM=200002
L=[0]*LIM

def bin_sum(Y):
    S=bin(Y)[2:]
    count=0
    for i in range(len(S)):
        count+=int(S[i])
    return count

def bin_sum2(Y):
    count=0
    for i in range(len(Y)):
        count+=int(Y[i])
    return count

for i in range(1,LIM):
    L[i]+=bin_sum(i)

def pop_num(N,b,L):
    if N==0:
        return 0
    v=N%b
    return pop_num(v,L[v],L)+1
    
def pop_num2(N,b,L,M):
    if N==0:
        return 0
    v=N%b
    return M[v]+1

M=[0]*200002
for i in range(1,200002):
    M[i]+=pop_num(i,L[i],L)
X=int(input())
Y=input()
d=bin_sum2(Y)+1
c=bin_sum2(Y)-1
e=int(Y,2)
for i in range(X):
    Y_i=Y[:i]+str(abs(int(Y[i])-1))+Y[i+1:]
    if Y_i[i]=="1":
        b=d
        f=e+2**i
    else:
        b=c
        f=e-2**i
    print(pop_num2(f,b,L,M))

Submission status: Runtime Error

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

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
x_pop = popcount(x)
for i in reversed(range(0,n)):
    if x&(1<<i):
        tmp_pop = x_pop - 1
    else:
        tmp_pop = x_pop + 1
    tmp2 = (x^(1<<i)) % tmp_pop
    cnt = 1
    while tmp2 > 0:
        tmp = tmp2
        tmp2 = tmp % popcount(tmp)
        cnt += 1
    print(cnt)

Submission status: Runtime Error

Solution code:
# coding: utf-8


def bi(x, n_digit):
    output = ""
    for i in range(n_digit-1, -1, -1):
        if x >= 2**i:
            x -= 2**i
            output += "1"
        else:
            output += "0"
    return output


def popcount(bi_n):
    output = 0
    for c in bi_n:
        if c == "1":
            output += 1
    return output


def main():
    N = int(input())
    bi_X = input()

    fs = [None] * 20

    def rec(x):
        pop_x = popcount(bi(x, 18))
        r = x % pop_x
        if r == 0:
            return 1
        elif fs[r] is not None:
            return 1 + fs[r]
        else:
            return 1 + rec(r)

    for i in range(1, 20):
        fs[i] = rec(i)
    fs[0] = 0
    
    pop_X = popcount(bi_X)
    qp = pop_X+1
    qm = pop_X-1

    bi_qp = [None] * N
    bi_qm = [None] * N
    bi_qp[0] = 1 % qp
    bi_qm[0] = 1 % qm
    bi_qp[1] = 2 % qp
    bi_qm[1] = 2 % qm
    for i in range(2, N):
        bi_qp[i] = ((bi_qp[1])*(bi_qp[i-1])) % qp
        bi_qm[i] = ((bi_qm[1])*(bi_qm[i-1])) % qm
    
    rp = 0
    rm = 0
    for i in range(N):
        p = N-1-i
        coo = int(bi_X[i])
        rp = (rp + (((coo % qp) * bi_qp[p]) % qp)) % qp
        rm = (rm + (((coo % qm) * bi_qm[p]) % qm)) % qm

    for i in range(N):
        if bi_X[i] == "0":
            ri = (rp + bi_qp[N-1-i]) % qp
            if ri < 20:
                print(1 + fs[ri])
            else:
                pop_ri = popcount(bi(ri, 18))
                print(2 + fs[ri % pop_ri])
        else:
            ri = (rm - bi_qm[N-1-i]) % qm
            if ri < 20:
                print(1 + fs[ri])
            else:
                pop_ri = popcount(bi(ri, 18))
                print(2 + fs[ri % pop_ri])



main()
# print(main())

Submission status: Runtime Error

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

memo = {}

if N == 1:
    print(1)
    exit()


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 count_one(num):
    if num in memo:
        return memo[num]
    else:
        v = popcount(num)
        memo[num] = v
        return v


memo2 = {}

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

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

Submission status: Runtime Error

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

#Sのビット数
bitcount=0
for i in range(N):
  if S[i]=='1':
    bitcount+=1
bp=bitcount+1
bm=bitcount-1
    

fXp=X%bp
fXm=X%bm
    

def f(n):
  c=0
  x=1
  while x<=n:
    if n&x>0:
      c+=1
    x*=2
  return n%c

ls=[0 for i in range(bitcount+2)]  
ls2=[0 for i in range(bitcount+2)]
for i in range(1,bitcount+2):
  ls[i]=f(i)
  ls2[i]=ls2[ls[i]]+1

for i in range(N):
  if S[i]=='0':
    print(ls2[(fXp+2**(N-1-i))%bp]+1)
  else:
    if (X^(2**(N-1-i)))==0:
      print(0)
    else:
      print(ls2[(fXm-2**(N-1-i))%bm]+1)
  
      #print(ls2[(fXm-ls_bitm[N-1-i])%bm]+1)