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:
n = int(input())
tmp = input()

s = int(tmp, 2)
nn = sum([int(a) for a in tmp if a == '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


def division_binary_shift(a, b):
    """
    a // b

    :param a: dividend
    :param b: divisor
    :return: quotient
    """
    if a < b:
        return 0
    if b == 0:
        raise ZeroDivisionError

    q = 0
    sq = 1
    ori_b = b
    while a >= b:
        b <<= 1
        if a >= b:
            sq <<= 1
        else:
            b >>= 1
            a -= b
            q += sq
            sq = 1
            b = ori_b

    return q


for i in range(n):
    ss = s ^ (1 << (n-i-1))
    c = 0
    # t = popcount(ss)
    # while ss != 0:
    #     ss -= t*division_binary_shift(ss, t)
    #     t = popcount(ss)
    #     c += 1
    # print(ss, popcount(ss), c)
    print(c)

Submission status: Wrong Answer

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

def getMod(_str, n, k):
    res = 0
    i = 0
    j = n - 1
    for i in range(len(_str)):  
        if (_str[j] == '1') :  
            res += (1<<i)%k
            res %= k 
        j -= 1
    return res

def inv(i):
    if x[i] == '1':
        return '0'
    else:
        return '1'

n = inp()
x = list(input().strip())
tt = x.count('1')
for i in range(n):
    ctr = tt-1 if x[i]=='1' else tt+1
    x[i] = inv(i)
    no = getMod(''.join(x),n,ctr)
    ct = 1
    while no:
        k = bin(no).count('1')
        no %= k
        ct += 1
    print(ct)
    x[i] = inv(i)

Submission status: Wrong Answer

Solution code:
import collections
n = int(raw_input())
x = int(raw_input(),2)
mem = {0:0}

memo = {}
def k(x, mod):
	if x in memo:
		return memo[x]
	ximod = 1 % mod
	for i in range(x+1):
		if i: ximod *= 2
		ximod %= mod
		memo[x] = ximod
	memo[x] = ximod
	return ximod

def g(x, mod):
	ximod = 1 % mod
	r = 0
	for i in range(n):
		
		if i: ximod *= 2
		ximod %= mod
		if x & (1 << i):
			r += ximod
			r %= mod
	return r
def f(x):
	if x in mem:
		return mem[x]
	cc=  collections.Counter(bin(x))
	compute = g(x,cc['1'])
	if compute == 0: 
		mem[x] = 1
		return 1
	mem[x] = 1 + f(compute)
	return 1 + f(compute)


for i in range(n - 1, -1, -1):
	if i == n - 1:
		t = f(x ^ (1 << i))
		c = collections.Counter(bin(x))['1'] - 1
		print t
	else:
		#k(i, c) == 0
		if  c and k(i, c) == 0:
			print t
		else:
			print f(x ^ (1 << i))

Submission status: Wrong Answer

Solution code:
"""
    こんにちは。これはクシャルです
    
    Author : thekushalghosh (クシャル)
    Team   : CodeDiggers
 
    I prefer Python language over the C++ language :p :D
        
    Visit my website : thekushalghosh.github.io
"""
import sys,math,cmath,time
start_time = time.time()
##########################################################################
################# ---- THE ACTUAL CODE STARTS BELOW ---- #################
    
def solve():
    n = inp()
    s = insr()
    a = [0] * (n + 1)
    for i in range(1,n + 1):
        q = bin(i).replace("0b","")
        a[i] = a[i % q.count("1")] + 1
    w = s.count("1")
    qq = int(s,2)
    for i in range(n):
        qw = 0
        if s[i] == "0":
            qw = qw + (2 ** (n - i - 1))
            w = w + 1
        else:
            qw = qw - (2 ** (n - i - 1))
            w = w - 1
        if w == 0:
            print(0)
        else:
            print(a[(qq + qw) % w] + 1)
    
################## ---- THE ACTUAL CODE ENDS ABOVE ---- ##################
##########################################################################
 
def main():
    global tt
    if not ONLINE_JUDGE:
        sys.stdin = open("input.txt","r")
        sys.stdout = open("output.txt","w")
    t = 1
    for tt in range(t):
        solve()
    if not ONLINE_JUDGE:
        print("Time Elapsed :",time.time() - start_time,"seconds")
        sys.stdout.close()
    
#---------------------- USER DEFINED INPUT FUNCTIONS ----------------------#
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    return(input().strip())
def invr():
    return(map(int,input().split()))
 
#------------------ USER DEFINED PROGRAMMING FUNCTIONS ------------------#
def counter(a):
    q = [0] * max(a)
    for i in range(len(a)):
        q[a[i] - 1] = q[a[i] - 1] + 1
    return(q)
def counter_elements(a):
    q = dict()
    for i in range(len(a)):
        if a[i] not in q:
            q[a[i]] = 0
        q[a[i]] = q[a[i]] + 1
    return(q)
 
def string_counter(a):
    q = [0] * 26
    for i in range(len(a)):
        q[ord(a[i]) - 97] = q[ord(a[i]) - 97],1
    return(q)
 
def factors(n):
    q = []
    for i in range(1,int(n ** 0.5) + 1):
        if n % i == 0: q.append(i); q.append(n // i)
    return(list(sorted(list(set(q)))))
 
def prime_factors(n):
    q = []
    while n % 2 == 0: q.append(2); n = n // 2
    for i in range(3,int(n ** 0.5) + 1,2):
        while n % i == 0: q.append(i); n = n // i
    if n > 2: q.append(n)
    return(list(sorted(q)))
 
def transpose(a):
    n,m = len(a),len(a[0])
    b = [[0] * n for i in range(m)]
    for i in range(m): 
        for j in range(n): 
            b[i][j] = a[j][i]
    return(b)
#-----------------------------------------------------------------------#
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
    input = sys.stdin.readline
main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    x = input()
    
    val = 0
    rui = 1
    mod = 0
    
    nagasa = 2*10**5+1
    #nagasa = 5
    d_li = [0]*(nagasa)
    
    for i in range(1,nagasa):
        t_v = i
        t_m = bin(t_v).count("1")
        ans = 0
        while t_v != 0:
            if d_li[t_v] != 0:
                ans += d_li[t_v]
                break
            ans += 1
            t_v %= t_m
            #t_m = bin(t_v).count("1")
        d_li[i] = ans
    
    #print(d_li)
    #exit()
    """
    for i in range(n):
        val += int(x[n-1-i])*rui
        rui *= 2
    """
    val = int(x, 2)
    #print(val)
    #exit()
    
    mod = bin(val).count("1")
    
    rui = pow(2,(n-1))
    exit()
        
    for i in range(n):
        t_v = val
        t_m = mod
        if int(x[i]) == 1:
            t_v -= rui
            t_m -= 1
        else:
            t_v += rui
            t_m += 1
        rui //= 2
        ans = 0
        #while t_v != 0:
        if t_v != 0:
            t_v %= t_m
            ans += 1
        
        ans += d_li[t_v]
        #t_m = bin(t_v).count("1")
        #ans_li.append(ans)
        print(ans)
        #print(ans_li)
        
if __name__ == '__main__':
    main()
"""
#print(ans_li)
for i in range(n):
    print(ans_li[n-1-i])
"""

Submission status: Wrong Answer

Solution code:
n= int(input())

ans_count = [-1 for _ in range(n)]

for i in range(1,n+1):
    b = bin(i)
    b=list(b)
    a = b.count("1")
    f = i%a
    if f == 0:
        ans_count[i-1]=1
    else:
        ans_count[i-1] = ans_count[f-1]+1

ans_count = [0]+ ans_count


inp = input()
x = list(inp)

org = int(inp, 2)
if "1" in x:      
    l = x.count("1")
else:
    l = 0





for i in range(n):
    a = x[i]
    print(0)
#     if a=="0":
#         N = org+(2**(n-i-1))
#         m= N%(l+1)
#         print(ans_count[m]+1)
#     else:
#         if l ==1:
#             print(0)
#         else:
#             N = org-(2**(n-i-1))
#             m=N%(l-1)
#             print(ans_count[m]+1)

Submission status: Wrong Answer

Solution code:
import collections
n = int(raw_input())
x = int(raw_input(),2)
mem = {0:0}


def k(x, mod):
	ximod = 1 % mod
	for i in range(x+1):
		if i: ximod *= 2
		ximod %= mod
	return ximod

def g(x, mod):
	ximod = 1 % mod
	r = 0
	for i in range(n):
		
		if i: ximod *= 2
		ximod %= mod
		if x & (1 << i):
			r += ximod
			r %= mod
	return r
def f(x):
	if x in mem:
		return mem[x]
	cc=  collections.Counter(bin(x))
	compute = g(x,cc['1'])
	if compute == 0: 
		mem[x] = 1
		return 1
	mem[x] = 1 + f(compute)
	return 1 + f(compute)


for i in range(n - 1, -1, -1):
	if i == n - 1:
		t = f(x ^ (1 << i))
		c = collections.Counter(bin(x))['1'] - 1
		print t
	else:
		#k(i, c) == 0
		if  c and k(i, c) == 0:
			print t
		else:
			print f(x ^ (1 << i))

Submission status: Wrong Answer

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

def mp(): return map(int, input().split())
def lmp(): return list(map(int, input().split()))

n = int(input())
x = list(input())
xc = x.count("1")
xu = []
xd = []
if xc == 0:
    for i in range(n):
        print(1)
        exit()
t = 1
for i in range(n):
    mod = xc+1
    xu.append(t%mod)
    t *= 2
t = 1
for i in range(n):
    mod = xc-1
    if mod == 0:
        xd.append(0)
    else:
        xd.append(t%mod)
        t *= 2
xu.reverse()
xd.reverse()
s_xu = 0
s_xd = 0
for i in range(n):
    if x[i] == "1":
        s_xu += xu[i]
        s_xd += xd[i]

# print(xu)
# print(xd)

for i in range(n):
    cnt = 1
    if x[i] == "0":
        tar = (s_xu+xu[i])%(xc+1)
        #print(tar)
        while tar != 0:
            b_tar = list(bin(tar)[2:])
            tar %= b_tar.count("1")
            cnt += 1
        print(cnt)
    else:
        if s_xd-xd[i] == 0:
            print(1)
        else:
            tar = (s_xd-xd[i])%(xc-1)
            #print(tar)
            while tar != 0:
                b_tar = list(bin(tar)[2:])
                tar %= b_tar.count("1")
                cnt += 1
            print(cnt)

Submission status: Wrong Answer

Solution code:
N=int(input())
X=input()
X10=int(X,2)
one=X.count('1')
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
if one==1:
  for i in range(N):
    e=X10%2
    if X[i]=='0':
      Y=e+pow(2,N-i-1,2)
      print(f(Y)+1)
     
    elif X[i]=='1':
      print(0)

if one>1:
  a=X10%(one-1)
  b=X10%(one+1)
  c=one-1
  d=one+1
  for i in range(N):
    if X[i]=='1':
      Y=(a-pow(2,N-i-1,c))%c
      print(f(Y)+1)
    if X[i]=='0':
      Y=(b+pow(2,N-i-1,d))%d
      print(f(Y)+1)

Submission status: Wrong Answer

Solution code:
N = int(input())
import sys
from functools import lru_cache

sys.setrecursionlimit(2000)

X = input()
Y = int(X,2)
@lru_cache(maxsize=None)
def f(x):
    counter = 0
    a = x
    while a>0:
        a = x % bin(a).count("1")
        counter += 1
    return counter 


for i in range(N):
    k = Y>>(N-i) & 1
    
    if k == 0:
        Z = Y + pow(2,N-i-1)
    else:
        Z = Y - pow(2,N-i-1)
    
    print(f(Z))

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 = -1
    dp.append(amari)

memo = [-1]*(2*10**5+10)
memo[0] = 0
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:
d = {}


def calc(num,c):
    
    s = int(num,2)
    if s in d:
        return (d[s])
    
    ar = list(map(int,num))
    ss = sum(ar)
    

    if s % ss != 0: 
        return calc(format(s%ss,'b'),c+1)
    else:

        return c+1

n = int(input())
x = input()
l = [0] * n
lc =[0] * n
c = sum(list(map(int,x)))

for i in range(n):
    if x[i] == '0':
        l[i] = x[0:i] + '1' + x[i+1:len(x)]
        lc[i] = c + 1
    else:
        l[i] = x[0:i] + '0' + x[i+1:len(x)]
        lc[i] = c-1

for i in range(n):
    if int(l[i],2) == 0:
        print(0)
    else:
        aaa = int(l[i],2) % lc[i]
        if aaa != 0:
            ooo = calc(            str(format(aaa,'b')),1                        )
            d[aaa] = ooo
            print(ooo)
        else:
            print(1)

Submission status: Wrong Answer

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

popcount = [0] * (N + 1)
co = [0] * (N + 1)
for i in range(1,N+1):
    a = bin(i)[2:]
    cnt = a.count('1')
    popcount[i] = i % cnt
    nex = popcount[i]
    if nex != 0:
        co[i] = nex + 1
    else:
        co[i] = 1
    
for i in range(N):
    x = X
    if x[i] == '0':
        x = x[:i] + '1' + x[i+1:]
    else:
        x = x[:i] + '0' + x[i+1:]
    num = x.count('1')
    if num == 0:
        print(0)
        break
    pop = int(x,2) % num
    ans = co[pop] + 1
    print(ans)

Submission status: Wrong Answer

Solution code:
"""
    こんにちは。これはクシャルです
    
    Author : thekushalghosh (クシャル)
    Team   : CodeDiggers
 
    I prefer Python language over the C++ language :p :D
        
    Visit my website : thekushalghosh.github.io
"""
import sys,math,cmath,time
start_time = time.time()
##########################################################################
################# ---- THE ACTUAL CODE STARTS BELOW ---- #################
    
def solve():
    n = inp()
    s = insr()
    a = [0] * (n + 1)
    for i in range(1,n + 1):
        q = bin(i).replace("0b","")
        a[i] = a[i % q.count("1")] + 1
    w = s.count("1")
    qw = 0
    for i in range(n):
        if s[i] == "0":
            qw = qw + (2 ** (n - i - 1))
            w = w + 1
        else:
            qw = qw - (2 ** (n - i - 1))
            w = w - 1
        if w == 0:
            print(0)
        else:
            print(a[(int(s,2) + qw) % w] + 1)
    
################## ---- THE ACTUAL CODE ENDS ABOVE ---- ##################
##########################################################################
 
def main():
    global tt
    if not ONLINE_JUDGE:
        sys.stdin = open("input.txt","r")
        sys.stdout = open("output.txt","w")
    t = 1
    for tt in range(t):
        solve()
    if not ONLINE_JUDGE:
        print("Time Elapsed :",time.time() - start_time,"seconds")
        sys.stdout.close()
    
#---------------------- USER DEFINED INPUT FUNCTIONS ----------------------#
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    return(input().strip())
def invr():
    return(map(int,input().split()))
 
#------------------ USER DEFINED PROGRAMMING FUNCTIONS ------------------#
def counter(a):
    q = [0] * max(a)
    for i in range(len(a)):
        q[a[i] - 1] = q[a[i] - 1] + 1
    return(q)

def counter_elements(a):
    q = dict()
    for i in range(len(a)):
        if a[i] not in q:
            q[a[i]] = 0
        q[a[i]] = q[a[i]] + 1
    return(q)

def string_counter(a):
    q = [0] * 26
    for i in range(len(a)):
        q[ord(a[i]) - 97] = q[ord(a[i]) - 97],1
    return(q)
 
def factors(n):
    q = []
    for i in range(1,int(n ** 0.5) + 1):
        if n % i == 0: q.append(i); q.append(n // i)
    return(list(sorted(list(set(q)))))
 
def prime_factors(n):
    q = []
    while n % 2 == 0: q.append(2); n = n // 2
    for i in range(3,int(n ** 0.5) + 1,2):
        while n % i == 0: q.append(i); n = n // i
    if n > 2: q.append(n)
    return(list(sorted(q)))

def transpose(a):
    n,m = len(a),len(a[0])
    b = [[0] * n for i in range(m)]
    for i in range(m): 
        for j in range(n): 
            b[i][j] = a[j][i]
    return(b)
#-----------------------------------------------------------------------#
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
    input = sys.stdin.readline
main()

Submission status: Wrong Answer

Solution code:
N = int(input())
X = input()
times = {}
times[0] = 0

for i in range(1,200000):
  bi = format(i, 'b')
  arr = list(map(int, bi))
  sbi = sum(arr)
  if i%sbi == 0:
    times[i] = 1
  else:
    times[i] = 1+times[i%sbi]
    
arr = list(map(int, X))
sbX = sum(arr)
X10 = int(X,2)
mo = [1,-1]
if sbX-1 == 0:
  mo2 = [X10%(sbX+1),0]
else:
  mo2 = [X10%(sbX+1),X10%(sbX-1)]

for i in range(N):
  waru = sbX+mo[int(X[i])]
  if waru == 0:
    print(0)
  else:
    print(times[(pow(2,(N-i-1),waru)+mo2[int(X[i])])%waru]+1)

Submission status: Wrong Answer

Solution code:
import sys
import  math
from heapq import *
import fractions
import bisect
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

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

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

mlist_num_1up=[0]*N
mlist_num_1down=[0]*N
mlist_num_1up[0]=1
mlist_num_1down[0]=1


if(1<num_1):
    for i in range(1,N):
        mlist_num_1up[i]=(mlist_num_1up[i-1]*2)%(num_1+1)
        mlist_num_1down[i]=(mlist_num_1down[i-1]*2)%(num_1-1)
else:
    for i in range(1,N):
        mlist_num_1up[i]=(mlist_num_1up[i-1]*2)%(num_1+1)

    upmod_ori=0
    for i in range(N):
        if(X[i]=='1'):
            upmod_ori+=mlist_num_1up[i]
    mlist_num_1up.reverse()
    for i in range(N):
        if(X[i]=='1'):
            a=0
            print(a)
        else:
            mod=upmod_ori+mlist_num_1up[i]
            mod%=(num_1+1)
            print(1 if mod==0 else 2)
    sys.exit(0)



mlist_num_1up.reverse()
mlist_num_1down.reverse()

upmod_ori=0
downmod_ori=0
for i in range(N):
    if(X[i]=='1'):
        upmod_ori+=mlist_num_1up[i]
        downmod_ori+=mlist_num_1down[i]


fans=[0]*31
fans[0]=0
fans[1]=1
for i in range(2,31):
    mod=0
    for p in range(7):
        if((i>>p) & 1):
            mod+=1
    fans[i]=fans[i%mod]+1
    
for i in range(N):
    if(X[i]=='1'):
        mod=downmod_ori-mlist_num_1down[i]
        mod%=(num_1-1)
    else:
        mod=upmod_ori+mlist_num_1up[i]
        mod%=(num_1+1)
    mod1=0
    for p in range(31):
        if((mod>>p) & 1):
            mod1+=1
    print(fans[mod1]+1)

Submission status: Wrong Answer

Solution code:
N=int(input())
X=input()
xx=int(X)
xxx=str(xx)
sa=N-len(xxx)
X_len=len(X)
a=0
for i in range(sa,N):
    a=int(X[i])*(2**(N-i-1))+a

print(a)



fx=[-1]*(2*(10**5))
for i in range(X_len):
    ans=0
    if(X[i]=='0'):
        b=a+2**(X_len-i-1)
    else:
        b=a-2**(X_len-i-1)

    while(b!=0):

        fx=b%str(format(b,'b')).count('1')
        ans=ans+1
        b=fx

    print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
x = list(input())
y = int(''.join(x), 2)

memo = [0]


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


for i in range(1, n):
    tmp = i % popcount(i)
    memo.append(memo[tmp] + 1)

print(0)

Submission status: Wrong Answer

Solution code:
from collections import deque

n = int(input())
x = eval('0b' + input())

memo = {0: 0}

def solve(X):
    x = X
    stack = deque([])
    while x:
        if x in memo:
            break
        stack.append(x)
        x = x % bin(x).count("1")
    cnt = memo[x] + 1
    while stack:
        x = stack.pop()
        memo[x] = cnt
        cnt += 1
    return cnt - 1



ans = []

for i in range(1):
    y = 0
    if x & (1 << i):
        y = x & ~(1 << i)
    else:
        y= x | (1 << i)
    ans.append(solve(y))

for ansi in reversed(ans):
    print(ansi)

Submission status: Wrong Answer

Solution code:
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))

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()
s = ''
ans = [0 for _ in range(2**n + 1)]
pop = 0
for i in x:
    if i == '1': pop += 1

for i in range(n):
    if x[i] == '0':
        s = x[:i] + '1' + x[i+1:]
        pc = pop + 1
    else:
        s = x[:i] + '0' + x[i+1:]
        pc = pop - 1
    num = int(s, 2)
    cnt = 0
    road = []
    while True:
        if num == 0:
            print(i+1, ans[int(s, 2)])
            #print(ans)
            break
        if ans[num] > 0:
            for r in road: ans[r] += ans[num]
            print(i+1, ans[int(s, 2)])
            #print(ans)
            break
        road += [num]
        num = (num%pc)
        cnt += 1
        pc = popcount(num)
        for r in road: ans[r] += 1

Submission status: Wrong Answer

Solution code:
def popcount(u):
    t = bin(u)
    h = t.count("1")
    return u % h 
    
pri = [-1 for i in range(2*(10**5) + 1)]
pri[0] = 0
for i in range(1,2*(10**5)+1):
    if pri[i] == -1:
        now =  popcount(i)
        pri[i] = pri[now] + 1
    
n = int(input())
x = list(input())
c = x.count("1") + 1
d = c - 2

if d == -1:
    for i in range(n):
        print(1)
    exit()
elif d == 0:
    p = x.index("1")
    if p == n-1:
        for i in range(n-1):
            print(2)
        print(0)
        exit()
    if p != n-1:
        for i in range(n):
            if i != p:
                print(1)
            elif i == p:
                print(0)
        exit()
    
    

amaric = [1 % c]
amarid = [1 % d]
for i in range(n-1):
    amaric.append((amaric[-1]*2)%c)
    amarid.append((amarid[-1]*2)%d)

motoc = 0
motod = 0
for i in range(n):
    if x[i] == "1":
        motoc += amaric[n-1-i]
        motod += amarid[n-1-i]
for i in range(n):
    if x[i] == "0":
        op = motoc
        op += amaric[n-1-i]
        op %= c
    elif x[i] == "1":
        op = motod
        op -= amarid[n-1-i]
        op %= d
    print(pri[op]+1)

Submission status: Wrong Answer

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

def f(n):
    res = 0
    for i in range(n):
        if n == 0:
            return res
        else:
            res += 1
            n = n % bc(n)
    return res

N,X = open(0).read().split()
N = int(N)
pc = X.count('1')
na = 0
nb = 0
if N == 1:
    if X == '1':
        print(1)
    else:
        print(0)
else:
    if pc == 0:
        for i in range(N):
            print(1)
    elif pc == N:
        for i in range(1,N+1):
            na = (na+pow(2,N-i,N-1)) % (N-1)
        for i in range(1,N+1):
            temp = na
            temp = (temp-pow(2,N-i,N-1)) % (N-1)
            print(f(temp)+1)
    elif pc == 1:
        ind = X.index('1')
        na = pow(2,N-ind-1,2)
        for i in range(1,N+1):
            if i != ind + 1:
                temp = na
                temp = (temp+pow(2,N-i,2)) % 2
                print(f(temp)+1)
            else:
                print(0)
    else:
        for i in range(1,N+1):
            if X[i-1] == '1':
                na = (na+pow(2,N-i,pc-1)) % (pc-1)
        for i in range(1,N+1):
            if X[i-1] == '1':
                nb = (nb+pow(2,N-i,pc+1)) % (pc+1)
        for i in range(1,N+1):
            if X[i-1] == '1':
                temp = na
                temp = (temp-pow(2,N-i,pc-1)) % (pc-1)
                print(f(temp)+1)
            else:
                temp = nb
                temp = (temp+pow(2,N-i,pc+1)) % (pc+1)
                print(f(temp)+1)

Submission status: Wrong Answer

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

def popcount(i):
    return bin(i).count('1')

N = INT()
S = list(map(int, input()))[::-1]

pcnt1 = S.count(1) - 1
pcnt2 = S.count(1) + 1
base1 = base2 = 0
for i in range(N):
    if S[i]:
        if pcnt1 != 0:
            base1 += pow(2, i, pcnt1)
        base2 += pow(2, i, pcnt2)

ans = [0] * N
for i in range(N):
    cur = 0
    if S[i]:
        if pcnt1 != 0:
            cur += (base1 - pow(2, i, pcnt1)) % pcnt1
    else:
        cur += (base2 + pow(2, i, pcnt2)) % pcnt2
    cnt = 1
    while cur:
        cur %= popcount(cur)
        cnt += 1
    ans[i] = cnt
for a in ans[::-1]:
    print(a)

Submission status: Wrong Answer

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

memo = [0]*n
memo2 = [-1]*(2*10**5+10)
ans = [-1]*n
popcnt = 0

for i in range(n):
    if x[i] == "1":
        popcnt += 1

amariStaticA = 0
amariStaticB = 0
for i in range(n):
    if x[i] == "1":
        amariStaticA += pow(2, n-i-1, max(1, popcnt-1))
        amariStaticB += pow(2, n-i-1, popcnt+1)
amariStaticA %= max(1, popcnt-1)
amariStaticB %= popcnt+1

for i in range(n):
    amari = 0
    if x[i] == "0":
        amari = amariStaticB + pow(2, n-i-1, popcnt+1)
        amari %= popcnt+1
    else:
        amari = amariStaticA - pow(2, n-i-1, max(1, popcnt-1))
        amari %= max(1, popcnt-1)
    if amari == 0:
        ans[i] = 1
    else:
        memo[i] = amari

for i in range(len(memo)):
    cnt = 1
    firstMemo = copy.deepcopy(memo[i])
    while memo[i] != 0:
        popcnt = bin(memo[i]).count("1")
        memo[i] %= max(1, popcnt)
        cnt += 1
        if memo[i] == 0:
            ans[i] = cnt
            memo2[firstMemo] = cnt
            break


for anss in ans:
    print(anss)

Submission status: Wrong Answer

Solution code:
n=int(input())
s=input()
cc=s.count("1")
flg=[False for i in range(n)]
for i in range(n):
    if s[i]=="1":
        flg[i]=True
xx=int(s,2)
for i in range(n):
    ans=0
    tt="0"*max(0,i-1)+"1"+"0"*(n-i-1)
    x=xx^int(tt,2)
    if flg[i]==True:
        c=cc-1
    if flg[i]==False:
        c=cc+1
    while x>0:
        x%=c
        ans+=1
        if x==0:
            print(ans)
            break
        two=bin(x)
        c=two.count("1")

Submission status: Wrong Answer

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

maxbit = x.count("1")

box = [0] * (maxbit + 1)

def f(i):
  cnt = 0
  while i > 0:
    if box[i] != 0:
      return box[i] + cnt
    i %= bin(i).count("1")
    cnt += 1
  return cnt

# for i in range(1, maxbit + 1):
#   box[i] = f(i)

for i in range(lenx):
  if x[i] == "0":
    mb = maxbit + 1
    t = x10 + 2 ** (lenx - 1 - i)
  else:
    mb = maxbit - 1
    t = x10 - 2 ** (lenx - 1 - i)
  # print(t, mb)
  if t == 0:
    print(0)
  else:
    t %= mb 
    if t == 0:
      print(1)
    else:
      ans = f(t) + 1 
      box[t] = ans
      print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = input()
XX = list(i for i in X)
c = dict()
for i in range(N):
    xxx = XX[:]
    xxx[i] = '0' if xxx[i] == '1' else '1'
    j = int(''.join(xxx), 2)
    if j in c:
        print(c[j])
        continue
    jj = j
    cnt = 0
    while jj > 0:
        cnt += 1
        jj = jj % bin(jj).count('1')
        if jj in c:
            cnt = c[jj]
            break
    print(cnt)
    c[j] = cnt

Submission status: Wrong Answer

Solution code:
def popcount(x):
  count = 0
  bin_x = bin(x)[2:]
  #print(bin_x)
  for i in bin_x:
    if i == "1":
      count += 1
  return count

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

data = []
for d in X:
  data.append(d)

for i in range(N):
  temp = data
  ans = 0
  #i番目のビット反転
  if temp[i] == "1":
    temp[i] = "0"
  else:
    temp[i] = "1"
  
  #10進数に変換(str -> int)
  bin_n = str("".join(map(str, temp)))
  int_n = int(bin_n,2)
  #print("int_n = " + str(int_n))

  while int_n > 0:
    ans += 1
    j = popcount(int_n)
    int_n = int_n % j

  print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

n = int(input())

x = input()

c = x.count('1')

L = {}


for i in range(n):
    #print(int(str(x[:i]+str((int(x[i])+1)%2)+x[i+1:]),2))
    a = int(str(x[:i]+str((int(x[i])+1)%2)+x[i+1:]),2)
    b = 0
    if x[i] == '1':
        b = c-1
    else:
        b = c+1
    cnt = 0
    h = a
    for i in range(100):
        #print(a,h,b)
        if i == 1:
            t = h
        
        if h==0:
            
            print(i)
            if i > 0:
                L[t] = i-1
            break
        h = h%b
#        print('!!!!!!!!!!!!!!!!!',h)
        if h in L:
            #print('!!!!!!')
            cnt += L[h]
            print(cnt)
            break
        b = bin(h).count('1')
            
#print(L)

Submission status: Wrong Answer

Solution code:
import collections
n = int(raw_input())
x = int(raw_input(),2)
mem = {0:0}

def g(x, mod):
	ximod = 1 % mod
	r = 0
	for i in range(n):
		
		if i: ximod *= 2
		ximod %= mod
		if x & (1 << i):
			r += ximod
			r %= mod
	return r
def f(x):
	if x in mem:
		return mem[x]
	cc=  collections.Counter(bin(x))
	compute = g(x,cc['1'])
	if compute == 0: 
		mem[x] = 1
		return 1
	mem[x] = 1 + f(compute)
	return 1 + f(compute)

for i in range(n - 1, -1, -1):
	if i == n - 1:
		t = f(x ^ (1 << i))
		c = collections.Counter(bin(x))['1'] - 1
		print t
	else:
		if  c and (1 << i) % c == 0:
			print t
		else:
			print f(x ^ (1 << i))