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 popcnt(n):
    return bin(n).count("1")
N = int(input())
L = [0]*(N+1)
for i in range(1,N+1):
    L[i] = L[i%popcnt(i)]+1
X = input()
M = X.count("1")+1
m = max(1,M-2)
X = list(X)
XM = int(X[-1])
Xm = int(X[-1])
tM = 1
tm = 1
X.reverse()
for i in range(1,N):
    tM = tM*2%M
    tm = tm*2%m
    if X[i] == "1":
        XM = (XM + tM)%M
        Xm = (Xm + tm)%m
ans = []
tM = 1
tm = 1
for i in range(N):
    A = 0
    if X[i] == "0":
        A = (XM + tM)%M
    else:
        A = (Xm + m - tm)%m
        if M == 2:
            A = 0
    ans.append(A)
    tM = (tM*2)%M
    tm = (tm*2)%m
ans.reverse()
for a in ans:
    print(L[a]+1)

Submission status: Wrong Answer

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

for i in range(1, N+1):
  if X[i-1] == '0':
    b = X[:i-1]+'1'+X[i:]
  else:
    b = X[:i-1]+'0'+X[i:]
  popcount = b.count('1')
#  v = 0
#  for j in range(len(b)):
#    v += int(b[j]) * 2**(len(b)-j-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 getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

popc = [0] * ((1 << 19) + 1)
for bit in range(1, 1 << 19):
    opt = bin(bit).count('1')
    popc[bit] = bit % opt

f_list = [0] * ((1 << 19) + 1)
for i in range(1, 1 << 19):
    now = popc[i]
    cnt = 1
    while True:
        if now == 0:
            f_list[i] = cnt
            break
        now = popc[now]
        cnt += 1

N = getN()
X = input()
NX = len(X)
time = X.count('1')
t1 = time + 1
t2 = time - 1

lis_left_1 = [0] * (NX + 1)

now = 1 % t1
lis_left_1[0] = now
for i in range(1, NX + 1):
    now = (2 * now) % t1
    lis_left_1[i] = now

lis_left_2 = [0] * (NX + 1)

if t2 > 0:
    now = 1 % t2
    for i in range(1, NX + 1):
        now = (2 * now) % t2
        lis_left_2[i] = now
else:
    now = 0

left_mother_1 = 0
for i in range(NX):
    if int(X[i]) == 1:
        left_mother_1 += lis_left_1[NX - i - 1]

left_mother_2 = 0
for i in range(NX):
    if int(X[i]) == 1:
        left_mother_2 += lis_left_2[NX - i - 1]

for i in range(N):
    # 1が0に left_mother_2, t2
    if int(X[i]) == 1:
        if t2 == 0:
            print(0)
            continue
        opt_mom = left_mother_2
        opt_mom -= lis_left_2[NX - i - 1]
        opt_mom %= t2
        print(f_list[opt_mom] + 1)
    # 0が1に left_mother_1, t1
    else:
        opt_mom = left_mother_1
        opt_mom += lis_left_1[NX - i - 1]
        opt_mom %= t1
        print(f_list[opt_mom] + 1)

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 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 == 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()
p=x.count("1")
Ma=[1]+[0]*(n-1)
Mb=[1]+[0]*(n-1)
for i in range(1,n):
  if p>1:
    Ma[i]=Ma[i-1]*2%(p-1)
  else:
    Ma[i]=0
  Mb[i]=Mb[i-1]*2%(p+1)
Sa=Sb=0
for i in range(n):
  if x[i]=="1":
    Sa+=Ma[n-1-i]
    Sb+=Mb[n-1-i]
for i in range(n):
  a=1
  if x[i]=="1":
    if p-1==0:
      s=0
    else:
      s=(Sa-Ma[n-1-i])%(p-1)
  else:
    s=(Sb+Mb[n-1-i])%(p+1)
  while(s>0):
    t=0
    r=s
    while(r>0):
      t+=r&1
      r//=2
    s%=t
    a+=1
  print(a)

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 calc(x):#xは数字
        if x==0:
            return 0
        xn=x
        x=bin(x)[2:]
        cnt=sum(list(map(int,list(x))))
        if xn%cnt==0:
            return 1
        else:
            return calc(xn%cnt)+1
    
    n=int(input())    
    x=input()
    cnt=sum(list(map(int,list(x))))
    x=int(x,2)
    ans=[]
    for i in range(n):
        if x>>i&1:
            if cnt-1==0:
                ans.append(1)
            else:
                ans.append(calc((x-2**i)%(cnt-1))+1)
        else:
            ans.append(calc((x+2**i)%(cnt+1))+1)
    print(*ans[::-1],sep='\n')

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from functools import reduce, lru_cache
import collections, heapq, itertools, bisect
import math, fractions
import sys, copy

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline().rstrip())
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline().rstrip())
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

def main():
    N = I()
    X = S()
    original_popcount = X.count("1")

    upper_popcount = original_popcount + 1
    lower_popcount = original_popcount - 1

    if original_popcount == 0:
        for i in range(N):
            print(1)
        return

    if original_popcount == 1:
        for i in range(N):
            if X[-1] == "1":
                if i != N-1:
                    print(2)
                else:
                    print(0)
            else:
                if X[i] == "1":
                    print(0)
                else:
                    print(1)
        return

    # Xが0の可能性
    upper = [0] * N
    lower = [0] * N
    upper[-1] = 1 % upper_popcount
    lower[-1] = 1 % lower_popcount

    for i in range(1, N)[::-1]:
        upper[i-1] = (2 * upper[i]) % upper_popcount
        lower[i-1] = (2 * lower[i]) % lower_popcount

    mu = 0
    ml = 0
    for i in range(N):
        if X[i] == "1":
            mu = (mu + upper[i]) % upper_popcount
            ml = (ml + lower[i]) % lower_popcount

    for i in range(N):
        if X[i] == "0":
            m = (mu + upper[i]) % upper_popcount
        else:
            m = (ml - lower[i]) % lower_popcount

        ans = 1
        while m:
            tmp = m
            ones = 0
            while tmp:
                if tmp & 1 == 1:
                    ones += 1
                tmp //= 2
            m %= ones
            ans += 1

        print(ans)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

fn = dict()

def f(n, count):
    # binary = bin(n)[2:]
    popcount = bin(n).count('1')
    # for b in binary:
    #     if b == '1':
    #         popcount += 1
    count += 1
    if n%popcount == 0:
        return count
    else:
        if n%popcount in fn:
            return fn[n%popcount]
        else:
            x = f(n%popcount, count)
            fn[n%popcount] = x- count
            # fn[n] = x
            return x

for i in range(N):
    X_i = X[:]
    if X_i[i] == '1':
        X_i[i] = '0'
    else:
        X_i[i] = '1'
    X_i = ''.join(X_i)
    n = int(X_i, 2)
    if n == 0:
        ans = 0
    else:
        ans = f(n, 0)
    fn[n] = ans
    print(ans)
    # print(fn)
# print(fn)

Submission status: Wrong Answer

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


def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)

    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):
    tmp = pow(2, i)
    tmp2 = X ^ tmp
    div = popcount(tmp2)
    cnt = 0
    while div != 0:
        tmp2 = tmp2 % div
        div = popcount(tmp2)
        cnt += 1
    print(cnt)

Submission status: Wrong Answer

Solution code:
# def popcount(x):
#     bitx = bin(x)
#     cnt = bitx.count('1')
#     return cnt

n = int(input())
x = list(input())
popcount = x.count('1')
stock = [1] * n

for i in range(1, n):
    stock[i] = stock[i - 1] * 2
stock.reverse()


for i in range(n):
    tmp = x.copy()
    tmp2 = popcount
    if tmp[i] == '1':
        tmp[i] = '0'
        tmp2 -= 1
    else:
        tmp[i] = '1'
        tmp2 += 1
    num = 0
    if tmp[n-1] == '0':
        for i in range(n):
            num += int(tmp[i]) * stock[i]
    
    if tmp2 == 0:
        print(0)
    elif num > 0 and num % tmp2 == 0:
        print(1)
    elif tmp[n - 1] == '1' and tmp2 % 2 == 0 and tmp2 > 2:
        print(3)
    else:
        print(2)

Submission status: Wrong Answer

Solution code:
def f(n):
    if n in memo:
        return memo[n]
    c=list(str(bin(n)))[2:].count('1')
    r=n%c
    if r>0:
        memo[n]=f(r)+1
    else:
        memo[n]=1
    return memo[n]

memo={0:0}
N=int(input())
X=list(input())
XC=X.count('1')
XN=int('0b'+''.join(X),2)
for i in range(N):
    if X[i]=='1':
        if XC==1:
            print(0)
            continue
        tx=(XN%(XC-1)-pow(2,N-i-1,XC-1))%XC-1
        if tx<0:
            tx+=XC-1
    else:
        tx=(XN%(XC+1)+pow(2,N-i-1,XC+1))%(XC+1)
    print(f(tx)+1)

Submission status: Wrong Answer

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

def resCount(n):
    tmp = bin(n).count('1')
    if tmp == 1:
        return 1
    elif tmp == 0:
        return 0
    else:
        return 1 + resCount(n % tmp)

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

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)]
        exit()
    elif Xc == 1:
        d = X.index(1)
        for j in range(N):
            if d == j:
                print(0)
            else:
                print(1)
        exit()

    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:
N = int(input())
X = str(input())
A=[0] * N
for i in range(N):
    A[i]=int(X[-i])
A.reverse()
ans=0
for i in range(N-1,-1,-1):
    if A[i]==0:
        A[i]=1
        for j in range(N):
            ans+=(2**j)*A[j]
        q=0
        k=ans
        while k>0:
            a=bin(k)
            k=k%a.count('1')
            q+=1
        print(q)
        A[i]=0
        ans=0
    if A[i]==1:
        A[i]=0
        for j in range(N):
            ans+=(2**j)*A[j]
        q=0
        k=ans
        while k>0:
            a=bin(k)
            k=k%a.count('1')
            q+=1
        print(q)
        A[i]=1
        ans=0

Submission status: Wrong Answer

Solution code:
def power(x, n):
    if n == 0: return 1
    value = power(x, int(n / 2))
    value *= value
    if n % 2 == 1: value *= x
    return value

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

number = int(''.join(x), 2)
count = x.count('1')

def f(num, cnt):
    if num == 0:
        return cnt
    popcount = format(num, 'b').count('1')
    return f(num % popcount, cnt+1)

for i in range(n):
    if x[i] == '0':
        m = number + power(2, n-i-1)
        print(f(m % (count+1), 1))
    if x[i] == '1':
        m = number + power(2, n-i-1)
        if (count - 1):
            print(f(m % (count-1), 1))
        else:
            print(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)
else:
    amari_cnt_m = 0

dp = []
for d in range(n):
    if X[d] == "0":
        amari = (amari_cnt_p + pow(2,n-d-1,cnt+1))%(cnt+1)
    else:
        if cnt != 1:
            amari = (2*(cnt-1) + amari_cnt_m - pow(2,n-d-1,cnt-1))%(cnt-1)
        else:
            amari = -1
    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 = 2
    while True:
        c = bin(n).count("1")
        if n%c == 0:
            break
        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=str(input())
pop=[0]
a=1
b=0
count=1
for i in range(1,n):
    ni=0
    a=i
    while a:
        a&=(a-1)
        ni+=1
    pop.append(ni)

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)
else:
    amari_cnt_m = 0

dp = []
for d in range(n):
    if X[d] == "0":
        amari = (amari_cnt_p + pow(2,n-d-1,cnt+1))%(cnt+1)
    else:
        if cnt != 1:
            amari = (cnt-1 + amari_cnt_m - pow(2,n-d-1,cnt-1))%(cnt-1)
        else:
            amari = -1
    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 = 2
    while True:
        c = bin(n).count("1")
        if n%c == 0:
            break
        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()

NumberList = dict()

for i in range(N):
    if X[i] == '0':
        if i != 0:    
            tmp = X[:i] + '1' + X[i + 1:]
        else:
            tmp = '1' + X[i + 1:]
    else:
        if i != 0:    
            tmp = X[:i] + '0' + X[i + 1:]
        else:
            tmp = '0' + X[i + 1:]
    
    ten_m = int(tmp, 2)
    two_pop = bin(ten_m).count("1")
    
    ten_m_tmp = ten_m
    count = 0
    NumberList_tmp = []
    while ten_m != 0:
        if ten_m in NumberList:
            count += NumberList[ten_m]
            break
        ten_m = ten_m % two_pop
        two_pop = bin(ten_m).count("1")
        count += 1
        
        NumberList_tmp.append(ten_m)
    
    tmp = 1
    NumberList_tmp.reverse()
    for i in NumberList_tmp:
        NumberList[i] = tmp
        tmp += 1
    print(count)

Submission status: Wrong Answer

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

def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    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

memo = {}

def counter(count, X_current, X_one_current):
    if X_current in memo:
        return memo[X_current] + count

    X_prev = X_current

    X_current = X_current % X_one_current
    X_one_current = popcount(X_current)
    count += 1

    if X_current == 0:
        memo[X_prev] = 1
        return count
    else:
        value = counter(count, X_current, X_one_current)
        memo[X_prev] = value
        return value


def solve(N, X):
    X_oct = int(X, 2)
    X_one_count = X.count("1")

    memo = {}
    for i, x in enumerate(X):
        if x == '1':
            X_current = X_oct - 2 ** (N-1-i)
            X_one_current = X_one_count - 1
        elif x == '0':
            X_current = X_oct + 2 ** (N - 1 - i)
            X_one_current = X_one_count + 1

        if X_one_current == 0:
            print(0)
            continue

        count = counter(0, X_current, X_one_current)
        print(count)

    return

def main():
    N = int(input())
    X = input()
    solve(N, X)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from itertools import combinations
N = int(input())
X = int(input(),2)
X2 = bin(X)
#L, R, d=map(int,input().split())
#C = []
# for i in range(N):
#    C.append((input().replace(".","0").replace("#","1")))
# S=list(map(int,input().split()))
# B=list(map(int,input().split()))
def calc(n,x):
    if n!=0:
        return calc(n%str(bin(n))[2:].count("1"),x+1)
    elif n<=0:
        return x

for i in reversed(range(1,N+1)):
    print(calc(X^(1 << i),0))

Submission status: Wrong Answer

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

fn = dict()

def f(n, count):
    # binary = bin(n)[2:]
    popcount = bin(n).count('1')
    # for b in binary:
    #     if b == '1':
    #         popcount += 1
    count += 1
    if n%popcount == 0:
        return count
    else:
        if n in fn:
            return fn[n]
        else:
            x = f(n%popcount, count)
            fn[n%popcount] = x- count
            # fn[n] = x
            return x

for i in range(N):
    X_i = X[:]
    if X_i[i] == '1':
        X_i[i] = '0'
    else:
        X_i[i] = '1'
    X_i = ''.join(X_i)
    n = int(X_i, 2)
    if n == 0:
        ans = 0
    else:
        ans = f(n, 0)
    fn[n] = ans
    print(ans)
    # print(fn)
# print(fn)

Submission status: Wrong Answer

Solution code:
p = {}
def popc(num):
    ans = 0
    while num >0:
        b = bin(num)
        a = list(str(b))
        num = num % a.count("1")
        ans +=1
    return ans

n = int(input())
s = list(str(input()))
for i in range(n):
    if s[i] == "1":
        s[i] = "0"
    else:
        s[i] = "1"

    num = ''.join(map(str,s))
    print(popc(int(num)))
    if s[i] == "1":
        s[i] = "0"
    else:
        s[i] = "1"

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
  while z != 0:
    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:
n = int(input())
x = list(input())
cnt = x.count("1")

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

popcountlst = [None] * (10 ** 5)
for i in range(10 ** 5):
    popcountlst[i] = popcount(i)

for i in range(n):
    y = x[:]
    if x[i] == "1":
        y[i] = "0"
        z = "".join(y)
        z = int(z, 2)
        if z == 0:
            print(1)
        else:
            z %= (cnt - 1)
            if z == 0:
                print(1)
            else:
                ans = 1
                while z > 0:
                    z %= popcountlst[z]
                    ans += 1
                print(ans)
    else:
        y[i] = "1"
        z = "".join(y)
        z = int(z, 2)
        z %= (cnt + 1)
        if z == 0:
            print(1)
        else:
            if z == 0:
                print(1)
            else:
                ans = 1
                while z > 0:
                    z %= popcountlst[z]
                    ans += 1
                print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
# from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
# import numpy as np
# sys.setrecursionlimit(int(pow(10,6)))

mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

try:
    sys.stdin = open("input.txt", "r")
    sys.stdout = open("out.txt", "w")
except:
    pass


# @lru_cache(None)

n=L()[0]
X=input()
if X=="0"*n:
    for i in range(n):
        print(1)
    exit()
if X=="1":
    print(0)
    exit()
curr=curr2=1
nao=mnao=0
bit=X.count("1")+1
bit2=X.count("1")-1
if bit==2:
    if X[n-1]=="1":
        for i in range(n):
            if X[i]=="0":
                print(2)
            else:
                print(1)
        exit()
    else:
        for i in range(n):
            if i==n-1:
                print(2)
            elif X[i]=="0":
                print(1)
            else:
                print(0)
        exit()

for i in range(n-1,-1,-1):
    if X[i]=="1":
        nao+=curr%bit
        nao%=bit
        mnao+=curr2%bit2
        mnao%=bit2
    curr*=2
    curr%=bit
    curr2*=2
    curr2%=bit2
print(curr,curr2,bit,bit2,nao,mnao)
for  i in range(n):
    FN=0
    if X[i]=="0":
        FN=nao
        ex=pow(2,n-i-1,bit)
        FN+=ex
        FN%=bit
    else:
        FN=mnao
        ex=pow(2,n-i-1,bit2)
        FN-=ex
        FN%=bit2
        if FN<0:
            FN+=bit2
    step=1
    # print(FN)
    while(FN):
        bitcnt=bin(FN).count("1")
        FN%=bitcnt
        step+=1
    print(step)

Submission status: Wrong Answer

Solution code:
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

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

X_10 = int("0b" + X, 0)
for i in range(N):
    num = X_10
    if X[i] == "0":
        num += int(2**(N-i-1))
    else:
        num -= int(2**(N-i-1))
    num_2 = bin(num)
    count = 0
    while True:
        count_2 = 0
        """
        for j in range(len(num_2)):
            if num_2[j] == "1":
                count_2 += 1
        """
        count_2 = popcount(int(num_2, 0))
        if count_2 == 0:
            break
        else:
            count += 1
        num_2 = bin(int(num_2, 0) % count_2)
    print(count)

Submission status: Wrong Answer

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

def resCount(n):
    tmp = bin(n).count('1')
    if tmp == 1 or tmp == 0:
        return 1
    elif tmp == 0:
        return 0
    else:
        return 1 + resCount(n % tmp)

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

Submission status: Wrong Answer

Solution code:
N = int(input())
X = int(input(),2)
count = 0
for i in range(N):
    T = X
    T = T ^ (1<<N-1-i)
    while True:
        count += 1
        if T == 0:
            print(count)
            break
        T = T % bin(T).count('1')
        if T == 0:
            print(count)
            break
    count = 0

Submission status: Wrong Answer

Solution code:
def inv(X, i):
    if X % 2 ** i == 0:
        X += 2 ** i
    else:
        X -= 2 ** i
    return X

def ppc(x):
    return bin(x).count('1')

N = int(input())
X = int('0b' + input(), 0)

for i in range(N):
    p = inv(X, i)
    counter = 0

    while True:
        if p == 0: break
        p = p % ppc(p)
        counter += 1

    print(counter)

Submission status: Wrong Answer

Solution code:
'''Author- Akshit Monga'''
n=int(input())
x=input()
x=x[::-1]
ans1=0
ans2=0
c=x.count('1')
for i in range(0,n):
    if x[i]:
        ans1=(ans1+pow(2,i,c+1))%(c+1)
        if c!=1:
            ans2=(ans2+pow(2,i,c-1))%(c-1)
to_print=[]
for i in range(0,n):
    if x[i]=='1':
        if c==1:
            to_print.append(0)
            continue
        var=(ans2%(c-1)-pow(2,i,c-1))%(c-1)
        a = 1
        while var:
            var = var % bin(var).count('1')
            a += 1
        to_print.append(a)
    else:
        # print(ans1)
        var = (ans1%(c+1) + pow(2, i, c +1))%(c+1)
        # print(c+1)
        # print(var)
        a = 1
        while var:
            var = var % bin(var).count('1')
            a += 1
        to_print.append(a)
for i in to_print[::-1]:
    print(i)

Submission status: Wrong Answer

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

def resCount(n):
    tmp = bin(n).count('1')
    if tmp == 1 or tmp == 0:
        return 1
    else:
        return 1 + resCount(n % tmp)

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