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:
n = int(input())
s = input()
a = 0

def pop_cnt(a):
    res = 0
    while a > 0:
        if (a & 1) == 1:
            res += 1
        a >>= 1
    return res
    
    
for i in range(len(s) - 1, -1, -1):
    if s[i] == '1':
        a += (1 << (len(s) - i - 1))
#print(a)
for i in range(len(s)):
    b = a
    if s[i] == '1':
        b -= (1 << (len(s) - i - 1))
    else:
        b += (1 << (len(s) - i - 1))
    ans = 0 
    while b != 0:
        b = b % pop_cnt(b)
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
s = list(input())
st = s.count('1')
num = 0
for i,x in enumerate(s[::-1]):
    if x == '1': num += pow(2,i)
for i in range(n):
    ntmp = pow(2,n-i-1)
    if s[i] == '0':
        nnow = num + ntmp
        stnow = st + 1
    else:
        nnow = num - ntmp
        stnow = st - 1
    res = 0
    while nnow:
        # print(nnow)
        nnow %= stnow
        stnow = bin(nnow).count('1')
        res += 1
    print(res)

Submission status: Time Limit Exceeded

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

map_dic = {
    '0': '1',
    '1': '0'
}


def popcount(n):
    return bin(n)[2:].count('1')


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


for i in range(N):
    x_str = copy.deepcopy(x)
    x_str = x_str[:i] + map_dic[x_str[i]] + x_str[i+1:]
    x_val = int(x_str, 2)
    print(f(x_val))

Submission status: Time Limit Exceeded

Solution code:
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)[2:].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)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]
def NSTR(n): return [input() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7


def bit_sum(n):
    wa = 0
    while n > 0:
        wa += n & 1
        n >>= 1
    return wa

def bit(n, k):
    return (n >> k) & 1

def main():
    N = INT()
    X = input()
    origX = X
    wa = X.count("1")
    x = 0
    for c in X:
        x <<= 1
        if c == "1":
            x |= 1
    X = x
    # wa+1
    px = X % (wa+1)
    if wa != 1:
        nx = X % (wa-1)
    else:
        nx = None

    for i, c in enumerate(origX):
        count = 0
        x = X ^ (1 << N-i-1)
        if c == "1":
            if x == 0:
                print(0)
                continue
            x = (nx-pow(2, N-i-1, wa-1)) % (wa-1)
            count += 1
            while x != 0:
                count += 1
                x %= bit_sum(x)
            print(count)
        else:
            if x == 0:
                print(0)
                continue
            x = (px+pow(2, N-i-1, wa+1)) % (wa+1)
            count += 1
            while x != 0:
                count += 1
                x %= bit_sum(x)
            print(count)
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

n = int(input())
x = list(input())
for i in range(n):
    tmp = x.copy()
    if tmp[i] == '1':
        tmp[i] = '0'
    else:
        tmp[i] = '1'
    tmp = int(''.join(tmp), 2)
    cnt = 0
    while True:
        if tmp == 0:
            break
        tmp = popcount(tmp)
        cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    x = input()
    base = 0
    b = 1
    for i in range(n):
        base += int(x[-i - 1]) * b
        b *= 2
    for i in range(n):
        d = 1 if x[i] == "0" else -1
        now = base + d * pow(2, n - i - 1)
        cnt = 0
        while now:
            now %= int(bin(now)[2:].count("1"))
            cnt += 1
        print(cnt)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    X = int(input(), 2)
    ans = []
    for i in range(N-1, -1, -1):
        count = 0
        target = 1 << i
        Xi = X ^ target

        # process
        while Xi:
            count += 1
            popcount = bin(Xi).count("1")
            Xi %= popcount

        ans.append(count)
    
    print(*ans, sep="\n")
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

for i in range(len(x)):
  if x[i] == "0":
    x[i] = "1"
  else:
    x[i] = "0"
  n = int("".join(x), 2)
  count = 0
  while n != 0:
    one_num = bin(n)
    n = n % one_num.count("1")
    count += 1
  print(count)
  if x[i] == "0":
    x[i] = "1"
  else:
    x[i] = "0"

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

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)

	ans = []
	for i in range(N):
		tmpX = []
		if X[i] == "1":
			tmpX = X[:i] + "0" + X[i+1:]
		else:
			tmpX = X[:i] + "1" + X[i+1:]

		tmp = 0
		for i,val in enumerate(tmpX):
			if val == "1":
				tmp += 1
		oct = int(tmpX, 2)

		ans_tmp = 0
		while True:
			if oct == 0:
				break
			oct = oct % tmp
			bin_bin = bin(oct)[2:]
			tmp = 0
			for i,val in enumerate(bin_bin):
				if val == "1":
					tmp += 1
			ans_tmp += 1
		ans.append(ans_tmp)

	for i in ans:
		print(i)



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

Submission status: Time Limit Exceeded

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

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)

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

for i in range(N):
  A = X.copy()
  A[i] ^= 1
#  print(A)
  n = num(A)
#  print(n)
  call = 0
  if n > 0:
    f(n)
  print(call)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = int(input(), 2)
for i in range(n):
    k = 1 << (n - 1 - i)
    x = k ^ s
    cnt = 0
    while x > 0:
        pc = bin(x).count("1")
        x %= pc
        cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

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

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

    for i in range(N):
        a = N-i
        tmp = 1
        tmp <<= a-1
        n = X^tmp
        print(f(n))
main()

Submission status: Time Limit Exceeded

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


def popcount(n): 
    count = 0
    while (n): 
        n &= (n-1)  
        count+= 1
    return count

def f(n):
    # print("initial n:",n)
    ans = 0
    while(n!=0):
        t = popcount(n)
        n%=t
        ans+=1
    return ans


for i in range(n-1,-1,-1):
    temp  = x^(1<<i)
    print(f(temp))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = input()
d = {}
def sub(val, pc):
    if pc==0:
        return 0
    tmp = val % pc
    if tmp in d:
        return d[tmp] + 1
    npc = 0
    for i in range(tmp.bit_length()):
        if tmp>>i&1:
            npc += 1
    ans = sub(tmp, npc) + 1
    d[val] = ans
    return ans
pc = sum(item=="1" for item in a)
aval = int(a, 2)
ans = [None]*n
# print(a)
for i in range(n):
    if a[i]=="1":
        val = aval - (1<<(n-1-i))
        ans[i] = sub(val, pc-1)
#         print(1, bin(val)[2:], pc-1)
    else:
        val = aval + (1<<(n-1-i))
        ans[i] = sub(val, pc+1)
#         print(0, bin(val)[2:], pc+1)
write("\n".join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    N = int(input())
    s = input()
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    
    @lru_cache(None)
    def r(n):
        if n==0:
            return 0
        bc=0
        for i in range(N):
            if n>>i&1:
                bc+=1
        return r(n%bc)+1

    mod=s.count("1")
    c1=0
    c2=0
    cur1=1%(mod+1)
    
    if mod>1:
        cur2=1%(mod-1)
        for i in range(N):
            if s[-1-i]=="1":
                c1+=cur1
                c1%=(mod+1)
                c2+=cur2
                c2%=(mod-1)

            cur1=cur1*2%(mod+1)
            cur2=cur2*2%(mod-1)
    else:

        for i in range(N):
            if s[-1-i]=="1":
                c1+=cur1
                c1%=(mod+1)
            cur1=cur1*2%(mod+1)



    for i in range(N):
        if s[i]=="1":
            f=-1
            cmod=mod-1
        else:
            f=1
            cmod=mod+1

        if cmod==0:
            print(0)
            continue
        
        if f==1:
            n=c1+pow(2,N-1-i,cmod)
            n%=cmod
        else:
            n=c2-pow(2,N-1-i,cmod)
            n%=cmod

        print(1+r(n))
    #printe(c1,c2)





if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy
from functools import lru_cache

# 整数1個だけ
N = int(input().strip())
X = input().strip()


@lru_cache
def popcount(x):
    cnt = 0
    while x > 0:
        x, m = divmod(x, 2)
        if m:
            cnt += 1
    return cnt


def b2i(x):
    v = 0
    for i, b in enumerate(reversed(x)):
        v += pow(2, i) * int(b)
    return v


for i in range(N):
    x = [v for v in X]
    x[i] = "0" if x[i] == "1" else "1"
    n = b2i(x)
    fn = 0
    while n > 0:
        n = n % popcount(n)
        fn += 1
    print(fn)

Submission status: Time Limit Exceeded

Solution code:
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
X = str(input())
start_number = int(X,2)
start_mod = X.count("1")

# print(start_number,"debug")
for i in range(n):
  if X[i] == "1":
    now_number = start_number - pow(2,n-1-i)
    now_mod = start_mod - 1
      
  else:
    now_number = start_number + pow(2,n-1-i)
    now_mod = start_mod + 1

  ci = 0
  while now_number != 0:
    # print(now_number,now_mod)
    now_number %= now_mod
    now_mod = bin(now_number).count("1")
    ci += 1
  print(ci)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def popcount(n):
    return Counter(bin(n)[2:])['1']

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

n = int(input())
x = input().rstrip()

for i in range(n):
    a = str(1 - int(x[i]))
    b = x[:i] + a + x[i+1:]
    print(f(int(b, 2)))

Submission status: Time Limit Exceeded

Solution code:
def solve(a, c):
    res = 0
    while a !=0:
        a = a%c
        new_a = bin(a)[2:]
        c=0
        for w in new_a:
            if w=='1':
                c+=1
        res+=1

    return res

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

num = int(x,2)
count = 0

for e in x:
    if e=='1':
        count+=1


for j in range(n):
    i = n-1-j
    c = count
    a = num
    if x[j]=='0': #change to 1
        a+=2**(i)
        c+=1
    else:
        a-=2**(i)
        c-=1

    print(solve(a,c))

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

def num_divisors_table(n):
    table = [0 for i in range(n + 1)]
    
    for i in range(1, n + 1):
        for j in range(i, n + 1, i):
            table[j] += 1
    
    return table

# ここから書き始める
def popcount(num):
    return num.count("1")


n = int(input())
x = input()
for i in range(n):
    y = x[:i]
    if x[i] == "1":
        y += "0"
    else:
        y += "1"
    y += x[i + 1:]
    ans = 0
    while int(y, 2) != 0:
        y = int(y, 2) % int(popcount(y))
        y = bin(y)[2:]
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
c = copy.deepcopy

def f(a):
    x = c(a)
    cnt = 0
    while x > 0:
        x %= bin(x).count("1")
        cnt += 1

    return cnt

def main():

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

    a = int(x, base=2)

    for i in range(n):
        a ^= 1 << (n - i - 1)
        print(f(a))
        a ^= 1 << (n - i - 1)

main()

Submission status: Time Limit Exceeded

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

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):
    b = ''.join([str(int(not(int(v)))) if j == i else v for j, v in enumerate(x)])
    print(f(int(b, 2), 0))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=input()
chk=0
for i,j in enumerate(x[::-1]):
    if j=="1":
        chk+=2**i
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:
        pc=bin(t)[2:].count("1")
        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)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200000)
N = int(input())
X = int(input(),2)
memo = {}

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

for i in range(N):
    a = N-i
    tmp = 1
    tmp <<= a-1
    n = X^tmp
    print(f(n))

Submission status: Time Limit Exceeded

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

def f(n):
    cnt = 0
    while n!=0:
        popcount = sum(map(int, bin(n)[2:]))
        n = n % popcount
        cnt += 1
    return cnt

for i in range(1, N+1):
    print(f(X ^ (1 << (N-i))))

Submission status: Time Limit Exceeded

Solution code:
def popcnt(n):
    s = 0
    while n > 0:
        s += n % 2
        n //= 2
    return s

def solve(n):
    if n==0: return 0
    return 1+solve(n%popcnt(n))

n = int(input())
s = input()
x = int(s,2)
a = s.count('1')
for i in range(n):
    b = a
    p = 2 ** (n - 1 - i)
    if s[i]=='1':
        b-=1
        p*=-1
    else:
        b+=1
        p*=1
    x+=p
    if b==0: print(0)
    else:
        print(1+solve(x%b))
    x-=p

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=int(input(),2)
#print(s)

def popcnt(s):
  bs=bin(s)
  r=sum([int(ii) for ii in bs[2:]])
  #print(bs,r)
  return(r)

for ii in range(n):
  x=s ^ 2**(n-1-ii)
  #print(x)
  f=0
  while x>0:
    x=x%popcnt(x)
    f+=1
  print(f)

Submission status: Time Limit Exceeded

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

for i in range(N - 1, -1, -1) :
  x = X ^ (1 << i)
  
  ret = 0
  while x != 0 :
    x = x % bin(x).count('1')
    ret += 1

  print(ret)

Submission status: Time Limit Exceeded

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

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:]
  n = int(x, 2)
  ans = 0
  while n:
    y = x.count('1')
    n = n%y
    x = format(n, 'b')
    ans += 1
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
def nasu(a):
  ans = 1
  while a != 0:
    k = bin(a).count("1")
    a %= k
    ans += 1
  return ans

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

t = X.count("1")
X = int(X, 2)

L = [0] * N
for i in range(N):
  a = X ^ (1 << i)
  if a == 0:
    L[i] == 0
    continue
  if X & (1 << i) != 0:
    k = t - 1
  else:
    k = t + 1
  a %= k
  L[i] = nasu(a)

for i in range(N - 1, -1, -1):
  print(L[i])

Submission status: Time Limit Exceeded

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

c0 = X.count('1')
for i, x in enumerate(X):
    if x == '1':
        y = Xi - (1 << (N - 1 - i))
        c = c0 - 1
    else:
        y = Xi + (1 << (N - 1 - i))
        c = c0 + 1

    if not y:
        print(0)
        continue
    y %= c
    ans = 1
    while y:
        y %= bin(y).count('1')
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

N = int(input())
X = input()
x = []
for i in range(N):
    x.append(X[i])
    
def popcount(n):
    return Counter(bin(n))['1']

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

for i in range(N):
    n = x.copy()
    if x[i] == '1':
        n[i] = '0'
    else:
        n[i] = '1'
    n = ''.join(n)
    print(f(int(n, 2)))

Submission status: Time Limit Exceeded

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

for i in range(1,n+1):
	xlist = list(x)
	if xlist[i-1]=='0':xlist[i-1]='1'
	else:xlist[i-1]='0'
	xstr=''.join(xlist)
	xint=int(xstr,2)
	res = 0
	while xint>0:
		c=bin(xint).count('1')
		xint=xint%c
		res +=1
	print(res)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = [int(x) for x in list(input())]
lx = len(x)-1

memo = [0]*(n+1)

for val in range(1, n+1):
    tmp = val
    cnt = 0
    while tmp > 0:
        if tmp & 1:
            cnt += 1
            tmp = (tmp-1)//2
        else:
            tmp = tmp//2
    memo[val] = memo[val % cnt] + 1


xx = 0
xx_cnt = 0
for i, y in enumerate(x):
    xx += (1 << (lx-i))*y
    if y == 1:
        xx_cnt += 1

for i in range(n):
    if x[i] == 0:
        val = xx + (1 << (lx-i))*1
        cnt = xx_cnt + 1
    else:
        val = xx - (1 << (lx-i))*1
        cnt = xx_cnt - 1

    ans = 0
    if val == 0:
        print(ans)
    else:
        while val > n:
            ans += 1
            val = val % cnt
            tmp = val % cnt
            cnt = 0
            while tmp > 0:
                if tmp & 1:
                    cnt += 1
                    tmp = (tmp-1) // 2
                else:
                    tmp = tmp // 2
        print(memo[val]+ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = input()
for i in range(n):
    t = x[:i] + ('0' if x[i] == '1' else '1') + x[i + 1:]
    ans = 0
    while int(t, 2) > 0:
        t = bin(int(t, 2) % (t.count('1')))[2:]
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():
    N = in_n()
    X = int(in_s(), 2)

    for i in range(N):
        # X[i] = str(int(not int(X[i])))
        a = X ^ (1 << N - i - 1)
        a = bin(a)[2:]
        # print(a)
        count = 0
        while int(a, 2):
            a = bin(int(a, 2) % a.count('1'))[2:]
            count += 1
        print(count)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = input()
y = int(x, 2)
pc = x.count('1')

for i in range(n):
    if x[i] == '1':
        xi = y - 2**(n-i-1)
        pci = pc - 1
    else:
        xi = y + 2**(n-i-1)
        pci = pc + 1
    count = 0
    while xi > 0:
        xi = xi % pci
        pci = bin(xi).count('1')
        count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:


def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    
    def pcnt(X):
        st=str(bin(X))
        return st.count("1")
    
    def calc(X):
        if X==0:
            return 0
        cnt=0
        while X!=0:
            #print(X,pcnt(X))
            X=X%pcnt(X)
            cnt+=1
        return cnt
    
    N=I()
    Xst=input()
    a=Xst.count("1")
    X=int(Xst,2)
    
    for i in range(N):
        if Xst[i]=="0":
            xa=a+1
            X2=X+(1<<(N-i-1))
        else:
            xa=a-1
            X2=X-(1<<(N-i-1))
        cnt=0
        #print(X2,xa)
        if X2!=0:
            X2=X2%xa
            cnt=1+calc(X2)
        print(cnt)
    
    
        

main()

Submission status: Time Limit Exceeded

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

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

result = []
for i in range(N):
    n = X ^ (1 << (N - 1 - i))
    t = 0
    while n != 0:
        n %= popcount(n)
        t += 1
    result.append(t)
print(*result, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import copy

# 整数1個だけ
N = int(input().strip())
X = input().strip()


def popcount(x):
    cnt = 0
    while x > 0:
        x, m = divmod(x, 2)
        if m:
            cnt += 1
    return cnt


def b2i(x: list):
    v = 0
    for i, b in enumerate(reversed(x)):
        v += pow(2, i) * int(b)
    return v


for i in range(N):
    x = [v for v in X]
    x[i] = "0" if x[i] == "1" else "1"
    n = b2i(x)
    fn = 0
    while n > 0:
        n = n % popcount(n)
        fn += 1
    print(fn)

Submission status: Time Limit Exceeded

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

for i in range(len(x)):
    s = list(x);
    if (s[i] == '0'): s[i] = '1'
    else: s[i] = '0'
    j = int("".join(s), 2)
    ans = 0
    while(j!=0):
        j %= bin(j).count('1')
        ans+=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
N = int(input())
X = int(input(), base=2)
memo = collections.defaultdict(int)
memo[0] = 0


def f(x):
    if x in memo:
        return memo[x]
    else:
        y = x % bin(x).count('1')
        ret = 1 + f(y)
        memo[x] = ret
        return ret


ans = []
for i in range(N - 1, -1, -1):
    ans += [f(X ^ (1 << i))]
print('\n'.join(map(str, ans)))