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:


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def popcount(N):
    if N == 0:
        return 0
    one_count = 0
    temp = N
    while temp > 0:
        one_count += temp%2
        temp //= 2
    return 1+popcount(N%one_count)


def solve():
    N = read_int()
    X = input()
    one_count = X.count('1')
    if one_count == 0:
        for _ in range(N):
            print(0)
        return

    new_X = [0]*N
    steps = [0]*N

    base_up = 1
    up_under_modulo = 0

    for i in range(N-1, -1, -1):
        if X[i] == '1':
            up_under_modulo = (up_under_modulo+base_up)%(one_count+1)
        if X[i] == '0':
            new_X[i] += base_up
            steps[i] = 1
        base_up = (base_up*2)%(one_count+1)

    base_down = 1
    down_under_modulo = 0

    for i in range(N-1, -1, -1):
        if X[i] == '1':
            if one_count-1 != 0:
                down_under_modulo = (down_under_modulo+base_down)%(one_count-1)
        if X[i] == '1':
            new_X[i] += -base_down
        if one_count != 1:
            base_down = (base_down*2)%(one_count-1)
            steps[i] = 1
        else:
            steps[i] = 0

    for i in range(N):
        if X[i] == '1':
            if one_count-1 != 0:
                new_X[i] = (new_X[i]+down_under_modulo)%(one_count-1)
        else:
            new_X[i] = (new_X[i]+up_under_modulo)%(one_count+1)

    for i in range(N):
        print(steps[i]+popcount(new_X[i]))


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def popcount(N):
    if N == 0:
        return 0
    one_count = 0
    temp = N
    while temp > 0:
        one_count += temp%2
        temp //= 2
    return 1+popcount(N%one_count)


def solve():
    N = read_int()
    X = input()
    one_count = X.count('1')
    if one_count == 0:
        for _ in range(N):
            print(0)
        return

    new_X = [0]*N
    steps = [0]*N

    base_up = 1
    up_under_modulo = 0

    for i in range(N-1, -1, -1):
        if X[i] == '1':
            up_under_modulo = (up_under_modulo+base_up)%(one_count+1)
        if X[i] == '0':
            new_X[i] += base_up
            steps[i] = 1
        base_up = (base_up*2)%(one_count+1)

    base_down = 1
    down_under_modulo = 0

    for i in range(N-1, -1, -1):
        if X[i] == '1':
            if one_count-1 != 0:
                down_under_modulo = (down_under_modulo+base_down)%(one_count-1)
        if X[i] == '1':
            new_X[i] += -base_down
        if one_count != 1:
            base_down = (base_down*2)%(one_count-1)
            steps[i] = 1
        else:
            steps[i] = 0

    for i in range(N):
        if X[i] == '1':
            new_X[i] = (new_X[i]+down_under_modulo)%(one_count-1)
        else:
            new_X[i] = (new_X[i]+up_under_modulo)%(one_count+1)

    for i in range(N):
        print(steps[i]+popcount(new_X[i]))


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
def popcount(N):
  S = bin(N)
  return S[2:].count('1')

def func(S, i):
  if S[i] == '0':
    N = eval('0b' + S[0:i] + '1' + S[i + 1:])
  else:
    N = eval('0b' + S[0:i] + '0' + S[i + 1:])
  
  cnt = 0
  while 1:
    N = N % popcount(N)
    cnt += 1
    if N == 0:
      break
      
  return cnt

N = int(input())
S = input()
for n in range(N):
  print(func(S,n))

Submission status: Runtime Error

Solution code:
def popcount(N):
  S = bin(N)
  return S[2:].count('1')

def func(S, i):
  if S[i] == '0':
    N = eval('0b' + S[0:i] + '1' + S[i + 1:])
  else:
    N = eval('0b' + S[0:i] + '0' + S[i + 1:])
  
  cnt = 0
  while 1:
    N = N % popcount(N)
    cnt += 1
    if N == 0:
      break
      
  return cnt

N = int(input())
S = input()
for n in range(1,N + 1):
  print(func(S,n))

Submission status: Runtime Error

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

def solve():
    N = INT()
    xbin = input()
    xdec = int(xbin, 2)
    m = xbin.count('1')

    a = xdec % (m+1)
    b = xdec % (m-1)

    num = [0]*N
    for i in range(1, N):
        num[i] = num[i % bin(i).count('1')] + 1

    for i in range(N):
        if xbin[i] == '0':
            y = ( a + pow(2, N-i-1, m+1) ) % ( m+1 )
            print(num[y] + 1)
        elif m <= 1:
            print(0)
        else:
            y = ( b + pow(2, N-i-1, m-1) ) % ( m-1 )
            print(num[y] + 1)

if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

def solve():
    N = INT()
    xbin = input()
    xdec = int(xbin, 2)
    m = xbin.count('1')

    num = [0]*N
    for i in range(1, N):
        num[i] = num[i % bin(i).count('1')] + 1

    pop = [m + 1, m - 1]
    x = [xdec % pop[0], xdec % pop[1]]

    reg = [[0]*2 for i in range(N)]
    reg[N-1] = [1, 1]
    for i in range(N-2, -1, -1):
        reg[i][0] = reg[i+1][0]*2 % pop[0]
        reg[i][1] = reg[i+1][1]*2 % pop[1]

    for i in range(N):
        if xbin[i] == '0':
            y = ( x[0] + reg[i][0] ) % pop[0]
        else:
            y = ( x[1] - reg[i][1] ) % pop[1]
        print(num[y] + 1)

if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

def solve():
    N = INT()
    xbin = input()
    xdec = int(xbin, 2)
    m = xbin.count('1')

    num = [0]*2*10**5
    for i in range(1, 2*10**5):
        num[i] = num[i % bin(i).count('1')] + 1

    pop = [m + 1, m - 1]
    x = [xdec % pop[0], xdec % pop[1]]

    reg = [[0]*2 for i in range(N)]
    reg[N-1] = [1, 1]
    for i in range(N-2, -1, -1):
        reg[i][0] = reg[i+1][0]*2 % pop[0]
        reg[i][1] = reg[i+1][1]*2 % pop[1]

    for i in range(N):
        if xbin[i] == '0':
            y = ( x[0] + reg[i][0] ) % pop[0]
        else:
            y = ( x[1] - reg[i][1] ) % pop[1]
        print(num[y] + 1)

if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

def solve():
    N = INT()
    xbin = input()
    xdec = int(xbin, 2)
    m = xbin.count('1')

    num = [0]*2*10**5
    for i in range(1, 2*10**5):
        num[i] = num[i % bin(i).count('1')] + 1
    
    reg = [0]*N
    reg[N-1] = 1
    for i in range(N-2, -1, -1):
        reg[i] = reg[i+1]*2

    pop = [m + 1, m - 1]
    x = [xdec % pop[0], xdec % pop[1]]

    for i in range(N):
        if xbin[i] == '0':
            y = x[0] + reg[i] % pop[0]
        else:
            y = x[1] - reg[i] % pop[1]
        print(num[y] + 1)

if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

def solve():
    N = INT()
    xbin = input()
    xdec = int(xbin, 2)
    m = xbin.count('1')

    num = [0]*2*10**5
    for i in range(1, 2*10**5):
        num[i] = num[i % bin(i).count('1')] + 1
    
    reg = [0]*N
    reg[N-1] = 1
    for i in range(N-2, -1, -1):
        reg[i] = reg[i+1]*2

    for i in range(N):
        if xbin[i] == '0':
            x = xdec + reg[i]
            popcount = m + 1
        else:
            x = xdec - reg[i]
            popcount = m - 1
        print(num[x % popcount] + 1)

if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
N = cin()[0]
X = input()
ans = [1] * N
A = [0] * N

cnt = X.count("1")
M0 = 0
M1 = 0
temp0 = 1
temp1 = 1

for i in range(N):
    if(X[N - 1 - i] == '1'):
        if(cnt != 1):
            M0 = (M0 + temp0) % (cnt - 1)
        M1 = (M1 + temp1) % (cnt + 1)

    if(cnt != 1):
        temp0 = (temp0 * 2) % (cnt - 1)
    temp1 = (temp1 * 2) % (cnt + 1)

temp0 = 1
temp1 = 1

for i in range(N):

    if(X[N - 1 - i] == '0'):
        A[N - 1 - i] = (M1 + temp1) % (cnt + 1)

    else:
        if(cnt == 1):
            A[i] = 0
            ans[N - 1 - i] -= 1
        
        else:
            A[N - 1 - i] = abs(M0 - temp0) % (cnt - 1)

    if(cnt != 1):
        temp0 = (temp0 * 2) % (cnt - 1)
    temp1 = (temp1 * 2) % (cnt + 1)

for i in range(N):

    while(A[i]):

        pop_count = bin(A[i]).count("1")
        A[i] %= pop_count
        ans[i] += 1

for i in range(N):  print(ans[i]);

Submission status: Runtime Error

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

def solve():
    N = INT()
    xbin = input()
    xdec = int(xbin, 2)
    m = xbin.count('1')

    num = [0]*(2*10**5+1)
    for i in range(1, 2*10**5+1):
        num[i] = num[i % bin(i).count('1')] + 1

    reg = [0]*N
    tmp = 1
    for i in range(1, N+1):        
        if len(xbin) < i or xbin[-i] == '0':
            x = xdec + tmp
            popcount = m + 1
        else:
            x = xdec - tmp
            popcount = m - 1
        reg[i-1] = x % popcount
        tmp *= 2

    for i in range(N-1, -1, -1):
        print(num[reg[i]]+1)


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

def solve():
    N = INT()
    xbin = input()
    xdec = int(xbin, 2)
    m = xbin.count('1')

    num = [0]*(2*10**5+1)
    for i in range(1, 2*10**5+1):
        num[i] = num[i % bin(i).count('1')] + 1

    reg = [0]*N
    tmp = 1
    for i in range(N):        
        if xbin[N-1-i] == '0':
            x = xdec + tmp
            popcount = m + 1
        else:
            x = xdec - tmp
            popcount = m - 1
        reg[i] = x % popcount
        tmp *= 2

    for i in range(N-1, -1, -1):
        print(num[reg[i]]+1)

if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

def solve():
    N = INT()
    xbin = input()
    xdec = int(xbin, 2)
    m = xbin.count('1')

    num = [0]*(2*10**5+1)
    for i in range(1, 2*10**5+1):
        num[i] = num[i % bin(i).count('1')] + 1

    for i in range(N):
        if xbin[i] == '0':
            x = xdec + 2**(N-1-i)
            popcount = m + 1
        else:
            x = xdec - 2**(N-1-i)
            popcount = m - 1
        print(num[x % popcount] + 1)

if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
x = X[::-1]
one = X.count('1')
up = 0
down = 0
for i in range(N):
    up += (int(x[i]) * pow(2,i,one+1) % (one+1))
    up %= one+1
    if one > 1:
        down += (int(x[i]) * pow(2,i,one-1) % (one-1))
        down %= one-1
# print(up,down)
def f(ud,one):
    if one <= 0:
        return 0
    else:
        if ud == 0:
            return 1

        cnt = 0
        while ud != 0:
            ud = ud % one
            one = format(ud,'b').count('1')
            cnt += 1
        return cnt



for i in range(len(X)):
    if X[i] == '1':
        print(f((down - pow(2,(len(X)-1) - i, one-1)) % (one-1),one-1))
        #print(down - pow(2,(len(X)-1) - i, one-1) % (one-1))
    else:
        print(f((up + pow(2,(len(X)-1) - i, one+1)) % (one+1),one+1))
        #print(up + pow(2,(len(X)-1) - i, one+1) % (one+1))

Submission status: Runtime Error

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

def main():
  n = int(input())
  x = input()
  c = x.count('1')
  # popcount(n)は高々c+1
  m = 22000
  dp = [0]*(m+2)
  
  for i in range(1, m+2):
    dp[i] = dp[i % popcnt(i)] + 1
    
  if c == 1:
    for i in range(n):
      if x[i] == '0':
        xp = int(x, 2) % (c+1)
        print(dp[(xp + pow(2, n-i-1, c+1)) % (c+1)] + 1)
      else:
        print(0)
    exit()
  
  # 1が増えたときと減ったときのpopcount
  cp, cm = c+1, c-1
  xp, xm = int(x, 2) % cp, int(x, 2) % cm
  
  for i in range(n):
    if x[i] == '0':
      print(dp[(xp + pow(2, n-i-1, cp)) % cp] + 1)
    else:
      print(dp[(xm - pow(2, n-i-1, cm)) % cm] + 1)


def popcnt(n):
  return bin(n).count('1')

  
if __name__ == '__main__':
  main()

Submission status: Runtime Error

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

def main():
  n = int(input())
  x = input()
  arr = []
  for i in range(n):
    arr += [inv(x, i)]
    
  dp = [None]*(max(arr)+1)
  dp[0] = 0
  
  for n in arr:
    dp = f(n, dp)
    print(dp[n])
  
  
def inv(x, i):
  if x[i] == '0':
    tmp = '1'
  else:
    tmp = '0'
  s = x[:i] + tmp + x[i+1:]
  return int(s, 2)

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

def f(n, dp):
  if dp[n] == None:
    p = n % popcnt(n)
    tmp = dp[p]
    if tmp != None:
      dp[n] = tmp + 1
      return dp
    else:
      dp = f(p, dp)
      dp[n] = dp[p] + 1
      return dp
  else:
    return dp
  
if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
pc=[0]*(2*10**5+1)
pc[1]=1
for i in range(1,2*10**5+1):
  pc[i]=pc[i>>1]+pc[i&1]
f=[0]*(2*10**5+1)
for i in range(1,2*10**5+1):
  f[i]=f[i%pc[i]]+1
xx=int(x,2)
j=2**(n-1)
cnt=x.count('1')
xm=xx%(cnt-1)
xp=xx%(cnt+1)
for i in range(n):
  if x[i]=='1':
    c=cnt-1
    nx=(xm-(j>>i)%c)%c
  else:
    c=cnt+1
    nx=(xp+(j>>i)%c)%c
  print(f[nx]+1)

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
pc=[0]*(2*10**5+1)
pc[1]=1
for i in range(1,2*10**5+1):
  pc[i]=pc[i>>1]+pc[i&1]
f=[0]*(2*10**5+1)
for i in range(1,2*10**5+1):
  f[i]=f[i%pc[i]]+1
xx=int(x,2)
j=2**(n-1)
cnt=x.count('1')
for i in range(n):
  if x[i]=='1':
    c=cnt-1
    nx=(xx-(j>>i))%c
  else:
    c=cnt+1
    nx=(xx+(j>>i))%c
  print(f[nx]+1)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
X = input()
X_10 = 0
popcount_X = 0

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

def f_func(n):
  popcnt = popcount(n)
  if popcnt == 0:
    return 0
  return n % popcnt

for i in range(N):
  j = N - (i + 1)
  X_10 += int(X[i]) * 2 ** j
  if X[i] == '1':
    popcount_X += 1

popcount_X_plus = popcount_X + 1
popcount_X_minus = popcount_X - 1
if popcount_X_plus == 0:
  fX_plus = 0
else:
  fX_plus = X_10 % popcount_X_plus

fX_minus = X_10 % popcount_X_minus


for i in range(N):
  j = N - (i + 1)
  
  Xi = 0
  f = 0
  ans = 1
  
  if X[i] == '0':
    Xi = X_10 + 2**j
    f = (fX_plus + 2**j % popcount_X_plus) % popcount_X_plus
    
  elif X[i] == '1':
    Xi = X_10 - 2**j
    if popcount_X_minus == 0:
      f = 0
    else:
      f = (fX_minus - 2**j % popcount_X_minus) % popcount_X_minus
      
  
  while f > 0:
    f = f_func(f)
    ans += 1
  print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
X = input()
X_10 = 0
popcount_X = 0

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

def f_func(n):
  popcnt = popcount(n)
  if popcnt == 0:
    return 0
  return n % popcnt

for i in range(N):
  j = N - (i + 1)
  X_10 += int(X[i]) * 2 ** j
  if X[i] == '1':
    popcount_X += 1

popcount_X_plus = popcount_X + 1
popcount_X_minus = popcount_X - 1
fX_plus = X_10 % popcount_X_plus
fX_minus = X_10 % popcount_X_minus

for i in range(N):
  j = N - (i + 1)
  
  Xi = 0
  f = 0
  ans = 1
  
  if X[i] == '0':
    Xi = X_10 + 2**j
    if popcount_X_plus == 0:
      f = 0
    else:
      f = (fX_plus + 2**j % popcount_X_plus) % popcount_X_plus
    
  elif X[i] == '1':
    Xi = X_10 - 2**j
    if popcount_X_minus == 0:
      f = 0
    else:
      f = (fX_minus - 2**j % popcount_X_minus) % popcount_X_minus
      
  
  while f > 0:
    f = f_func(f)
    ans += 1
  print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
X = input()
X_10 = 0
popcount_X = 0

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

def f_func(n):
  if n == 0:
    return 0
  return n % popcount(n)

for i in range(N):
  j = N - (i + 1)
  X_10 += int(X[i]) * 2 ** j
  if X[i] == '1':
    popcount_X += 1

popcount_X_plus = popcount_X + 1
popcount_X_minus = popcount_X - 1
fX_plus = X_10 % popcount_X_plus
fX_minus = X_10 % popcount_X_minus

for i in range(N):
  j = N - (i + 1)
  
  Xi = 0
  f = 0
  ans = 1
  
  if X[i] == '0':
    Xi = X_10 + 2**j
    if popcount_X_plus == 0:
      f = 0
    else:
      f = (fX_plus + 2**j % popcount_X_plus) % popcount_X_plus
    
  elif X[i] == '1':
    Xi = X_10 - 2**j
    if popcount_X_minus == 0:
      f = 0
    else:
      f = (fX_minus - 2**j % popcount_X_minus) % popcount_X_minus
      
  
  while f > 0:
    f = f_func(f)
    ans += 1
  print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
X = input()
X_10 = 0
popcount_X = 0

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

def f_func(n):
  if n == 0:
    return 0
  return n % popcount(n)

for i in range(N):
  j = N - (i + 1)
  X_10 += int(X[i]) * 2 ** j
  if X[i] == '1':
    popcount_X += 1

popcount_X_plus = popcount_X + 1
popcount_X_minus = popcount_X - 1
fX_plus = X_10 % popcount_X_plus
fX_minus = X_10 % popcount_X_minus

for i in range(N):
  j = N - (i + 1)
  
  Xi = 0
  f = 0
  popcnt = 0
  ans = 1
  
  if X[i] == '0':
    Xi = X_10 + 2**j
    popcnt = popcount_X + 1
    f = (fX_plus + 2**j % popcount_X_plus) % popcount_X_plus
    
  elif X[i] == '1':
    Xi = X_10 - 2**j
    popcnt = popcount_X - 1
    f = (fX_minus - 2**j % popcount_X_minus) % popcount_X_minus
  
  while f > 0:
    f = f_func(f)
    ans += 1
  print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
X = input()
X_10 = 0
popcount_X = 0

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

def f_func(n):
  return n % popcount(n)

for i in range(N):
  j = N - (i + 1)
  X_10 += int(X[i]) * 2 ** j
  if X[i] == '1':
    popcount_X += 1

popcount_X_plus = popcount_X + 1
popcount_X_minus = popcount_X - 1
fX_plus = X_10 % popcount_X_plus
fX_minus = X_10 % popcount_X_minus

for i in range(N):
  j = N - (i + 1)
  
  Xi = 0
  f = 0
  popcnt = 0
  ans = 1
  
  if X[i] == '0':
    Xi = X_10 + 2**j
    popcnt = popcount_X + 1
    f = (fX_plus + 2**j % popcount_X_plus) % popcount_X_plus
    
  elif X[i] == '1':
    Xi = X_10 - 2**j
    popcnt = popcount_X - 1
    f = (fX_minus - 2**j % popcount_X_minus) % popcount_X_minus
  
  while f > 0:
    f = f_func(f)
    ans += 1
  print(ans)

Submission status: Runtime Error

Solution code:
def pop_count(n):
    return bin(n).count("1")


N = int(input())
X = list(map(int, input()))
X_m = 0
X_p = 0
pop_X = 0
if 1 in X:
    pop_X += X.count(1)
    for i in range(N):
        if X[N - i - 1]:
            X_m += pow(2, i, pop_X - 1)
            X_m %= pop_X - 1
            X_p += pow(2, i, pop_X + 1)
            X_p %= pop_X + 1

for i in range(N):
    ans = 1
    n = 0
    if X[i]:
        n += X_m
        n -= pow(2, N - i - 1, pop_X - 1)
        n %= pop_X - 1
    else:
        n += X_p
        n += pow(2, N - i - 1, pop_X + 1)
        n %= pop_X + 1
    while n:
        n %= pop_count(n)
        ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
def pop_count(n):
    return bin(n).count("1")


N = int(input())
X = list(map(int, input()))
pop_X = X.count(1)
X_m = 0
X_p = 0
for i in range(N):
    if X[N - i - 1]:
        X_p += pow(2, i, pop_X + 1)
        X_p %= pop_X + 1
        X_m += pow(2, i, pop_X - 1)
        X_m %= pop_X - 1

for i in range(N):
    ans = 1
    n = 0
    if X[i]:
        n += X_m
        n -= pow(2, N - i - 1, pop_X - 1)
        n %= pop_X - 1
    else:
        n += X_p
        n += pow(2, N - i - 1, pop_X + 1)
        n %= pop_X + 1
    while n:
        n %= pop_count(n)
        ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
def solve():
  N = int(input())
  X = input()
  bl = X.count('1')
  bitp = 0
  for i in range(N):
    bitp += int(X[i])*pow(2,N-1-i,bl+1)
    bitp %= bl+1
  bitm = 0
  if bl>1:
    for i in range(N):
      bitm += int(X[i])*pow(2,N-1-i,bl-1)
      bitm %= bl-1
  
  ans = [0]*N
  dp = [0]*(N+1)
  for i in range(1,N+1):
    dp[i] = dp[i%(bin(i).count('1'))]+1
  for i in range(N):
    if X[i]=='1':
      bit1 = bitm - pow(2,N-1-i,bl-1)
      bl1 = bl-1
      if bl1==0:
        ans[i] = 0
        continue
    else:
      bit1 = bitp + pow(2,N-1-i,bl+1)
      bl1 = bl+1
    ans[i] = dp[bit1%bl1]+1
  return ans
print(*solve(),sep='\n')

Submission status: Runtime Error

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

ansl = [0]*n
for i in range(1,n):
    ans = 0
    num = i
    while True:
        pc = bin(num).count("1")
        num %= pc
        ans += 1
        if num == 0: break
    ansl[i] = ans

print(ansl)
for i in range(n):
    bit = (1<<(n-1-i))
    num = x^bit
    pc = bin(num).count("1")
    next_num = num%pc
    a = ansl[next_num] + 1
    print(a)

Submission status: Runtime Error

Solution code:
def solve():
  N = int(input())
  X = input()
  bl = X.count('1')
  bitp = 0
  for i in range(N):
    bitp += int(X[i])*pow(2,N-1-i)
    bitp %= bl+1
  bitm = 0
  if bl>0:
    for i in range(N):
      bitm += int(X[i])*pow(2,N-1-i)
      bitm %= bl-1
  
  ans = [0]*N
  dp = [0]*(N+1)
  for i in range(1,N+1):
    dp[i] = dp[i%(bin(i).count('1'))]+1
  for i in range(N):
    if X[i]=='1':
      bit1 = bitm - pow(2,N-1-i)
      bl1 = bl-1
      if bl1==0:
        ans[i] = 0
        continue
    else:
      bit1 = bitp + pow(2,N-1-i)
      bl1 = bl+1
    ans[i] = dp[bit1%bl1]+1
  return ans
print(*solve(),sep='\n')

Submission status: Runtime Error

Solution code:
def solve():
  N = int(input())
  X = input()
  bl = X.count('1')
  bit = 0
  for i in range(N):
    bit += int(X[i])*pow(2,N-1-i)
    bit %= bl
  ans = [0]*N
  dp = [0]*(N+1)
  for i in range(1,N+1):
    dp[i] = dp[i%(bin(i).count('1'))]+1
  for i in range(N):
    if X[i]=='1':
      bit1 = bit - pow(2,N-1-i)
      bl1 = bl-1
      if bl1==0:
        ans[i] = 0
        continue
    else:
      bit1 = bit + pow(2,N-1-i)
      bl1 = bl+1
    ans[i] = dp[bit1%bl1]+1
  return ans
print(*solve(),sep='\n')