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()
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:
N = int(input())
X = input()

#%%
def popcount(n):
    ans = 0
    temp = format(n, "b")
    for i in temp:
        if i == "1":
            ans += 1

    return ans

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

    return cnt

A = []
for i in range(N):
    if X[i] == "1":
        XX = list(X)
        XX[i] = "0"
        temp = f(int("".join(XX), 2))
        print(temp)
    elif X[i] == "0":
        XX = list(X)
        XX[i] = "1"
        temp = f(int("".join(XX), 2))
        print(temp)

Submission status: Time Limit Exceeded

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

value = int(X,2)
#print(value)
TFlist =[]
for i in range(N):
  if X[i] == '0':
  	TFlist.append(False)
  else:
    TFlist.append(True)
#print(TFlist)
p = sum(TFlist)


def count_ones_by_bin(num):
    bin_num = bin(num)[2:]
    count = 0
    for i in bin_num:
            count += int(i)
    return count
  
def popcount(n):
 # print("popcount",n)
  return (n  % count_ones_by_bin(n))

for i in range(N):
#  print("N", N)
  cnt = 0
  tmp = 0
  if p != 1 or (not TFlist[i]):
    if TFlist[i]: tmp = (value - (pow(2,(N-i-1), (p-1)))) % (p-1)
    else: tmp = (value +  pow(2,(N-i-1), (p+1) )  ) % (p+1)
    # print(tmp)
    cnt += 1
  while tmp != 0:
    cnt+= 1
    tmp = popcount(tmp)
  print(cnt)

Submission status: Time Limit Exceeded

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

#s="".join(list(map(str,lis)))
#print(s)
#sys.exit()
#print(lis)
#sys.exit()
orig=0
for i in range(n):
    if lis[i]=="0":
        lis[i]=0
    else:
        lis[i]=1
orcount=sum(lis)
beki=[1 for i in range(n+1)]
for i in range(n):
    beki[i+1]=beki[i]*2
#print(beki)
#print(lis)
for i in range(n):
    j=n-i-1
    if lis[i]==1:
        orig+=beki[j]
#print(orig)
dp=[0 for i in range(n+1)]
dp[1]=1
for i in range(1,n):
    #u=count1(i+1)
    count=0
    j=0
    while beki[j]<=i+1:
        if ((i+1)>>j) %2==1:
            count+=1
        j+=1
    z=1
    dp[i+1]=z+dp[(i+1)%count]
#print(dp)
for i in range(n):
    if lis[i]==0:
        num=orig+beki[n-i-1]
        pr=orcount+1
    else:
        num=orig-beki[n-i-1]
        pr=orcount-1
    #print(num,pr)
    if pr==0:
        print(0)
    else:
        print(1+dp[num%pr])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = int(input(), 2)
def pc(a, cnt):
    if int(a, 2) == 0:
        return cnt

    tmp = int(a, 2)%a.count("1")
    if tmp == 0:
        return cnt + 1
    else:
        a = bin(tmp)
        return pc(a[2:], cnt + 1)

for i in range(n):
    print(pc(bin(x^2**(n-i-1))[2:], 0))

Submission status: Time Limit Exceeded

Solution code:
#AIsing2020 d

import sys,math,collections,itertools,copy
input = sys.stdin.readline


def popcount(n):
    cou1 = 0
    while n>0:
        cou1+=n%2
        n = n//2
    return cou1

def count(nc):
    co = 0
    while nc >0:
        cou1 = popcount(nc)
        nc = nc%cou1
        co +=1
    return co

N = int(input())
X = int('0b'+input().rstrip(),2)

for i in range(N,0,-1):
    a = X
    if a>>(i-1) & 1:
        a -= 2**(i-1)
    else:
        a += 2**(i-1)
    co = count(a)
    print(co)

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
for i in range(X):
    Y_i=Y[:i]+str(abs(int(Y[i])-1))+Y[i+1:]
    if Y_i[i]=="1":
        b=d
    else:
        b=c
    print(pop_num2(int(Y_i,2),b,L,M))

Submission status: Time Limit Exceeded

Solution code:

def popcount(n):
    s = bin(n)
    return s.count("1")
def func(n,depth):
    if n == 0:
        return depth
    else:
        return func(n%popcount(n),depth+1)
def reverse(bin_n,i):
    i_bit_rev = bin(1<<i)
    return bin_n^int(i_bit_rev,2)
  
N = int(input())
X=int(input(),2)
for i in range(N):
    ans = func(reverse(X,N-i-1),0)
    print(ans)

Submission status: Time Limit Exceeded

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

#N = 3
#X = '011'

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

def func(n, l):
    if n == 0:
        return l
    n = n % popcount(n)
    return func(n, l+1)

list_X = list(X)
for i in range(N):
    #Xのi桁目を反転したbinary
    x = copy.copy(list_X)
    if x[i] == '0':
        x[i] = '1'
    else:
        x[i] = '0'
    z = int(''.join(x), 2)
    print(func(z, 0))

Submission status: Time Limit Exceeded

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

def f(x):
    global count
    count = 0
    popcount(x)
    return count

def popcount(x):
    global count
    if x.count('1')==0:
        return
    else:
        count += 1
        popcount(bin(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:]

    print(f(bin_num))

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)]
    
    x = int(X, 2)
    for i, xi in enumerate(X):
        if xi == "0":
            temp = (x + 2**(N-i-1))
        else:
            temp = (x - 2**(N-i-1))

        if temp == 0:
            print(0)
        else:
            temp = temp % bin(temp).count("1")
            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:
# import math
# print(math.log(2*10**5))

n = int(input())
x = input()
z = 0
for i in range(n):
    z += 2**(n-i-1)*int(x[i])
num_1 = x.count("1")

for i in range(n):
    if x[i] == "0":
        tmp_num_1 = num_1 + 1
        tmp_z = 2**(n-i-1) + z
    elif x[i] == "1":
        tmp_num_1 = num_1 - 1
        tmp_z = -2**(n-i-1) + z
    counter = 0
    while tmp_z > 0:
        tmp_z = tmp_z % tmp_num_1
        tmp_num_1 = bin(tmp_z).count("1")
        counter += 1
    print(counter)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = list(map(int, input()))
# N = 2*10**5
# X = list(map(int, "10"*(N//2)))

Xp = sum(X)
        
# print(Xp)
a = 0
b = 0
# c = 0
# :N
for i, x in enumerate(X):
    i_reverse = N-i-1
    if Xp > 1:
        a = (a + x * (1<<i_reverse)) % (Xp-1)
    b = (b + x * (1<<i_reverse)) % (Xp+1)
    # c = (c + x * (1<<i_reverse))
    # print(bin(c))

# print(a, b)

# :N
for i in range(N):
    i_reverse = N-i-1
    if Xp > 1:
        m = ([a, b][X[i]==0] + [-1, 1][X[i]==0] * pow(2, i_reverse, [Xp-1, Xp+1][X[i]==0])) % [Xp-1, Xp+1][X[i]==0]
    else:
        if X[i]==0:
            m = (b + pow(2, i_reverse, Xp+1)) % (Xp+1)
        else:
            print(0)
            continue
    count = 1
    # print(i, ([a, b][X[i]==0], [-1, 1][X[i]==0]*(1<<i_reverse)), [Xp-1, Xp+1][X[i]==0], X[i]==0)
    # print(m)
    while m > 0:
        p = sum([int(c) for c in str(bin(m)[2:])])
        m = m % p
        count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
dp = { 0:0, 1:1, 2:1 }
N = int(sys.stdin.readline().strip())
X = sys.stdin.readline().strip()

def f(num):
    if num in dp:
        return dp[num]
    
    b = bin(num)
    popcount = b.count('1')
    
    if num % popcount == 0:
        dp[num] = 1
    else:
        dp[num] = 1 + f(num % popcount)

    return dp[num]

nX = int(X, 2)
for i in range(0, N):
    if X[i] == '0':
        print(f(nX + 2**(N-i-1)))
    else:
        print(f(nX - 2**(N-i-1)))

Submission status: Time Limit Exceeded

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

sys.setrecursionlimit(20000000)

def yn(b):
    print("Yes" if b==1 else "No")
    return

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

def resolve():
    readline=sys.stdin.readline

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

    #pc=[0]*(10**5+1)
    #for i in range(1,10**5):
    #    pc[i]=count_ones_by_bin(i)
    amr1=[0]*((10**5)*2 + 5)
    amr2=[0]*((10**5)*2 + 5)
    bits=[False]*((10**5)*2 + 5)
    pc=[-1]*((10**5)*2 + 5)
    bcnt=0
    j=0
    for i in x:
        if int(i)==1:
            bcnt += 1
            bits[j]=True
        j+=1

    base1=0
    base2=0
    for i in range(n):
        jo=n-i-1
        amr1[i]=pow(2,jo,bcnt+1)
        if (bcnt-1)==0:
            amr2[i]=pow(2,jo)
        else:
            amr2[i]=pow(2,jo,bcnt-1)
        if bits[i]==True:
            base1+=amr1[i]
            base2+=amr2[i]
    for i in range(n):
        ans=0
        if bits[i]==True: #1->0
            if (bcnt-1)==0:
                base=0
            else:
                base=(base2-amr2[i])%(bcnt-1)
                ans+=1
        else:
            base=(base1+amr1[i])%(bcnt+1)
            ans+=1
        
        while base > 0:
            if pc[base]==-1:
                pc[base]=count_ones_by_bin(base)
            base=base%pc[base]
            ans+=1
        print(ans)
    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = input()
m = x.count('1')
def f(x, m, cnt=0):
    if x == 0:
        return cnt
    x %= m
    m = bin(x).count('1')
    cnt += 1
    return f(x, m, cnt) 

for i in range(n):
    if x[i] == '0':
        print(f(int(x[:i] + '1' + x[i+1:], 2), m+1))
    else:
        print(f(int(x[:i] + '0' + x[i+1:], 2), m-1))

Submission status: Time Limit Exceeded

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

def calc(num, cnt, ans):
  if cnt == 0:
    ans += 1
    return ans
  mod = num % cnt
  if mod == 0:
    ans += 1
    return ans
  else:
    ans += 1
    cnt = bin(mod).count('1')
    return(calc(mod, cnt, ans))

n = int(X, 2)
c = X.count('1')
for i in range(1, N+1):
  num = n
  cnt = c
  if X[i-1] == '0':
    num += 2**(N-i)
    cnt += 1
    print(calc(num, cnt, 0))
  else:
    num -= 2**(N-i)
    cnt -= 1
    if num == 0:
      print(0)
    else:
      print(calc(num, cnt, 0))

Submission status: Time Limit Exceeded

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

dp = [0] * 200001


def popcount(n: int):
    bin_n = bin(n)
    return str(bin_n).count('1')


for i in range(N):
    count = 0
    if X[i] == '1':
        tmp = int(X)
        tmp -= 10 ** (N - i - 1)
    else:
        tmp = int(X)
        tmp += 10 ** (N - i - 1)

    tmp = int(str(tmp), 2)

    while True:
        if tmp == 0:
            print(count)
            break
        else:
            count += 1
            tmp = tmp % popcount(tmp)
            origin = tmp
            if tmp == 0:
                dp[origin] = count
                print(count)
                break
            elif tmp == 1:
                dp[origin] = count + 1
                print(count + 1)
                break
            elif tmp == 2:
                dp[origin] = count + 1
                print(count + 1)
                break
            elif dp[tmp] != 0:
                dp[origin] = count + dp[tmp]
                print(count + dp[tmp])
                break
            else:
                count += 1
                tmp = tmp % popcount(tmp)

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 = []
	mem = {}
	for i in range(N):
		oct = int(X, 2)
		ttt = 2**(N-i-1)

		if X[i] == "1":
			oct -= ttt
		else:
			oct += ttt

		#oct = int(tmpX, 2)
		oct_mae = oct

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

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

		ans.append(ans_tmp)

	for i in ans:
		print(i)
	#print(mem)

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

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

Submission status: Time Limit Exceeded

Solution code:
def popcount(n):
    cnt = 0
    for i in range(n):
        if ((n >> i) & 1):
            cnt +=1
    return cnt

def f(n):
    cnt = 0
    while True:
        if n == 0:
            break
        n = n % popcount(n)
        cnt += 1
    return cnt

def numChange(list, i):
    num = 0
    j = 0
    while True:
        if i < 0:
            break
        num += int(list[i]) * pow_r(2, j)
        i -= 1
        j += 1
    return num

def pow_r(x, n):
    if n == 0:
        return 1
    if n % 2 == 0:
        return pow_r(x ** 2, n // 2)
    else:
        return x * pow_r(x ** 2, (n - 1) // 2)

if __name__ == "__main__":
    n = int(input())
    xList = list(input())
    k = len(xList) - 1
    for i in range(n):
        if xList[i] == '0':
            xList[i] = '1'
        else:
            xList[i] = '0'
        xNum = numChange(xList, k)
        print(f(xNum))
        if xList[i] == '0':
            xList[i] = '1'
        else:
            xList[i] = '0'

Submission status: Time Limit Exceeded

Solution code:
# D Anything Goes to Zero

n = int(input())
x = input()
for i in range(n):
  xi = int(x, 2)
  xi = xi ^ (1 << n-i-1)

  ans = 0
  while xi != 0:
    xi = xi % bin(xi).count("1")
    ans += 1
  print(ans)

Submission status: Time Limit Exceeded

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

'''

'''

def convert_to_int(b):
    res = 0
    for i in reversed(range(len(b))):
        res += 2**i
    return res


from math import floor, log
def get_popcount(x):
    if x == 0:
        return 0

    count = 0
    exp = floor(log(x, 2))
    while x:
        c = 2**exp
        if x >= c:
            x -= c
            count += 1
        exp -= 1
    return count

def sim(cur, popcount):
    count = 0
    while cur != 0:
        cur %= popcount
        count += 1
        popcount = get_popcount(cur)
    return count


def solve(n, x):
    res = 0
    popcount = sum(1 if s == "1" else 0 for s in x)
    tot = int(x, 2)
    exp = n-1

    for i in range(n):
        if x[i] == "0":
            print(sim(tot+2**exp, popcount+1))
        else:
            print(sim(tot-2**exp, popcount-1))
        exp -= 1



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

Submission status: Time Limit Exceeded

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

dp=[-1]*(n+1)

dp[0]=0
dp[1]=1

def cou(num):
    ans = 0
    while num>0:
        ans+=num%2
        num//=2
    return ans

def fun(num,step):
    num2=num%cou(num)
    if dp[num2]!=-1:
        dp[num]=dp[num2]+step
    else:
        fun(num2,step+1)

for i in range(2,n+1):
    fun(i,1)

num1=''.join(x)
num2=int(num1,2)
su = sum(list(map(int,x)))

for i in range(n):
    num4=num2
    su2=su
    if x[i]=='1':
        num4-=2**(n-1-i)
        su2-=1
    else:
        num4+=2**(n-1-i)
        su2+=1
    if su2 == 0:
        print('0')
        continue
    elif num4<=n:
        print(dp[num4])
    else:
        num3=num4%su2
        print(dp[num3]+1)

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 = sum([1 for c in xs if c == "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())
Xinput=list(input())
Xs=[0]*N
for i in range(N):
  Xs[i]=Xinput

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

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

qdict={}
def f(nbin):
  n10=int(nbin,2)
  cnt=0
  while n10>0:
    if n10 not in qdict.keys():
      q=procount(n10)
      qdict[n10]=q
      n10=n10%procount(n10)
    else:
      n10=n10%qdict[n10]
    cnt+=1
  return cnt

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

Submission status: Time Limit Exceeded

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

su = s.count('1')
sun = int(s,2)


table = [0]*200001
table[1] = 1
for i in range(2,200001):
    table[i] = 1 + table[i % bin(i).count('1')]

def pow(n,e,mod):
    ret=1
    b=n
    while e > 0:
        if e % 2 == 1:
            ret = ret * b % mod
        b = b * b % mod
        e = e//2
    return ret

for i in range(n):
    if s[i] == '0':
        print(1+table[(sun+pow(2,n-1-i,su+1))%(su+1)])
    else:
        if su-1 == 0:
            print(0)
        else:
            print(1+table[(sun-pow(2,n-1-i,su-1)+su-1)%(su-1)])

Submission status: Time Limit Exceeded

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

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

def p(x):
    # x:str
    return x.count('1')

from functools import lru_cache

@lru_cache(maxsize=2 * 10 ** 6)
def f(n, k):
    b = bin(n) # binary str
    q = p(b[2:]) # 1の個数
    if q == 0:
        return k
    else:
        return f(n % q, k + 1)

nx = int(x, 2)
for i in range(n):
    if x[i] == '0':
        y = nx + pow(2, n - 1 - i)
    else:
        y = nx - pow(2, n - 1 - i) 
    print(f(y, 0))

Submission status: Time Limit Exceeded

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

N = int(input())
X = input()
listX = []
for j in X:
    listX.append(j) #Xをリスト化したやつ

for i in range(1,N+1):
    
    count = 0
    
    if listX[i-1] == '0':
        listX[i-1] = '1' 
        strX = ''.join(listX) #所定位置のビットを反転させて文字列化したやつ
        listX[i-1] = '0'
        x = int(strX, 2) #10進法にしたやつ
        while x > 0:
            x = x % popcount(x)
            count += 1
        print(count)
    
    else:
        listX[i-1] = '0'
        strX = ''.join(listX)
        listX[i-1] = '1'
        x = int(strX, 2)
        while x > 0:
            x = x % popcount(x)
            count += 1
        print(count)

Submission status: Time Limit Exceeded

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

val = 0
rui = 1
mod = 0

nagasa = 2*10**5+1
#nagasa = 5
d_li = [0]*(nagasa)

for i in range(1,nagasa):
    t_v = i
    t_m = bin(t_v).count("1")
    ans = 0
    while t_v != 0:
        if d_li[t_v] != 0:
            ans += d_li[t_v]
            break
        ans += 1
        t_v %= t_m
        #t_m = bin(t_v).count("1")
    d_li[i] = ans

#print(d_li)
#exit()
"""
for i in range(n):
    val += int(x[n-1-i])*rui
    rui *= 2
"""
val = int(x, 2)
#print(val)
#exit()

mod = bin(val).count("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:
    if t_v != 0:
        t_v %= t_m
        ans += 1
    
    ans += d_li[t_v]
    #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])

Submission status: Time Limit Exceeded

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

def f(n):
    return int(n.count("1"))
    
    
for i in range(N):
    counter = 0
    temp = X[:]
    if temp[i] == "0":
        temp[i] = "1"
    else:
        temp[i] = "0"
#######################
    
    while f(temp) != 0:
        counter += 1
        a = int(str(''.join(temp)), 2) % f(temp)
       
        
        temp = list(str(bin(a)))[:]
        

        
    print(counter)

Submission status: Time Limit Exceeded

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

n = int(input())
x = input()
c = ""
for i in range(n): 
    if x[i] == "1": c = "0"
    else: c = "1"
    print(f(int(x[:i] + c + x[i + 1:], 2)))

Submission status: Time Limit Exceeded

Solution code:

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

# def main():
n_ansl = [0]*(n)
for i in range(1,n):
# for i in range(1,20):
    cnt = 0
    one = bin(i).count("1")
    rem = i
    while rem != 0:
        one = bin(rem).count("1")
        rem = rem%one   
        cnt += 1
    n_ansl[i] = cnt


one_cnt = x.count('1')
# if one_cnt == 0:
#     for _ in range(n):
#         print(1)
#     exit()

c2bl = [1]*n
c2blp = [1]*n
c2blm = [1]*n

curr_2b = 1
curr_2b_p = 1
curr_2b_m = 1
curr_sum = 0
curr_sum_p1 = 0
curr_sum_m1 = 0

x = x[::-1]
# for i in range(n-1, -1, -1):
for i, curr_x in enumerate(x):
    c2bl[i] = curr_2b
    c2blp[i] = curr_2b_p
    c2blm[i] = curr_2b_m
    if x[i] == '1':
        curr_sum += curr_2b
        curr_sum_p1 += curr_2b_p
        curr_sum_m1 += curr_2b_m
        if one_cnt >0:
            curr_sum%=one_cnt
        curr_sum_p1%=(one_cnt+1)
        if one_cnt > 1:
            curr_sum_m1%=(one_cnt-1)
    curr_2b*=2
    curr_2b_p*=2
    curr_2b_m*=2
    if one_cnt > 0:
        curr_2b%=one_cnt
    curr_2b_p%=(one_cnt+1)
    if one_cnt > 1:
        curr_2b_m%=(one_cnt-1)



    
curr_2b = 1
curr_2b_p = 1
curr_2b_m = 1
ansl = [0]*(n)
# for i in range(n-1, -1, -1):
for i, curr_x in enumerate(x):
    if x[i] == '1':
        # diff = (-1)*curr_2b_m
        diff = (-1)*c2blm[i]
        if one_cnt > 1:
            ans = (curr_sum_m1 + diff)%(one_cnt-1)
            ansl[n-i-1] = n_ansl[ans]+1
        else:
            ansl[n-i-1] = 0
    else:
        # diff = curr_2b_p
        diff = c2blp[i]
        ans = (curr_sum_p1 + diff)%(one_cnt+1)
        ansl[n-i-1] = (n_ansl[ans]+1)
    # curr_2b *= 2
    # curr_2b*=2
    # curr_2b_p*=2
    # curr_2b_m*=2
    # curr_2b%=one_cnt
    # curr_2b_p%=(one_cnt+1)
    # if one_cnt > 1:
    #     curr_2b_m%=(one_cnt-1)


# print(ansl)
for a in ansl:
    print(a)

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from collections import defaultdict, deque


def solve(*args: str) -> str:
    n = int(args[0])
    X = list(args[1])

    ret = []
    dp = defaultdict(int)
    for i in range(n):
        Y = X.copy()
        Y[i] = '0' if Y[i] == '1' else '1'
        m = int(''.join(Y), 2)

        count = 0
        deq = deque()
        while m:
            deq.append(m)
            if 0 < dp[m]:
                count += dp[m]
                break

            m = m % bin(m).count('1')
            count += 1
        ret.append(str(count))

        while deq:
            dp[deq.popleft()] = count
            count -= 1
    return '\n'.join(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Time Limit Exceeded

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

from functools import lru_cache


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


cache = dict()

@lru_cache(maxsize=1000000)
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))
        ret = 1 + f(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:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

from functools import lru_cache
@lru_cache(None)
def dfs(X):
    if X == 0:
        return 0
    popcount = bin(X).count("1")
    if popcount == 1:
        return 1
    return dfs(X%popcount)+1

for i in reversed(range(0,n)):
    print(dfs(X^(1<<i) ))

Submission status: Time Limit Exceeded

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

def find(s):
    n = int(s,2)
    num_1 = s.count("1")
    cnt = 0
    while n != 0:
        n = n % num_1
        cnt += 1
        num_1 = bin(n).count("1")
    return cnt

for i in range(n):
    if x[i] == "0":
        if i < n -1:
            tmp = x[:i] + "1" +x[i+1:]
        else:
            tmp = x[:i] + "1"
    else :
        if i < n -1:
            tmp = x[:i] + "0" +x[i+1:]
        else:
            tmp = x[:i] + "0"

    print(find(tmp))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
X=list(input())#リスト分解

def popcount(n) :
    count=0
    while n>0 :
        Z=list(bin(n))
        z=Z.count("1")
        n=n%z
        count+=1
    print(count)


for i in range(len(X)) :
    if X[i]=="1" :
        X[i]="0"
        x="".join(X)
        n=int(x,2)
        popcount(n)
        X[i]="1"

    if X[i]=="0" :
        X[i]="1"
        x="".join(X)
        n=int(x,2)
        popcount(n)
        X[i]="0"

Submission status: Time Limit Exceeded

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

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

k = [0,1,1,2,1,2,1,2,1,2,1,2,1,2,2,3,1,2,1] #18まで
one = [0]*N

c = 0
for i in range(N):
    if X[i] == "1":
        c += 1
for i in range(N):
    if X[i] == "1":
        one[i] = c-1
    else:
        one[i] = c+1
#print(one)

b1 = bin_num = int(X, 2)

for i in range(N):
    if X[i] == "0":
        B1 = b1 + 2**(N-1-i)
    else:
        B1 = b1 - 2**(N-1-i)
    #print(B1)
    if B1 == 0:
        print(0)
        continue
    else:
        B2 = B1%one[i]
    x = format(B2, 'b')
    #print(x)
    S = len(bin(B2))
    c2 = popcnt1(B2)

    if c2 == 0:
        print(1)
    else:
        print(2+k[B2%c2])