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:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

def solve():
    N = II()
    bb = input()
    X = list(map(int, bb))
    # print(X)
    num = int(bb, 2)
    # print(num)
    # return

    bit = sum(X)
    one_bit_cnt = {num: bit}
    f_cnt = {}

    def popcount(n):
        return sum( list(map(int, list(bin(n).replace('0b', '')))))

    def f(n, pop):
        cnt = 0
        while n > 0:
            fc = f_cnt.get(n, -1)
            if fc != -1:
                return cnt + fc
            n = n % pop
            pop = one_bit_cnt.get(n, -1)
            if pop == -1:
                pop = popcount(n)
                one_bit_cnt[n] = pop
            cnt += 1

        return cnt

    ex = N-1
    for i, x in enumerate(X):
        if x == 1:
            n = num - pow(2, ex)
            pop = bit - 1
        else:
            n = num + pow(2, ex)
            pop = bit + 1
        one_bit_cnt[n] = pop
        # print(n, pop)
        fc = f_cnt.get(n, -1)
        if fc != -1:
            print(fc)
        else:
            fc = f(n, pop)
            print(fc)
            f_cnt[n] = fc

        ex -= 1


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
n,x = open(0).read().splitlines()

n = int(n)
x = int(x,2)

#count
d = {0:0}

def calc(n):
    if n not in d:
        pop = n % bin(n).count('1')
        d[n] = calc(pop) + 1
    return d[n]

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

Submission status: Time Limit Exceeded

Solution code:
def popcount(n):
    result = 0
    while n > 0:
        result += 1
        n &= n - 1
    return result

def popfunc(n):
    result = 0
    while n > 0:
        result += 1
        n = n % popcount(n)
    return result

N = int(input())
divider = 2**(N-1)

X = int(input(), 2)

while divider > 0:
    print(popfunc(X^divider))
    divider = divider // 2

Submission status: Time Limit Exceeded

Solution code:
import sys

def input():
    return sys.stdin.readline()[:-1]

def ppp(x):
    s = format(x, 'b')
    return s.count('1')

n = int(input())
# pop_li = [ppp(i) for i in range(n+1)]
x = input()
for i in range(n):
    tmp = list(x)
    tmp[i] = str((int(x[i])+1)%2)
    xi = int(''.join(tmp) , 2)
    if xi==0:
        print(0)
    else:
        cnt = 0
        while xi!=0:
            cnt += 1
            xi = xi%ppp(xi)
        print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# 2進数表記のときの1の数 O(log k)
def popcount(k):
    ret = 1
    while k > 1:
        if k%2 != 0:
            ret += 1
        k //= 2
    return ret

def f(k):
    ret = 0
    while k != 0:
        k = k % popcount(k)
        ret += 1
    return ret

def rev(s, i):
    ret = list(s)
    if ret[i] == "1":
        ret[i] = "0"
    else:
        ret[i] = "1"
    # print("".join(ret))
    return int("".join(ret), 2)

n = int(input())
x_s = input()

# 2進変換
# x_b = int(x_s, 2)

for i in range(n):
    x_b_rev = rev(x_s, i)
    print(f(x_b_rev))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))
#%%code

def naive(a):
    if a==0:return 0
    b=a
    for i in range(1,1000000):
        t=bin(b).count("1") #popcount
        b%=t
        if b==0:
            return i
    assert b==0
def resolve():
    N,=pin()
    X=int(input(),2)
    #print(+X)
    cnt=0
    for i in range(N):
        temp=X^(1<<(N-i-1))
    #    print(temp,";")
        print(naive(temp))
#%%submit!
resolve()

Submission status: Time Limit Exceeded

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()
X = int(input(), 2)

for i in range(N-1, -1, -1):
    cur = X ^ (1<<i)
    cnt = 0
    while cur:
        cur %= popcount(cur)
        cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = list(map(int, list(input())))
X.reverse()
def int2bit(n):
	ret = [0 for i in range(18)]
	cnt = 0
	i = 0
	while n > 0:
		ret[i] = n % 2
		cnt += n % 2
		n = n // 2
		i += 1
	return (ret, cnt)

def func(bit, popcount):
	ret = 0
	base = 1
	for b in bit:
		ret = (ret + base*b) % popcount
		base = (base * 2) % popcount
	return ret

def func2(n):
	(bit, popcount) = int2bit(n)
	return func(bit, popcount)

F = [0 for _ in range(N+1)]

for n in range(1, N+1):
	a = func2(n)
	F[n] = 1 + F[a]
P = sum(X)
for i in range(N):
	idx = N - 1 - i
	X[idx] = 1 - X[idx]
	if X[idx] == 1:
		print(1 + F[func(X, P+1)])
	if X[idx] == 0:
		if P == 1:
			print(0)
		else:
			print(1 + F[func(X, P-1)])
	X[idx] = 1 - X[idx]

Submission status: Time Limit Exceeded

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
from sys import flags
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
x=list(input())
cnt=Counter(x)
x=int("".join(x),2)
# print(x)
# print(math.log2(2*10**5))
# print(cnt)
def wari(now):
    tmp=cnt["1"]
    # print(flag,tmp)
    if flag==1:
        tmp-=1
    else:
        tmp+=1
    # print(tmp)
    if tmp==0:
        return 0
    now%=tmp
    ans=1
    while now:
        cnt2=0
        n=0
        while now>=pow(2,n):
            if now&1<<n:
                cnt2+=1
            n+=1
        now%=cnt2
        ans+=1
    return ans

for i in range(n):
    flag=0
    if x&1<<(n-1-i):
        flag=1
        x-=pow(2,(n-1-i))
    else:
        flag=0
        x+=pow(2,(n-1-i))

    print(wari(x))

    if x&1<<(n-1-i):
        x-=pow(2,(n-1-i))
    else:
        x+=pow(2,(n-1-i))

Submission status: Time Limit Exceeded

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


N = int(input())
X = input()
dp = [-1 for _ in range(N)]


def solve(n):
    global res
    if dp[-1] >= 0:
        return dp[n]
    if popcnt1(n) == 0:
        dp[n] = res
        return res
    n = n % popcnt1(n)
    res += 1
    solve(n)


for i in range(N):
    res = 0
    tX = list(X)
    if X[i] == "0":
        tX[i] = "1"
    else:
        tX[i] = "0"
    tXs = "".join(tX)
    solve(int(tXs, 2))
    dp[i] = res
    print(res)

Submission status: Time Limit Exceeded

Solution code:
k=int(input())
x=input()
cnt=x.count("1")
n=int(x,2)
for i in range(k):
    temp=0
    ntemp=n
    if x[i]=="0":
        temp=cnt+1
        ntemp+=(2**(k-i-1))
    else:
        temp=cnt-1
        ntemp-=(2**(k-i-1))
    ans=0
    #print(ntemp,temp)
    while ntemp>0:
        ntemp%=temp
        temp=str(bin(ntemp)).count("1")
        ans+=1
    print(ans)

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)

Submission status: Time Limit Exceeded

Solution code:
import math
import collections
import bisect
from collections import deque
from copy import copy, deepcopy


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


def main():
    N = int(input())
    X = input()
    decX = int(X, 2)

    ans = [0 for i in range(len(X) + 1)]
    for i in range(len(X) - 1, -1, -1):
        # print(i)
        tmp = 1 << i ^ decX
        while(1):
            if tmp == 0:
                break
            tmp %= popcount(tmp)
            ans[i] += 1
        print(ans[i])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def calc(val, my_dict, cnt):
    num_one = bin(val).count('1')
    if val in my_dict:
        return cnt + my_dict[val]
    else:
        if num_one == 0:
            return cnt
        nex = val % num_one
        ret = calc(nex, my_dict, cnt+1)
        my_dict[val] = ret - cnt
        return ret


n = int(input())
x = input()
tmp = list(x)
my_dict = dict()

for i in range(n):
    tmp[i] = '0' if tmp[i] == '1' else '1'
    val = int(''.join(tmp), 2)
    print(calc(val, my_dict, 0))
    tmp[i] = '0' if tmp[i] == '1' else '1'

Submission status: Time Limit Exceeded

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


c = dict()
for i in range(len(X)):
    x = list(X)

    if X[i] == '1':
        x[i] = '0'
    else:
        x[i] = '1'
    x = "".join(x)
    c[i] = 0
    while True:
        cnt = x.count('1')
        if cnt == 0:
            break
        bins = int(x, 2)
        n = bins % cnt
        c[i] += 1
        if n == 0:
            break

        x = format(n, '08b')

for i in range(N):
    print(c[i])

Submission status: Time Limit Exceeded

Solution code:
FAST_IO = 1
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()

    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())
rrmm = lambda n: [rrm() for _ in xrange(n)]


dic = {}
def f(x):
    if x in dic:
        return dic[x]
    if x== 0:
        return 0
    tmp = x% bin(x).count('1')
    dic[x] = f(tmp)+1
    return dic[x]
    
N = rri()
num = int('0b'+rr(),2)
count = bin(num).count('1')
for i in range(N):
    if not num & (1<<(N-i-1)):
        cur_count = count+1
    else:
        cur_count =count-1
    if cur_count ==0:
        print(0)
    else:
        cur_num = num ^ (1<<(N-i-1))
        cur_num = cur_num%cur_count
        print(f(cur_num)+1)

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
def calc(num,c):
    s = int(num,2)
    ss = 0
    for i in range(len(num)):
        if num[i] == '1':
            ss += 1

    if s % ss != 0:
        return calc(bin(s%ss),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:
n = int(input())
x = input()

for i in range(n):
  c = x[i]
  t = '0'
  if c == '0':
    t = '1'
  s = x[:i] + t + x[i+1:]
  ans = 0
  m = int(s, 2)
  # print(s, m)
  while m > 0:
    #print('in while :', m)
    m = m % bin(m).count('1')
    ans += 1
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=int(input(),2)
dic=[0]*200000
def f(x):
    if dic[x]!=0:
        return dic[x]
    cnt=0
    for i in bin(x):
        cnt+=i=='1'
    if cnt == 0:
        return 0
    dic[x]=f(x%cnt)+1
    return dic[x]
cnt=0
for i in bin(x):
    cnt+=i=='1'
ans=[]
for i in range(n-1,-1,-1):
    j=x^(1<<i)
    if j==0:
        ans.append(0)
    else :
        if x&(1<<i)==0:
            ans.append(f(j%(cnt+1))+1)
        else :
            ans.append(f(j%(cnt-1))+1)
print(*ans,sep='\n')

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
b=int(input(),2)
ls=[0]*n
bi=1
for i in range(n):
  k=b ^ bi
  ans=0
  while k>0:
    x=format(k, 'b').count("1")
    k=k%x
    ans+=1
  ls[n-1-i]=ans
  bi*=2
for i in ls:
  print(i)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = eval("0b" + input())

def toggl_ith_bit(num, i):
    return num ^ (1 << i)

def popcount(num):
    s = 0
    b = num
    while b != 0:
        s += (b & 1 > 0)
        b >>= 1
    return s

for i in range(n - 1, -1, -1):
    xi = toggl_ith_bit(x, i)
    cnt = 0
    while xi != 0:
        cnt += 1
        xi %= popcount(xi)
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = str(input())
from functools import lru_cache

@lru_cache(maxsize=100000)
def popcount(y):
    return bin(y).count("1")

@lru_cache(maxsize=100000)
def f(m):
    if m == 0:
        return 0
    else:
        amari = m % popcount(m)
        return 1 + f(amari)
    
for i in range(n):
    moji = list(x)
    if moji[i] == "1":
        moji[i] = "0"
    else:
        moji[i] = "1"
    str_moji = "".join(moji)
    print(f(int(str_moji, 2)))

Submission status: Time Limit Exceeded

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

        if X_count == 1 and target & X:
            ans.append(0)
            continue

        if target & X:
            Xi %= (X_count - 1)
        else:
            Xi %= (X_count + 1)

        # 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=input()
f=[0]*n
for i in range(1,n):
    popcount=format(i,'b').count('1')
    f[i]=f[i%popcount]+1
# print(f)
for i in range(len(x)):
    if x[i]=='1':
        x_changed=x[:i]+'0'+x[i+1:]
    else:
        x_changed=x[:i]+'1'+x[i+1:]
    num_changed=int(x_changed,2)
    # print(x_changed,num_changed)
    popcount=format(num_changed,'b').count('1')
    if num_changed<n:
        print(f[num_changed])
    else:
        print(f[num_changed%popcount]+1)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x2=input()
x3=int(x2,2)

a=[0 for _ in range(n)]

for j in range(n):
  d=0
  b=x2
  b=b[:j]+"0"+b[1+j:] if b[j]=="1" else b[:j]+"1"+b[1+j:]
  x=int(b,2)
  while x>0:
    c=0
    for i in range(n):
      if (x>>i)&1 ==1:
        #print(i)
        c+=1
    x=x%c
    d+=1
  a[j]=d
for m in a:
  print(m)

Submission status: Time Limit Exceeded

Solution code:


def popcount(n):
  if n == 0:
    return 0

  cnt = 0
  for bit in format(n, 'b'):
    if bit == '1':
      cnt += 1

  return 1 + popcount(n % cnt)

def main():
  n = int(input())
  src = input()
  base = int(src, 2)

  for i in range(n - 1, -1, -1):
    num = base + 2 ** i if src[n - i - 1] == '0' else base - 2 ** i
    print(popcount(num))



main()

Submission status: Time Limit Exceeded

Solution code:
# D - Anything Goes to Zero
import sys
sys.setrecursionlimit(10**8)

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

def check(n, r):
    if n == 0:
        return print(r)
    d = str(bin(n)).count('1')
    check(n%d, r+1)

ones = X.count('1')
for i in range(N):
    e = -1
    if X[i] == '0':
        e = 1
    num = int(X, 2) + e * pow(2, N-1-i)
    check(num, 0)

Submission status: Time Limit Exceeded

Solution code:
"""
NTC here
"""


#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase

profile = 0
pypy = 1


def iin(): return int(input())


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



def main():
    T = 1
    while T:
        T -= 1
        n = iin()
        a = list(map(int, list(input())))
        ans = []
        def calc(a, md):
            ch = len(a)-1
            rm = 0
            for i in a:
                if i:
                    rm = (rm+ pow(2, ch, md))%md
                ch -= 1
            return rm%md
        
        def bin_calc(a):
            ans = []
            while a:
                ans.append(a&1)
                a >>= 1
            return ans[::-1]
        sm = sum(a)
        for i in range(n):
            sol = 0
            s1 = sm - a[i]
            a[i] = + (not a[i])
            s1 += a[i]
            a1 = a
            while s1:
                # print(a1, s1)
                sol += 1
                rm = calc(a1, s1)
                if rm:
                    a1 = bin_calc(rm)
                    s1 = sum(a1)
                else:
                    break
            a[i] = + (not a[i])
            ans.append(sol)
        print(*ans, sep='\n')





    
        










    




                

        

 
 
 
 
 
 
# region fastio
 
BUFSIZE = 8192
 
 
class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 
if pypy:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
    input = lambda: sys.stdin.readline().rstrip("\r\n")
 
# endregion
 
if __name__ == "__main__":
    if profile:
        import cProfile
        cProfile.run('main()')
    else:
        main()

Submission status: Time Limit Exceeded

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


n = int(input())
x = input()
xx = x
nx = int(x, 2)
pnx = popcnt(nx)
popl = [-1]*(2*10**5+10)

for i in range(n):
    if i == 0:
        a = 1 << (n-1)
    else:
        a = a >> 1
    x = nx ^ a
    if xx[i] == "1":
        px = pnx-1
    else:
        px = pnx+1
    ans = 0
    while x != 0:
        x = x % px
        if popl[x] == -1:
            px = popcnt(x)
            popl[x] = px
        else:
            px = popl[x]
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())

def solve():
    N = 200000
    mem = [None]*(N+1)
    mem[0] = 0
    cnt = [0]
    for _ in range(18):
        cnt = [x+i for i in range(2) for x in cnt]
    def dfs(x):
        if mem[x] is not None:
            return mem[x]
        p = cnt[x]
        res = dfs(x%p)+1
        mem[x] = res
        return res

    ans = [dfs(i) for i in range(N+1)]
    n = I()
    x = list(map(int, input()))
    cnt_x = sum(x)
    s = 0
    p = 1
    l = [0]*n
    for i in range(n)[::-1]:
        xi = x[i]
        if xi:
            l[i] = p
        p <<= 1
    cnt_p = cnt_x+1
    rp = [li%cnt_p for li in l]
    sp = sum(rp)%cnt_p
    if cnt_x > 1:
        cnt_m = cnt_x-1
        mp = [li%cnt_m for li in l]
        sm = sum(mp)%cnt_m
    p >>= 1
    for i in range(n):
        if x[i]:
            k = cnt_x-1
            if k == 0:
                print(0)
            else:
                a = (sm-p)%k
                print(ans[a]+1)
        else:
            k = cnt_x+1
            a = (sp+p)%k
            print(ans[a]+1)
        p >>= 1
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = input()
# print (int(x,2))
a = x.count('1')
# print (a)



for i in range(n):
  if x[i] == '0':
    b = '1'
    cnt = a + 1
  else:
    b = '0'
    cnt = a - 1
  d = x[:i] + b + x[i+1:]
  # print (d, int(d,2))
  v = int(d,2)
  out = 0
  while v != 0:
    v %= cnt
    cnt = bin(v).count('1')
    out += 1
  print (out)

Submission status: Time Limit Exceeded

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

def solve(N, X):
    X_oct = int(X, 2)
    X_one_count = sum([1 for x in X if x == '1'])

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

        if X_one_current == 0:
            print(0)
            continue

        count = 0
        while True:
            X_current = X_current % X_one_current
            X_one_current = sum([1 for x in bin(X_current) if x == '1'])
            count += 1

            if X_current == 0:
                break

            if X_current in memo:
                count += memo[X_current]
                break

        print(count)

    return

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

if __name__ == '__main__':
    main()

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:
n = int(input())
x = input()
xint = int(x,2)

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

for i in range(1,n+1):
	xint = int(x,2)
	if x[i-1]=='0':xint+=2**(n-i)
	else:xint-=2**(n-i)
	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(input(), 2)

memo = dict()

def f(n: int) -> int:
  if n == 0:
    return 0
  elif n in memo:
    return memo[n]
  else:
    res = f(n % (bin(n).count("1"))) + 1
    memo[n] = res
    return res

for i in range(0, N)[::-1]:
  print(f(X ^ (2 ** i)))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = int(input(), 2)
ans = [0] * n

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

for i in range(n):
    tmp = x
    if (tmp >> (n-i-1)) & 1:
        tmp &= ~(1 << (n-i-1))
    else:
        tmp |= (1 << (n-i-1))
    cnt = 0
    while tmp != 0:
        cnt += 1
        c = popcnt(tmp)
        tmp = tmp % c
    ans[i] = cnt

for v in ans:
    print(v)

Submission status: Time Limit Exceeded

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


c = dict()
for i in range(len(X)):
    x = list(X)

    if X[i] == '1':
        x[i] = '0'
    else:
        x[i] = '1'

    c[i] = 0
    while True:
        cnt = x.count('1')
        if cnt == 0:
            break
        x_c = "".join(x)
        bins = int(x_c, 2)
        n = bins % cnt
        c[i] += 1
        if n == 0:
            break

        x = format(n, '08b')

for i in range(N):
    print(c[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = int(input())
X = input()

def popcount(n):
    bin_str = bin(n)
    return bin_str.count('1')
#print(popcount(N))

cnt = 0
def func(n):
    global cnt
    if n == 0:
        return cnt
    n = n % popcount(n)
    cnt += 1
    return func(n)
#print(func(7))

def toggle_nth_bit(num: int, n: int):
    return num ^ (1 << n)

lst = []
for i in range(0,N):
    lst.append(toggle_nth_bit(int(X,2),i))
#print(lst)

for i in lst[::-1]:
    ans = func(i)
    print(ans)
    cnt -= ans

Submission status: Time Limit Exceeded

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

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


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


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


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

Submission status: Time Limit Exceeded

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


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


def solve(n):
    global res
    if popcnt1(n) == 0:
        return res
    n = n%popcnt1(n)
    res += 1
    solve(n)


for i in range(N):
    res = 0
    tX = list(X)
    if X[i] == "0":
        tX[i] = "1"
    else:
        tX[i] = "0"
    tXs = "".join(tX)
    solve(int(tXs, 2))
    print(res)

Submission status: Time Limit Exceeded

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

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

popcount0 = popcount(int( "0b"+"".join(x) ,0 ))

jisho = ["yet"]*n

for i in range(n):
    xx = x[:]
    if xx[i]=="0":
        xx[i] = "1"
        pop = popcount0+1
    else:
        xx[i] = "0"
        pop = popcount0-1
        
    intxi = int( "0b"+"".join(xx) ,0 )
#    print(intxi,intxi%pop)
    if intxi==0:
        print(0)
        continue
    else:
        c=0
        while intxi!=0:
            if c==0:
                intxi=intxi%pop
            else:
                if jisho[intxi]=="yet":
                    togo = intxi%popcount(intxi)
                    jisho[intxi]= togo
                    intxi = togo
                else:
                    intxi =jisho[intxi]
                
            #print(m)
            c+=1
        print(c)
#        print("f(n)=",c)

Submission status: Time Limit Exceeded

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

val = 0
rui = 1
mod = 0
for i in range(n):
    val += int(x[n-1-i])*rui
    rui *= 2
    if int(x[n-1-i]) == 1:
        mod += 1

rui = 1
ans_li = []
    
for i in range(n):
    t_v = val
    t_m = mod
    if int(x[n-1-i]) == 1:
        t_v -= rui
        t_m -= 1
    else:
        t_v += rui
        t_m += 1
    rui *= 2
    ans = 0
    while t_v != 0:
        t_v %= t_m
        ans += 1
        t_m = bin(t_v).count("1")
    ans_li.append(ans)
    #print(ans_li)

#print(ans_li)
for i in range(n):
    print(ans_li[n-1-i])