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: Wrong Answer

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

input = sys.stdin.readline

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

inf = float('inf')
mod = 1000000007

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

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

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

		oct = int(tmpX, 2)

		ans_tmp = 0
		if oct in mem:
			ans_tmp = mem[oct]

		else:
			while True:
				if oct == 0:
					break
				tmp = bc(oct)
				oct = oct % tmp
				ans_tmp += 1
				if oct == 0:
					break
				if oct in mem:
					ans_tmp += mem[oct]
					break

		if oct in mem:
			pass
		else:
			mem[oct] = ans_tmp

		ans.append(ans_tmp)

	for i in ans:
		print(i)

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

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

Submission status: Wrong Answer

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

input = sys.stdin.readline

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

inf = float('inf')
mod = 1000000007

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

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

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

		oct = int(tmpX, 2)

		ans_tmp = 0
		if oct in mem:
			ans_tmp = mem[oct]

		else:
			while True:
				if oct == 0:
					break
				tmp = bc(oct)
				oct = oct % tmp
				ans_tmp += 1
				if oct == 0:
					break
				if oct in mem:
					ans_tmp += mem[oct]
					break

		if ans_tmp in mem:
			pass
		else:
			mem[oct] = ans_tmp

		ans.append(ans_tmp)

	for i in ans:
		print(i)

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

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

Submission status: Wrong Answer

Solution code:
def rem(n, a):
    if a == 0:
        return 0
    ans=0
    for i in n:
        ans*=2
        ans+=i
        ans%=a
    return ans
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
    
n, x = int(input()), list(map(int,input()))

p = x.count(1)
m = [0] * n
q = p - 1
if q!=0:
    m[0] = 1
    for i in range(1, n):
        m[i] = 2 * m[i - 1] % q

w = p + 1
k = [0] * n
k[0] = 1
for i in range(1, n):
    k[i] = 2 * k[i - 1] % w

s = rem(x, q)
t = rem(x, w)
for i in range(n):
    if x[i] == 0:
        a = (t + k[n - i - 1]) % w
        
    else:
        if q == 0:
            print(0)
            continue
        a = (s - k[n - i - 1]) % q

    cnt = 1
    b = popcnt(a)
    # if i == 21:
    #     print(a,b)
    while b:
        a %= b
        b = popcnt(a)
        cnt += 1
    print(cnt)

Submission status: Wrong Answer

Solution code:
def f(n):
    ret = 0
    while True:
        popcount = sum(list(map(int,bin(n)[2:])))
        if popcount ==0:
            break
        n = n%popcount
        ret += 1
        if n==0:
            return ret
N = int(input())
X = input()
for i in range(N):
    tmp = list(X)
    if tmp[i]=='0':
        tmp[i] = '1'
    else:
        tmp[i]='0'
    print(f(int('0b'+"".join(tmp),0)))

Submission status: Wrong Answer

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

import sys
input=sys.stdin.readline

LEN=2*10**5+10

moves=[0]*LEN
for i in range(1,LEN):
    popcount=0
    for j in range(20):
        if i&(i<<j):
            popcount+=1
    moves[i]=moves[i%popcount]+1

n=int(input())
x=input()
k=x.count('1')
if k==0:
    for i in range(n):
        print(0)
elif k==1:
    pos=x.index('1')
    for i in range(n):
        if i==pos:
            print(0)
        else:
            if pos==n-1:
                print(2)
            else:
                if i==n-1:
                    print(2)
                else:
                    print(0)
else:
    sum1=0
    sum2=0
    tmp1=1
    tmp2=1
    for i in range(n-1,-1,-1):
        if x[i]=='1':
            sum1+=tmp1
            sum1%=k+1
            sum2+=tmp2
            sum2%=k-1
        tmp1*=2
        tmp1%=k+1
        tmp2*=2
        tmp2%=k-1
    for i in range(n):
        if x[i]=='0':
            tmp=sum1+pow(2,n-i-1,k+1)
            tmp%=k+1
            print(moves[tmp]+1)
        else:
            tmp=sum2-pow(2,n-i-1,k-1)
            tmp%=k-1
            print(moves[tmp]+1)

Submission status: Wrong Answer

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

input = sys.stdin.readline

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

inf = float('inf')
mod = 1000000007

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

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

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

		oct = int(tmpX, 2)

		ans_tmp = 0
		if oct in mem:
			print("ss")
			ans_tmp = mem[oct]

		else:
			while True:
				if oct == 0:
					break
				tmp = bc(oct)
				oct = oct % tmp
				ans_tmp += 1
				if oct == 0:
					break
				if oct in mem:
					ans_tmp += mem[oct]
					break

		if ans_tmp in mem:
			pass
		else:
			mem[oct] = ans_tmp

		ans.append(ans_tmp)

	for i in ans:
		print(i)

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

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

Submission status: Wrong Answer

Solution code:
def examA():
    L, R, D = LI()
    ans = R//D - (L-1)//D
    print(ans)
    return

def examB():
    N = I()
    A = LI()
    ans = 0
    for i,a in enumerate(A):
        if i%2==0:
            if a%2==1:
                ans += 1
    print(ans)
    return

def examC():
    N = I()
    ans = [0]*N
    for x in range(1,101):
        for y in range(1,101):
            for z in range(1,101):
                cur = x**2 + y**2 + z**2 + x*y + y*z + x*z
                if cur<N+1:
                    ans[cur-1] += 1

    for v in ans:
        print(v)
    return

def examD():
    def popcnt0(n):
        c = 0
        for i in range(20):
            c += (n >> i) & 1
        return c
    def cnt(num):
        c = 0
        while(num>0):
            #num %= bin(num).count("1")
            num %= popcnt0(num)
            c += 1
        return c
    N = I()
    X = SI()
    S_upper = [0]*N
    S_lower = [0]*N
    start_upper = 0
    start_lower = 0
    bit = 0
    ans = [0]*N
    for s in X:
        if s=="1":
            bit += 1
    if bit==1:
        b = 0
        for i in range(N):
            if X[i]=="1":
                ans[i] = 0
                b = i
            else:
                ans[i] = 1
        if b==N-1:
            for i in range(N-1):
                ans[i] += 1
        for v in ans:
            print(v)
        return
    elif bit==0:
        for v in ans:
            print(1)
        return

    for i in range(N):
        S_upper[i] = pow(2,N-i-1,bit+1)
        S_lower[i] = pow(2,N-i-1,bit-1)
        if X[i]=="1":
            start_upper += S_upper[i]
            start_lower += S_lower[i]
            start_upper %= (bit+1)
            start_lower %= (bit-1)
    for i in range(N):
        if X[i]=="0":
            cur = (start_upper + S_upper[i]) % (bit+1)
            ans[i] = cnt(cur)+1
        else:
            cur = (start_lower - S_lower[i] + 2*(bit -1)) % (bit-1)
            ans[i] = cnt(cur)+1
        #print(cur)

    for v in ans:
        print(v)
    return

def examE():
    T = I()
    ans = [0]*T

    for t in range(T):
        pass


    for v in ans:
        print(v)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(2*10**6)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""

n = onem()

po = input()[:-1]
num = int("0B" + po,0)
co = po.count("1")

for i in range(n):
	if po[i] == "0":
		coco = co + 1
		if coco == 0:
			continue
		ima = num + pow(2,(n-1-i),coco)
		count = 0
		while True:
			if ima == 0:
				break
			else:
				ima %= coco
				count += 1
				coco = format(ima,"b").count("1")
	else:
		coco = co - 1
		if coco == 0:
			continue
		ima = num - pow(2,(n-1-i),coco)
		count = 0
		while True:
			if ima == 0:
				break
			else:
				ima %= coco
				count += 1
				coco = format(ima,"b").count("1")
	print(count)

Submission status: Wrong Answer

Solution code:
def f(n):
    ret = 0
    while(n):
        n = n%bin(n).count('1')
        ret += 1
    return ret

cut = 50

m = int(input())
x = input()
if(len(x) > cut): x = x[-cut: ]

n = int('0b' + x, 2)
large = f(n)
for i in range(m):
    if(m > cut):
        if(i < m-cut): print(large)
        else:
            num = n ^ (1 << (m-i-1))
            print(f(num))

    
    num = n ^ (1 << (m-i-1))
    print(f(num))

Submission status: Wrong Answer

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

def main():
    n = int(input())
    x = input()
    count = 0
    sub = 1
    last = [[0, 0]]*n
    for i in range(n):
        if x[i] == "1":
            count += 1
            
    if count == 0:
        for i in range(n):
            print(1)
        sys.exit()
    if count == 1:
        if x[-1] == "1":
            for i in range(n-1):
                print(2)
            print(0)
            sys.exit()
        else:
            for i in range(n-1):
                if x[i] == "1":
                    print(0)
                else:
                    print(1)
            print(2)
            sys.exit()
    
    sub1, sub2 = 1, 1
    num1, num2 = 0, 0
    for i in range(n):
        last[i] = [sub1, sub2]
        if x[n-i-1] == "1":
            num1 += sub1
            num2 += sub2
            num1 %= count-1
            num2 %= count+1
        sub1 *= 2
        sub2 *= 2
        sub1 %= count-1
        sub2 %= count+1
            
    
    
    key = [0]*(2**18+1)
    for i in range(1, 2**18):
        c = 0
        for j in range(18):
            if (i>>j)&1:
                c += 1
        judge = i%c
        key[i] = key[judge] + 1
    
    for i in range(n):
        if x[i] == "1":
            judge = (num1^last[n-1-i][0])%(count-1)
            print(1+key[judge])
        else:
            judge = (num2^last[n-1-i][1])%(count+1)
            print(1+key[judge])
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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


def popcount(n): 
    count = 0
    while (n): 
        n &= (n-1)  
        count+= 1
    return count

cache = {}
def f(n):
    if n not in cache:
        ans = 0
        while(n!=0):
            t = popcount(n)
            n%=t
            ans+=1
        cache[n] = ans
    else:
        ans = cache[n]
    return ans

# t2 = popcount(x)
for i in range(n-1,-1,-1):
    temp  = x^(1<<i)
    print(f(temp))

Submission status: Wrong Answer

Solution code:
def popcount(n):
    if n == 0:
        return 0
    n2 = n
    diver = 0
    while n2 != 0:
        if n2 % 2 == 1:
            diver += 1
        n2 = n2 // 2
    return diver


N = int(input())
X_in = input()
X_len = len(X_in)
X_d_r = list(X_in.lstrip('0'))[::-1]
X = 0
for i, c in enumerate(X_d_r):
    if c == '1':
        X += 1<<i
# print('X in dec is ', X)
for i in range(X_len-1, -1, -1):
    # print(i, X_in[-i-1])
    if X_in[-i-1] == '0':
        X_tmp = X + 1<<i
    else:
        X_tmp = X - 1<<i
    # print(X_tmp)
    ans = 0
    while X_tmp != 0:
        ans += 1
        X_tmp = X_tmp % popcount(X_tmp)
    print(ans)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
n=int(input())
x=list(input())
for i in range(n):
    ans=0
    s=deepcopy(x)
    if s[i]=='0':
        s[i]="1"
    else:
        s[i]="0"
    ss="".join(s)
    t=int(ss,2)
    c=ss.count("1")
    while t>0:
        t%=c
        ans+=1
        if t==0:
            print(ans)
            break
        two=bin(t)
        c=two.count("1")

Submission status: Wrong Answer

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

memo = [-1] * (n+1)
def calc(x):
    if(memo[x] != -1):
        return memo[x]
    if(x==0):
        return 0
    cnt = 0
    x2 = x
    while(x2 > 0):
        cnt += (x2&1)
        x2 //= 2
    next = x%cnt
    memo[x] = 1 + calc(next)
    return memo[x]

cnt0 = x.count('1')
if(cnt0 == 0):
    ans = [1] * n
    print('\n'.join(map(str,ans)))
    exit()
if(cnt0==1):
    ans = [0] * n
    for i in range(n):
        ans1 = 1 + ( x[-1] == '1')
        if(x[i]=='0'):
            ans[i] = ans1
        else:
            ans[i] = 0
    print('\n'.join(map(str,ans)))
    exit()

rem_p = [0] * n
rem_m = [0] * n
rem_p[0] = 1
rem_m[0] = 1%(cnt0-1)

for i in range(1,n):
    rem_p[i] = (2*rem_p[i-1])%(cnt0+1)
    rem_m[i] = (2*rem_m[i-1])%(cnt0-1)

x_p = 0
x_m = 0
for i in range(n):
    if(x[n-1-i] == '1'):
        x_p += rem_p[i]
        x_m += rem_m[i]
x_p %= (cnt0+1)
x_m %= (cnt0-1)

ans = [0] * n
for i in range(n):
    if(x[i]=='1'):
        first = (x_m - rem_m[n-1-i])%(cnt0-1)
        ans[i] = calc(first) + 1
    else:
        first = (x_p + rem_p[n-1-i])%(cnt0+1)
        ans[i] = calc(first) + 1

print('\n'.join(map(str,ans)))

Submission status: Wrong Answer

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

def int2bit(n):
	ret = [0 for i in range(18)]
	i = 0
	while n > 0:
		ret[i] = n % 2
		n = n // 2
		i += 1
	return ret

def func(bit, popcount):
	ret = 0
	base = 1
	for b in bit:
		ret = (ret + base*b) % popcount
		base = (base * 2) % popcount
	return ret

F = [0 for _ in range(N+1)]
for n in range(1, N+1):
	b = int2bit(n)
	popcount = sum(b)
	a = func(b, popcount)
	if n == 7:
		print(n, b, popcount, a)
	F[n] = 1 + F[a]
P = sum(X)
for i in range(N):
	bit = [X[j] if i != j else 1 - X[j] for j in range(N)]
	bit.reverse()
	if X[i] == 0:
		print(1 + F[func(bit, P+1)])
	if X[i] == 1:
		if P == 1:
			print(0)
		else:
			print(1 + F[func(bit, P-1)])

Submission status: Wrong Answer

Solution code:
def f(n):
    ret = 0
    while(n):
        n = n%bin(n).count('1')
        ret += 1
    return ret

m = int(input())
x = input()
if(len(x) > 100): x = x[-100: ]

n = int('0b' + x, 2)
large = f(n)
for i in range(m):
    if(m > 100):
        if(i < m-100): print(large)
        else:
            num = n ^ (1 << (m-i-1))
            print(f(num))

    
    num = n ^ (1 << (m-i-1))
    print(f(num))

Submission status: Wrong Answer

Solution code:
def func(N):
    return N%bin(N).count("1")

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

popcount = X.count("1")
X_num = int(X,2)
bi = 2**(N-1)


for i in range(N):
    if(X[i] == "0"):
        hoge = X_num+bi
        I_count = popcount + 1
    else:
        hoge = X_num-bi
        I_count = popcount - 1
    count = 1
    if I_count == 0:
        print(0)
        continue
    hoge = hoge%I_count
    while hoge != 0:
        hoge = func(hoge)
        count += 1
    print(count)
    bi >>= 1

Submission status: Wrong Answer

Solution code:
def examA():
    L, R, D = LI()
    ans = R//D - (L-1)//D
    print(ans)
    return

def examB():
    N = I()
    A = LI()
    ans = 0
    for i,a in enumerate(A):
        if i%2==0:
            if a%2==1:
                ans += 1
    print(ans)
    return

def examC():
    N = I()
    ans = [0]*N
    for x in range(1,101):
        for y in range(1,101):
            for z in range(1,101):
                cur = x**2 + y**2 + z**2 + x*y + y*z + x*z
                if cur<N+1:
                    ans[cur-1] += 1

    for v in ans:
        print(v)
    return

def examD():
    def cnt(num):
        c = 0
        while(num>0):
            num %= bin(num).count("1")
            c += 1
        return c
    N = I()
    X = SI()
    S_upper = [0]*N
    S_lower = [0]*N
    start_upper = 0
    start_lower = 0
    bit = 0
    ans = [0]*N
    for s in X:
        if s=="1":
            bit += 1
    if bit==1:
        b = 0
        for i in range(N):
            if X[i]=="1":
                ans[i] = 0
                b = i
            else:
                ans[i] = 1
        if b==N-1:
            for i in range(N-1):
                ans[i] += 1
        for v in ans:
            print(v)
        return
    elif bit==0:
        for v in ans:
            print(v+1)
        return

    for i in range(N):
        S_upper[i] = pow(2,N-i-1,bit+1)
        S_lower[i] = pow(2,N-i-1,bit-1)
        if X[i]=="1":
            start_upper += S_upper[i]
            start_lower += S_lower[i]
            start_upper %= (bit+1)
            start_lower %= (bit-1)
    for i in range(N):
        if X[i]=="0":
            cur = (start_upper + S_upper[i]) % (bit+1)
            ans[i] = cnt(cur)+1
        else:
            cur = (start_lower - S_lower[i] + bit -1) % (bit-1)
            ans[i] = cnt(cur)+1
        #print(cur)

    for v in ans:
        print(v)
    return

def examE():
    T = I()
    ans = [0]*T

    for t in range(T):
        pass


    for v in ans:
        print(v)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(2*10**6)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Wrong Answer

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

# 入力を整数に変換して受け取る
def input_int():
    return int(input())


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return map(int, input().split())


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


def popcount(n):
    return format(n, "#b").count("1")

amaris = {}
def func(n, cnt):
    if n in amaris.keys():
        return amaris[n]

    temp = popcount(n)

    if n == 0:
        return cnt

    amari = n % temp
    cnt += 1
    ret = func(amari, cnt)
    amaris[n] = ret
    return ret


def main():
    n = input_int()
    x = input()

    bin_x = int(x, 2)
    for i in range(1, n + 1):
        check = "0" * (i - 1)
        check += "1"
        check += "0" * (n - i)

        print(func(bin_x ^ int(check, 2), 0))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def examA():
    L, R, D = LI()
    ans = R//D - (L-1)//D
    print(ans)
    return

def examB():
    N = I()
    A = LI()
    ans = 0
    for i,a in enumerate(A):
        if i%2==0:
            if a%2==1:
                ans += 1
    print(ans)
    return

def examC():
    N = I()
    ans = [0]*N
    for x in range(1,101):
        for y in range(1,101):
            for z in range(1,101):
                cur = x**2 + y**2 + z**2 + x*y + y*z + x*z
                if cur<N+1:
                    ans[cur-1] += 1

    for v in ans:
        print(v)
    return

def examD():
    def cnt(num):
        c = 0
        while(num>0):
            num %= bin(num).count("1")
            c += 1
        return c
    N = I()
    X = SI()
    S_upper = [0]*N
    S_lower = [0]*N
    start_upper = 0
    start_lower = 0
    bit = 0
    ans = [0]*N
    for s in X:
        if s=="1":
            bit += 1
    if bit==1:
        b = 0
        for i in range(N):
            if X[i]=="1":
                ans[i] = 0
                b = i
            else:
                ans[i] = 1
        if b==N-1:
            for i in range(N-1):
                ans[i] += 1
        for v in ans:
            print(v)
        return
    elif bit==0:
        for v in ans:
            print(v+1)
        return

    for i in range(N):
        S_upper[i] = pow(2,N-i-1,bit+1)
        S_lower[i] = pow(2,N-i-1,bit-1)
        if X[i]=="1":
            start_upper += S_upper[i]
            start_lower += S_lower[i]
            start_upper %= (bit+1)
            start_lower %= (bit-1)
    for i in range(N):
        if X[i]=="0":
            cur = (start_upper + S_upper[i]) % (bit+1)
            ans[i] = cnt(cur)+1
        else:
            cur = (start_lower - S_lower[i]) % (bit-1)
            ans[i] = cnt(cur)+1
        #print(cur)

    for v in ans:
        print(v)
    return

def examE():
    T = I()

    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(2*10**6)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Wrong Answer

Solution code:
N = int(input())
Ali = [0]*(N+1)
 
for x in range(1,101):
  for y in range(1,101):
    for z in range(1,101):
      i = x**2+y**2+z**2+x*y+y*z+z*x
      if i<=N:
        Ali[i] += 1
        
for i in range(N):
  print(Ali[i+1])

Submission status: Wrong Answer

Solution code:
n=int(input())
x=int(input(),2)
dic={}
def f(x):
    if x in dic:
        return dic[x]
    cnt=0
    for i in bin(x):
        cnt+=i=='1'
    if cnt == 0:
        return 0
    dic[x]=f(x%cnt)+1
    return dic[x]
for i in range(n-1,-1,-1):
    f(x^(1<<i))

Submission status: Wrong Answer

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

def popcount(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

n = int(input())
x = input()
k = x.count("1")
U = 2**20
C = [0]*U
for i in range(1, U):
  q = popcount(i)
  C[i] = C[i%q] + 1
for i in range(n):
  temp = 0
  now = k
  if x[i] == "1":
    now -= 1
  else:
    now += 1
  for j, s in enumerate(x):
    if (j != i and s == "1") or (j == i and s == "0"):
      temp += pow(2, n-1-j, now)
      temp %= now
  res = C[temp] + 1
  print(res)

Submission status: Wrong Answer

Solution code:
from sys import stdin, stdout

def popcount(n):
    cnt = 0
    while n > 0:
        cnt += n & 1
        n = n >> 1
    return cnt

def main():
    n = int(input())
    s = stdin.readline()
    x = 0
    ones = 0
    for i in reversed(s):
        x *= 2
        if i == '1':
            x += 1
            ones += 1

    if ones == 0:
        for i in range(n):
            stdout.write('1 ')
        stdout.write('\n')
        return
    elif ones == 1:
        for i in range(n):
            if s[i] == '1':
                stdout.write('0 ')
            else:
                if i + 1 == n:
                    stdout.write('2 ')
                else:
                    stdout.write('1 ')
        stdout.write('\n')
        return

    ans = []

    plus = x % (ones + 1)
    minus = x % (ones - 1)

    for i in range(n):
        if s[n - i - 1] == '1':
            y = minus
            y -= 1 << i
            y %= ones - 1
            if y < 0:
                y += ones - 1
            cnt = 1
            while y > 0:
                cnt += 1
                y = y % popcount(y)
            ans.append(cnt)
        else:
            y = plus
            y += 1 << i
            y %= ones + 1
            cnt = 1
            while y > 0:
                cnt += 1
                y = y % popcount(y)
            ans.append(cnt)

    for i in reversed(ans):
        stdout.write(str(i) + ' ')
    stdout.write('\n')

main()