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:
def popcount(n):
        temp = format(n,'b')
        return temp.count('1')

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

def bit_rev(x,i):
        return bin(x^(1<<i))

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

        for i in range(N):
                temp_X = bit_rev(X,N-i-1)
                print(f(int(temp_X,2)))

main()

Submission status: Time Limit Exceeded

Solution code:
n,x=int(input()),input()
o=x.count("1")
l=[0]*(o+1)
a=int(x,2)
for i in range(1,o+1):l[i]=l[i%bin(i).count("1")]+1
c=pow(2,n-1)
for b in x:
    if b=="1":
        k=a-c
        gg=o-1
    else:
        k=a+c
        gg=o+1
    if k:
        print(1+l[k%gg])
    else:print(0)
    c//=2

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = list(str(input()))
# popcount = X.count("1")

for n in range(1,N+1):
    temp = X[n-1]
    if X[n-1] == "0":
        X[n-1] = "1"
        # pop = popcount + 1
    else:
        X[n-1] = "0"
        # pop = popcount - 1
    pop = X.count("1")
    X_int = int("".join(X),2)
    X[n-1] = temp
    count = 0
    while X_int != 0:
        X_int = X_int % pop
        temp_list = list(str(bin(X_int)))
        pop = temp_list.count("1")
        count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
def f(n):
    if n == 0:
        return 0
    elif n in d:
        return d[n]
    else:
        popcount = str(bin(n)).count('1')
        d[n] = max(1, f(n % popcount) + 1)
        return d[n]

n = int(input())
x = list(map(str, (input())))
d = {}
for i in range(n):
    if x[i] == '1':
        x[i] = '0'
    else:
        x[i] = '1'
    s = ''.join(x)
    if x[i] == '1':
        x[i] = '0'
    else:
        x[i] = '1' 
    xx = int(s, 2)
    print(f(xx))

Submission status: Time Limit Exceeded

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


N = int(input())

AAA = [0]
for i in range(1, 2**N):
    AAA.append(AAA[i % popcount(i)] + 1)

X = int(input(), 2)

for i in range(N):
    Xi = X ^ (1 << (N-i-1))
    print(AAA[Xi])

Submission status: Time Limit Exceeded

Solution code:

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


def popcount(n):
  num=list(bin(n)[2:])
  num = [int(s) for s in num]
  return sum(num)

n_dic={1:1,2:1}

def f(first_n):
  i=0
  n=first_n
  while not n==0:
    if n in n_dic:
      n_dic[first_n]=n_dic[n]+i
      return n_dic[n]+i
    else:
      n = n % popcount(n)
      i+=1
  return i

for i in range(1,n+1):
  if x[i-1]=="0":
    tmp="1"
  else:
    tmp="0"
  X="0b"+x[:i-1]+tmp+x[i:]
  X=int(X,2)
  print(f(X))
#print(n_dic)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from collections import Counter

def count_ones_by_bin(num):
    bin_num = bin(num)[2:]
    count = 0
    for i in bin_num:
            count += int(i)
    return count



n=int(input())
x=input()
d={}
j=[]
for i in range(n-1,-1,-1):
  ans=0
  if x[i]=="1":
    y=x[:i]+"0"+x[i+1:]
  else:
    y=x[:i]+"1"+x[i+1:]
  c=int(y,2)
  a=int(y,2)

  while True:
    if a in d:
      j.append(d[a]+ans)
      break
    b=count_ones_by_bin(a)
    if b==0 or a==0:
      d[c]=ans
      j.append(ans)
      break
    a%=b
    ans+=1
for i in range(n-1,-1,-1):
  print(j[i])

Submission status: Time Limit Exceeded

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

d = [0 for _ in range(N)]
for i in range(1, N):
    v = i % bin(i)[2:].count("1")
    d[i] = d[v] + 1
   
for i in range(N):
    if X[i] == "0":
        x = X[:i] + "1" + X[i+1:]
    else:
        x = X[:i] + "0" + X[i+1:]
        
    val = int(x, 2)
    if val == 0:
        print(0)
    else:
        print(d[val % x.count("1")] + 1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X ='0b'+ input()
def popcount(n): #10進数をもらって10進数を返す
    n2 = bin(n)
    counter_1 = 0
    for i in range(len(str(n2))):
        
        if str(n2)[i] == '1':
            counter_1 +=  1
    return counter_1

def anything(n): #2進数をもらってcounter 10進数を返す
    #print(n)
    n10 = int(n,0)
    counter = 0
    while n10 > 0:
        #print('popcount(n10)', popcount(n10))
        n10 = n10 % popcount(n10)
        counter +=1
        #print(n10)
    return counter
#print(anything(n))

line = []
for i in range(N):
    x = X
    if x[i+2] == '0':
        x = x[:i+2] +'1' +  x[i+3:]
    else:
        x = x[:i+2] +'0' +  x[i+3:]
        
    line.append(x)
for i in line:
    print(anything(i))

Submission status: Time Limit Exceeded

Solution code:
import sys 

readline = sys.stdin.readline 

N = int(input())
X_str= input()
X = list(X_str)
bit_count = X_str.count('1')

def popcount(number, bit_counter):
    num = number
    counter = 0
    while num != 0:
        bit_con = bit_counter if counter == 0 else bin(num)[2:].count('1')
        num = num % bit_con
        counter += 1

    return counter

for i in range(N):
    # ビットの反転
    x_copy = X.copy()
    bit_count_n = bit_count
    if x_copy[i] == '0':
        x_copy[i] = '1'
        bit_count_n += 1
    else:
        x_copy[i] = '0'
        bit_count_n -= 1

    bit_int = int("".join(x_copy), 2)

    print(popcount(bit_int, bit_count_n))

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")
    memo2 = {}

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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


def saiki(i, count):
    if i == 0:
        return count
    else:
        count_saiki = count
        i_bin = str(bin(i))
        i_bin_one = i_bin.count("1")
        ni = i % i_bin_one
        count_saiki += 1
        return saiki(ni, count_saiki)

x_lis = []
for i in range(n):
    x_copy = copy.copy(x)
    if x[i] == "1":
        x_copy[i] = "0"
    else:
        x_copy[i] = "1"
    x_lis.append("".join(x_copy))

for xi in x_lis:
    xi_int = int(xi, 2)
    count = 0
    print(saiki(xi_int, count))

Submission status: Time Limit Exceeded

Solution code:
import copy
def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f

N = int(input())
X = list(map(int,input()))
stri = ''.join(map(str, X))
num = int(stri, 2)
count_1 = popcount(num)
count_1_base = count_1
# print(count_1)
for i in range(N):
    temp = copy.copy(X)
    count_1 = count_1_base
    if(temp[i] == 0):
        temp[i] =  1
        count_1 += 1
    else:
        temp[i] =  0
        count_1 -= 1
    stri = ''.join(map(str, temp))
    num = int(stri, 2)
    i = 0
    for i in range(1000000):
        if(count_1 == 0):
            i -= 1
            # print(num)
            break
        surplus = num%count_1
        if(surplus == 0):
            break
        num = surplus
        count_1 = popcount(num)
    print(i+1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = input()
for i in range(n):
  s = x[:i] + chr(97 - ord(x[i])) + x[i + 1:]
  n = int(s, 2)
  r = 0
  while True:
    m = s.count('1')
    if m == 0:
      break
    n %= m
    s = bin(n)
    r += 1
  print(r)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = input()
keep = X
cou = 0
def popcount(N, X, time):
    if(N==0):
        return print(time)
    N = N % X.count('1')
    X = format(N, 'b')
    popcount(N, X, time+1)
for i in range(N):
    if(X[i:i+1] == '0'):
        X = X[:i] + '1' + X[i+1:]
    elif(X[i:i+1] == '1'):
        X = X[:i] + '0' + X[i+1:]
    num = int(X, 2)
    popcount(num, X, cou)
    X = keep
    cou = 0

Submission status: Time Limit Exceeded

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))

# ===CODE===

eps = 10 ** (-9)


def main():
    def popcounter(n):
        cnt = 0
        if n == 0:
            return 0
        for _ in range(INF):
            tmp = bin(n).count("1")
            n = n % tmp
            cnt += 1

            if n == 0:
                return cnt

    n = ni()
    x = input()
    x_1 = x.count("1")

    num = int(x, 2)

    ans = []
    for i in range(len(x)):
        if x[len(x) - 1 - i] == "1":
            tmp_n = num - pow(2, i)
        else:
            tmp_n = num + pow(2, i)
        ans.append(popcounter(tmp_n))

    l = len(ans)
    for i in range(l - 1, -1, -1):
        print(ans[i])


if __name__ == '__main__':
    main()

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

x_count = popcount(x)

for i in range(n - 1, -1, -1):
    xi = toggl_ith_bit(x, i)
    if xi == 0:
        print(0)
        continue
    xi_count = x_count + 1 if (xi & (1 << i)) else x_count - 1
    cnt = 1
    xi %= xi_count
    while xi != 0:
        cnt += 1
        xi %= popcount(xi)
    print(cnt)

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
    v=N%b
    return pop_num(v,L[v],L)+1
    
def pop_num2(N,b,L,M):
    if N==0:
        return 0
    v=N%b
    return M[v]+1

M=[0]*200002
for i in range(1,200002):
    M[i]+=pop_num(i,L[i],L)
X=int(input())
Y=input()
d=bin_sum2(Y)+1
c=bin_sum2(Y)-1
e=int(Y,2)
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
        f=e+2**(X-1-i)
    else:
        b=c
        f=e-2**(X-1-i)
    print(pop_num2(f,b,L,M))

Submission status: Time Limit Exceeded

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

dp = {}

def popcount(n):
    if dp.setdefault(n, 0):
        return dp[n]
    b = format(n, 'b')
    dp[n] = b.count('1') 
    return dp[n]

def f(n):
    global ans
    if n==0:
        return 0
    ans += 1
    return f(n % popcount(n))

for i in range(len(X)):
    ans = 0
    t = X[:]
    t[i] = '0' if t[i]=='1' else '1'
    f(int("".join([c for c in t]), 2))
    print(ans)

Submission status: Time Limit Exceeded

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

for i in range(1, N+1):
  if X[i-1] == '0':
    b = X[:i-1]+'1'+X[i:]
  else:
    b = X[:i-1]+'0'+X[i:]
  popcount = b.count('1')
  v = 0
  for j in range(len(b)):
    v += int(b[j]) * 2**(len(b)-j-1)
  c = 0
  while v != 0:
    v = v % popcount
    c+= 1   
    popcount = bin(v).count("1")
  print(c)

Submission status: Time Limit Exceeded

Solution code:

N = int(input())
X = input()
ans_dic = {}

for n in range(N):
    s = list(X)
    if X[n] == "0":
        s[n:n+1] = "1" 
    else:
        s[n:n+1] = "0" 
    s = "".join(s)
    first_num  = int(s, 2)
    ans = 0
    num_list = []
    while True:
        one = list(s).count("1")
        num = int(s, 2)
        if one == 0:
            break

        if num in ans_dic:
            ans += ans_dic[num]
            ans_dic[first_num] = ans
            break

        amari = num % one
        num_list.append(num)
        if amari == 0:
            ans += 1
            for n in range(len(num_list)):
                ans_dic[num_list[n]] = ans - n
            break
        else:
            s = str(bin(amari))[2:]
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
    n = int(input())
    s = int(input(), 2)
    pc0 = bin(s).count("1")
    ans = []
    for i in range(n):
        k = 1 << (n - 1 - i)
        x = k ^ s
        if x > s:
            pc1 = pc0 + 1
        else:
            pc1 = max(1, pc0 - 1)
        cnt = 0
        while x > 0:
            if cnt == 0:
                pc = pc1
            else:
                pc = bin(x).count("1")
            x %= pc
            cnt += 1
        ans.append(cnt)
    print("\n".join(str(y) for y in ans))
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def popcount(x):
    global count
    if x==0:
        return
    else:
        count += 1
        x = bin(x)
        popcount(int(x, 2) % x.count('1'))

for i in range(len(x)):
    if x[i]=='1':
        bin_num = x[:i]+'0'+x[i+1:]
    else:
        bin_num = x[:i]+'1'+x[i+1:]
    bin_num = int(bin_num, 2)

    count = 0
    popcount(bin_num)
    print(count)

Submission status: Time Limit Exceeded

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

def fn(cnt, n):
    if n == 0:return 0
    n = n % sum(map(int, str(bin(n)).lstrip('0b')))
    cnt += 1
    return cnt + fn(0, n)
 
def calc(idx, xx):
    xx = ''.join([str(1-int(c)) if i == idx-1 else c for i, c in enumerate(xx)])
    num = int(xx, 2)
    return fn(0, num)
    
for i in range(1, N+1):
    print(calc(i, x))

Submission status: Time Limit Exceeded

Solution code:
from numba import njit

@njit('i8(i8)', cache=True)
def popcount(n):
    a = 0
    while n != 0:
        a += n & 1
        n >>= 1
    return a

@njit('i8(i8)', cache=True)
def fun(n):
    ops = 0
    while n:
        bits = popcount(n)
        n %= bits
        ops += 1
    return ops

def funwrap(n, pc):
    if n == 0:
        return 0
    return 1 + fun(n % pc)

n = int(input())
xs = list(map(int, input()))

from functools import reduce
sm = reduce(lambda x,y: x*2+y, xs)
pc = xs.count(1)

for i in range(n):
    df = 1 if xs[i] ^ 1 == 1 else -1

    dn = 1 << (n - (i + 1))
    smi = sm + dn * df
    pci = pc + df

    print(funwrap(smi, pci))

Submission status: Time Limit Exceeded

Solution code:
def convertbi_10(t):
    td=[]
    for a in t:
        td.append(int(a))
    td.reverse()
    n=0
    b=0
    for a in td:
        n=n+(2**b)*a
        b+=1
    
    return n

def convert10_bi(t):
    b=t
    a=1
    td=[]
    while(1):
        if b%(2**a)==2**(a-1):
            td.append('1')
            b=b-(2**(a-1))
        else:
            td.append('0')
        a+=1
        if b==0:
            break
    
    td.reverse()
    s=''
    for a in td:
        s=s+a


    return s

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

for i in range(n):
    
    k=0
    lock=0
    sd=x#convertbi_10(x)

    w=[]
    c=0
    for j in sd:
        if c==i:
            if j=='0':
                w.append('1')
            elif j=='1':
                w.append('0')
        else:
            w.append(j)
        c=c+1
    
    r=''
    for a in w:
        r=r+a
    
    s=convertbi_10(r)

    while s>0:
        m=0
        c=0
        l=convert10_bi(s)
        for b in l:
            if b=='1':
                m=m+1
            c=c+1
        
        s=s%m
        k=k+1
    
    print(k)

Submission status: Time Limit Exceeded

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

from functools import lru_cache


@lru_cache(maxsize=200000)
def popcount(bits: str):
    return len([elm for elm in bits if elm == '1'])


@lru_cache(maxsize=100000000000)
def mod(a, b):
    return a % b

@lru_cache(maxsize=1000000000)
def f(num):
    if num == 0:
        return 0
    else:
        # if not cache.get(num % pc, None) is None:
        #     return cache[num % pc]
        # pc = popcount('{:b}'.format(num))
        pc = popcount(''.join(sorted('{:b}'.format(num))))
        ret = 1 + f(mod(num, pc))
        # cache[num % pc] = ret
        return ret


def reverse_bit(bits: str, digit):
    def toggle(a):
        if a == '1':
            return '0'
        else:
            return '1'

    ret = list(bits)
    ret[digit-1] = toggle(bits[digit-1])
    return ''.join(ret)

def convert(x: str):
    ans = 0
    i = 0
    for elm in list(x)[::-1]:
        if elm == '1':
            ans += 2 ** i
        i += 1
    return ans


answers = {}

for i in range(1, N+1):
    bits = reverse_bit(X, i)
    # pc = popcount(bits)
    # print(f'# {bits} {convert(bits)} {pc}')
    x = convert(bits)
    if not answers.get(x, None) is None:
        print(answers[x])
        continue
    ret = f(x)
    answers[x] = ret
    print(ret)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def getInts():
    return [ int(x) for x in input().split() ]

cache2 = {}
def popcount(n):
    if n in cache2:
        return cache2[n]
    c = "{0:b}".format(n).count('1')
    cache2[n] = c
    return c

cache = {}
cache[0] = 0
def divide(n):
    originN = n
    count = 0
    if n in cache:
        return cache[n]
    while n>0:
        count += 1
        n = n%popcount(n)
    cache[originN] = count
    return count


def findX(X, i):
    s = list(X)
    if s[i]=='1':
        s[i]='0'
    else:
        s[i]='1'
    return int("".join(s),2)
    
def f(x,y,z):
    if (x,y,z) in cache:
        return cache[(x,y,z)]
    
    v =  x**2+y**2+z**2+x*y+y*z+z*x
    cache[(x,y,z)] = v
    return v

[N] = getInts()
X = input()
for i in range(N):
    xi = findX(X, i)
    print(divide(xi))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=input()
clist=[0,1,1,2,1,2,1,2,1,2,1,2,1,2,2,3]
for i in range(n):
    a=x
    if a[i]=="0":
        a=a[:i] + "1" + a[i+1:]
    else:
         a=a[:i] + "0" + a[i+1:]
    a2=int(a,2)
    c=0
    b=a2
    if a2==0:
        print(0)
        continue
    while b!=0:
        if b<=15:
            c+=clist[b]
            break
        z=0
        while a2!=0:
            if a2%2==1:
                z+=1
            a2=a2//2
        b=b%z
        a2=b
        c+=1
    print(c)

Submission status: Time Limit Exceeded

Solution code:
def popcount(n):
    base = 1
    count = 0
    
    while base <= n:
        if n & base:
            count += 1
        base <<= 1
    return count

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

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

base = 1 << (N - 1)
for _ in range(N):
    print(f(X ^ base))
    base >>= 1

Submission status: Time Limit Exceeded

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


def solve(N: int, X: str):
    def pc(n):
        return bin(n).count("1")

    def f(i):
        if i == 0 : return 0
        p = 0
        k = i
        while(k!= 0):
            t = k
            p+=1
            k = t % pc(t)
        return p
    
    # ts = [f(i) for i in range(2*10**5+1)]
    ts = {}
    for i in range(2*10**5+1):
        ts[i] = f(i)

    x = int(X, 2)
    px = X.count("1")
    for i, xi in enumerate(X):
        if xi == "0":
            temp = (x + 2**(N-i-1))
            l = px+1
        else:
            temp = (x - 2**(N-i-1))
            l = px-1

        if temp == 0:
            print(0)
        else:
            temp = temp % l
            print(ts[temp]+1)
    
    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:
N = int(input())
X = input()

d = {}
def popcount(s):
    if not s in d:
        cnt = 0
        for c in s:
            if c == '1':
                cnt += 1
        d[s] = cnt
    return d[s]

one = popcount(X)
K = int(X, 2)
for i in range(N):
    pop = one
    if X[i] == '1':
        pop -= 1
    else:
        pop += 1

    k = K
    bit = N-i-1
    if X[i] == '1':
        k -= 2**bit
    else:
        k += 2**bit
    #print(X[i], pop, k)
    ans = 0
    while k > 0:
        k %= pop
        pop = popcount(bin(k)[2:])
        ans += 1
        #print('  ', bin(k), pop, ans)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

memo = {0: 0}

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



ans = []

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

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

Submission status: Time Limit Exceeded

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

sum1=0

def solve():
    ans=[]

    for i in range(len(x)):
        if x[i]=="0":
            xx=x[:i]+"1"+x[i+1:]
        else:
            xx=x[:i]+"0"+x[i+1:]
        
        num=int(xx,2) #string=>bit int
        kaisuu=0

        while(num>0):
            bit_str=bin(num)
            num_list=Counter(bit_str)
            waru=num_list['1']

            num=num%waru
            kaisuu+=1
        
        ans.append(kaisuu)


    for i in range(len(ans)):
        print(ans[i])

    
if __name__ == "__main__":
     solve()

Submission status: Time Limit Exceeded

Solution code:
def func(x):
    cnt = 0
    while x > 0:
        val = str(bin(x)).count('1')
        x %= val
        cnt += 1
    return cnt
 
def main():
    N = int(input())
    s = input()
    for i in range(N):
        if s[i] == "0":
            str_x = s[:i] + '1' + s[(i+1):]
        else:
            str_x = s[:i] + '0' + s[(i+1):]
        print(func(int(str_x, 2)))
 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def popcount(x):
    count = 0
    while x != 0:
        count += x&1
        x = x>>1
    return count

x = int(s, 2)
ans = []
for i in range(n):
    y =  x
    if (x >> i) & 1 == 1:
        y -= 2**i;
    else:
        y += 2**i;
    count = 0
    while y != 0:
        y = y % popcount(y)
        count += 1

    ans.append(count)

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

Submission status: Time Limit Exceeded

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

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

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

jisho = ["yet"]*n
for i in range(n):
    if x[i]=="0":
        pop = popcount0+1
        intxi = intx+pow(2,n-i-1)
    else:
        x[i] = "0"
        pop = popcount0-1
        intxi = intx-pow(2,n-i-1)
        
    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(intxi)
            c+=1
        print(c)
        #print()
#        print("f(n)=",c)

Submission status: Time Limit Exceeded

Solution code:
#! /Library/Frameworks/Python.framework/Versions/3.7/bin/python3
import sys
sys.setrecursionlimit(10 ** 6)

n = int(input())
x = input()
z = '1' * n
o = '0' * n

if (z == x):
  u = n - 1
  d = n - 1
elif (z == o):
  u = 1
  d = 1
else:
  tmp = len(list(filter(lambda x: x == '1', x)))
  u = tmp + 1
  d = tmp - 1


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 <= 2 * 10**5 + 1 and ans[i] != 0):
    return count + ans[i]
  elif (i == 0):
    return count
  else:
    return solve(popcount(i), count + 1)


ans = [0] * (2 * 10 ** 5 + 1)
for i in range(1, 2 * 10 ** 5):
  ans[i] = solve(i, 0)
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:
n = int(input())
x = input()
for i in range(n):
    num = x[:i]
    if x[i] == '0':
        num += '1'
    else:
        num += '0'
    num += x[i + 1:]
    #print(num)
    ans = 0
    pop = num.count('1')
    if pop == 0:
        print(0)
        continue
    num = int(num, 2) % pop
    num = bin(num)
    ans = 1
    #print(num)
    while int(num, 2) != 0:
        pop = num.count('1')
        num = int(num, 2) % pop
        num = bin(num)
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

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(19):
            if (x>>j)&1:
                r+=1
            if x>>j==0:
                break
        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)