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 = list(input())[::-1]
num = 0
nump = 0
numm = 0
pop_num = 0
for i in range(N):
    if x[i] == "1":
        pop_num += 1
for i in range(N):
    if x[i] == "1":
        num += pow(2,i,pop_num)
        num %= pop_num 
        nump += pow(2,i,pop_num+1)
        nump %= pop_num  + 1
        numm += pow(2,i,pop_num - 1)
        numm %= pop_num - 1



def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

x = x[::-1]
def calc(i,depth,n):
    if depth == 0:
        if x[i] == "1":
            tmp = numm
            tmp -=  2 ** (N - i - 1)
            tmp %= (pop_num - 1)
            return calc(i,depth+1,tmp)
        else:
            tmp = nump
            tmp +=  2 ** (N - i - 1)
            tmp %= (pop_num + 1)
            return calc(i,depth+1,tmp)
    else:
        if n == 0: return depth
        if popcnt(n) == 0:
            while True:
                print("A")
        return calc(i,depth+1, n % popcnt(n))
        

for i in range(N):
    print(calc(i,0,0))

Submission status: Runtime Error

Solution code:
N = int(input())
x = list(input())[::-1]
num = 0
nump = 0
numm = 0
pop_num = 0
for i in range(N):
    if x[i] == "1":
        pop_num += 1
for i in range(N):
    if x[i] == "1":
        num += pow(2,i,pop_num)
        num %= pop_num 
        nump += pow(2,i,pop_num+1)
        nump %= pop_num  + 1
        numm += pow(2,i,pop_num - 1)
        numm %= pop_num - 1



def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

x = x[::-1]
def calc(i,depth,n):
    if depth == 0:
        if x[i] == "1":
            tmp = numm
            tmp -=  2 ** (N - i - 1)
            tmp %= (pop_num - 1)
            return calc(i,depth+1,tmp)
        else:
            tmp = nump
            tmp +=  2 ** (N - i - 1)
            tmp %= (pop_num + 1)
            return calc(i,depth+1,tmp)
    else:
        if n == 0: return depth
        return calc(i,depth+1, n % popcnt(n))
        

for i in range(N):
   # print(calc(i,0,0))

Submission status: Runtime Error

Solution code:
N = int(input())
x = list(input())[::-1]
num = 0
nump = 0
numm = 0
pop_num = 0
for i in range(N):
    if x[i] == "1":
        pop_num += 1
for i in range(N):
    if x[i] == "1":
        num += pow(2,i,pop_num)
        num %= pop_num 
        nump += pow(2,i,pop_num+1)
        nump %= pop_num  + 1
        numm += pow(2,i,pop_num - 1)
        numm %= pop_num - 1



def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

x = x[::-1]
def calc(i,depth,n):
    if depth == 0:
        if x[i] == "1":
            tmp = numm
            tmp -=  2 ** (N - i - 1)
            tmp %= (pop_num - 1)
            return calc(i,depth+1,tmp)
        else:
            tmp = nump
            tmp +=  2 ** (N - i - 1)
            tmp %= (pop_num + 1)
            return calc(i,depth+1,tmp)
    else:
        if n == 0: return depth
        return calc(i,depth+1, n % popcnt(n))
        

for i in range(N):
    print(calc(i,0,0))

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
B = input()

B_array = np.array(list(map(int, list(B))))
B_1 = B_array.sum()
mod_list_m1 = []
mod_list = []
mod_list_p1 = []
if B_1 == 1:
    for i in range(N):
        print(0)
else:
    for i in range(N):
        mod_list.append((2**i) % (B_1))
        mod_list_m1.append((2**i) % (B_1-1))
        mod_list_p1.append((2**i) % (B_1+1))
    mod_list = np.array(mod_list)[::-1]
    mod_list_m1 = np.array(mod_list_m1)[::-1]
    mod_list_p1 = np.array(mod_list_p1)[::-1]

    mod_m1 = B_array.dot(mod_list_m1) % (B_1-1)
    mod_p1 = B_array.dot(mod_list_p1) % (B_1+1)
    print(mod_m1)

    def calc_small(n, iter):
        iter += 1
        mod = n % bin(n).count("1")
        if mod == 0:
            return iter
        else:
            return calc_small(mod, iter)

    for i in range(N):
        mod = (mod_m1 - mod_list_m1[i]) % (B_1-1) if B_array[i] == 1 else (mod_p1 + mod_list_p1[i]) % (B_1+1)
        iter = 1
        if mod == 0:
            print(iter)
        else:
            print(calc_small(mod, iter))

Submission status: Runtime Error

Solution code:
N = int(input())
x = list(input())[::-1]
num = 0
nump = 0
numm = 0
pop_num = 0
for i in range(N):
    if x[i] == "1":
        pop_num += 1
for i in range(N):
    if x[i] == "1":
        num += pow(2,i,pop_num)
        num %= pop_num 
        num += pow(2,i,pop_num+1)
        nump %= pop_num  + 1
        num += pow(2,i,pop_num - 1)
        numm %= pop_num - 1



def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

x = x[::-1]
def calc(i,depth,n):
    if depth == 0:
        if x[i] == "1":
            tmp = numm
            tmp -=  2 ** (N - i - 1)
            tmp %= (pop_num - 1)
            return calc(i,depth+1,tmp)
        else:
            tmp = nump
            tmp +=  2 ** (N - i - 1)
            tmp %= (pop_num + 1)
            return calc(i,depth+1,tmp)
    else:
        if n == 0: return depth
        return calc(i,depth+1, n % popcnt(n))
        

for i in range(N):
    print(calc(i,0,0))

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
B = input()

B_array = np.array(list(map(int, list(B))))
B_1 = B_array.sum()
mod_list_m1 = []
mod_list = []
mod_list_p1 = []
if B_1 == 1:
    for i in range(N):
        print(1)
else:
    for i in range(N):
        mod_list.append((2**i) % (B_1))
        mod_list_m1.append((2**i) % (B_1-1))
        mod_list_p1.append((2**i) % (B_1+1))
    mod_list = np.array(mod_list)[::-1]
    mod_list_m1 = np.array(mod_list_m1)[::-1]
    mod_list_p1 = np.array(mod_list_p1)[::-1]

    mod_m1 = B_array.dot(mod_list_m1) % (B_1-1)
    mod_p1 = B_array.dot(mod_list_p1) % (B_1+1)
    print(mod_m1)

    def calc_small(n, iter):
        iter += 1
        mod = n % bin(n).count("1")
        if mod == 0:
            return iter
        else:
            return calc_small(mod, iter)

    for i in range(N):
        mod = (mod_m1 - mod_list_m1[i]) % (B_1-1) if B_array[i] == 1 else (mod_p1 + mod_list_p1[i]) % (B_1+1)
        iter = 1
        if mod == 0:
            print(iter)
        else:
            print(calc_small(mod, iter))

Submission status: Runtime Error

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

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N=ii()
    X=input()

    x=int(X,2)
    pop_X=bin(x).count("1")

    pm1 = x % (pop_X-1)
    pp1 = x % (pop_X+1)
    
    for i in range(N):
        sign = 1
        pop_Xi = pop_X
        if X[i] == "1": 
            sign *= -1
            pop_Xi -= 1
            _x = pm1
        else:
            pop_Xi += 1
            _x = pp1
        
        if pop_Xi == 0:
            print(0)
            continue
        
        
        two = pow(2,N-1-i,pop_Xi)
        X_i = _x + sign * two
        X_i %= pop_Xi
        count = 1
        while X_i:
            pop_Xi = bin(X_i).count("1")
            X_i = X_i % pop_Xi
            count += 1

        print(count)



if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
'''再帰
def f(n):
    t = int(n,2) % list(n).count('1')
    if t == 0:
        return 1
    else:
        return f(str(bin(t))) + 1
'''
def f(n):
    
    t = int(n,2) % list(n).count('1')
    cnt = 1
    while(t):
        t = t % str(bin(t)).count('1')
        cnt += 1
        #print(cnt)
    return cnt

for i in range(n):
    xb = list(x)
    xb[i] = '0' if xb[i] == '1' else '1'
    print(f(''.join(xb)))

Submission status: Runtime Error

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

def main():
    N = int(input())
    X = int(input(),2)
    LIST = []
    ANS = [0]*N
    TEMP = [0]*N
    CHAIND = [0]*N
    bit = 1

    cnt = count_ones_by_bitmask(X)
    p = X % (cnt+1)
    m = X % (cnt-1)
    for i in range(N):
        LIST.append(X^bit)
        if LIST[i]!=0:
            ANS[i] = 1
            if (X & bit == 0):
                TEMP[i] = (p + bit % (cnt+1) ) % (cnt+1)
            else:
                TEMP[i] = (m - bit % (cnt-1) ) % (cnt-1)            
        bit = bit<<1





    CHA = list(set(TEMP))

    for i in range(len(CHA)):
        an = 0
        cha = CHA[i]
        cnt = count_ones_by_bitmask(CHA[i])
        while cnt>0:
            an += 1
            cha = cha%cnt
            cnt = count_ones_by_bitmask(cha)
        CHAIND[CHA[i]] = an

    for i in reversed(range(N)):
        print(ANS[i]+CHAIND[TEMP[i]])


def count_ones_by_bitmask(num):
    count = 0
    while num:
        count += num & 1
        num >>= 1
    return count

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
x = list(input())[::-1]
num = 0
nump = 0
numm = 0
pop_num = 0
for i in range(N):
    if x[i] == "1":
        pop_num += 1
for i in range(N):
    if x[i] == "1":
        num += ((2 ** i) % pop_num)
        num %= pop_num 
        nump += ((2 ** i) % (pop_num+1))
        nump %= pop_num  + 1
        numm += ((2 ** i) % (pop_num-1))
        numm %= pop_num - 1



def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

x = x[::-1]
def calc(i,depth,n):
    if depth == 0:
        if x[i] == "1":
            tmp = numm
            tmp -=  2 ** (N - i - 1)
            tmp %= (pop_num - 1)
            return calc(i,depth+1,tmp)
        else:
            tmp = nump
            tmp +=  2 ** (N - i - 1)
            tmp %= (pop_num + 1)
            return calc(i,depth+1,tmp)
    else:
        if n == 0: return depth
        return calc(i,depth+1, n % popcnt(n))
        

for i in range(N):
    print(calc(i,0,0))

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
ans = [1 for _ in range(N)]
#original 1 count
l = 0
for k in range(N):
  if X[k] == '1':
    l+=1


intN = int(X, 2)
if l >1:
  N1 = intN %(l-1)
N0 = intN % (l+1)


start = []
if N == 1:
  if X[0] == '1':
    print(0)
    exit()
  else:
    print(1)
    exit()
else:
  s1 = 1
  s0 = 1
  for k in range(N-1, -1, -1):
    if X[k] == '1':
      if l == 1:
        ans[k] = 0
        ia =0
      else:  
        ia = (N1 - s1)%(l-1)
    else:
      ia = (N0 + s0)%(l+1)
    start.append(ia)
    s1 = s1*2%(l-1)
    s0 = s0*2%(l+1)
start = start[::-1]
"""
ml = len(bin(l+1))-2
poplist = [0 for _ in range(N)]
t = 1
while t < N + 1:
  t *= 2
  for k in range(t//2, N, t):
    for j in range(t//2):
      if k+j>N-1:
        break
      poplist[k+j] += 1
"""

def popcount(n):
  c = 0
  n = bin(n)[2:]
  for k in range(len(n)):
    if n[k] == '1':
      c+=1
  return c

for k in range(len(start)):
  for count in range(10*5):
    if start[k] == 0:
      ans[k] += count
      break
    else:
      start[k] = start[k] % popcount(start[k])

for k in range(N):
  print(ans[k])

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False
# show_flg = True


def main():
    N = I()
    X = S()
    bit_cnt = X.count('1')
    one_inv_cnt = bit_cnt - 1
    zero_inv_cnt = bit_cnt + 1
    MAX = 2 * 10 ** 5 + 1

    # 大きい数の余り
    # 繰り返し２乗法の発展？
    zero_inv_mod = 0
    one_inv_mod = 0
    for i in range(len(X)-1, -1, -1):
        b = int(X[i])
        zero_inv_mod = (zero_inv_mod * 2 + b) % zero_inv_cnt
        one_inv_mod = (one_inv_mod * 2 + b) % one_inv_cnt

    f = [0] * MAX
    pop_count = [0] * MAX
    for i in range(1, MAX):
        pop_count[i] = pop_count[i//2] + i % 2
        f[i] = f[i % pop_count[i]] + 1


    # print(zero_inv_cnt, zero_inv_mod)
    # print(one_inv_cnt, one_inv_mod)

    for i in range(len(X)-1, -1, -1):
        if X[N-1-i] == '1':
            nxt = one_inv_mod
            nxt -= pow(2, i, one_inv_cnt)
            nxt %= one_inv_cnt
            print(f[nxt] + 1)
        else:
            nxt = zero_inv_mod
            nxt += pow(2, i, zero_inv_cnt)
            nxt %= zero_inv_cnt
            print(f[nxt] + 1)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
x = list(input())[::-1]
print(len(x))
num = 0
nump = 0
numm = 0
pop_num = 0
for i in range(N):
    if x[i] == "1":
        pop_num += 1
for i in range(N):
    if x[i] == "1":
        num += ((2 ** i) % pop_num)
        num %= pop_num 
        nump += ((2 ** i) % (pop_num+1))
        nump %= pop_num  + 1
        numm += ((2 ** i) % (pop_num-1))
        numm %= pop_num - 1



def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

x = x[::-1]
def calc(i,depth,n):
    if depth == 0:
        if x[i] == "1":
            tmp = numm
            tmp -=  2 ** (N - i - 1)
            tmp %= (pop_num - 1)
            return calc(i,depth+1,tmp)
        else:
            tmp = nump
            tmp +=  2 ** (N - i - 1)
            tmp %= (pop_num + 1)
            return calc(i,depth+1,tmp)
    else:
        if n == 0: return depth
        return calc(i,depth+1, n % popcnt(n))
        

for i in range(N):
    print(calc(i,0,0))

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
B = str(input())

B_array = np.array(list(map(int, list(B))))
B_1 = B_array.sum()
mod_list_m1 = []
mod_list = []
mod_list_p1 = []
if B_1 == 1:
  for i in range(N):
    print(0)
else:
    for i in range(N):
        mod_list.append((2**i) % (B_1))
        mod_list_m1.append((2**i) % (B_1-1))
        mod_list_p1.append((2**i) % (B_1+1))
    mod_list = np.array(mod_list)[::-1]
    mod_list_m1 = np.array(mod_list_m1)[::-1]
    mod_list_p1 = np.array(mod_list_p1)[::-1]

    mod_m1 = B_array.dot(mod_list_m1) % (B_1-1)
    mod_p1 = B_array.dot(mod_list_p1) % (B_1+1)
    print(mod_m1)

    def calc_small(n, iter):
        iter += 1
        mod = n % bin(n).count("1")
        if mod == 0:
            return iter
        else:
            return calc_small(mod, iter)

    for i in range(N):
        mod = (mod_m1 - mod_list_m1[i]) % (B_1-1) if B_array[i] == 1 else (mod_p1 + mod_list_p1[i]) % (B_1+1)
        iter = 1
        if mod == 0:
            print(iter)
        else:
            print(calc_small(mod, iter))

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
B = str(input())

B_array = np.array(list(map(int, list(B))))
B_1 = B_array.sum()
mod_list_m1 = []
mod_list = []
mod_list_p1 = []
if B_1 == 1:
    print(0)
else:
    for i in range(N):
        mod_list.append((2**i) % (B_1))
        mod_list_m1.append((2**i) % (B_1-1))
        mod_list_p1.append((2**i) % (B_1+1))
    mod_list = np.array(mod_list)[::-1]
    mod_list_m1 = np.array(mod_list_m1)[::-1]
    mod_list_p1 = np.array(mod_list_p1)[::-1]

    mod_m1 = B_array.dot(mod_list_m1) % (B_1-1)
    mod_p1 = B_array.dot(mod_list_p1) % (B_1+1)
    print(mod_m1)

    def calc_small(n, iter):
        iter += 1
        mod = n % bin(n).count("1")
        if mod == 0:
            return iter
        else:
            return calc_small(mod, iter)

    for i in range(N):
        mod = (mod_m1 - mod_list_m1[i]) % (B_1-1) if B_array[i] == 1 else (mod_p1 + mod_list_p1[i]) % (B_1+1)
        iter = 1
        if mod == 0:
            print(iter)
        else:
            print(calc_small(mod, iter))

Submission status: Runtime Error

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


N = int(input())
A = int(input().rstrip(), 2)


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


AL = []
for n in range(N):
    AL.append(f(n))

# print(AL)

for i in range(N)[::-1]:
    a = A ^ (1 << i)
    n = a % bin(a).count('1')
    # print(bin(a), n)
    print(AL[n]+1)

Submission status: Runtime Error

Solution code:
N = int(input())
x = list(input())[::-1]
print(len(x))
num = 0
pop_num = 0
for i in range(N):
    if x[i] == "1":
        pop_num += 1
for i in range(N):
    if x[i] == "1":
        num += 2 ** i
        num %= pop_num 



def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

x = x[::-1]
def calc(i,depth,n):
    if depth == 0:
        if x[i] == "1":
            tmp = (num - 2 ** (N - i - 1)) % (pop_num - 1)
            return calc(i,depth+1,tmp)
        else:
            tmp = (num + 2 ** (N - i - 1)) % (pop_num + 1)
            return calc(i,depth+1,tmp)
    else:
        if n == 0: return depth
        return calc(i,depth+1, n % popcnt(n))
        

for i in range(N):
    print(calc(i,0,0))

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
B = str(input())

B_array = np.array(list(map(int, list(B))))
B_1 = B_array.sum()
mod_list_m1 = []
mod_list = []
mod_list_p1 = []
for i in range(N):
    mod_list.append((2**i) % (B_1))
    mod_list_m1.append((2**i) % (B_1-1))
    mod_list_p1.append((2**i) % (B_1+1))
mod_list = np.array(mod_list)[::-1]
mod_list_m1 = np.array(mod_list_m1)[::-1]
mod_list_p1 = np.array(mod_list_p1)[::-1]

mod_m1 = B_array.dot(mod_list_m1) % (B_1-1)
mod_p1 = B_array.dot(mod_list_p1) % (B_1+1)

def calc_small(n, iter):
    iter += 1
    mod = n % bin(n).count("1")
    if mod == 0:
        return iter
    else:
        return calc_small(mod, iter)

for i in range(N):
    mod = (mod_m1 - mod_list_m1[i]) % (B_1-1) if B_array[i] == 1 else (mod_p1 + mod_list_p1[i]) % (B_1+1)
    iter = 1
    if mod == 0:
        print(iter)
    else:
        print(calc_small(mod, iter))

Submission status: Runtime Error

Solution code:
if __name__ == '__main__':
    n = int(input().strip())
    x = input().strip()

    pre_count = [1, 1, 2, 1, 2,
                 1, 2, 1, 2, 1,
                 2, 1, 2, 2, 2,
                 1]
    count_1 = x.count("1")
    for i in range(n):
        count = 1
        _x = list(x)
        _x[i] = "0" if _x[i] == "1" else "1"
        _x = int("".join(_x), 2)
        _x = int(_x % bin(_x).count("1"))
        if not _x == 0:
            count += pre_count[_x - 1]
        print(count)

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
B = str(input())

B_array = np.array(list(map(int, list(B))))
B_1 = B_array.sum()
mod_list_m1 = []
mod_list = []
mod_list_p1 = []
for i in range(N):
    mod_list.append((2**i) % (B_1))
    mod_list_m1.append((2**i) % (B_1-1))
    mod_list_p1.append((2**i) % (B_1+1))
mod_list = np.array(mod_list)[::-1]
mod_list_m1 = np.array(mod_list_m1)[::-1]
mod_list_p1 = np.array(mod_list_p1)[::-1]

mod_m1 = B_array.dot(mod_list_m1) % (B_1-1)
mod_p1 = B_array.dot(mod_list_p1) % (B_1+1)
print(mod_m1)

def calc_small(n, iter):
    iter += 1
    mod = n % bin(n).count("1")
    if mod == 0:
        return iter
    else:
        return calc_small(mod, iter)

for i in range(N):
    mod = (mod_m1 - mod_list_m1[i]) % (B_1-1) if B_array[i] == 1 else (mod_p1 + mod_list_p1[i]) % (B_1+1)
    iter = 1
    if mod == 0:
        print(iter)
    else:
        print(calc_small(mod, iter))

Submission status: Runtime Error

Solution code:

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


def popcount(n):
  num=list(bin(n)[2:])
  num = [int(s) for s in num]
  return sum(num)

n_dic=[0]*50000000

def f(first_n):
  i=0
  n=first_n
  while not n==0:
    if not n_dic[n]==0:
      n_dic[first_n]=n_dic[n]+i
      return n_dic[n]+i
    else:
      n = n % popcount(n)
      i+=1
  return i

for i in range(1,n+1):
  if x[i-1]=="0":
    tmp="1"
  else:
    tmp="0"
  X="0b"+x[:i-1]+tmp+x[i:]
  X=int(X,2)
  print(f(X))
#print(n_dic)

Submission status: Runtime Error

Solution code:
if __name__ == '__main__':
    n = int(input().strip())
    x = input().strip()

    pre_count = [1, 1, 2, 1, 2,
                 1, 2, 1, 2, 1,
                 2, 1, 2, 2, 2]
    count_1 = x.count("1")
    for i in range(n):
        count = 1
        _x = list(x)
        if _x[i] == "1":
            _x[i] = "0"
            _count_1 = count_1 - 1
        else:
            _x[i] = "1"
            _count_1 = count_1 + 1
        _x[i] = "0"
        _x = int("".join(_x), 2)
        _x = int(_x % _count_1)
        if not _x == 0:
            count += pre_count[_x - 1]
        print(count)

Submission status: Runtime Error

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

def popcount(X,ones,count): 
 
    if ones==0:
        return count
    else:
      
        X=X%ones
        
        count+=1
 
        ones=str(bin(X)).count("1")
        
        return popcount(X,ones,count)
 
GroundOnes=x.count("1")
GroundX=int(x,2)
 
CaseOne= GroundX%(GroundOnes-1)
CaseZero= GroundX%(GroundOnes+1)

TwoPowerCaseOne=[]
TwoPowerCaseZero=[]

for j in range(N):
  TwoPowerCaseOne.append(2**(N-j-1) % (GroundOnes-1))
  TwoPowerCaseZero.append(2**(N-j-1) % (GroundOnes+1))
  
for i in range(N):
    
    #CaseOne
    if x[i]=="1":
        ones=GroundOnes-1
        X=CaseOne-TwoPowerCaseOne[i]
        
    #CaseZero
    else:
        ones=GroundOnes+1
        X=CaseZero+TwoPowerCaseZero[i]
            
 
    # print("for loop",i)
    # print("ones",ones)
    # print("new2bit",new2bit)
    # print(" ------ return --- ",popcount(X,ones,0))
    print(i+1,popcount(X,ones,0))

Submission status: Runtime Error

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()


N=int(input())
X=input()
C=X.count("1")

lst=[]
lstcount=[]
for x in [C-1,C+1]:
    flg=0
    if x<=0:
        lst.append(0)
        lstcount.append(0)
    else:
        Z=0
        p=1
        for i in range(N):
            if X[-i-1]=="1":
                Z+=p
            p*=2
            if Z>=x:
                Z%=x
                flg=1
            if flg:
                p%=x
        lst.append(Z)
        lstcount.append(flg)
#print(lst)
fac1=[1]
fac2=[1]
C1=C-1
C2=C+1
for i in range(N):
    fac1.append(fac1[-1]*2%C1)
    fac2.append(fac2[-1]*2%C2)

for i in range(N):

    _C=C+(1 if X[i]=="0"  else -1 )
    if _C==0:
        print(0)
        continue
    if  X[i]=="0":
        lstidx=1
    else:
        lstidx=0

    idx=(N-1-i)

    value=lst[lstidx]+(fac2[idx] if  X[i]=="0" else fac1[idx])
    bit=value
    count=0
    while value and _C:
        count+=1
        value%=_C
        _C=0
        bit=value
        while bit:
            _C+=bit&1
            bit>>=1
    print(max(count,1))

Submission status: Runtime Error

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()


N=int(input())
X=input()
C=X.count("1")

lst=[]
lstcount=[]
for x in [C-1,C+1]:
    flg=0
    if x<=0:
        lst.append(0)
        lstcount.append(0)
    else:
        Z=0
        p=1
        for i in range(N):
            if X[-i-1]=="1":
                Z+=p
            p*=2
            if Z>=x:
                Z%=x
                flg=1
            if flg:
                p%=x
        lst.append(Z)
        lstcount.append(flg)
#print(lst)
fac1=[1]
fac2=[1]
C1=C-1
C2=C+1
for i in range(N):
    fac1.append(fac1[-1]*2%C1)
    fac2.append(fac2[-1]*2%C2)

for i in range(N):

    _C=C+(1 if X[i]=="0"  else -1 )
    if _C==0:
        print(0)
        continue
    if  X[i]=="0":
        lstidx=1
    else:
        lstidx=0

    idx=(N-1-i)

    value=lst[lstidx]+(fac2[idx] if  X[i]=="0" else fac1[idx])
    bit=value
    count=0
    while value:
        count+=1
        value%=_C
        _C=0
        bit=value
        while bit:
            _C+=bit&1
            bit>>=1
        if _C==0:
            break
    print(max(count,1))

Submission status: Runtime Error

Solution code:
N = int(input())
x = list(input())[::-1]

num = 0
pop_num = 0
for i in range(N):
    if x[i] == "1":
        num += 2 ** i
        pop_num += 1

def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c
import sys
sys.setrecursionlimit(10**6)

x = x[::-1]
def calc(i,depth,n):
    if depth == 0:
        if x[i] == "1":
            tmp = (num - 2 ** (N - i - 1)) % (pop_num - 1)
            return calc(i,depth+1,tmp)
        else:
            tmp = (num + 2 ** (N - i - 1)) % (pop_num + 1)
            return calc(i,depth+1,tmp)
    else:
        if n == 0: return depth
        return calc(i,depth+1, n % popcnt(n))
        

for i in range(N):
    print(calc(i,0,0))

Submission status: Runtime Error

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()


N=int(input())
X=input()
C=X.count("1")

lst=[]
lstcount=[]
for x in [C-1,C+1]:
    flg=0
    if x<=0:
        lst.append(0)
        lstcount.append(0)
    else:
        Z=0
        p=1
        for i in range(N):
            if X[-i-1]=="1":
                Z+=p
            p*=2
            if Z>=x:
                Z%=x
                flg=1
            if flg:
                p%=x
        lst.append(Z)
        lstcount.append(flg)
#print(lst)
fac1=[1]
fac2=[1]
C1=C-1
C2=C+1
for i in range(N):
    fac1.append(fac1[-1]*2%C1)
    fac2.append(fac2[-1]*2%C2)

for i in range(N):

    _C=C+(1 if X[i]=="0"  else -1 )
    if _C==0:
        print(0)
        continue
    if  X[i]=="0":
        lstidx=1
    else:
        lstidx=0

    idx=(N-1-i)

    value=lst[lstidx]+(fac2[idx] if  X[i]=="0" else fac1[idx])
    bit=value
    count=0
    while value:
        count+=1
        value%=_C
        _C=0
        bit=value
        while bit:
            _C+=bit&1
            bit>>=1
    print(max(count,1))