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())
pre = [-1]*(N+1)
pre[0]=0
for i in range(1,N+1):
  ans = 0
  tmp = i
  while True:
    if pre[tmp]!=-1:
      pre[i]=ans+pre[tmp]
      break
    cnt = bin(tmp).count('1')
    ans+=1
    tmp = tmp%cnt
#print(pre)

X = int(input(),2)
S = sum([X>>j&1 for j in range(N)])

ans = []
for i in range(N):
  if X>>i&1:
    s2 = S-1
    if s2 == 0:
      ans.append(0)
      continue
    x2 = X-pow(2,i,s2)
  else:
    s2 = S+1
    x2 = X+pow(2,i,s2)
  amari = x2%s2
  ans.append(1+pre[amari])
for i in range(N-1,-1,-1):
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

def complement(c):
    if c=='1':
        return '0'
    else:
        return '1'

H = {}

def pop(n):
    return "{0:b}".format(n).count('1')
def toZero(n):
    if n==0:
        return 0
    if n==1:
        return 1
    if n in H:
        return H[n]
    r = 1 + toZero(n%pop(n))
    H[n] = r
    return r

[N] = getInts()
X = input()
Xi = int(X, 2)
X = list(X)

i=0
p = pop(Xi)
if Xi > 1:
    while 2**i < Xi:
        if p+1 > 0:
            toZero(2**i%(p+1))
        if p-1 > 0:
            toZero(2**i%(p-1))
        i+=1
for i in range(N):
    X[i] = complement(X[i])
    n = int("".join(X),2)
    print(toZero(n))
    X[i] = complement(X[i])

Submission status: Time Limit Exceeded

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

num_of_1 = x.count("1")

first = int(x, 2)

def f(x):
    if x == 0:
        return 0
    return 1 + f(x % bin(x).count('1'))

if num_of_1 == 1:
    for i in range(n):
        if x[i] == '1':
            print(0)
        elif i == n-1:
            print(2)
        else:
            print(1)
    exit()

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

    ans = 0

    a = first + 2 ** (n - i - 1) if x[i] == "0" else first - 2 ** (n - i - 1)

    a = a % temp_num_of_1

    ans += 1 + f(a)

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=str(input())
pop=[0]
a=1
b=0
for i in range(1,n):
    ni=0
    a=i
    while a:
        a&=(a-1)
        ni+=1
    nii=i%ni
    pop.append(pop[nii]+1)

x1=int(x,2)    

a=x1
popi=0
while a:
    a&=(a-1)
    popi+=1
x2=popi

for i in range(n):
    xi=(2**(n-1)>>i)^x1
    if (2**(n-1)>>i)&x1:
        x3=x2-1
    else:
        x3=x2+1
    popi=0
    if xi!=0:
        xi=xi%x3
        ans=pop[xi]+1
        print(ans)
    else:
        print(0)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    def popcount(n):
        res = 0
        for bit in range(len(bin(n)) - 2):
            res += (n >> bit) & 1
        return res

    n = int(input())
    X = int(input(), 2)
    cnt_one = 0
    for i in range(n):
        cnt_one += (X >> i) & 1

    for i in range(n):
        if (X >> (n - i - 1)) & 1:
            cnt = cnt_one - 1
            x = X - pow(2, n - i - 1)
        else:
            cnt = cnt_one + 1
            x = X + pow(2, n - i - 1)
        res = 0
        while x:
            if res != 0:
                cnt = popcount(x)
            x %= cnt
            res += 1
        print(res)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
def popcount(n):
    return bin(n).count("1")
  
def f(n):
  if n==1:
    return 1
  if n==0:
    return 0
  #s=bin(n)[1:]
  r=n%popcount(n)
  return (f(r)+1)

def f2(n,pc,mp):
  if n==1:
    return 1
  if n==0:
    return 0
  #s=bin(n)[1:]
  r=n%(pc+mp)
  return (f(r)+1)

  
n=int(input())
x=input()
#x=np.array([y for y in x])
x_num=int(x,2)
#x_len=n
n+=1
#n_2=2**n
n+=-1
pc=x.count("1")
mp=0
for m in range(n):
  #print(2**(n-m-1))
  if x[m]=="1":
    r=x_num-2**(n-m-1)
    #print("PLUS")
    mp=-1
  else:
    r=x_num+2**(n-m-1)
    mp=1
  #print(r)
  
  print(f2(r,pc,mp))

Submission status: Time Limit Exceeded

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue
#import numpy as np
# sympy as syp(素因数分解とか)
Mod = 1000000007
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1] 
for i in range(2, 10**5 + 1):
    fact.append((fact[-1] * i) % Mod)
    inv.append((-inv[Mod % i] * (Mod // i)) % Mod)
    factinv.append((factinv[-1] * inv[-1]) % Mod)
    
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % p
    
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[y] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)
def pow_k(x, n):

    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x
def main():  #startline-------------------------------------------
    n = int(input())
    x = input()
    xint = int(x, 2)
    popcount = x.count("1")
    def countbin(i,popcount):  #f(x)を求める関数
        cnt = 0
        while i != 0:
            i %= popcount
            cnt += 1
            popcount = bin(i).count("1")
        return cnt
    for i in range(len(x)):
        if x[i] == "0":
            print(countbin(xint + pow_k(2,n - i - 1),popcount+1))
        else:
            print(countbin(xint - pow_k(2,n - i - 1),popcount-1))

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

Submission status: Time Limit Exceeded

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

def solve(a, pc):
    if pc == 0:
        return 0
    elif pc == 1:
        return 1
    return solve(a % pc, bin(a % pc).count('1')) + 1
        
pc = bin(x).count('1')
pc_p = pc + 1
pc_m = pc - 1
for i in reversed(range(n)):
    a = 1 << i ^ x
    if x >> i & 1 == 1:
        print(solve(a, pc_m))
    else:
        print(solve(a, pc_p))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def binbin(binn):
    return bin(binn).count("1")

def popcount(n):
    if n == 0:
        return 0
    return 1 + popcount(n % binbin(n))

def main():
    N = int(input())
    X = input().strip()

    x = 0
    for i in range(N):
        if X[-1 - i] == '1':
            x += pow(2, i)
    xc = binbin(x)
    x1 = x % (xc + 1)
    if xc == 1:
        x2 = -1
    else:
        x2 = x % (xc - 1)
    for i in range(N):
        z = pow(2, N - i - 1)
        if X[i] == '0':
            if x + z == 0:
                print(0)
            else:
                print(1 + popcount((x + z) % (xc + 1)))
        else:
            if x - z == 0:
                print(0)
            else:
                print(1 + popcount((x - z) % (xc - 1)))



    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, X = open(0).read().split()
n = int(n)
x = int(X, 2)
X = list(map(int, X))

def popcount(q):
    c = 0
    while q:
        q, r = divmod(q, 2)
        c += r
    return c

ma = 5*10**5
dp = [0] * ma
for i in range(1, ma):
    dp[i] = dp[i%popcount(i)]+1

c = popcount(x)
a = x % (c+1)
if c == 1:
    for i in range(n):
        if X[i]:
            print(0)
        else:
            print(dp[(a + pow(2, n-i-1, c+1)) % (c+1)] + 1)
else:
    b = x % (c-1)
    for i in range(n):
        if X[i]:
            print(dp[(b - pow(2, n-i-1, c-1)) % (c-1)] + 1)
        else:
            print(dp[(a + pow(2, n-i-1, c+1)) % (c+1)] + 1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import statistics
import itertools
from collections import deque
n=int(input())
x=str(input())
ans_lis =[0]*10000000

def p(s):
    ss=bin(s)
    ans=ss.count('1')
    return ans
def o(d):
    i=0
    while d!=0:
        i+=1
        q=p(d)
        d%=q
    return i

lis=[]
for i in range(n):
    num=x[i]
    lis.append(num)



lisss=lis
for g in range(n):
    
    if lisss[g]=='0':
        lisss[g]='1'
    
    else:
        lisss[g]='0'
    ans=0
   
    for j in range(n):
        if lisss[j]=='1':
            jj=int(j)
            ans+=2**(n-jj-1)
    print(o(ans))
    if lisss[g]=='0':
        lisss[g]='1'
    
    else:
        lisss[g]='0'

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
N = int(input())
X = input()

x_num = int(X, 2)
cnt1 = X.count('1')


def f(cnt):
    if (cnt > 0):
        pcount = p_count(cnt)
        return f(cnt % pcount) + 1
    else:
        return 0


def p_count(x):
    cnt = 0
    while (x > 0):
        if x % 2 != 0:
            cnt += 1
        x //= 2
    return cnt


def f1(x):
    cnt = 0
    while (x > 0):
        x %= bin(x).count('1')
        cnt += 1
    return cnt


for i, x in enumerate(list(X)):
    if (x == '1'):
        #x_num = int(''.join(X), 2)
        if (x_num - (2**(N-(i+1)))) != 0:
            print(f1((x_num - (2 ** (N - (i + 1)))) % (cnt1 - 1)) + 1)
        else:
            print(0)
    else:
        #x_num = int(''.join(X), 2)
        print(f1((x_num + (2 ** (N - (i + 1)))) % (cnt1 + 1)) + 1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = input()
popcount_X = X.count('1')
numX = int(X, 2)
a = numX % (popcount_X + 1)
b = numX % (popcount_X - 1) if popcount_X != 1 else 0
for i, x in enumerate(X, 1): #リストのインデクス，要素，第二引数に開始位置
    if x == '1' and popcount_X == 1:
        print(0); continue
    ans = 1
    if x == '1':
        temp = (b - pow(2, N - i)) % (popcount_X - 1)
    else:
        temp = (a + pow(2, N - i)) % (popcount_X + 1)
    while temp:
        p = format(temp, 'b').count('1') #2進数，1の個数
        temp %= p
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

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

def f(n):
  ans = 0
  while n:
    ans += 1
    n = n % format(n,"b").count("1")
  return ans
  


for i in range(N):
  if x[i] == '0':
    print(f(int(x[:i] + "1" + x[i+1:],2)))
  elif x[i] == '1':
    print(f(int(x[:i] + "0" + x[i+1:],2)))

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())
orig=0
for i in range(n):
    if lis[i]=="0":
        lis[i]=0
    else:
        lis[i]=1
orcount=sum(lis)
m1=0
m3=0
if orcount==1:
    for i in range(n):
        if lis[i]==1:
            m3=(m3+pow(2,n-i-1,orcount+1))
elif orcount>1:
    for i in range(n):
        if lis[i]==1:
            m1=(m1+pow(2,n-i-1,orcount-1))
            m3=(m3+pow(2,n-i-1,orcount+1))
        
        
m1=m1
m3=m3
#print(m1)
#print(m3)
#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 pow(2,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+pow(2,n-i-1)
        pr=orcount+1
        num=m3+pow(2,n-i-1,pr)
    else:
        #num=orig-pow(2,n-i-1)
        pr=orcount-1
        if pr!=0:
            num=m1-pow(2,n-i-1,pr)
    #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 = input()
ans = [1 for _ in range(N)]

def popcount(n):
  c = 0
  n = str(bin(n))[2:]
  for _ in range(len(n)):
    if n[_] == '1':
      c += 1
  return c

l = 0
for k in range(N):
  if X[k] == '1':
    l+=1
firstpop = [l for _ in  range(N)]

intN = int(X, 2)

start = []
if N == 1:
  if X[0] == '1':
    ia = 0
    firstpop[0] -= 1
  else:
    ia = 1
    firstpop[0] += 1
  start.append(ia)

else:
  for k in range(N):
    if X[k] == '1':
      ia = intN - 2**(N-k-1)
      firstpop[k] -= 1
    else:
      ia = intN + 2**(N-k-1)
      firstpop[k] += 1
    start.append(ia)

mp = l + 1
poplist = [0]
for _ in range(1, mp):
  poplist.append(popcount(_))


for k in range(N):
  if firstpop[k] == 0:
    ans[k] = 0
  else:
    start[k] %= firstpop[k]

for k in range(len(start)):
  for count in range(10*5):
    if start[k] == 0:
      ans[k] += count
      break
    else:
      start[k] = start[k] % poplist[start[k]]

for k in range(N):
  print(ans[k])

Submission status: Time Limit Exceeded

Solution code:
def readinput():
    n=int(input())
    x=input()
    return n,x

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

def f(n):
    #print(n)
    if n==0:
        return 0
    else:
        m=n%popcount(n)
        return f(m)+1

def main(n,x):
    intx=int(x,2)
    ans=[]
    b=1
    for i in range(n):
        y=intx^b
        ans.append(f(y))
        b=b*2
    return reversed(ans)


if __name__=='__main__':
    n,x=readinput()
    ans=main(n,x)
    for a in ans:
        print(a)

Submission status: Time Limit Exceeded

Solution code:
def solve(N,X):
    ans = []
    cnt = X.count("1")

    for i in range(N):
        if X[i] == "1":
            X[i] = "0"
            ans.append(cal(X,cnt-1,0))
            X[i] = "1"
        else:
            X[i] = "1"
            ans.append(cal(X,cnt+1,0))
            X[i] = "0"

    return ans

def cal(X,cnt,rec):
    if cnt == 0:
        return rec
    else:
        amari = 0
        for i in range(len(X)):
            if X[i] == "1":
                amari += pow(2,len(X)-i-1,cnt)
                amari %= cnt
        b = bin(amari)[2:]
        Y = [b[i] for i in range(len(b))]
        cnt = Y.count("1")
        return cal(Y,cnt,rec+1)

def main():
    N = int(input())
    X = list(input())

    ans = solve(N,X)
    for i in range(N):
        print(ans[i])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

num_of_1 = x.count("1")

first = int(x, 2)

def f(x):
    if x==0:
        return 0
    return 1+f(x%bin(x).count('1'))

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

    ans = 0

    if temp_num_of_1 > 0:
        a = first + 2 ** (n - i - 1) if x[i] == "0" else first - 2 ** (n - i - 1)

        a = a % temp_num_of_1

        temp = bin(a)[2:]

        ans += 1 + f(a)

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys #追加


n=int(input())
sys.setrecursionlimit(10**6*2)

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

one_cnt=s.count("1")


ans=[]

ans_memo=[0]*(2*(10**5)+2)
#print(ans_memo)
ans_memo[1]=1
ans_memo[2]=1

def DEF(x,cnt):
    global ans_memo
    #print(x,cnt,ans_memo)
    if x==0:
        return 0
    if x<2*(10**5)+1:    
        if ans_memo[x]!=0:
            return ans_memo[x]
        else:
            if x%(str(bin(x)).count("1"))==0:
                ans_memo[x]=1
                return 1
            else:
                tmp=DEF(x%(str(bin(x)).count("1")),cnt+1)+1
                ans_memo[x]=tmp
                return tmp
    else:
        if x%(str(bin(x)).count("1"))==0:
            return 1
        else:
            tmp=DEF(x%(str(bin(x)).count("1")),cnt+1)+1
            return tmp


ans=[]

for i in range(n):
    tmp=2**(n-i-1)
    tmp_num=X
    #1の時
    if tmp&tmp_num:
        tmp_num-=tmp
        if tmp_num==0:
            ans.append(0)
        else:
            tmp_num=tmp_num%(one_cnt-1)
            ans.append(DEF(tmp_num,1)+1)
        
    else:
        tmp_num+=tmp
        #print(bin(tmp_num),n-i-1)
        tmp_num=tmp_num%(one_cnt+1)
        ans.append(DEF(tmp_num,1)+1)

#print(ans_memo)

for item in ans:
    print(item)

Submission status: Time Limit Exceeded

Solution code:
def base10toN(num, base):
    converted_string, modstring = "", ""
    currentnum = num
    if not num:
        return '0'
    while currentnum:
        mod = currentnum % base
        currentnum = currentnum // base
        converted_string = chr(48 + mod + 7*(mod > 10)) + converted_string
    return converted_string
n=int(input())
x=input()
xint=int(x, 2)
ones=0
for i in range(n):
  if x[i]=='1':
    ones+=1
for i in range(n):
  counter=0
  if x[i]=='0':
    temp=xint+pow(2,n-1-i)
    temp1=ones+1
  else:
    temp=xint-pow(2,n-1-i)
    temp1=ones-1
  ans=0
  while temp!=0:
    temp=temp%temp1
    temp2=base10toN(temp,2)
    temp1=0
    for i in range(len(temp2)):
      if temp2[i]=='1':
        temp1+=1
    ans+=1
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
pre = [-1]*(N+1)
pre[0]=0
for i in range(1,N+1):
  ans = 0
  tmp = i
  while True:
    if pre[tmp]!=-1:
      pre[i]=ans+pre[tmp]
      break
    cnt = 0
    for j in range(100):
      if tmp>>j&1:
        cnt+=1
    ans+=1
    #if cnt==0: print(tmp)
    tmp = tmp%cnt
#print(pre)

X = int(input(),2)
S = sum([X>>j&1 for j in range(N)])

ans = []
for i in range(N):
  if X>>i&1:
    s2 = S-1
    x2 = X-2**i
  else:
    s2 = S+1
    x2 = X+2**i
  if s2 == 0:
    ans.append(0)
    continue
  amari = x2%s2
  #if amari >= N:
    #print(x2,s2,amari)
  ans.append(1+pre[amari])
for i in range(N-1,-1,-1):
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = input()
firstPopcount =  X.count('1')
firstV = int(X, 2)
xlen = len(X)
for i in range(1, N+1):
  if X[i-1] == '0':
    #b = X[:i-1]+'1'+X[i:]
    popcount = firstPopcount + 1
    v = firstV + 2** (xlen - (i-1)-1)
  else:
    #b = X[:i-1]+'0'+X[i:]
    popcount = firstPopcount - 1
    v = firstV - 2** (xlen - (i-1)-1)
  #v = int(b, 16)
  #print(v)
  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()

def popcount(n):
  return format(n,"b").count("1")
  

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


for i in range(N):
  if x[i] == '0':
    print(f(int(x[:i] + "1" + x[i+1:],2)))
  elif x[i] == '1':
    print(f(int(x[:i] + "0" + x[i+1:],2)))

Submission status: Time Limit Exceeded

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

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

n = int(X, 2)
c = X.count('1')
a = n % (c+1)
if c != 1:
  b = n % (c-1) + c - 1
for i in range(1, N+1):
  if X[i-1] == '0':
    p = (2**(N-i)) % (c+1)
    print(calc(a+p, c+1, 0))
  else:
    if c == 1:
      print(0)
    else:
      m = (2**(N-i)) % (c-1)
      print(calc(b-m, c-1, 0))

Submission status: Time Limit Exceeded

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

def f(n):
    k = 0
    while n != 0:
        k += 1
        pop = str(bin(n)).count("1")
        n = n%pop
    return k


for p in range(N):
    Xi = int(X,2) ^ 2**(N-p-1)
    print(f(Xi))

Submission status: Time Limit Exceeded

Solution code:
def bitcount(N):  # 立ってるbitの数
    bitcnt = [0]
    for _ in range(N):
        bitcnt += [i + 1 for i in bitcnt]
    return bitcnt


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

num, cnt = int(x, 2), x.count('1')
lbit = bitcount(18)
for i in range(n):
    ans = 1
    if x[i] == '0':
        ctmp = cnt + 1
        tmp = num % ctmp + pow(2, n - (i + 1), ctmp)
    elif x[i] == '1':
        if cnt == 1:
            print(0)
            continue
        ctmp = cnt - 1
        tmp = num % ctmp - pow(2, n - (i + 1), ctmp)
    tmp %= ctmp
    ctmp = lbit[tmp]
    while tmp > 0:
        ans += 1
        tmp %= ctmp
        ctmp = lbit[tmp]
    print(ans)

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 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())
    x = input()
    xList = list(x)
    k = len(xList) - 1
    for i in range(n):
        xList[i] = str(int(xList[i]) ^ 1)
        xNum = int("".join(xList), 2)
        print(f(xNum))
        xList[i] = str(int(xList[i]) ^ 1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
X = input()
n = len(X)
ans = 0
numX = X.count("1")
N = 2*(10**5)
table = []

def solve(numX,X):
    global ans
    if numX == 0:
        return 0
    y = int(X,2)%numX
    if y == 0:
        ans = 1
        return 0
    else:
        ans = 1 + table[y-1]

def make_table(numX,X):
    global ans
    ans += 1
    y = int(X,2)%numX
    if y == 0:
        return 0
    else:
        z = bin(y)[2:]
        make_table(z.count("1"),z)

for i in range(1,N+1):
    ans = 0
    aaa = bin(i)[2:]
    bbb = aaa.count("1")
    make_table(bbb,aaa)
    table.append(ans)

for i in range(n):
    ans = 0
    tmpX = ""
    tmp = ""
    if X[i] == "0":
        tmpnumX = numX + 1
        tmp = "1"
    else:
        tmpnumX = numX - 1
        tmp = "0"
    if i == 0:
        tmpX = tmp + X[1:]
    elif i == n-1:
        tmpX = X[:i] + tmp
    else:
        tmpX = X[:i] + tmp + X[i+1:]
    solve(tmpnumX,tmpX)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def resCount(n):
    tmp = bin(n).count('1')
    if tmp == 1:
        return 1
    elif tmp == 0:
        return 0
    else:
        return 1 + resCount(n % tmp)
N= int(input())
X = input()
Xi = int(X, 2)

for i in range(N):
    res, n = 1, Xi ^ (1<<(N-i-1))
    print(resCount(n))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


from functools import lru_cache

def binbin(binn):
    return bin(binn).count("1")

def popcount(n):
    if n == 0:
        return 0
    return 1 + popcount(n % binbin(n))

def main():
    N = int(input())
    X = input().strip()

    x = int(X, 2)
    xc = binbin(x)
    for i in range(N):
        z = pow(2, N - i - 1)
        if X[i] == '0':
            if x + z == 0:
                print(0)
            else:
                print(1 + popcount((x + z) % (xc + 1)))
        else:
            if x - z == 0:
                print(0)
            else:
                print(1 + popcount((x - z) % (xc - 1)))



    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=str(input())
pop=[0]
a=1
b=0
for i in range(1,n):
    ni=0
    a=i
    while a:
        a&=(a-1)
        ni+=1
    nii=i%ni
    pop.append(pop[nii]+1)
x1=0
for i in range(n):
    if int(x[i])&1:
        x1+=2**(n-1-i)

a=x1
popi=0
while a:
    a&=(a-1)
    popi+=1
x2=popi

for i in range(n):
    xi=(2**(n-1)>>i)^x1
    if (2**(n-1)>>i)&x1:
        x3=x2-1
    else:
        x3=x2+1
    popi=0
    if xi!=0:
        xi=xi%x3
        ans=pop[xi]+1
        print(ans)
    else:
        print(0)

Submission status: Time Limit Exceeded

Solution code:
import sys #追加

n=int(input())
sys.setrecursionlimit(10**6*2)

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

one_cnt=s.count("1")


ans=[]

ans_memo=[0]*(2*(10**5)+2)
#print(ans_memo)
ans_memo[1]=1
ans_memo[2]=1

def DEF(x,cnt):
    global ans_memo
    #print(x,cnt,ans_memo)
    if x==0:
        return 0
    if x<2*(10**5)+1:    
        if ans_memo[x]!=0:
            return ans_memo[x]
        else:
            if x%(str(bin(x)).count("1"))==0:
                ans_memo[x]=1
                return 1
            else:
                tmp=DEF(x%(str(bin(x)).count("1")),cnt+1)+1
                ans_memo[x]=tmp
                return tmp
    else:
        if x%(str(bin(x)).count("1"))==0:
            return 1
        else:
            tmp=DEF(x%(str(bin(x)).count("1")),cnt+1)+1
            return tmp


ans=[]

for i in range(n):
    tmp=2**(n-i-1)
    tmp_num=X
    #1の時
    if tmp&tmp_num:
        tmp_num-=tmp
        if tmp_num==0:
            ans.append(0)
        else:
            tmp_num=tmp_num%(one_cnt-1)
            ans.append(DEF(tmp_num,1)+1)
        
    else:
        tmp_num+=tmp
        #print(bin(tmp_num),n-i-1)
        tmp_num=tmp_num%(one_cnt+1)
        ans.append(DEF(tmp_num,1)+1)

#print(ans_memo)

for item in ans:
    print(item)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import numpy as np


def popcount(n):
    s = str(bin(n))[2:]
    return s.count("1")


@lru_cache(None)
def func(n):
    if n == 0:
        return 0
    return func(n % popcount(n)) + 1


def rev(s, i):
    result = np.copy(s)
    if result[i]=='0':result[i]='1'
    else:result[i]='0'
    return ''.join(result)

  
N = int(input())
X = input()
X_array = np.array(list(X))

for i in range(N):
    print(func(int(rev(X_array, i), 2)))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
W = input()
X = int(W, 2)
T = W.count("1")
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

a = X % (T-1) if T > 1 else 0
b = X % (T+1)

def mod(x: int, y: int) -> int:
  res = x % y
  if res < 0:
    res -= y
  return res

for i in range(0, N)[::-1]:
  n  = 0
  if W[N-i-1] == '1':
    n = T - 1
    if n == 0:
      print(0)
    else:
      print(f(mod(a - (2 ** i), n)) + 1)
  else:
    n = T + 1
    print(f(mod(b + (2 ** i), n)) + 1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = input()
ans = [0]*(n+1)

for i in range(1,n+1):
    s = format(i, 'b')
    c = s.count('1')
    a = i%c
    ans[i] += 1
    ans[i] += ans[a] 

one_cnt = x.count('1')
numx = int(x,2)

for i in range(n):
    temp = one_cnt
    if x[i]=='0':
        temp += 1
        num = numx%temp + pow(2,n-1-i,temp)
    else:
        if temp>1:
            temp -= 1
            num = numx%temp - pow(2,n-1-i,temp)
        else:
            print(0)
            continue
    print(ans[num%temp]+1)

Submission status: Time Limit Exceeded

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

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

if (z == x):
  u = n - 1
  d = n - 1
elif (o == x):
  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 and ans[i] != 0):
    return count + ans[i]
  elif (i == 0):
    return count
  else:
    return solve(popcount(i), count + 1)


def solve2(i, div):
  if (i <= 2 * 10**5):
    return ans[i]
  else:
    return ans[i % div] + 1


ans = [0] * (2 * 10 ** 5 + 1)
for i in range(1, 2 * 10 ** 5 + 1):
  ans[i] = solve(i, 0)
for i in range(n):  
  if(x[i] == '0'):
    print(solve2(X + 2 ** (n-i-1), u))
  else:
    print(solve2(X - 2 ** (n-i-1), d))

Submission status: Time Limit Exceeded

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


n = int(input())
X = input()
x = int(X, 2)
basecount = popcount(x)

pair = 1 << n-1
for bit in X:
    if bit == '1':
        Xi = x - pair
        mod = basecount - 1
    else:
        Xi = x + pair
        mod = basecount + 1
    pair //= 2

    if Xi:
        Xi %= mod
        count = 1
        while Xi:
            mod = popcount(Xi)
            Xi %= mod
            count += 1
        print(count)
    else:
        print(0)