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:
import sys
input = sys.stdin.readline

#n = int(input())
#l = list(map(int, input().split()))

'''
a=[]
b=[]
for i in range():
    A, B = map(int, input().split())
    a.append(A)   
    b.append(B)'''

n=int(input())
x=input().strip("\n")
cnt=0
for i in range(n):
    if x[i:i+1]=="1":
        cnt+=1
    print("a")
"""
#xx=list(x)
pre=int(x,2)
#print(pre)
for i in range(n):
    if x[i:i+1]=="1":
        #t=-1
        ad=-2**(n-1-i)
    else:
        #t=1
        ad=2**(n-1-i)
    #cnt+=t
    now=pre+ad
    ans=0
    while now!=0:
        now%=bin(now).count("1")
        ans+=1
        
    print(ans)
    #cnt-=t"""

Submission status: Wrong Answer

Solution code:
# 2125
# 方針．f(n)を求めるのがlog(N)で終わりそうだから普通に素直に実装すればいいのでは？
N = int(input())
X = list(input())

import math
# 最初にpopcount用のリストを作成する，そもそも2**(10**5)だから圧倒的に範囲が足らなかった
#L = [0 for i in range(int(math.log(N,2))+10)]
#for i in range(int(math.log(N,2))+10):
#    bi = list(str(bin(i)))
#    bi = bi[1:]
#    L[i] = bi.count('1')

# i番目のビットを反転させて,
dic={}
bn0 = X.count('1')+1
x0 = int(''.join(X),2)
x0 %= bn0

for i in range(N):
    # ちゃんともとに戻してね，ということで本のビット
    b = int(X[i]) & 1
    bn = b ^ 1

    xi = x0 - b * pow(2,N-1-i,bn0) + bn * pow(2,N-1-i,bn0)
    xi %= bn0
    num = xi
    count = 1
    while num > 0:
        bi = list(str(bin(num)))
        bi = bi[2:]
        st = ''.join(bi)
        if st in dic:
            bic = dic[st]
        else:
            bic = bi.count('1')
            dic[st] = bic
        num = num % bic
        count += 1
    print(count)

Submission status: Wrong Answer

Solution code:
import sys


def popcount(x: int):
    return bin(x).count("1")


def main():
    N = int(sys.stdin.readline().rstrip())
    X = sys.stdin.readline().rstrip()

    Xdec = int(X, 2)

    # X がゼロなら終了
    if Xdec == 0:
        print(0)
        return

    # 1回目の演算用
    md = popcount(Xdec)
    md_p, md_m = md + 1, md - 1

    tmp_p = Xdec % md_p
    if md_m != 0:
        tmp_m = Xdec % md_m

    for i in range(0, N, 1):
        if X[i] == "1":  # 1->0
            if md_m == 0:
                print(0)
                continue
            x_m = pow(2, (N - 1 - i), md_m)
            tmp = (tmp_m - x_m) % md_m

        if X[i] == "0":  # 0->1
            x_p = pow(2, (N - 1 - i), md_p)
            tmp = (tmp_p + x_p) % md_p

        cnt = 1
        while tmp:

            tmp = tmp % popcount(tmp)
            cnt += 1

        print(cnt)


main()

Submission status: Wrong Answer

Solution code:
a = int(input())
b = input()

def func(c):
    x = c.count("1")
    if x == 0:
        return 0
    n = 1
    nsum = 0
    for i in reversed(range(len(c))):
        if c[i] == "1":
            nsum += n
            if n > x:
                n = n % x
        n *= 2
    nsum %= x
    cans = bin(nsum).count("1")
    if cans == 0:
        return 1
    else:
        return 1 + func(bin(nsum))

for i in range(a):
    s = list(b)
    s[i] = "0" if s[i] == "1" else "1"
    c = "".join(s)

Submission status: Wrong Answer

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

dd={}
def get_f(v):
	global dd
	if v == 0:
		return 0
		
	if v in dd:
		return dd[v]
	
	pn = bin(v).count('1')
	ret = 1+get_f(v % pn)
	dd[v] = ret
	return ret
	
def bb(n, s):
	saigo = int(s[-1])
	for i, c in enumerate(s[:-1]):
		if c == '0':
			print(get_f(saigo)+1)
		else:
			print(0)
	if saigo == '0':
		print(get_f(1)+1)
	else:
		print(0)
		

def main():
	n = int(input())
	#b , c = tin()
	s = input()
	sa=s[::-1]
	n_one=s.count('1')
	if n_one == 1:
		bb(n,s)
		return 
	#pa(n_one)
	#pa(s)
	amari_p = 0
	amari_n = 0
	for i, c in enumerate(sa):
		if c == '1':
			amari_p += pow(2,i,n_one+1)
			amari_n += pow(2,i,n_one-1)
			amari_p %= n_one+1
			amari_n %= n_one-1
		
	#pa(amari_p)
	#pa(amari_n)
	for i, c in enumerate(s):
		keta = n - i - 1
		if c == '1':
			ta = amari_n
			ta -= pow(2,keta,n_one-1)
			ta %= n_one-1
		else:
			ta = amari_p
			ta += pow(2, keta, n_one+1)
			#pa(('q',ta))
			ta %= n_one+1
		#pa((keta,pow(2,keta),ta))
		print(get_f(ta)+1)
		
		
	
		
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

dd={}
def get_f(v):
	global dd
	if v == 0:
		return 0
	elif v == 1:
		return 1
		
	if v in dd:
		return dd[v]
	
	pn = bin(v).count('1')
	ret = 1+get_f(v % pn)
	dd[v] = ret
	return ret
	
def bb(n, s):
	saigo = int(s[-1])
	for i, c in enumerate(s[:-1]):
		if c == '0':
			print(get_f(saigo)+1)
		else:
			print(0)
	if saigo == '0':
		print(2)
	else:
		print(0)
		

def main():
	n = int(input())
	#b , c = tin()
	s = input()
	sa=s[::-1]
	n_one=s.count('1')
	if n_one == 1:
		bb(n,s)
		return 
	#pa(n_one)
	#pa(s)
	amari_p = 0
	amari_n = 0
	for i, c in enumerate(sa):
		if c == '1':
			amari_p += pow(2,i,n_one+1)
			amari_n += pow(2,i,n_one-1)
			amari_p %= n_one+1
			amari_n %= n_one-1
		
	#pa(amari_p)
	#pa(amari_n)
	for i, c in enumerate(s):
		keta = n - i - 1
		if c == '1':
			ta = amari_n
			ta -= pow(2,keta,n_one-1)
			ta %= n_one-1
		else:
			ta = amari_p
			ta += pow(2, keta, n_one+1)
			#pa(('q',ta))
			ta %= n_one+1
		#pa((keta,pow(2,keta),ta))
		print(get_f(ta)+1)
		
		
	
		
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

dd={}
def get_f(v):
	global dd
	if v == 0:
		return 0
	elif v == 1:
		return 1
		
	if v in dd:
		return dd[v]
	
	pn = bin(v).count('1')
	ret = 1+get_f(v % pn)
	dd[v] = ret
	return ret
	
def bb(n, s):
	saigo = int(s[-1])
	for i, c in enumerate(s[:-1]):
		if c == '0':
			print(get_f(saigo))
		else:
			print(0)
	if saigo == '1':
		print(0)
	else:
		print(2)
		

def main():
	n = int(input())
	#b , c = tin()
	s = input()
	sa=s[::-1]
	n_one=s.count('1')
	if n_one == 1:
		bb(n,s)
		return 
	#pa(n_one)
	#pa(s)
	amari_p = 0
	amari_n = 0
	for i, c in enumerate(sa):
		if c == '1':
			amari_p += pow(2,i,n_one+1)
			amari_n += pow(2,i,n_one-1)
			amari_p %= n_one+1
			amari_n %= n_one-1
		
	#pa(amari_p)
	#pa(amari_n)
	for i, c in enumerate(s):
		keta = n - i - 1
		if c == '1':
			ta = amari_n
			ta -= pow(2,keta,n_one-1)
			ta %= n_one-1
		else:
			ta = amari_p
			ta += pow(2, keta, n_one+1)
			#pa(('q',ta))
			ta %= n_one+1
		#pa((keta,pow(2,keta),ta))
		print(get_f(ta)+1)
		
		
	
		
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

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


def readstr():
    return input().strip()


def readint():
    return int(input())


def readnums():
    return map(int, input().split())


def readstrs():
    return input().split()


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


def main():
    N = readint()
    X = readstr()
    if all(x == '0' for x in X):
        print(0)
        exit()
    s = sum(tuple(map(int, X)))
    s1 = s + 1
    s2 = s - 1 if s != 1 else 1
    m1 = int(X, 2) % s1
    m2 = int(X, 2) % s2
    t1 = [1]
    t2 = [1]
    for i in range(N):
        t1.append(t1[i] * 2 % s1)
        t2.append(t2[i] * 2 % s2)
    for i in range(N):
        ans = 0
        if X[i] == '0':
            x = (m1 + t1[(N - i - 1)]) % s1
        else:
            x = (m2 - t2[(N - i - 1)]) % s2
        d = popcount(x)
        ans += 1
        while x:
            x %= d
            d = popcount(x)
            ans += 1
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N=int(input())
X=input()
def calc(n,count):
    if n==0:
        return count
    popcount=bin(n).count("1")
    next_n=n%popcount
    #print(next_n)
    if next_n==0:
        return count+1
    else:
        return calc(next_n, count+1)

popcount=X.count("1")
if popcount==1:
    plus=0
    for i in range(N):
        x=X[i]
        if x=="1":
            plus+=pow(2,N-i-1,popcount+1)
    for i in range(N):
        x=X[i]
        if x==1:
            print(0)
        else:
            ans=plus+pow(2,N-i-1,popcount+1)
            ans%=(popcount+1)
            print(calc(ans,1))
    exit()


plus=0
minus=0
for i in range(N):
    x=X[i]
    if x=="1":
        plus+=pow(2,N-i-1,popcount+1)
        minus+=pow(2,N-i-1,popcount-1)
        plus%=(popcount+1)
        minus%=(popcount-1)

for i in range(N):
    x=X[i]
    if x=="1":
        ans=minus-pow(2,N-i-1,popcount-1)
        ans%=(popcount-1)
        print(calc(ans,1))

    else:
        ans=plus+pow(2,N-i-1,popcount+1)
        ans%=(popcount+1)
        print(calc(ans,1))

Submission status: Wrong Answer

Solution code:
n = int(input())
s=input()
p=0
c=0
for i in range(n):
    if s[i]=='1':
        p+=2**(n-i-1)
        c+=1

if c>1:
    e=p%(c+1)
    f=p%(c-1)
    for i in range(n):
        z=c
        b=e
        a=f
        if s[i]=='0':
            b+=2**(n-i-1)
            z+=1
            b%=z
        else:
            a-=2**(n-i-1)
            z-=1
            a%=z
        
        l=1
        
        if z==c-1:
            while a>0 and z>0:
                if a%z>0:
                    a%=z
                    z=bin(a).count('1')
                    l+=1
                else:
                    break
        else:
            while b>0 and z>0:
                if b%z>0:
                    b%=z
                    z=bin(b).count('1')
                    l+=1
                else:
                    break
            
        print(l)

Submission status: Wrong Answer

Solution code:
def popcount(number, bit_counter):
    num = number
    counter = 0
    while num != 0: # 5,6回程度
        bit_con = 0
        if counter == 0:
            bit_con = bit_counter  
        else:
            bit_con = bin(num)[2:].count('1')
        num = num % bit_con
        counter += 1

    return counter

if __name__ == "__main__":
    import sys 

    readline = sys.stdin.readline 

    N = int(input())
    X_str= readline()
    print(X_str)
    X = list(X_str)
    bit_count = X_str.count('1')

    for i in range(N):
        # ビットの反転
        x_copy = X.copy()
        bit_count_n = bit_count
        if x_copy[i] == '0':
            x_copy[i] = '1'
            bit_count_n += 1
        else:
            x_copy[i] = '0'
            bit_count_n -= 1

        bit_int = int("".join(x_copy), 2)

        print(popcount(bit_int, bit_count_n))

Submission status: Wrong Answer

Solution code:
print(1)

Submission status: Wrong Answer

Solution code:
n=int(input())
xs=input()
xk=list(map(int,list(xs)))
xj=xk.count(1)

x=int(xs,2)

def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f

for i in range(n-1,-1,-1):
    xi=x^(1<<i)
    pxi=xj
    if xk[n-1-i]==0:
        pxi=pxi+1
    else:
        pxi=pxi-1
    if xi==0:
        print(0)
    else:
        xi=xi%pxi
        if xi==0:
            print(1)
        else:
            icnt=1
#            while xi>0:
#                icnt+=1
#                xi=xi%popcount(xi)
            print(icnt)

Submission status: Wrong Answer

Solution code:
N=int(input())
X=input()
popcount=X.count('1')
Xnum1 = 0
Xnum0 = 0
if popcount != 1:
    for i in range(N):
        Xnum1 = (Xnum1 + (2**(N-i-1)%(popcount-1)))%(popcount-1)
for i in range(N):
    Xnum0 = (Xnum0 + (2**(N-i-1)%(popcount+1)))%(popcount+1)
for i in range(N):
    if popcount==1 and X[i]=='1':
        print(0)
        continue
    if X[i]=='1':
        Xi = (Xnum1 - (2**(N-i-1)%(popcount-1)))%(popcount-1)
    else:
        Xi = (Xnum0 + (2**(N-i-1)%(popcount+1)))%(popcount+1)
    ans = 1
    while Xi!=0:
        Xi = Xi % bin(Xi).count('1')
        ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
import copy
#N = int(input())
#X = input()

N = 23
X = '00110111001011011001110'

mem_func = [-1 for i in range(2**N)]

def popcount(n):
    return str(bin(n)).count('1')

def func(n, l):
    # mem_func定義済み
    if mem_func[n] != -1: return mem_func[n] + l
    # mem_func未定義
    if n == 0: return l
    #print(n, popcount(n))
    n = n % popcount(n)
    return func(n, l+1)

list_X = list(X)
standard = popcount(int(X, 2))

for i in range(N):
    x = copy.copy(list_X)
    if x[i] == '0':
        x[i] = '1'
        z = int(''.join(x), 2)
        mem_func[z] = func(z%(standard+1), 1)
        print(mem_func[z])
    else:
        x[i] = '0'
        z = int(''.join(x), 2)
        mem_func[z] = func(z%(standard-1), 1)
        print(mem_func[z])

Submission status: Wrong Answer

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

dp=[-1]*(200001)

dp[0]=0
dp[1]=1

def fun(num,step):
    num2=num%sum(list(map(int,bin(num)[2:])))
    if dp[num2]!=-1:
        dp[num]=dp[num2]+step
    else:
        fun(num2,step+1)

for i in range(2,200001):
    fun(i,1)

num1=''.join(x)
num2=int(num1,2)
su = sum(list(map(int,x)))

for i in range(n):
    num4=num2
    su2=su
    if x[i]=='1':
        su2-=1
        if su2!=0:
            num4%=su2
            num4-=pow(2,(n-1-i),su2)        
    else:
        su2+=1
        num4%=su2
        num4+=pow(2,(n-1-i),su2)
    if su2 == 0:
        print('0')
    elif num4<=20000:
        print(dp[num4])
    else:
        num3=num4%su2
        print(dp[num3]+1)

Submission status: Wrong Answer

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from functools import lru_cache


@lru_cache(maxsize=2*10**5)
def f2(x):
    if x == 0: return 0
    y = bin(x).count("1")
    return 1 + f2(x % y)

def resolve():
    N = int(input())
    W = 16
    S = input()
    cnt0 = S.count("1")

    if cnt0 == 0:
        print(*[0]*N, sep="\n")
        return

    X = int(S, 2)

    dc = {}
    for k, v in (("0", 1), ("1", -1)):
        x = cnt0 + v
        y = X % x if x else 0
        dc[k] = (x, v, y)

    ans = []
    for i, si in enumerate(S):
        cnt, v, n = dc[si]

        if cnt == 0:
            ans.append(0)
            continue

        ni = N - i - 1
        n = (n + v * pow(2, ni, cnt)) % cnt

        ans.append(1+f2(n))

    print(*ans, sep="\n")


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

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

    _x = list(x)
    pre_count = [1, 2, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 3, 4]
    count_1 = x.count("1")

    pre_mod0 = int(x, 2) % (count_1 + 1)
    if not count_1 - 1 == 0:
        pre_mod1 = int(x, 2) % (count_1 - 1)

    for i in range(n):
        _count_1 = count_1 - 1 if _x[i] == "1" else count_1 + 1
        if _count_1 == 0:
            print(0)
        else:
            pre_mod = pre_mod1 if _x[i] == "1" else pre_mod0
            mod = (2 ** (n - i - 1))
            mod %= _count_1
            if _x[i] == "0":
                mod += pre_mod
            else:
                mod = mod - pre_mod + _count_1
            if mod < 16:
                print(pre_count[int((mod) % _count_1)])
            else:
                print(0)

Submission status: Wrong Answer

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

dp=[-1]*(200001)

dp[0]=0
dp[1]=1

def fun(num,step):
    num2=num%sum(list(map(int,bin(num)[2:])))
    if dp[num2]!=-1:
        dp[num]=dp[num2]+step
    else:
        fun(num2,step+1)

for i in range(2,200001):
    fun(i,1)

num1=''.join(x)
num2=int(num1,2)
su = sum(list(map(int,x)))

for i in range(n):
    num4=num2
    su2=su
    if x[i]=='1':
        #num4-=pow(2,(n-1-i))
        su2-=1
    else:
        #num4+=pow(2,(n-1-i))
        su2+=1
    if su2 == 0:
        print('0')
    elif num4<=20000:
        print(dp[num4])
    else:
        num3=num4%su2
        print(dp[num3]+1)

Submission status: Wrong Answer

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

dp=[-1]*(200001)

dp[0]=0
dp[1]=1

def fun(num,step):
    num2=num%sum(list(map(int,bin(num)[2:])))
    if dp[num2]!=-1:
        dp[num]=dp[num2]+step
    else:
        fun(num2,step+1)

for i in range(2,200001):
    fun(i,1)

num1=''.join(x)
num2=int(num1,2)
su = sum(list(map(int,x)))

for i in range(n):
    num4=num2
    su2=su
#    if x[i]=='1':
#        num4-=pow(2,(n-1-i))
#        su2-=1
#    else:
#        num4+=pow(2,(n-1-i))
#        su2+=1
    if su2 == 0:
        print('0')
    elif num4<=20000:
        print(dp[num4])
    else:
        num3=num4%su2
        print(dp[num3]+1)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

import numpy as np


#N = 2 * 10 ** 5
#X = np.random.randint(0, 2, N)
#Y = int('0b' + ''.join(X.astype(str).tolist()), 0)

N = int(input())
X = input()
Y = int('0b' + X, 0)
X = np.array(list(X), int)

p = int(X.sum())
m1 = Y % (p + 1)
m2 = Y % max(1, p - 1)


count = np.zeros((N + 1, ))
for n in range(1, N):
    i = np.array(list(bin(n))[2:], int).sum()
    count[n] = 1 + count[n % i]

ans = [0] * N
flag = 0
for n in range(1, N + 1):
    if X[n - 1]:
        z = m2 - pow(2, N - n, max(1, p - 1))
        z %= max(1, p - 1)
        if p - 1 == 0:
            flag = 1
    else:
        z = pow(2, N - n, p + 1) + m1
        z %= p + 1
        if p == 0:
            z = 0

    ans[n - 1] = int(count[z] + 1)
    if z == 0 and flag:
        ans [n - 1] = 0

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

Submission status: Wrong Answer

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

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

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

ones = X.count('1')
A_1 = 0
A_2 = 0
d = 1
pows = [0] * N
for i, a in enumerate(X[::-1]):
    if ones == 1:
        A_2 += (int(a) * d) % (ones + 1)
        pows[i] = (d % (ones + 1), 0)
    else:
        A_1 += (int(a) * d) % (ones - 1)
        A_2 += (int(a) * d) % (ones + 1)
        pows[i] = (d % (ones + 1), d % (ones - 1))
    d *= 2
for i in range(N):
    ans = 1
    total = ones
    sumA = 0
    if X[i] == '0':
        total += 1
        sumA = A_2 + pows[N - i - 1][0]
    else:
        total -= 1
        sumA = A_2 - pows[N - i - 1][1]
    if total == 0:
        print(0)
        continue
    n = sumA % total
    while n != 0:
        n = n % popcount(n)
        ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

import numpy as np


#N = 2 * 10 ** 5
#X = np.random.randint(0, 2, N)
#Y = int('0b' + ''.join(X.astype(str).tolist()), 0)

N = int(input())
X = input()
Y = int('0b' + X, 0)
X = np.array(list(X), int)

p = int(X.sum())
m1 = Y % (p + 1)
m2 = Y % max(1, p - 1)


count = np.zeros((N + 1, ))
for n in range(1, N):
    i = np.array(list(bin(n))[2:], int).sum()
    count[n] = 1 + count[n % i]

ans = [0] * N
flag = 0
for n in range(1, N + 1):
    if X[n - 1]:
        z = m2 - pow(2, N - n, max(1, p - 1))
        z %= max(1, p - 1)
        if p - 1 == 0:
            flag = 1
    else:
        z = pow(2, N - n, p + 1) + m1
        z %= p + 1
        if p == 0:
            z = 1

    ans[n - 1] = int(count[z] + 1)
    if z == 0 and flag:
        ans [n - 1] = 0

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

Submission status: Wrong Answer

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

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

if one==1:
    for i in range(n):
        if x[i]=="1":
            print(0)
        elif i==n-1:
            print(2)
        else:
            print(1)
    
    
elif one>1:
    
    Xp = X % (one+1)
    Xm = X % (one-1)

    def f(x):
        if x==0:
            return 0
        return 1+f(x%bin(x).count("1"))

    for i in range(n):
        
        if x[i]=="0":
            c = pow(2, n-i-1, one+1)
            print(f((Xp+c)%(one+1))+1)
        else:
            c = pow(2, n-i-1, one-1)
            print(f((Xm-c)%(one-1))+1)
else:
    for i in range(n):
        if i==n-1:
            print(2)
        else:
            print(1)

Submission status: Wrong Answer

Solution code:
n = int(input())
x = str(input())
Xp = 0
Xm = 0
one = x.count("1")


if one==1:
    for i in range(n):
        if x[i]=="1":
            print(0)
        elif i==n-1:
            print(2)
        else:
            print(1)
    
    
elif one>1:
    
    for i in range(n):
        Xp+=int(x[i])*2**(n-i-1)
        Xm+=int(x[i])*2**(n-i-1)
        Xp%=one+1
        Xm%=one-1

    def f(x):
        if x==0:
            return 0
        return 1+f(x%bin(x).count("1"))

    for i in range(n):
        
        if x[i]=="0":
            c = pow(2, n-i-1, one+1)
            print(f((Xp+c)%(one+1))+1)
        else:
            c = pow(2, n-i-1, one-1)
            print(f((Xm-c)%(one-1))+1)
else:
    for i in range(n):
        if i==n-1:
            print(2)
        else:
            print(1)

Submission status: Wrong Answer

Solution code:
n = int(input())
x = str(input())
Xp = 0
Xm = 0
one = x.count("1")


if one==1:
    for i in range(n):
        if x[i]=="1":
            print(0)
        elif i==n-1:
            print(2)
        else:
            print(1)
    
    
elif one>1:
    
    for i in range(n):
        Xp+=int(x[i])*2**(n-i-1)
        Xm+=int(x[i])*2**(n-i-1)
        Xp%=one+1
        Xm%=one-1

    l = [0, 1]
    for i in range(2,one+1):
        if i%2==0:
            l.append(1)
        else:
            l.append(l[i%bin(i).count("1")]+1)

    for i in range(n):
        
        if x[i]=="0":
            c = pow(2, n-i-1, one+1)
            print(l[(Xp+c)%(one+1)]+1)
        else:
            c = pow(2, n-i-1, one-1)
            print(l[(Xm-c)%(one-1)]+1)
else:
    for i in range(n):
        if i==n-1:
            print(2)
        else:
            print(1)

Submission status: Wrong Answer

Solution code:
n = int(input())
x = '0b' + input()
f = [-1]*n

num = int(x, 2)
xcnt1 = x.count('1')
if xcnt1 == 0:
    for _ in range(n):
        print(0)
    exit()

for i in range(n):
    if x[i+2] == '0':
        f[i] = (num % (xcnt1+1) + pow(2, n-i-1, xcnt1+1)) % (xcnt1+1)
    else:
        if xcnt1 - 1 == 0:
            continue
        f[i] = (num % (xcnt1-1) - pow(2, n-i-1, xcnt1-1)) % (xcnt1-1)

for i in range(n):
    if f[i] == -1:
        print(0)
        continue

    num = f[i]
    x = bin(num)
    xcnt1 = x.count('1')
    cnt = 1
    while True:
        if num == 0:
            print(cnt)
            break

        num = num % xcnt1
        x = bin(num)
        xcnt1 = x.count('1')
        cnt += 1

Submission status: Wrong Answer

Solution code:
from collections import deque
LIM=200004
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
    
M=[0]*200005
for i in range(1,200004):
    M[i]+=pop_num(i,L[i],L)
X=int(input())
Y=input()
d=bin_sum2(Y)
e=int(Y,2)%(d+1)
f=int(Y,2)%max(1,(d-1))
for i in range(X):
    if int(Y[i])==1:
        b=max(d-1,1)
        flag=max(0,d-1)
    else:
        b=d+1
        flag=1

Submission status: Wrong Answer

Solution code:
from collections import deque
LIM=200004
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
    
M=[0]*200005
for i in range(1,200004):
    M[i]+=pop_num(i,L[i],L)
X=int(input())
Y=input()
d=bin_sum2(Y)
e=int(Y,2)%(d+1)
f=int(Y,2)%max(1,(d-1))

Submission status: Wrong Answer

Solution code:
from collections import deque
LIM=200004
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
    
M=[0]*200005
for i in range(1,200004):
    M[i]+=pop_num(i,L[i],L)
X=int(input())
Y=input()
d=bin_sum2(Y)
e=int(Y,2)%(d+1)
f=int(Y,2)%max(1,(d-1))
for i in range(X):
    if Y[i]=="1":
        b=max(d-1,1)
        flag=max(0,d-1)
        g=(f-2**(X-1-i)%b+b)%b
    else:
        b=d+1
        flag=1
        g=(e+2**(X-1-i))%b

Submission status: Wrong Answer

Solution code:
n=int(input())
x=input()
xx=x.count('1')
if xx!=1 and xx!=0:
    xx2=int(x,2)
    a1=xx2%(xx-1)
    a2=xx2%(xx+1)
    k=2**n
    for i in range(n):
        k//=2
        if x[i]=='0':
            k=k%(xx+1)
            aa1=(a2+k)%(xx+1)
            aa2=str(bin(aa1)).count('1')
        else:
            k=k%(xx-1)
            aa1=(a1-k)%(xx-1)
            aa2=str(bin(aa1)).count('1')
        if aa1==0:
            print(1)
        else:
            count=1
            while aa1!=0:
                aa1%=aa2
                aa2=str(bin(aa1)).count('1')
                count+=1
            print(count)
elif xx==0:
    for i in range(n):
        print(1)
else:
    x1=int(x,2)
    for i in range(n):
        k=2**(n-1-i)
        if x[i]=='1':
            print(0)
        else:
            x1+=k
            x2=2
            count=0
            while x1!=0:
                x1%=x2
                x2=str(bin(x1)).count('1')
                count+=1
            print(count)

Submission status: Wrong Answer

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

n = int(input())
x = input()
z = '1' * n
o = '0' * n
X = int(x, 2)
m = 2 * 10**5

if (n == 1 and x == '1'):
  print(0)
  exit()

if (z == x):
  u = n - 1
  d = n - 1
elif (o == x):
  u = 1
  d = 1
else:
  tmp = len(list(filter(lambda x: x == '1', x)))
  u = tmp + 1
  if (tmp < 2):
    d = 1
  else:
    d = tmp - 1


def popcount(i):
  return i % len(list(filter(lambda x: x == '1', format(i, 'b'))))


def solve(i, count):
  if (i <= m and ans[i] != 0):
    return count + ans[i]
  elif (i == 0):
    return count
  else:
    return solve(popcount(i), count + 1)


def solve2(i, div):
  if (i <= m):
    return ans[i]
  else:
    return ans[i % div] + 1


ans = [0] * (m + 1)
_u = m // u
U = X % u + (u * _u) + u
_d = m // d
D = X % d + (d * _d) * 2 + d * 2
Us = [0] * m
Ds = [0] * m
for i in range(1, m + 1):
  ans[i] = solve(i, 0)
Us[0] = 1 % u
Ds[0] = 1 % d
for i in range(1, m):
  Us[i] = (Us[i - 1] * 2) % u
  Ds[i] = (Ds[i - 1] * 2) % d
for i in range(n):
  if(x[i] == '0'):
    print(solve2(U + Us[n-i-1], u))
  else:
    print(solve2(D - Ds[n-i-1], d))

Submission status: Wrong Answer

Solution code:
n = int(input())
x = '0b' + input()
f = [-1]*n

num = int(x, 2)
xcnt1 = x.count('1')
if xcnt1 == 0:
    for _ in range(n):
        print(0)
    exit()

for i in range(n):
    if x[i+2] == '0':
        f[i] = (num + 2**(n-i-1)) % (xcnt1 + 1)
    else:
        if xcnt1 - 1 == 0:
            continue
        f[i] = (num - 2**(n-i-1)) % (xcnt1 - 1)

for i in range(n):
    if f[i] == -1:
        print(0)
        continue

    intx = f[i]
    x = bin(intx)
    len1 = x.count('1')
    cnt = 1
    while True:
        if intx == 0:
            print(cnt)
            break
        
        intx = intx % len1
        x = bin(intx)
        len1 = x.count('1')
        cnt += 1