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())
x = input()
xl = len(x)

xi = int(x, 2)
x = "0" * (n - xl) + x
def popcount(n):
    n = bin(n)
    return sum([int(a) for a in n[2:]])

def a(n):
    c = 0
    while n != 0:
        n %= popcount(n)
        c += 1
    return c

n -= 1
c2 = 0
temp = 0
for i in x:
    c2 = 0
    temp = (xi ^ (1 << n))
    n -= 1
    print(a(temp))

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.read
from copy import deepcopy
from collections import defaultdict
def main():
    n = int(input())
    x = list(input())
    memo = defaultdict(int)
    for i1 in range(n):
        x2 = deepcopy(x)
        if x2[i1] == '1':
            x2[i1] = '0'
        else:
            x2[i1] = '1'
        x3 = int("".join(x2), 2)
        r = 0
        while x3:
            r += 1
            if memo[x3] == 0:
                p = bin(x3).count('1')
                memo[x3] = p
                x3 = x3 % p
            else:
                x3 = x3 % memo[x3]
        print(r)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
def funk(x, temp_count):
    if x in log_dict:
        ans = log_dict[x]
        return ans
    x_temp = x % temp_count
    if x_temp == 0:
        log_dict[x] = 1
        return 1
    temp_count = bin(x_temp).count("1")
    ans = funk(x_temp, temp_count)
    ans += 1
    log_dict[x] = ans
    return ans
n = int(input())
bit = input()
bit_list = list(bit)
count = bit.count("1")
log_dict = {}
log_dict[0] = 0
log_dict[1] = 1
log_dict[2] = 1
for i in range(n):
    temp_count = count
    if bit[i] == "1":
        temp_count -= 1
        bit_list[i] = "0"
        x_bit = ''.join(bit_list)
        bit_list[i] = "1"
    else:
        temp_count += 1
        bit_list[i] = "1"
        x_bit = ''.join(bit_list)
        bit_list[i] = "0"
    x = int(x_bit, 2)
    ans = funk(x, temp_count)
    print(ans)

Submission status: Time Limit Exceeded

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

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

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
        g=u
        p=0
        n+=1
        while g>0:
            p+=g%2
            g=g//2
    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:
# -*- coding: utf-8 -*-
N = int(input())
X = input()
#N = 2 * 100000
#X = "0" * N
#def hanten(a,i):
#    if a[i] == "0":
#        return(a[:i] + "1"+ a[i+1:])
#    else:
#        return(a[:i] + "0"+ a[i+1:])

def hanten(num, n):
    #print(1 << n, num ^ (1 << n))
    return num ^ (1 << n)
#print('\n'.join(X))
for i in range(1,N+1):
    #hantened = int(hanten(X,i),2)
    hantened = hanten(int(X,2),N-i)
    #print(hantened)
    cnt = 0
    while (hantened > 0):
        hantened = hantened % bin(hantened).count("1")
        cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

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


def read():
    N = int(input().strip())
    X = input().strip()
    return N, X


def strdiv(X, k, d):
    P = 0
    q = 0
    for i in range(len(X)):
        q <<= 1
        if i == k:
            q |= 1-int(X[i])
        else:
            q |= int(X[i])
        p, q = divmod(q, d)
        # 商
        P <<= 1
        P |= p
    return P, q


def solve(N, X):
    P = [-1 for i in range(N+1)]
    B = sum([1 for a in X if a == "1"])
    
    for k in range(N):
        if X[k] == "0":
            b = (B + 1)
        else:
            b = (B - 1)
        ans = 0
        x = X

        if b == 0:
            print(0)
        else:
            # first step
            p, q = strdiv(x, k, b)
            ans += 1
            x = bin(q)[2:]
            b = sum([1 for a in x if a == "1"])

            # second step (q < N)
            if P[q] == -1:
                r = q
                while r > 0:
                    p, r = strdiv(x, k, b)
                    ans += 1
                    x = bin(r)[2:]
                    b = sum([1 for a in x if a == "1"])
                P[q] = ans
            print(P[q])


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Time Limit Exceeded

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

def calculate(k):
  a = bin(k)[2:]
  b = str(a)
  one_count = 0
  for s in b:
    if s == '1':
      one_count += 1
  c = k % one_count
  
  return c

for i in range(n):
  if x[i] == '0':
    y = y_origin + 2**(n-i-1)
    ans = 0
    while y > 0:
      y = calculate(y)
      ans += 1
    print(ans)
  else:
    y = y_origin - 2**(n-i-1)
    ans = 0
    while y > 0:
      y = calculate(y)
      ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def mpower(a, b, n):
    if b == 0:
        return 1
    if b == 1:
        return a % n
    a1 = a
    k = 1
    while a1 < n and k < b:
        a1 = a1 * a
        k = k + 1

    a1 = a1 % n
    b1 = b // k
    a2 = a
    b2 = b % k
    return (mpower(a1, b1, n)*mpower(a2, b2, n)) % n


def main():
    n = int(input())
    x = input()
    k = int(x, 2)
    p = x.count("1")
    if p > 1:
        kp0 = k % (p - 1)
    kp1 = k % (p + 1)
    f = [0] * (n + 1)
    for i in range(1, n + 1):
        f[i] = f[i % bin(i).count("1")] + 1
    for i in range(n):
        if x[i] == "1":
            pi = p - 1
            if pi == 0:
                print(0)
                continue
            print(f[(kp0 - mpower(2, n - i - 1, pi)) % pi] + 1)
        else:
            pi = p + 1
            print(f[(kp1 + mpower(2, n - i - 1, pi)) % pi] + 1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = int(input(),2)
zuru = [0, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 2, 3, 1, 2, 1, 2, 1, 1, 2, 3, 1, 2, 2, 3, 2, 2, 2, 2, 1, 2, 1, 2, 1, 2, 2, 3, 1, 2, 1, 3, 2, 2, 2, 2, 1, 2, 2, 3, 2, 2, 2, 1, 2, 2, 2, 2, 1, 2, 2, 3, 1, 2, 1, 2, 1, 1, 2, 3, 1, 2, 2, 3, 2, 2, 2, 2, 1, 1, 2, 3, 1, 2, 2, 2, 2, 2, 2, 2, 1, 3, 2, 3, 1, 2, 2, 3, 2, 2, 2, 3, 2, 2, 2, 2, 1, 2, 1, 3, 2, 2, 2, 1, 1, 2, 3, 3, 1, 2, 2, 3, 2, 3, 1, 2, 1, 2, 1, 2, 1, 2, 2, 3, 1, 2, 1, 3, 2, 2, 2, 3, 1, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 3, 3, 1, 2, 1, 3, 2, 2, 2, 2, 1, 2, 2, 2, 1, 3, 2, 2, 2, 2, 2, 2, 1, 2, 2, 3, 1, 1, 2, 2, 3, 3, 2, 2, 1, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 3, 1, 1, 2, 3, 2, 2, 2, 2, 1, 3, 2, 3, 1, 2, 3, 3, 1, 3, 1, 2, 2, 2, 2, 2, 1, 2, 1, 3, 1, 3, 2, 2, 2, 3, 2, 2, 1, 2, 2, 3, 2, 3, 1, 2, 3, 3, 2, 2, 1, 2, 2, 3, 1, 2, 1, 2, 1, 1, 2, 3, 1, 2, 2, 3, 2, 2, 2, 2, 1, 1, 2, 3, 1, 2, 2, 2, 2, 2, 2, 3, 1, 1, 2, 3, 1, 2, 2, 3, 2, 2, 2, 1, 2, 2, 2, 2, 1, 2, 2, 3, 2, 2, 2, 2, 1, 2, 1, 3, 1, 3, 2, 3, 2, 3, 1, 2, 1, 1, 2, 3, 1, 2, 2, 2, 2, 2, 2, 2, 1, 3, 2, 3, 1, 2, 2, 2, 1, 2, 2, 2, 1, 1, 2, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 2, 3, 3, 1, 2, 2, 3, 2, 3, 1, 3, 1, 2, 1, 3, 2, 2, 2, 2, 2, 3, 1, 2, 2, 3, 2, 3, 1, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 3, 3, 2, 2, 2, 3, 1, 1, 2, 3, 1, 2, 1, 3, 2, 3, 1, 2, 2, 2, 2, 2, 1, 2, 2, 3, 1, 1, 2, 2, 3, 3, 2, 2, 1, 3, 2, 3, 2, 3, 1, 3, 1, 3, 2, 2, 1, 2, 3, 3, 2, 2, 2, 2, 1, 3, 2, 3, 1, 2, 3, 3, 1, 3, 1, 2, 1, 1, 2, 3, 3, 2, 2, 2, 2, 3, 1, 2, 2, 2, 2, 3, 1, 2, 2, 3, 2, 3, 1, 2, 3, 3, 2, 2, 1, 3, 2, 3, 2, 3, 1, 2, 2, 2, 3, 3, 1, 2, 2, 3, 2, 3, 2, 3, 1, 2, 1, 2, 1, 2, 2, 3, 1, 2, 1, 3, 2, 2, 2, 2, 1, 2, 2, 3, 2, 2, 2, 1, 2, 2, 2, 2, 1, 2, 2, 3, 1, 2, 1, 3, 2, 2, 2, 2, 1, 2, 2, 1, 1, 2, 3, 2, 2, 2, 2, 3, 1, 1, 2, 3, 1, 2, 1, 2, 2, 3, 2, 2, 1, 2, 2, 3, 2, 2, 2, 3, 2, 2, 2, 2, 1, 2, 1, 3, 2, 2, 2, 1, 1, 2, 3, 3, 1, 2, 2, 3, 2, 3, 1, 3, 2, 2, 2, 2, 1, 3, 2, 3, 1, 2, 3, 2, 1, 3, 2, 1, 1, 1, 2, 3, 3, 3, 1, 2, 2, 3, 2, 3, 1, 1, 2, 3, 1, 2, 1, 3, 2, 2, 2, 2, 1, 2, 2, 2, 1, 3, 2, 2, 2, 2, 2, 2, 1, 2, 2, 3, 1, 1, 2, 2, 3, 3, 2, 2, 1, 2, 2, 1, 1, 2, 3, 2, 1, 2, 2, 3, 2, 2, 2, 2, 1, 2, 1, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 1, 2, 1, 3, 1, 3, 2, 2, 2, 3, 2, 3, 1, 2, 2, 3, 2, 3, 1, 2, 3, 3, 2, 3, 1, 3, 2, 3, 1, 2, 3, 2, 1, 3, 2, 2, 2, 2, 2, 3, 2, 1, 2, 3, 2, 3, 2, 2, 1, 2, 2, 3, 2, 3, 2, 3, 2, 3, 2, 2, 1, 2, 2, 3, 2, 2, 2, 1, 2, 2, 2, 2, 1, 2, 2, 3, 2, 2, 2, 2, 1, 2, 1, 3, 1, 3, 2, 3, 2, 3, 1, 2, 2, 2, 2, 3, 1, 1, 2, 3, 1, 2, 1, 2, 2, 3, 2, 3, 1, 2, 3, 3, 1, 3, 1, 2, 2, 3, 2, 2, 1, 3, 2, 3, 2, 2, 2, 1, 1, 2, 3, 3, 1, 2, 2, 3, 2, 3, 1, 1, 1, 2, 1, 3, 2, 2, 2, 2, 2, 3, 1, 3, 2, 1, 2, 3, 1, 1, 2, 3, 3, 3, 1, 3, 2, 3, 2, 1, 1, 2, 3, 3, 1, 3, 1, 2, 2, 3, 2, 3, 1, 1, 2, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 2, 2, 3, 1, 1, 2, 2, 3, 3, 2, 2, 1, 3, 2, 3, 2, 3, 1, 2, 1, 3, 2, 2, 1, 2, 2, 3, 1, 2, 1, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 3, 2, 3, 2, 3, 2, 2, 1, 2, 3, 3, 2, 2, 2, 3, 2, 3, 2, 3, 1, 2, 2, 3, 2, 3, 1, 2, 3, 3, 2, 3, 1, 1, 2, 3, 2, 3, 1, 2, 2, 2, 2, 3, 1, 3, 2, 3, 2, 3, 2, 2, 2, 3, 2, 2, 1, 3, 2, 3, 2, 1, 2, 3, 3, 3, 2, 2, 1, 2, 2, 3, 2, 3, 2, 3, 2, 2, 2, 2, 2, 2, 3, 3, 1]

_max = pow(2, n-1)
while 1:
  n = x ^ _max
  count = 0
  while n != 0:
    n = n % bin(n).count("1")
    count += 1
    if 0 <= n <=1024:
      count += zuru[n]
      break
  print(count)
  n = x ^ _max
  _max = _max // 2
  if _max == 0:
    break

Submission status: Time Limit Exceeded

Solution code:
import copy
N = int(input())
line = input()
for i in range(N):
    tmp = list(line)
    if tmp[i] == '0':
        tmp[i] = '1'
    elif tmp[i] == '1':
        tmp[i] = '0'
    else:
        print("error: tmp includes except 0 or 1")
        exit()
    cnt = tmp.count('1')
    if cnt == 0:
        print(0)
        continue
    num2 = int(''.join(tmp))
    num10 = int(str(num2), 2)
    devide = num10 % cnt
    devideCnt = 1
    while devide != 0:
        num10 = devide
        num2 = bin(num10)
        cnt = list(num2).count('1')
        devide = num10 % cnt
        devideCnt += 1
    print(devideCnt)

Submission status: Time Limit Exceeded

Solution code:
def count1(n):
    p=0
    while n!=0:
        if n%2==1:
            p+=1
        n//=2        
    return p

N=int(input())
X=input()
for i in range(N):
    Ni2=X
    if X[i]=='0':
        Ni2=X[:i]+'1'+X[(i+1):] #文字列は変更できない
    else:
        Ni2=X[:i]+'0'+X[(i+1):]
    Ni=int(Ni2,2)
    ans=0
    #print(Ni)
    while Ni!=0:
        Ni=Ni%count1(Ni)
        ans+=1
    print(ans)

Submission status: Time Limit Exceeded

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

v=a.count('1')

ans=[0]*n
A=[0]*n
# n以下の残り回数を記録
for i in range(n):
    x=i
    cnt=0
    while x>0:
        cnt+=1
        r = 0
        for j in range(20):
            if (x>>j)&1:
                r+=1
        x=x%r
    ans[i]=cnt

# 各桁をv＋１で割ったあまり
q = [0]*n
# 各桁をv-1で割ったあまり
r = [0]*n
for i in range(n):
    if a[i]=='1':
        if v!=0:
            q[i] = pow(2, n-i-1) % (v + 1)
        if v!=1:
            r[i] += pow(2, n-i-1) % (v - 1)
qq=sum(q)
rr=sum(r)

for i in range(n):
    if a[i]=='1':
        if v!=1:
            z = rr - pow(2,n-i-1)%(v-1)
            cnt = z % (v - 1)
            A[i] = 1 + ans[cnt]
    else:
        z=qq+pow(2,n-i-1)%(v+1)
        cnt=z%(v+1)
        A[i]=1+ans[cnt]

for i in A:
    print(i)

Submission status: Time Limit Exceeded

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


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


dp = [0] * 1000000
for i in range(n - 1, -1, -1):
    num = (2 ** i) ^ x
    ans = 0
    bit_count_init = bc(num)
    while True:
        bit_count = bc(num)
        if num == 0:
            print(ans)
            dp[bit_count_init] = ans
            break
        num %= bit_count
        ans += 1
        if dp[num] != 0:
            print(dp[num] + ans)
            break

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

from functools import lru_cache


bit = {}
@lru_cache(maxsize=None)
def popcount2(bits):
    if bits in bit:
        return bit[bits]
    ori_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[ori_bit] = ans
    return ans


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 rec2(n):
    if n in memo:
        return memo[n]
    
    p = bit[n]
    new_n = n % p
    ans = memo[new_n] + 1
    memo[n] = ans
    return memo[n]


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

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

    base_bit = 0
    for c in xs:
        if c == "1":
            base_bit += 1
    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
        else:
            xi = x - mask
            bit[xi] = bit[x] - 1
        print(rec2(xi))
        mask >>= 1


if __name__ == "__main__":
    submit()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
from copy import deepcopy
#print(s.count("1"))
#print(int(s,2))

def num(x):
    cnt = 0
    while True:
        a = x.count("1")
        b = int(x,2)
        if a:
            x = bin(b%a)[2:]
            #print(s)
        else:
            break
        cnt +=1
    return cnt
#print(num(s))

for i in range(n):
    ss = list(deepcopy(s))
    if ss[i] == "1":
        ss[i] = "0"
        ss = "".join(ss)
        print(num(ss))
    else:
        ss = list(deepcopy(s))
        #print(ss)
        ss[i]= "1"
        ss = "".join(ss)
        print(num(ss))
        #break
        #print(ss)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np


def f(x):
    c = 0
    x = int("0b"+x,2)
    while(x>0):
        x %= bin(x).count("1")
        c += 1
    
    return c

def solve(N: int, X: str):
    #print(X)
    for i in range(1, N+1):
        x = list(X)
        x[i-1] = str(1-int(x[i-1]))
        #print(''.join(x))
        print(f(''.join(x)))
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = next(tokens)  # type: str
    solve(N, X)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
@lru_cache(maxsize = None)

def calc(x):
    return (x % bin(x).count('1'))

n = input()
s = input()

hanten = 1 << int (n) - 1;
for i in range(int(n)):
    cal = (int(s, 2) ^ hanten)
    count = 0
    while (cal != 0):
        cal = calc(cal)
        count = count + 1
    print(count)
    hanten = hanten >> 1

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n=int(input())
x=input()
X=[0]*n
N=0
P=[]
for i in range(1,n+1):
    cnt = 0
    while i!=0:
        if i%2==1:
            cnt += 1
        i//=2
    P.append(cnt)
for i in range(n):
    X[i]=int(x[i])
    N+=(X[i])*(2**(n-i-1))
Y=X.copy()
for i in range(n):
    Ni=0
    Y[i]=int(Y[i]==0)
    if Y[i]==1:
        Ni=N+2**(n-i-1)
    else:
        Ni=N-2**(n-i-1)
    Z=Counter(Y)
    pop=Z[1]
    cnt = 0
    while Ni!=0:
        Ni=Ni%pop
        pop=P[Ni-1]
        cnt+=1
    print(cnt)
    Y[i]=int(Y[i]==0)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = int(input(), 2)
# したからi番目を反転
def reverse_x(i,x):
    a = 1<<i
    b = x^a
    return b
def f(n):
    def popcount(n):
        c = bin(n).count("1")
        return c
    count = 0
    while n != 0:
        n = n % popcount(n)
        count += 1
    return count
for i in range(N):
    print(f(reverse_x(N-i-1,X)))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def main():
    def f(n):
        if n == 0:
            return 0
        if d[n] != 0:
            return d[n]
        d[n] = f(n % sum(list(map(int, bin(n)[2:])))) + 1
    def rev(i):
        nonlocal c, X
        if X[i] == '0':
            c += 1
            X[i] = '1'
        else:
            c -= 1
            X[i] = '0'


    n = int(input())
    X = list(input())
    d = defaultdict(int)
    d[0] = 0
    printl = lambda x, y: print(d[x % y] + 1 if x != 0 else 0)
    for i in range(1, n):
        f(i)
    c = sum(list(map(int, X)))
    rev(0)
    m = int(''.join(X), 2)
    printl(m, c)
    for i in range(n - 1):
        rev(i)
        rev(i + 1)
        m = int(''.join(X), 2)
        printl(m, c)





if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
X=list(input())
m=0
onecount=0
for i in range(N):
  d=N-1-i
  if X[i]=='1':
    m+=2**d
    onecount+=1

def f(x):
  result={}
  result[0]=0
  result[1]=1
  if x in result:
    return result[x]
  else:
    a=str(bin(x))
    b=a.count('1')
    d=x%b
    return f(d)+1
  
for i in range(N):
  d=N-1-i
  if X[i]=='0':
    D=m+2**d
  else:
    D=m-2**d
  print(f(D))

Submission status: Time Limit Exceeded

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

popcount = {}
for i in range(n):
    inv_x = x.copy()
    inv_x[i] = "0" if x[i] == "1" else "1"
    k = int("".join(inv_x), 2)
    count = 0
    while k > 0:
        count += 1
        if k not in popcount:
            popcount[k] = bin(k)[2:].count("1")
            k %= bin(k)[2:].count("1")
        else:
            k %= popcount[k]
    print(count)

Submission status: Time Limit Exceeded

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

sdict = dict()
def popcount(ni):
    n_b = str(bin(ni))
    return n_b.count("1")

x_i = int(x, 2)
solve = 0
for i in range(n):
    if x[i] == "0":
        solve = x_i+2**(n-i-1)
    else:
        solve = x_i-2**(n-i-1)
    count = 0
    solved = []
    while solve > 0:
        if solve in sdict:
            count += sdict[solve]
            break
        else:
            solved.append(solve)
            solve = solve % popcount(solve)
            count+=1

    c = count
    for i in solved:
        sdict[i] = c
        c-=1

    print(count)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy

def popcount(N):
  cnt = 0
  flag = True
  while not(N == 0 or N == 1):
    cnt += N % 2
    N = N // 2
  return cnt + N

N = int(input())
X = input()
pd = dict()
cd = dict()
sum = 0

for i, x in enumerate(X[::-1]):
  if x == "1":
    sum += 2 ** i
    
for n in range(N-1, -1, -1):
  if (sum >> n & 1) == 1:
    x = sum - 2**n
  else:
    x = sum + 2**n
  
  cnt = 0
  flag = True
  ini = deepcopy(x)
  while x != 0:
    if cd.get(x):
      flag = False
      cd[ini] = cnt + cd[x]
      print(cd[ini])
      break
    cnt += 1
    if pd.get(x):
      x = x % pd[x]
    else:
      pd[x] = popcount(x)
      x = x % pd[x]
  
  if flag:
    cd[ini] = cnt
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = input()
cnt = x.count("1")

f = {0:0, 1:1, 2:1}

for i in range(3, 10**6):
    f[i] = f[i%(str(bin(i)).count("1"))] + 1


for i in range(n)[::-1]:
    xm = int(x, 2)
    if (xm >> i)%2 == 0:
        xm += 2**i
    else:
        xm -= 2**i
    if xm in f:
        print(f[xm])
    else:
        xm %= str(bin(xm)).count("1")
        print(f[xm] + 1)

Submission status: Time Limit Exceeded

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

for i in range(n):
    ith=s[i]
    j=n-(i+1)

    if(ith=='1'):
        y=x-2**j
    
    else:
        y=x+2**j
        

    c=0
    nos=bin(y)[2:].count('1')
    while(y>0):
        #print('a',y)
        y=y%nos
        z=bin(y)[2:]
        nos=z.count('1')
        c+=1
    print(c)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    #n=int(input())
    #a,b=map(int,input().split())
    #x=list(map(int,input().split()))
    #a=[list(map(lambda x:int(x)%2,input().split())) for _ in range(h)]

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

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
x = input()
for i in range(len(x)):
    a = x
    a = a[:i]+str(int(a[i]=='0'))+a[i+1:]
    aD = int(a,2)
    times = 0
    while not aD == 0:
        pop = 0
        for i in a: 
            if i == '1':
                pop += 1
        aD = aD%pop    
        a = bin(aD)[2:]
        times += 1
    print(times)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = int(input())
m = int(str(x), 2)
def pop(i):
  b = format(i, "b")
  array = list(map(int, b))
  return sum(array)
for i in range(n):
  y = m ^ (1<<(n-1-i))
  count = 0
  while y > 0:
    y = y % pop(y)
    count += 1
  print(count)