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:
def modpow(a, n, p):
  if n == 0:
    return 1
  if n == 1:
    return a % p 
  elif n % 2 == 1:
    return a * modpow(a, n-1, p) % p
  else:
    return modpow(a, n//2, p) **2 % p

l = [-1]*(2*10**5+1)
l[0] = 0
def f(n):
  if l[n] != -1:
    return l[n]
  else:
    b = bin(n)
    k = b.count("1")
    l[n] = f(n%k)+1
    return l[n]

 
  
  
n = int(input())
x = input()
#x = "1000101010"*20000
k = x.count("1")
x_mod_1 = int(x, 2) % (k+1)
x_mod_0 = int(x, 2) % (k-1) if k > 1 else 0
for i in range(n):
  if x[i] == "0":
    print(f(x_mod_1 + modpow(2, n-1-i, k+1))+1)

  else:
    if k > 1:
      print(f(x_mod_0 - modpow(2, n-1-i, k-1))+1)
    else:
      print(0)

Submission status: Wrong Answer

Solution code:
n=int(input())
x_=input()
px=x_.count("1")
if not px:
    print(0)
    for i in range(n-1):
        print(1)
    exit()
if px==1:
    for i in range(n):
        if int(x_[-i-1]):
            print(0)
        else:
            if not i:
                print(2)
            else:
                print(1)
    exit()
x=int(x_,2)

pow2=[1]

for i in range(n):
    tmp=pow2[-1]
    tmp*=2
    tmp%=px+1
    pow2.append(tmp)
pow22=[1]
for i in range(n):
    tmp=pow22[-1]
    tmp*=2
    tmp%=px-1
    pow22.append(tmp)
x1=x%(px+1)
x2=x%(px-1)
ans=[]
for i in range(n):
    tmp=0;dv=0
    if int(x_[-i-1]):
        tmp=x2-pow22[i]
        dv=px-1
    else:
        tmp=x1+pow2[i]
        dv=px+1
    if dv==0:
        ans.append(0)
        continue
    cnt=1
    while tmp:
        if not dv:
            break
        tmp%=dv
        dv=bin(tmp).count("1")
        if not tmp:
            break
        cnt+=1
    ans.append(cnt)
for i in ans[::-1]:
    print(i)

Submission status: Wrong Answer

Solution code:
def bitcount(N):  # 立ってるbitの数
    bitcnt = [0]
    for _ in range(N):
        bitcnt += [i + 1 for i in bitcnt]
    return bitcnt


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

num, cnt = int(x, 2), x.count('1')
lbit = bitcount(18)
for i in range(n):
    ans = 1
    if x[i] == '0':
        ctmp = cnt + 1
        tmp = num % ctmp + pow(2, n - (i + 1), ctmp)
    elif x[i] == '1':
        if cnt == 1:
            print(1)
            continue
        ctmp = cnt - 1
        tmp = num % ctmp - pow(2, n - (i + 1), ctmp)
    tmp %= ctmp
    ctmp = lbit[tmp]
    while tmp > 0:
        ans += 1
        tmp %= ctmp
        ctmp = lbit[tmp]
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = input()
popcount_X = X.count('1')
numX = int(X, 2)
a = numX % (popcount_X + 1)
b = numX % (popcount_X - 1) if popcount_X != 1 else 0
for i, x in enumerate(X, 1): #リストのインデクス，要素，第二引数に開始位置
    if x == '1' and popcount_X == 1:
        print(0); continue
    ans = 1
    if x == '1':
        temp = (b - pow(2, N - 1, popcount_X - 1)) % (popcount_X - 1)
    else:
        temp = (a + pow(2, N - i, popcount_X + 1)) % (popcount_X + 1)
    while temp:
        p = format(temp, 'b').count('1') #2進数，1の個数
        temp %= p
        ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from typing import List, Tuple

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


def binary_mod(bits: List[int], div: int) -> int:
    val = 0
    for b in bits:
        val = (val * 2 + b) % div
    return val


def f(x):
    cnt = 0
    while x > 0:
        x = x % bin(x).count('1')
        cnt += 1
    return cnt


popcount = sum(X)
div1 = popcount + 1
div2 = popcount - 1

if popcount == 0:
    print('\n'.join(map(str, [1] * N)))
else:
    cnt1 = 0
    cnt2 = 0

    if div1 > 0:
        cnt1 += 1
        rem1 = binary_mod(X, div1)
    if div2 > 0:
        cnt2 += 1
        rem2 = binary_mod(X, div2)

    for i in range(N):
        if X[i] == 0:
            if div1 > 0:
                r = (rem1 + pow(2, N - 1 - i, div1)) % div1
                cnt1 += f(r)
            print(cnt1)
        else:
            if div2 > 0:
                r = (rem2 - pow(2, N - 1 - i, div2) + div2) % div2
                cnt2 += f(r)
            print(cnt2)

Submission status: Wrong Answer

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

def onecount(mojix):
    ones=0
    for j in mojix:
        if j=="1":
            ones+=1
    return ones


def popcount(new2bit,ones,count):
    #print("popcount start",new2bit,ones,count)
    
    if ones==0:
        return count
    
    else:
        ten=int(new2bit,2)
        div=ten%ones
        
        count+=1
        
        new2bit=bin(div)
        ones=onecount(str(new2bit))
        
        return popcount(new2bit,ones,count)

ones=onecount(x)

for i in range(N):
    
    
    if x[i]=="1":
        x_ith="0"
        ones-=1
    else:
        x_ith="1"
        ones+=1
    if i==0:
        new2bit=x_ith+x[i+1:]
    elif i<N-1:
        new2bit=x[:i]+x_ith+x[i+1:]
    else:
        new2bit=x[:i]+x_ith
        
    #ones=onecount(new2bit)
    print(popcount(new2bit,ones,0))

Submission status: Wrong Answer

Solution code:
n=int(input())
x=str(input())
pop=[0]
a=1
b=0
for i in range(1,n):
    ni=0
    a=i
    while a:
        a&=(a-1)
        ni+=1
    nii=i%ni
    pop.append(pop[nii]+1)

x1=int(x,2)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def popcount(x):
    return bin(x)[2:].count("1")

def f(x):
    cnt=0
    while(x>0):
        x%=popcount(x)
        cnt+=1
    return cnt

n=int(input())
s=input()
d=s.count("1")
if d==0:
    for i in range(n):
        print(1)
elif d==1:
    if s[-1]=="1":
        for i in range(n-1):
            print(2)
        else:
            print(0)
    else:
        for i in range(n-1):
            if s[i]=="1":
                print(0)
            else:
                print(1)
        print(2)
else:
    ints=int(s,2)
    m=ints%(d-1)
    M=ints%(d+1)
    for i in range(n):
        if s[i]=="1":
            print(f((m-2**i)%(d-1))+1)
        else:
            print(f((M+2**i)%(d+1))+1)

Submission status: Wrong Answer

Solution code:
n = int(input())
x = input()
k = x.count("1")
s = int(x, 2)

def ev(n):
	cnt = 0
	while n != 0:
		m = bin(n).count("1")
		n = n % m
		cnt += 1
	return cnt

if k != 1:
	k1 = s%(k-1)
	k2 = s%(k+1)
	for i in range(n):
		if x[i] == "0":
			print(ev((k2+pow(2, n-i-1, k+1)) % (k+1))+1)
		else:
			print(ev((k1-pow(2, n-i-1, k-1)) % (k-1))+1)
else:
	k2 = s%(k+1)
	for i in range(n):
		if x[i] == "0":
			print(ev((k2+pow(2, n-i-1, k+1)) % k+1)+1)
		else:
			print(0)

Submission status: Wrong Answer

Solution code:
n=int(input())
x=str(input())
pop=[0]
a=1
b=0
for i in range(1,n):
    ni=0
    a=i
    while a:
        a&=(a-1)
        ni+=1
    nii=i%ni
    pop.append(pop[nii]+1)
x1=0

Submission status: Wrong Answer

Solution code:
def resCount(n):
    tmp = bin(n).count('1')
    if tmp == 1:
        return 1
    elif tmp == 0:
        return 0
    else:
        return 1 + resCount(n % tmp)
N= int(input())
X = input()
Xi = int(X, 2)

for i in range(N):
    res, n = 1, Xi ^ (1<<(N-i-1))
    print(n)

Submission status: Wrong Answer

Solution code:
n=int(input())
x=str(input())
pop=[0]
a=1
b=0
for i in range(1,n):
    ni=0
    a=i
    while a:
        a&=(a-1)
        ni+=1
    nii=i%ni
    pop.append(pop[nii]+1)
x1=0
for i in range(n):
    if int(x[i])&1:
        x1+=2**(n-1-i)

Submission status: Wrong Answer

Solution code:
def bitcount(N):  # 立ってるbitの数
    bitcnt = [0]
    for _ in range(N):
        bitcnt += [i + 1 for i in bitcnt]
    return bitcnt


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

num, cnt = int(x, 2), x.count('1')
lbit = bitcount(18)
for i in range(n):
    ans = 1
    if x[i] == '0':
        ctmp = cnt + 1
        tmp = num % ctmp + pow(2, n - (i + 1), ctmp)
    elif x[i] == '1':
        ctmp = cnt - 1
        if ctmp == 0:
            print(0)
            break
        tmp = num % ctmp - pow(2, n - (i + 1), ctmp)
    tmp %= ctmp
    ctmp = lbit[tmp]
    while tmp > 0:
        ans += 1
        tmp %= ctmp
        ctmp = lbit[tmp]
    print(ans)

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:
N= int(input())
X = input()


for i in range(N):
    res, n = 1, int(X, 2)
    print(n)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = input()
ans = [1 for _ in range(N)]

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

l = 0
for k in range(N):
  if X[k] == '1':
    l+=1
firstpop = [l for _ in  range(N)]

intN = int(X, 2)

start = []
if N == 1:
  if X[0] == '1':
    ia = 0
    firstpop[0] -= 1
  else:
    ia = 1
    firstpop[0] += 1
  start.append(ia)

else:
  for k in range(N):
    if X[k] == '1':
      ia = intN - 2**(N-k-1)
      firstpop[k] -= 1
    else:
      ia = intN + 2**(N-k-1)
      firstpop[k] += 1
    start.append(ia)

mp = l + 1
poplist = [0]
for _ in range(1, l+2):
  poplist.append(popcount(_))


for k in range(N):
  if firstpop[k] == 0:
    ans[k] = 0
  else:
    start[k] %= firstpop[k]

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] % poplist[start[k]]

Submission status: Wrong Answer

Solution code:
def Base_n_to_10(X,n):
    out = 0
    for i in range(1,len(str(X))+1):
        out += int(X[-i])*(n**(i-1))
    return out#int outn=int(input())
def Base_10_to_n(X, n):
    if (int(X/n)):
        return Base_10_to_n(int(X/n), n)+str(X%n)
    return str(X%n)
n=int(input())
x=input()
ans=[]
pc=x.count("1")
la=[float("inf")]*pc
for i in range(1,pc+1):
    i10=str(Base_10_to_n(i, 2)).count("1")
    if i%i10==0:
      la[i-1]=1
    else:
      la[i-1]=la[(i%i10)-1]+1
if pc!=1:
  x10=Base_n_to_10(x,2)
  a=x10%(pc+1)
  b=x10%(pc+1)
  for i in range(1,n+1):
    if x[i-1]=="0":
      ans.append((a+pow(2,n-i,pc+1))%(pc+1))
    else:
      ans.append((b-pow(2,n-i,pc-1))%(pc-1))
  for a in ans:
    if a==0:
      print(1)
    else:
      print(1+la[a-1])
else:
  x10=Base_n_to_10(x,2)
  for i in range(1,n+1):
    if x[i-1]=="0":
      ans.append((x10+pow(2,n-i,pc+1))%(pc+1))
    else:
      ans.append("n")
  for a in ans:
    if a==0:
      print(1)
    elif a=="n":
      print(0)
    else:
      print(1+la[a-1])

Submission status: Wrong Answer

Solution code:
N = int(input())
X = input()
firstPopcount =  X.count('1')
for i in range(1, N+1):
  if X[i-1] == '0':
    b = X[:i-1]+'1'+X[i:]
    popcount = firstPopcount + 1
  else:
    b = X[:i-1]+'0'+X[i:]
    popcount = firstPopcount - 1
  v = int(b, 16)
  c = 0
  while v != 0:
    v = v % popcount
    c+= 1
    popcount = bin(v).count("1")
  print(c)

Submission status: Wrong Answer

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

def f(x):
    count = 0
    while x != 0:
        count += 1
        x %= popcount(x)
    return count

N = int(input())
X = "0b"+input()
X10 = int(X, 2)
popcountX = X.count("1")

f_table = [f(i+1) for i in range(N)]  # 1 回やれば絶対この中に入る

# for i in range(1, N+1):
#     if X[i+1] == "0":
#         diff = pow(2, N-i)
#         popcount = popcountX + 1
#     else:
#         diff = -pow(2, N-i)
#         popcount = popcountX - 1
#     res = (int(X, 2) + diff) % popcount
#     ans = f_table[res]
#     print(ans)

Submission status: Wrong Answer

Solution code:
def resolve():
    #n=int(input())
    #a,b=map(int,input().split())
    #x=list(map(int,input().split()))
    #a=[list(map(lambda x:int(x)%2,input().split())) for _ in range(h)]

    def popcount(n):
        c=format(n,'b').count('1')
        if c!=0:
            return n%c
        else:
            return 0
    def f(n):
        count=0
        while n>0:
            n=popcount(n)
            count+=1
        return count
        
    n=int(input())    
    x=input()
    cnt=x.count('1')
    x10=int(x,2)
    ans=[]
    if cnt==1:
        e=x10%2
        for i in range(n-1,-1,-1):
            if x10>>i&1:
                print(f(e-(2**i)%2)+1)
            else:
                print(f((e+(2**i)%2)+1))
    if cnt==0:
        for i in range(n):
            print(1)
    if cnt>1:
        a,b=x10%(cnt-1),x10%(cnt+1)
        for i in range(n-1,-1,-1):
            if x10>>i&1:
                print(f(a-(2**i)%(cnt-1))+1)
            else:
                print(f(b+(2**i)%(cnt+1))+1)

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
from functools import lru_cache

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

@lru_cache(maxsize=None)
def popctmod(n):
  c = bin(n).count('1')
  if c==0: return 1
  r = n % c
  if r==0:
    return 1#回
  return popctmod(r) + 1

memo = {}
for i in range(N):
  if X[i]=='1':
    bitStr = X[:i] + '0' + X[i+1:]
  else:
    bitStr = X[:i] + '1' + X[i+1:]
  num = int(bitStr, 2)
  print(popctmod(num))

Submission status: Wrong Answer

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

def popcnt(x):
    n=x
    res=0
    while n>0:
        res+=n%2
        n//=2
    return res

table=[0,1]+[-1 for i in range(219998)]
for i in range(2,220000):
    table[i]=table[i%popcnt(i)]+1

moto=0
for i in range(N):
    if X[i]=='1':
        moto+=1

plus=0  #もとの数字に1のときのmodをしたやつ
minus=0

for i in range(N):
    plus+=int(X[i])*pow(2,N-1-i,max(1,moto-1))
    minus+=int(X[i])*pow(2,N-1-i,moto+1)
    plus%=(max(1,moto-1))
    minus%=(moto+1)

for i in range(N):
    ans=0
    if X[i]=='1':
        ans=plus
        ans-=pow(2,N-1-i,max(1,moto-1))
        ans%=(max(1,moto-1))
    else:
        ans=minus
        ans+=pow(2,N-1-i,moto+1)
        ans%=(moto+1)
    print(table[ans]+1)

Submission status: Wrong Answer

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

def popcount(num):
    bin_num = bin(num)[2:]
    count = 0
    for i in bin_num:
            count += int(i)
    return count

def f(num):
    i = 0
    while num > 0:
        num = num % popcount(num)
        i += 1
    return i


xl = []
i = n - 1
while i >= 0:
    xi = bin(x & ~pow(2, i))
    xl.append(xi)
    i = i - 1

for j in range(len(xl)):
    print(f(int(xl[j],0)))

Submission status: Wrong Answer

Solution code:
N = int(input())
X = int(input(),2)
mem = {}
def f(n):
    if n-1 in mem:
        return mem[n-1]
    count = 0
    while True:
        if n == 0:
            mem[n-1] = count
            return count
        n %= bin(n).count('1')
        count += 1
for i in range(N-1,-1,-1):
    print(f(X^(1<<i)))

Submission status: Wrong Answer

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

def binToInt(X):
    ret = 0
    for s in X:
        ret <<= 1
        if s == '1':
            ret += 1
    return ret

def cnt(n):
    ret = 0
    while n > 0:
        n, r = divmod(n, 2)
        ret += r
    return ret

def f(n):
    ret = 0
    while n > 0:
        ret += 1
        n %= cnt(n)
    return ret

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

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

Submission status: Wrong Answer

Solution code:
n = int(input())
xo = input()
output = []
import copy
fn = {}

for i in range(n):
  x = copy.copy(xo)
  if x[i] == "0":
    x = x[:i] + "1" + x[i+1:]
  else:
    x = x[:i] + "0" + x[i+1:]
  x = bin(int(x,2))
  counter = int(copy.copy(x),2)
  outi = 0
  while counter != 0:
    cop =  bin(counter).count("1")
    counter = counter%cop
    outi += 1
    if counter in fn.keys():
      outi += fn[counter]
      counter = 0
  fn[int(x,2)] = outi 
  output.append(str(outi))

Submission status: Wrong Answer

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

def func(x):
    popc = 0
    for i in x:
        if (i == "1"):
            popc += 1
    if (popc == 0):
        num = 0
    else:
        num = 1
        x = int(x, 2)%popc
        while (x != 0):
            popc = x
            x = x%popc
            num += 1
    
    return(num)

for i in range(n):
    if (x[i] == "1"):
        y = x[:i] + '0' + x[i+1:]
    else:
        y = x[:i] + '1' + x[i+1:]
    
    print(func(y))

Submission status: Wrong Answer

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

def binToInt(X):
    ret = 0
    for s in X:
        ret <<= 1
        if s == '1':
            ret += 1
    return ret

def cnt(n):
    ret = 0
    while n > 0:
        n, r = divmod(n, 2)
        ret += r
    return ret

def f(n):
    ret = 0
    while n > 0:
        ret += 1
        n %= cnt(n)
    return ret

N = int(input())
X = binToInt(input().decode())

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

Submission status: Wrong Answer

Solution code:
#n=200000
n=int(input())
#x="10"*100000
x=input()
d=[0]*(2*10**5+1)
for j in range(2*10**5+1):
  bin_num=j
  iti2=0
  count=0
  X=bin(bin_num)
  for i in X:
    if i=="1":
      iti2+=1
  count+=1
  if iti2==0:
    d[j]=0
  else:
    bin_num=bin_num%iti2  
    d[j]=d[bin_num]+1
  
iti=0
zero=0
for i in x:
  if i=="1":
    iti+=1
zero=n-iti

for i in range(n):
  bin_num = i
  ans=0
  if x[i]=="1":
    bin_num+=pow(2,i)
    iti2=iti-1
  else:
    bin_num+=pow(2,i)
    iti2=iti+1
  if iti2!=0:
    bin_num=bin_num%iti2
    print(d[bin_num]+1)
  else:
    print(0)

Submission status: Wrong Answer

Solution code:
#n=200000
#x="10"*100000
n=int(input())
x=input()
d=[0]*(2*10**5+1)
for j in range(2*10**5+1):
  bin_num=j
  iti2=0
  count=0
  X=bin(bin_num)
  for i in X:
    if i=="1":
      iti2+=1
  count+=1
  if iti2==0:
    d[j]=0
  else:
    bin_num=bin_num%iti2  
    d[j]=d[bin_num]
  
iti=0
zero=0
for i in x:
  if i=="1":
    iti+=1
zero=n-iti

for i in range(n):
  bin_num = i
  ans=0
  if x[i]=="1":
    bin_num+=pow(2,i)
    iti2=iti-1
  else:
    bin_num+=pow(2,i)
    iti2=iti+1
  if iti2!=0:
    bin_num=bin_num%iti2
    print(d[bin_num]+1)
  else:
    print(0)

Submission status: Wrong Answer

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

for i in range(n):
  y = 2**(n-i-1)
  z = y ^ x
  c = 0
  for j in range(z):
    c +=1
    str_z = str(bin(z))
    a = str_z.count("1")
    z = z%a
    if z ==0:
      print(c)
      break

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N = I()
X = list(input())

# xが0になるまで何回かかるか
def calc(x):
    n = len(x)
    c = x.count('1')
    now = 0
    for i in range(n):
        if x[i] == '1':
            now += 2**(n-1-i)
            now %= c
    if now == 0:
        return 1
    else:
        return calc(list(format(now,'b')))+1

count = X.count('1')

a = [1]*(N+1)
if count >= 2:
    a[0] = 1%(count-1)
    for i in range(1,N+1):
        a[i] = a[i-1]*2
        a[i] %= count-1

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

suma = 0
sumb = 0
for i in range(N):
    if X[i] == '1':
        suma += a[N-i-1]
        sumb += b[N-i-1]
        sumb %= (count+1)
        if count >= 2:
            suma %= (count-1)

ans = [0]*N
for i in range(N):
    if X[i] == '1':
        if count == 1:
            ans[i] = 1
            continue
        val = (suma-a[N-i-1])%(count-1)
        if val == 0:
            ans[i] = 1
        else:
            ans[i] = calc(list(format(val,'b')))+1
    else:
        val = (sumb+b[N-i-1])%(count+1)
        if val == 0:
            ans[i] = 1
        else:
            ans[i] = calc(list(format(val,'b')))+1

for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = input()
pop = X.count("1")
lst = [1]

for i in range(N-1):
    lst.append(lst[-1] * 2 % (pop + 1))

lst.reverse()
num1 = 0

for i in range(N):
    if X[i] == "1":
        num1 += lst[i]
        num1 = num1 % (pop + 1)
if pop == 1 or pop == 2:
    lst2 = [0] * N
else:
    lst2 = [1]
    for i in range(N-1):
        lst2.append(lst2[-1] * 2 % (pop - 1))

    lst2.reverse()
    num2 = 0
    
    for i in range(N):
        if X[i] == "1":
            num2 += lst2[i]
            num2 = num2 % (pop - 1)
            
b = int(X, 2)
for i in range(N):
    if X[i] == "1":
        if pop == 1:
            print(0)
            continue
        elif pop == 2:
            print(1)
            continue
        else:
            num = num2 - lst[i]
            num = num % (pop - 1)
    else:
        num = num1 + lst[i]
        num = num % (pop + 1)
    count = 1
    while num:
        num %= bin(num).count("1")
        count += 1
    print(count)

Submission status: Wrong Answer

Solution code:
from functools import lru_cache


result = 0
@lru_cache(maxsize=None)
def popcount(n):
    global result
   
    bin_n = bin(n)
    one = bin_n.count('1')
    tmp = n % one
    result += 1
    if tmp > 0:
        popcount(tmp)
    return(result)



N = int(input())
stri = input()

X = 0
for i in range(len(stri)):
    if stri[len(stri) -1 -i] == '1':
        X += 2 ** i

# print(popcount(1))
# print(1<<3)
# print(0b111 ^ 1<<2)
for i in range(len(stri)-1,-1,-1):
    tmpX = X ^ 1<<i
    # print(tmpX)
    if tmpX == 0:
        print(0)
    else:
        print(popcount(tmpX))
    result = 0

Submission status: Wrong Answer

Solution code:
# n = 2*10**5
# X = "10"*10**5
n = int(input())
X = input()
c = 0
cnt = 0
for i,x in enumerate(X):
    c += (1<<(n-i-1))*int(x)
    cnt += int(x)

amari_cnt_p = c % (cnt+1)
if cnt != 1:
    amari_cnt_m = c % (cnt-1)

dp = []
for d in range(n):
    if cnt == 1:
      dp.append(-1)
      continue

    if X[d] == "0":
        amari = (amari_cnt_p + pow(2,n-d-1,cnt+1))%(cnt+1)
    else:
        if cnt != 1:
            amari = (amari_cnt_m - pow(2,n-d-1,cnt-1))%(cnt-1)
        else:
            amari = 0
    dp.append(amari)

memo = [-1]*(2*10**5+10)
memo[0] = 1
def calc(n):
    if n == -1:
        return 0
    if n == 0:
        return 1
    if memo[n] != -1:
        return memo[n]
    cnt = 1
    while n > 0:
        c = bin(n).count("1")
        n %= c
        cnt += 1
    memo[n] = cnt
    return cnt

for d in dp:
    ans = calc(d)
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = input()
pop = X.count("1")
lst = [1]

for i in range(N-1):
    lst.append(lst[-1] * 2 % (pop + 1))

lst.reverse()
num1 = 0

for i in range(N):
    if X[i] == "1":
        num1 += lst[i]
        num1 = num1 % (pop + 1)
if pop == 1 or pop == 2:
    lst2 = [0] * N
else:
    lst2 = [1]
    for j in range(N-1):
        lst2.append(lst2[-1] * 2 % (pop - 1))

    lst2.reverse()
    num2 = 0
    
    for j in range(N):
        if X[j] == "1":
            num2 += lst2[j]
            num2 = num2 % (pop - 1)
            
b = int(X, 2)
for i in range(N):
    if X[i] == "1":
        if pop == 1:
            print(0)
            continue
        elif pop == 2:
            print(1)
            continue
        else:
            num = num2 - lst[i]
            num = num % (pop - 1)
    else:
        num = num1 + lst[i]
        num = num % (pop + 1)
    count = 1
    while num:
        num %= bin(num).count("1")
        count += 1
    print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
x = input()
one_num = x.count('1')

ans_reduce,ans_add = 0,0
for i in range(n):
    if(one_num>1):
        ans_reduce = (ans_reduce+pow(2,n-i-1,one_num-1)*(1 if x[i] == '1' else 0))%(one_num-1)
    ans_add = (ans_add+pow(2,n-i-1,one_num+1)*(1 if x[i] == '1' else 0))%(1+one_num)

for i in range(n):
    now_one = one_num + (-1 if x[i] == '1' else 1)
    if(now_one == 0):
        print(1)
        continue
    num = ((ans_reduce if x[i] == '1' else ans_add) + pow(2,n-i-1,now_one)*(-1 if x[i] == '1' else 1))%now_one
    ans = 1
    while(num!=0):
        ans += 1
        num = num % bin(num).count('1')
    print(ans)

Submission status: Wrong Answer

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

for i in range(N):
    res, n = 1, int(X, 2) ^ (1<<(N-i-1))
    print(n)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def main():
    n = int(input())
    s = int(input(), 2)
    pc0 = bin(s).count("1")
    ans = []
    f = [0] * (n + 1)
    for i in range(1, n + 1):
        f[i] = i % bin(i).count("1") + 1
    for i in range(n):
        k = 1 << (n - 1 - i)
        x = k ^ s
        if x > s:
            pc1 = pc0 + 1
        else:
            pc1 = max(1, pc0 - 1)
        cnt = 0
        while x > 0:
            if cnt == 0:
                pc = pc1
            else:
                pc = f[x]
            x %= pc
            cnt += 1
        ans.append(cnt)
    print("\n".join(str(y) for y in ans))
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
save_list = [idx for idx in range(200010)]

def cal_nums(number, flag=0):
    if number == 0:
        return 0
    if number <= 200000 and flag==1:
        return number % save_list[number]
    cp = number
    cnt = 0
    pos = 0
    # print(num_one)
    while cp != 0:
        cnt += cp % 2
        cp //= 2
    # print(cnt)
    
    return number % cnt

def func(number, flag=0):
    # print(num_one)
    if number == 0:
        return 0
    cnt = 0
    tmp = number
    while(1):
        cnt += 1
        tmp = cal_nums(tmp, flag)
        if tmp == 0:
            break
    return cnt

def cal_nums2(number):
    if number == 0:
        return 0
    if number <= 200000:
        return number % save_list[number]

def func2(number, num_one):
    if number == 0:
        return 0
    cnt = 0
    cnt += 1
    tmp = number % num_one
    if tmp == 0:
        return cnt
    while(1):
        cnt += 1
        tmp = cal_nums2(tmp)
        if tmp == 0:
            break
    return cnt

# print('ok')
for idx in range(1, 200000):
    # print('!')
    save_list[idx] = func(idx)
    # print(save_list[idx])
    # print('??')
    # print(save_list[idx])

# print('ok')

n = int(input())
string = input()
length = len(string)
tmp = 0
for i in range(length):
    tmp *= 2
    if string[i] == '1':
        tmp += 1

cnt_0 = 0
cnt_1 = 0

for idx in range(length):
    if string[idx] == '0':
        cnt_0 += 1
    else:
        cnt_1 += 1

# print('ok')
for idx in range(length):
    if string[idx] == '0':
        # print(tmp+(1<<(length-idx-1)))
        print(func2(tmp+(1<<(length-idx-1)), cnt_1+1))
        # print(tmp+(1<<(length-idx-1)))
    else:
        # print(tmp+(1<<(length-idx-1)))
        print(func2(tmp-(1<<(length-idx-1)), cnt_1-1))
        # print(tmp-(1<<(length-idx-1)))

Submission status: Wrong Answer

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

cnt = X.count("1")
div = [0] * (cnt + 10)
for i in range(1, cnt + 10):
    for n in range(20):
        div[i] += i >> n & 1

memo = [-1] * (cnt + 10)
memo[0] = 0
for i in range(1, cnt + 10):
    memo[i] = memo[i % div[i]] + 1

res0 = 0
res1 = 0
for i in range(N):
    if X[i] == "1":
        res0 = (res0 + pow(2, N - i - 1, cnt + 1)) % (cnt + 1)
        
        if cnt - 1 > 0:
            res1 = (res1 + pow(2, N - i - 1, cnt - 1)) % (cnt - 1)

for i in range(N):
    if X[i] == "0":
        div = cnt + 1
        tmp = (res0 + pow(2, N - i - 1, div)) % div
    else:
        if cnt - 1 > 0:
            div = cnt - 1
            tmp = (res1 + div - pow(2, N - i - 1, div)) % div
        else:
            tmp = 0
    print(memo[tmp] + 1)

Submission status: Wrong Answer

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

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

    if Xc == 0:
        [print(1) for i in range(N)]
    elif Xc == 1:
        d = X.index(1)
        ans1 = 0
        for j in range(N):
            if X[j]:
                ans1 += pow(2,N-1-j,Xc+1)
                ans1 %= Xc+1

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

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
import copy
n = int(input())
k = input()
xnum = int(k,2)

def f(x):
    a = bin(x)
    a = a[2:]
    num = a.count('1')
    ans = 1
    if num != 0:
        hantei = x % num
    else:
        hantei =  0
    while hantei != 0:
        ans += 1
        a = bin(hantei)
        a = a[2:]
        num = a.count('1')
        if num != 0:
            hantei = hantei % num
        else:
            hantei =  0
    return ans

z = []
for i in range(n):
    y = copy.deepcopy(k)
    if y[i] == '1':
        ynum = xnum - 2 ** (n-i-1)
        z.append(ynum)
    else:
        ynum = xnum + 2 ** (n-i-1)
        z.append(ynum)

for j in z:
    ans = f(j)
    print(ans)