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: Time Limit Exceeded

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

input = sys.stdin.readline

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

inf = float('inf')
mod = 1000000007

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

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

	XX_lin = []
	for i in X_lin:
		if i == "0":
			XX_lin.append("1")
		else:
			XX_lin.append("0")

	ans = []
	mem = {}
	for i in range(N):
		tmpX = copy.deepcopy(X_lin)
		tmpX[i] = XX_lin[i]

		oct = int("".join(tmpX), 2)

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

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

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

		ans.append(ans_tmp)

	for i in ans:
		print(i)

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

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

Submission status: Time Limit Exceeded

Solution code:
def sol():
    n=int(input())
    x=input()
    chk=0
    for i,j in enumerate(x[::-1]):
        if j=="1":
            chk+=2**i
    c={}
    d={}
    ans=[]
    for i,j in enumerate(x[::-1]):
        if j=="1":
            t=chk-2**i
        else:
            t=chk+2**i
        s=t
        cnt=0
        while t:
            if t not in c:
                pc=bin(t).count("1")
                c[t]=pc
            else:
                pc=c[t]
            t%=pc
            cnt+=1
            if t in d:
                cnt+=d[t]
                break
        if s not in d:
            d[s]=cnt
        ans.append(cnt)
    for i in ans[::-1]:
        print(i)

if __name__=="__main__":
    sol()

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys
import math
from collections import deque
from heapq import heappush, heappop

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


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


def isRaw():
    return list(map(int, ssRaw()))


INF = 1 << 29

DIV = (10**9) + 7
#DIV = 998244353

def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        finv[i] = finv[i-1]*inv[i] % mod

    class CONV:
        def __init__(self):
            self.fac = fac
            self.finv = finv
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % DIV) % DIV

    return CONV()


def cumsum(As):
    s = 0
    for a in As:
        s += a
        yield s


sys.setrecursionlimit(200005)


def dijkstra(G,start=0):
    heap = []
    cost = [INF]*len(G)
    heappush(heap,(0,start))
    while len(heap)!=0:
        c,n = heappop(heap)
        if cost[n] !=INF:
            continue
        cost[n]=c
        for e in G[n]:
            ec,v = e
            if cost[v]!=INF:
                continue
            heappush(heap,(ec+c,v))
    return cost


def main():
    cache={}
    def f(s,cur=0):
        if s in cache:
            return cache[s]
        ins = int(s,2)
        if ins==0:
            return cur
        pc = sum([c=='1' for c in s])
        next_s = bin(ins % pc)[2:]
        ret = cur
        if next_s in cache:
            ret = cache[next_s]+cur
        else:
            ret = f(next_s,cur+1)
        cache[s]=ret
        return ret
    N=iRaw()
    Xs=sRaw()
    for n in range(N):
        xl = [x for x in Xs]
        xl[n]="1" if xl[n]=="0" else "0"
        print(f("".join(xl)))

main()

Submission status: Time Limit Exceeded

Solution code:
LIM=200002
L=[0]*LIM

def bin_sum(Y):
    S=bin(Y)[2:]
    count=0
    for i in range(len(S)):
        count+=int(S[i])
    return count

def bin_sum2(Y):
    count=0
    for i in range(len(Y)):
        count+=int(Y[i])
    return count

for i in range(1,LIM):
    L[i]+=bin_sum(i)

def pop_num(N,b,L):
    if N==0:
        return 0
    count=1
    N=N%b
    while N!=0:
        b=L[N]
        N=N%b
        count+=1
    return count
X=int(input())
Y=input()
d=bin_sum2(Y)+1
c=bin_sum2(Y)-1
for i in range(X):
    Y_i=Y[:i]+str(abs(int(Y[i])-1))+Y[i+1:]
    if Y_i[i]=="1":
        b=d
    else:
        b=c
    print(pop_num(int(Y_i,2),b,L))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

from functools import lru_cache

def popcount1(n):
    ans = 0
    while n > 0:
        ans += n & 1
        n //= 2
    return ans

bit = {}
@lru_cache(maxsize=None)
def popcount2(bits):
    if bits in bit:
        return bit[bits]

    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555)
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333)
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f)
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff)
    ans = (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff)
    bit[bits] = ans
    return bit[bits]


memo = {0: 0}
@lru_cache(maxsize=None)
def rec(n):
    if n in memo:
        return memo[n]
    
    p = popcount2(n)
    new_n = n % p
    ans = rec(new_n) + 1
    memo[n] = ans
    return memo[n]


def submit():
    n = int(input())
    xs = list(input())
    x = int('0b' + "".join(xs), 0)

    # 前準備
    for i in range(1, 200001):
        rec(i)

    ans = []
    base_bit = popcount1(x)
    bit[x] = base_bit
    mask = 1 << (n - 1)
    for i in range(1, n + 1):
        if xs[i - 1] == "0":
            xi = x + mask
            bit[xi] = bit[x] + 1
            xs[i - 1] = "0"
        else:
            xs[i - 1] = "0"
            xi = x - mask
            bit[xi] = bit[x] - 1
            xs[i - 1] = "1"
        ans.append(rec(xi))
        mask >>= 1

    for a in ans:
        print(a)


if __name__ == "__main__":
    submit()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
Xinput=list(input())
Xs=[0]*N
for i in range(N):
  Xs[i]=Xinput

for i in range(N):
  if Xinput[i]=="0":
    Xs[i] = Xinput[:i]+["1"] + Xinput[i+1:]
  else:
    Xs[i]=Xinput[:i]+["0"] + Xinput[i+1:]

for i in range(N):
  Xs[i] = "".join(Xs[i])

def procount(n10):
  nbin=list(str(bin(n10)))[2:]
  return nbin.count("1")

def f(nbin):
  n10=int(nbin,2)
  cnt=0
  while n10>0:
    n10=n10%procount(n10)
    cnt+=1
  return cnt

for i in range(N):
  print(f(Xs[i]))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
X=input()
X_new=int(X, 2)
def toggle_nth_bit(num: int, n: int):
    return num ^ (1 << n)
def popcnt1(n):
    return bin(n).count("1")
def func(x):
    if x==0:
        return 0
    else:
        return func(x%popcnt1(x))+1
for i in range(0,N):
    print(func(toggle_nth_bit(X_new,N-i-1)))

Submission status: Time Limit Exceeded

Solution code:
def toggle_nth_bit(num: int, n: int):
    return num ^ (1 << n)
N = int(input())
X = input()
X_10 = int(X,2)
X_list = [0]*N
ans = 0
for i in range(N):
    j = toggle_nth_bit(X_10,N-i-1)
    while j>0:
        j=j%bin(j).count('1')
        ans += 1
    print(ans)
    ans = 0

Submission status: Time Limit Exceeded

Solution code:
def popcount(n):
    count = 0
    while n > 0:
        count += 1
        n = n % bin(n).count("1")
    return count


n = int(input())

a = input()


x = int(a,2)
nlis = range(n)

for i in reversed(nlis):
    check = 2 ** i
    ans = x ^ check
    ans = popcount(ans)
    print(ans)

Submission status: Time Limit Exceeded

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

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


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


def toggle(i):
  if (i == '1'):
    return '0'
  else:
    return '1'


def solve(i, count):
  if (i == 0):
    return count
  else:
    return solve(popcount(i), count + 1)


for i in range(n):
  if(i == 0):
    _x = toggle(x[0]) + x[1: n]
  elif (i == n - 1):
    _x = x[:i] + toggle(x[n - 1])
  else:
    _x = x[:i] + toggle(x[i]) + x[i + 1 :n]
  print(solve(int(_x, 2),0))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from functools import lru_cache

def main():
    N = int(input())
    s = input()
    X = int(s, 2)
    for i in range(N):
        if (s[i] == '0'):
            n = X + 2 ** (N - 1 - i)
        else:
            n = X - 2 ** (N - 1 - i) 

        print(f(n))

@lru_cache(maxsize=100000000)
def f(n):
    if n == 0:
        return 0

    popcount = Counter(bin(n)).get('1', 0)
    n = n % popcount

    return f(n) + 1


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# # ####################################################################
# import io
# import sys

# _INPUT = """\
# 23
# 00110111001011011001110

# 3
# 011

# """
# sys.stdin = io.StringIO(_INPUT)
####################################################################
import sys
def _p(*_a):
  #return
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
####################################################################
def _pa(_aa):
  #return
  for _a in _aa: _p(_a)
####################################################################
N = int(input())
X = input()

from collections import defaultdict
d = defaultdict(int)

def popcount(n):
  if d[n] > 0: return d[n]

  rtn = 0
  while n > 0:
    if n % 2 == 1: rtn += 1
    n = n >> 1

  d[n] = rtn
  return d[n]


for n in range(N)[::-1]:
  i = 1 << n
  x = int(X, 2)
  a = x^i
  # _p(n, i, x, a)

  cnt = 0
  while a>0:
    cnt += 1
    a = a % popcount(a)
    # _p(n, i, x, a)

  print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
for i in range(n):
    if s[i]=='0':
        x=s[:i]+'1'+s[i+1:]
    else:
        x=s[:i]+'0'+s[i+1:]
    num = int(x,base=2)
    d=0
    while num:
        z=num
        temp=num
        c=0
        while z:
            z=z&(z-1)
            c+=1
        d+=1
        num=temp%c
    print(d)

Submission status: Time Limit Exceeded

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


def popcount(v):
    count = 0
    while v > 0:
        if v & 1 == 1:
            count += 1
        v >>= 1
    return count


def f(n):
    if n == 0:
        return 0
    d = popcount(n)
    if (n == d):
        return 1
    else:
        return 1 + f(n % d)


n = int(input())
x = input()
xi = int(x, base=2)

init_popcount = x.count('1')

base = 2 ** (n - 1)
for i in range(n):
    if x[i] == '0':
        v = xi + base
        print(1 + f(v % (init_popcount + 1)))
    else:
        v = xi - base
        if v == 0:
            print(0)
        else:
            print(1 + f(v % (init_popcount - 1)))
    base //= 2

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = int(input())
A = [0] * (n+1)
#A = list(map(int, input().split()))
#l, r, d = map(int, input().split())

def popcnt1(n):
    return bin(n).count("1")

for i in range(1,n+1):
  A[i] = int(str(x), 2) ^ 2**(n-i)
for i in range(1,n+1):
  ans = 0
  while A[i] != 0:
    A[i] = A[i] % popcnt1(A[i])
    ans += 1
  print(ans)

Submission status: Time Limit Exceeded

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()))

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
    while True:
        if num == 0:
            ans[int(s, 2)] = cnt
            print(cnt)
            break
        if ans[num] > 0:
            ans[int(s, 2)] = cnt + ans[num]
            print(cnt + ans[num])
            break
        num = (num%pc)
        cnt += 1
        t = str(bin(num))
        pc = 0
        for j in t:
            if j == '1': pc += 1

Submission status: Time Limit Exceeded

Solution code:
def myf(s):
    res = 0
    while int(s, 0) != 0:
        popcount = s.count('1')
        s = bin(int(s, 0) % popcount)
        res += 1
    return res

n = int(input())
x = '0b' + input()
lst = ['1', '0']
for i in range(n):
  z = x[:i + 2] + lst[int(x[i + 2])] + x[i + 3:]
  print(myf(z))

Submission status: Time Limit Exceeded

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

for i in range(n):
    if i==0:
        y = str((int(x[i])*(-1) + 1)) + x[i+1:]
    elif i<n-1:
        y = x[:i] + str((int(x[i])*(-1) + 1)) + x[i+1:]
    else:
        #i==n-1
        y = x[:i] + str((int(x[i])*(-1) + 1))
    k = y.count("1")
    z = int(y, 2)
    #print("z, k", z, k)
    count = 0
    while z!=0:
        z = z%k
        k = str(bin(z))[2:].count("1")
        count+=1
    print(count)

Submission status: Time Limit Exceeded

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

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
sys.setrecursionlimit(1000000)

N = int(input())
X = input()[:-1][::-1]
origin = 0
for i in range(len(X)):
    origin += int(X[i]) * (2**i)

dic = defaultdict(int)

def calc_(n):
    global dic
    if n == 0:
        return 0
    if dic[n]>0:
        return dic[n]
    else:
        n_next = n % bin(n).count('1')
    temp = calc_(n_next)
    dic[n] = temp+1

    return temp + 1


for i in list(range(N))[::-1]:
    ans = 0
    if origin >> i & 1 == 1:
        val = origin - 2 ** i
    else:
        val = origin + 2 ** i

    print(calc_(val))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from sys import setrecursionlimit
from collections import Counter, deque, defaultdict
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
import random
setrecursionlimit(1000000)

# popcount table
popcount = {}
popcount[0] = 0
def gpc(n):
    if n in popcount:
        return popcount[n]
    else:
        popcount[n] = gpc(n // 2) + (n & 1)
        return popcount[n]

# mem rec
solutions = {}
def sol(Xk):
    if Xk == 0:
        solutions[(Xk, 0)] = 0
        return 0
    else:
        pc = gpc(Xk)
        if (Xk, pc) in solutions:
            return solutions[Xk, pc]
        else:
            count = 1 + sol(Xk % pc)
            solutions[Xk, pc] = count
            return count

def main():
    from builtins import int, map
    N = int(input())
    X = input()
    iX = int(X, 2)

    for k in range(N - 1, -1, -1):
        Xk = iX ^ (1 << k)
        ans = sol(Xk)
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

def turn(bn, n):
  bn_turned = bn
  if bn[n] == "1":
    bn_turned = bn_turned[:n] + "0" + bn_turned[n+1:]
  else:
    bn_turned = bn_turned[:n] + "1" + bn_turned[n+1:]
  return int(bn_turned, 2)

N = int(input())
X = input()
for i in range(N):
  print(f(turn(X, i)))

Submission status: Time Limit Exceeded

Solution code:
def popcount(n, bit, cnt):
    if n == 0:return cnt
    new = bin(n%bit).count("1")
    return popcount(n%bit, new, cnt + 1)
    
n = int(input())
x = input()
cnt = x.count('1')
num = 0
for i in range(n):
    num += int(x[-(i + 1)]) * pow(2, i)

   
for i in range(n):
    res = 0
    if x[i] == "1":
        temp = num - pow(2, n - i - 1)
        print(popcount(temp, cnt - 1, 0))
    else:
        temp = num + pow(2, n - i - 1)
        print(popcount(temp, cnt + 1, 0))

Submission status: Time Limit Exceeded

Solution code:
def calc(num,c):
    s = int(num,2)
    
    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


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

for i in l:
    if int(i,2) == 0:
        print(0)
    else:
        
        print(calc(i,0))

Submission status: Time Limit Exceeded

Solution code:
import copy

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

x = list(map(int, X))

num = int(X, 2)

c = x.count(1)

def popcount(n):
    nb = str(bin(n))
    xpop = list(map(int, nb[2:]))
    cpop = xpop.count(1)

    return n % cpop


for i in range(N):
    ct = copy.deepcopy(c)
    numt = copy.deepcopy(num)
    if x[i] == 0:
        ct += 1
        numt += 2 ** (N - i - 1)
    else:
        ct -= 1
        numt -= 2 ** (N - i - 1)

    res = 0
    while numt > 0:
        numt = popcount(numt)
        res += 1

    print(res)

Submission status: Time Limit Exceeded

Solution code:
def base10toN(num, base):
    converted_string, modstring = "", ""
    currentnum = num
    if not num:
        return '0'
    while currentnum:
        mod = currentnum % base
        currentnum = currentnum // base
        converted_string = chr(48 + mod + 7*(mod > 10)) + converted_string
    return converted_string
n=int(input())
pop=[0]*(2*10**5+1)
for i in range(1,2*10**5+1):
  temp=base10toN(i,2)
  ans=0
  for j in range(len(temp)):
    if temp[j]=='1':
      ans+=1
  r=i%ans
  pop[i]=pop[r]+1
x=input()
ones=0
ans1=[]
for i in range(n):
  if x[i]=='1':
    ones+=1
dividemore=0
divideless=0
for i in range(n):
  if x[i]=='1':
    dividemore=(pow(2,n-1-i,ones+1)+dividemore)%(ones+1)
    if ones>=2:
      divideless=(pow(2,n-1-i,ones-1)+divideless)%(ones-1)
for i in range(n):
  counter=0
  if x[i]=='0':
    temp=(dividemore+pow(2,n-1-i,ones+1))%(ones+1)
  else:
    if ones==1:
      ans1.append('0')
      continue
    else:
      temp=(divideless-pow(2,n-1-i))%(ones-1)
  ans1.append(str(pop[temp]+1))
print(' '.join(ans1))

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    sys.setrecursionlimit(200000)
    N = int(input())
    Y = input()
    X = int(Y,2)
    memo = {}
    Ycnt = Y.count("1")

    def f(n,cnt=None):
        if n == 0:
            return 0
        if n not in memo:
            if cnt:
                d = cnt
            else:
                d = bin(n).count("1")
            nx = n%d
            memo[n] = f(nx)+1
        return memo[n]

    for i in range(N):
        if Y[i] == "1":
            cnt = Ycnt - 1
        else:
            cnt = Ycnt + 1
        a = N-i
        tmp = 2**(a-1)
        n = X^tmp
        print(f(n,cnt))
main()

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
from decimal import *
import itertools


N = int(input())
X = int(input(), 2)

def popcnt(n):
    return bin(n).count("1")

ans = 0
cal = X

# 事前計算
firstCnt = popcnt(X)
#ibitめを反転
for i in range(N-1, -1, -1):
    # ibit目 たってる
    cnt = firstCnt
    target = X
    if (1 << i) & X:
        cnt-=1
    else:
        cnt += 1

    # 反転
    target ^= (1 << i)
    ans = 0
    while target != 0:
        ans+=1
        target = target % cnt
        cnt = popcnt(target)

    #print(ans)
    sys.stdout.write("%d\n" % ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# hello worldと表示する
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
n=I()
lis=list(SI())
orig=0
for i in range(n):
    if lis[i]=="0":
        lis[i]=0
    else:
        lis[i]=1
orcount=sum(lis)
for i in range(n):
    j=n-i-1
    if lis[i]==1:
        orig+=2**j
dp=[0 for i in range(n+1)]
dp[1]=1
for i in range(1,n):
    #u=count1(i+1)
    count=0
    j=0
    while 2**j<=i+1:
        if ((i+1)>>j) %2==1:
            count+=1
        j+=1
    z=1
    dp[i+1]=z+dp[(i+1)%count]
#print(dp)
for i in range(n):
    if lis[i]==0:
        num=orig+2**(n-i-1)
        pr=orcount+1
    else:
        num=orig-2**(n-i-1)
        pr=orcount-1
    if pr==0:
        print(0)
    else:
        print(1+dp[num%pr])

Submission status: Time Limit Exceeded

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

N2 = 2**N

Y = [[] for _ in range(N+1)]
for i in range(1, N+1):
    y = X
    if y[i-1] == '0':
        y = int(y, 2) + 2**(N-i)
    else:
        y = int(y, 2) - 2**(N-i)
    Y[i] = y
    

Dp = [[] for _ in range(N2+1)]
Dp[0] = 0

for y in Y[1:]:
    if Dp[y] != []:
        ans = Dp[y]
#        print('!!')
    else:
        count = 0
        while y != 0:
            y = y%bin(y).count('1')
            count += 1
        ans = count
        Dp[y] = ans
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def popcount(X):
    return X.count("1")
def fn(N,cnt):
    if N==0:
        print(cnt)
    else:
        cnt+=1
        tmp = str(bin(N)[2:])#
        return fn(N%popcount(tmp),cnt)

def changeCha(tmp,i):
    if tmp[i] == "1":
        list1 = list(tmp)
        list1[i] = '0'
        tmp = ''.join(list1)
    else:
        list1 = list(tmp)
        list1[i] = '1'
        tmp = ''.join(list1)
    return tmp

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

for i in range(N):
    tmp = X
    tmp = changeCha(tmp,i)
    #print(tmp)
    fn(int(tmp,2), 0)

Submission status: Time Limit Exceeded

Solution code:
import copy

def popcount(n):
    n = list(bin(n))
    count = 0
    for x in n:
        if x =="1":
            count += 1
    return count

if __name__ == "__main__":
    N = int(input())
    X = list(input())

    for i in range(N):
        Xn = copy.copy(X)
        if Xn[i] == '1':
            Xn[i] = '0'
        else:
            Xn[i] = '1'
        pop = int(''.join(Xn), 2)
        f = 0
        while pop!=0:
            f += 1
            pop = pop % popcount(pop)

        print(f)

Submission status: Time Limit Exceeded

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

x_list = list(x)

for i in range(n):
    temp = x_list.copy()
    temp[i] = "1" if temp[i] == "0" else "0"

    ans = 0
    
    while temp.count("1") != 0:
        a = int("".join(temp), 2)

        a = a % temp.count("1")

        temp = list(bin(a)[2:])

        ans += 1

    print(ans)

Submission status: Time Limit Exceeded

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

B = sum(X)

base_mod_1 = [1 for i in range(N)] # 2^i mod B+1
if B > 1:
  base_mod_2 = [1 for i in range(N)] # 2^i mod B-1

for i in range(1, N):
  base_mod_1[i] = (base_mod_1[i-1] * 2) % (B+1)
  if B > 1:
    base_mod_2[i] = (base_mod_2[i-1] * 2) % (B-1)

def num(A):
  b = 1
  r = 0
  for i in range(len(A)):
    r += b*A[-i-1]
    b *= 2
  return r

def f(n):
  global call
  call += 1
  bit = 0
  m = n
  while m > 0:
    if m % 2 == 1:
      bit += 1
    m //= 2
  next_n = n % bit
  if next_n > 0:
    f(next_n)

x = num(X)
#print(x)

for i in range(N):
  call = 0
  if X[i] == 0:
    y = (x + base_mod_1[-i-1]) % (B+1)
    R = B + 1
    call = 1
  else:
    if B > 1:
      y = (x - base_mod_2[-i-1]) % (B-1)
      R = B - 1
      call = 1
    else:
      y = 0
#  print(y, '+', call)
  if y > 0:
    f(y)
  print(call)

Submission status: Time Limit Exceeded

Solution code:
def get_onenum(A_binary):
    A_list=list(A_binary)
    one_num = 0
    for _ in A_list:
        if _ =='1':
            one_num += 1
    return one_num

def popcount(N):
    A_binary = bin(N)[2:]
    return(get_onenum(A_binary))

def f_(N):
    return N % popcount(N)

def f(N):
    ans=0
    while True:
        if N == 0:
            print(ans)
            break
        N = f_(N)
        ans+=1

N=int(input())
A=input()

A_list=list(A)

for n in range(N):
    A_list_temp=A_list.copy()
    if A_list[n]=='0':
        A_list_temp[n]='1'
    elif A_list[n]=='1':
        A_list_temp[n]='0'
        
    A_=''.join(list(A_list_temp))
    A_10=int(A_, 2)
    f(A_10)

Submission status: Time Limit Exceeded

Solution code:
def popcount(x):
  xbin = list(bin(x))
  p = 0
  for i in range(len(xbin)):
    if xbin[i] == '1':
      p += 1
  
  return p
      
import copy as cp
N = int(input())
X = input()

x = list(X)

for i in range(N):
  x = list(X)
  if x[i] == '0':
    x[i] = '1'
  else:
    x[i] = '0'
  
  xint = 0
  for j in range(N):
    xint += 2**(N-j-1)*int(x[j])

  c = 0
  while xint > 0:
    xint = xint % popcount(xint)
    c += 1
  
  print(c)

Submission status: Time Limit Exceeded

Solution code:
def f(val):
    if val == 0:
        return 0
    re = 0
    tmp = val
    popcount = 0
    while tmp > 0:
        if tmp%2 == 1:
            popcount += 1
        tmp //= 2
    return f(val%popcount) + 1

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

def main():
    n = int(input())
    X = input()
    x = int(X,2)
    Ans = []
    for i in range(n):
        if X[i] == "0":
            tmp = x + pow(2,n - i - 1)
        else:
            tmp = x - pow(2,n - i - 1)
        Ans.append(f(tmp))
    print(*Ans,sep="\n")


    return
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    def popcount(n):
        cnt = 0
        for b in range(20):
            cnt += (n >> b) & 1
        return cnt

    n = int(input())
    X = input()
    one = X.count("1")

    for i in range(n):
        x = list(X)
        cnt = one + 1 if x[i] == "0" else one - 1
        x[i] = "1" if x[i] == "0" else "0"
        x = int("".join(x), 2)
        res = 0
        while x:
            if res != 0:
                cnt = popcount(x)
            x %= cnt
            res += 1
        print(res)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
def popf(s):
    n=0
    u=int(s,2)
    p=s.count('1')
    while u>0:
        u=u%p
        p=bin(u).count('1')
        n+=1
    return n
def lpopf(s):
    ans=[]
    for i in range(len(s)):
        if s[i]=='0':
            ss=s[:i]+'1'+s[i+1:]
        else:
            ss=s[:i]+'0'+s[i+1:]
        ans.append(popf(ss))
    return ans
n=int(input())
x=input()
while len(x)<n:
    x+=input()
for a in lpopf(x):
    print(a)

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy
from collections import deque
import collections
stdin = sys.stdin

mod = 10**9+7

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
x = ns()
dp = {}

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

def f(xx):
    res = 0
    x = int(xx, 2)
    p = int(xx, 2)
    while p>0:
        if p in dp:
            res += dp[p]
            break
        pop = popcount(p)
        p = p%pop
        res += 1
    dp[x] = res
    return res

for i in range(n):
    if x[i]=='0':
        tmp = x[:i] + '1' + x[i+1:]
        print(f(tmp))
    else:
        tmp = x[:i] + '0' + x[i+1:]
        print(f(tmp))

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    import copy
    n = int(input())
    x = int(input(), 2)

    for i in range(n):
        ans = 0
        temp_x = copy.deepcopy(x)
        m = 2**(n - i - 1)
        temp_x ^= m
        while temp_x > 0:
            pc = sum(list(map(lambda i: int(i), format(temp_x, 'b'))))
            temp_x %= pc
            ans += 1

        print(ans)

resolve()

Submission status: Time Limit Exceeded

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

c = X.count('1')
up = True
for i in range(N):
    Xi = list(X)
    if Xi[i] == '1':
        Xi[i] = '0'
        c -= 1
        up = False
    else:
        Xi[i] = '1'
        c += 1
        up = True
    
    ans = 0
    n = int(''.join(Xi), 2)
    while n > 0:
        if ans != 0:
            n = n % bin(n).count('1')
        else:
            n = n % c
        ans += 1
    print(ans)
    
    if up:
        c -= 1
    else:
        c += 1

Submission status: Time Limit Exceeded

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


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

X_int = int(X, 2)

for i in range(N):
    mask = 2**(N-i-1)
    Xi = X_int ^ mask

    n = Xi
    ans = 0
    while n > 0:
        ans += 1
        n %= popcount(n)
    print(ans)