Problem:


Score : 400 points

Problem Statement

Let \mathrm{popcount}(n) be the number of 1s in the binary representation of n.
For example, \mathrm{popcount}(3) = 2, \mathrm{popcount}(7) = 3, and \mathrm{popcount}(0) = 0.

Let f(n) be the number of times the following operation will be done when we repeat it until n becomes 0: "replace n with the remainder when n is divided by \mathrm{popcount}(n)." (It can be proved that, under the constraints of this problem, n always becomes 0 after a finite number of operations.)

For example, when n=7, it becomes 0 after two operations, as follows:

\mathrm{popcount}(7)=3, so we divide 7 by 3 and replace it with the remainder, 1.

\mathrm{popcount}(1)=1, so we divide 1 by 1 and replace it with the remainder, 0.

You are given an integer X with N digits in binary.
For each integer i such that 1 \leq i \leq N, let X_i be what X becomes when the i-th bit from the top is inverted.
Find f(X_1), f(X_2), \ldots, f(X_N).

Constraints

1 \leq N \leq 2 \times 10^5

X is an integer with N digits in binary, possibly with leading zeros.

Input

Input is given from Standard Input in the following format:

N
X

Output

Print N lines. The i-th line should contain the value f(X_i).

Sample Input 1

3
011

Sample Output 1

2
1
1

X_1 = 7, which will change as follows: 7 \rightarrow 1 \rightarrow 0. Thus, f(7) = 2.

X_2 = 1, which will change as follows: 1 \rightarrow 0. Thus, f(1) = 1.

X_3 = 2, which will change as follows: 2 \rightarrow 0. Thus, f(2) = 1.

Sample Input 2

23
00110111001011011001110

Sample Output 2

2
1
2
2
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
3



Sample input:
3
011


Sample output:
2
1
1

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    X = int(input(),2)
    LIST = []
    PM = [-1]*N
    ANS = [0]*N
    TEMP = [0]*N
    CHAIND = [0]*N
    bit = 1
    for i in range(N):
        LIST.append(X^bit)
        PM[i] += (X & bit == 0)*2
        bit = bit<<1

    for i in range(N):
        cnt = count_ones_by_bitmask(X)
        if LIST[i]!=0:
            TEMP[i] += LIST[i] % (cnt+PM[i])
            ANS[i] += 1

    CHA = list(set(TEMP))

    for i in range(len(CHA)):
        an = 0
        cha = CHA[i]
        cnt = count_ones_by_bitmask(CHA[i])
        while cnt>0:
            an += 1
            cha = cha%cnt
            cnt = count_ones_by_bitmask(cha)
        CHAIND[CHA[i]] = an

    for i in reversed(range(N)):
        print(ANS[i]+CHAIND[TEMP[i]])


def count_ones_by_bitmask(num):
    count = 0
    while num:
        count += num & 1
        num >>= 1
    return count

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
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 <= n 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:
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):
    for i in range(n):
        y=x
        if x[i]=='1':
            y=x[:i]+'0'+x[i+1:]
        else:
            y=x[:i]+'1'+x[i+1:]
        yint=int(y,2)
        print(f(yint))

if __name__=='__main__':
    n,x=readinput()
    main(n,x)

Submission status: Time Limit Exceeded

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

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

def popcount(pop: int, cnt: int):
    val = 0
    if cnt == 0:
        return 0
    while True:
        val += 1
        pop = pop % cnt
        cnt = str(bin(pop)).count('1')
        if pop == 0:
            return val

init_cnt1 = str(bin(int(X, 2))).count('1')
for i in range(N):
    cnt1 = init_cnt1
    if X[i] == '0':
        cnt1 += 1
    else:
        cnt1 -= 1        

    reverse_bitX = toggle_nth_bit(int(X, 2), len(X)-i-1)
    print(popcount(reverse_bitX, cnt1))

Submission status: Time Limit Exceeded

Solution code:
def Base_n_to_10(X,n):
    out = 0
    for i in range(1,len(str(X))+1):
        out += int(X[-i])*(n**(i-1))
    return out#int outn=int(input())
def Base_10_to_n(X, n):
    if (int(X/n)):
        return Base_10_to_n(int(X/n), n)+str(X%n)
    return str(X%n)
n=int(input())
x=input()
ans=[]
pc=x.count("1")
la=[float("inf")]*pc
for i in range(1,pc+1):
    i10=str(Base_10_to_n(i, 2)).count("1")
    if i%i10==0:
      la[i-1]=1
    else:
      la[i-1]=la[(i%i10)-1]+1
if pc!=1:
  x10=Base_n_to_10(x,2)
  for i in range(1,n+1):
    if x[i-1]=="0":
      ans.append((x10+pow(2,n-i,pc+1))%(pc+1))
    else:
      ans.append((x10-pow(2,n-i,pc-1))%(pc-1))
  for a in ans:
    if a==0:
      print(1)
    else:
      print(1+la[a-1])
else:
  x10=Base_n_to_10(x,2)
  for i in range(1,n+1):
    if x[i-1]=="0":
      ans.append((x10+pow(2,n-i,pc+1))%(pc+1))
    else:
      ans.append("n")
  for a in ans:
    if a==0:
      print(1)
    elif a=="n":
      print(0)
    else:
      print(1+la[a-1])

Submission status: Time Limit Exceeded

Solution code:
import sys 

readline = sys.stdin.readline 

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

def popcount(number):
    num = number
    counter = 0
    while num != 0:
        one_bit = bin(num)[2:].count('1')
        num = num % one_bit
        counter += 1

    return counter

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

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

    print(popcount(bit_int))

Submission status: Time Limit Exceeded

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


def popcount(x):
    s = bin(x)[2:]

    return s.count('1')


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

    return count


for i in range(n):
    xxx = x[:i] + str(int(not (int(x[i])))) + x[i + 1:]
    nnn = int(xxx, 2)
    print(f(nnn))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
x=int(s,2)
ones=s.count('1')
d={}
d[0]=0

for i in range(1,n+1):
    yy=bin(i)[2:].count('1')
    d[i]=yy

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

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

    c=0
    while(y>0):
        y=y%nos
        nos=d[y]
        c+=1
    print(c)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
xo = input()
output = []
import copy

for i in range(n):
  x = copy.copy(xo)
  if x[i] == "0":
    x = x[:i] + "1" + x[i+1:]
  else:
    x = x[:i] + "0" + x[i+1:]
  x = bin(int(x,2))
  counter = int(x,2)
  outi = 0
  while counter != 0:
    counter_bi = bin(counter)
    cop = str(counter_bi).count("1")
    counter = counter%cop
    outi += 1
  output.append(str(outi))

print("\n".join(output))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

		oct_mae.append(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
				oct_mae.append(oct)
				if oct == 0:
					break
				if oct in mem:
					ans_tmp += mem[oct]
					break

		ans.append(ans_tmp)
		if oct_mae[0] in mem:
			pass
		else:
			for i,val in enumerate(oct_mae):
				mem[val] = ans_tmp
				ans_tmp -= 1

	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:
# 
import sys

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

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

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

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

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

fo = '0' + str(N) + 'b'
for i in reversed(range(N)):
    x = toggle_nth_bit(X,i)
    #print("----")
    #print(format(X, fo))
    #print(format(x, fo))

    print(f(x))

Submission status: Time Limit Exceeded

Solution code:
import math

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

N = 2 * 10 ** 5

lst = [0 for _ in range(N)]

def bit_ans(X, bit):
  if X == 1:
    return 1
  elif X == 0:
    return 0
  
  param = X
  counter = 0

  if X > N:
    counter += 1
    param = X % bit
  
  while True:
    if param == 0:
      break

    param = param % lst[param-1]
    counter += 1
  return counter


for i in range(N):
  k = i+1
  s = bin(k)
  lst[i] = s[2:].count('1')

search_lst = []
bit_count = x.count('1')
for i in range(n):
  if x[i] == '0':

    search_lst.append((int(x[:i] + '1' + x[i+1:],2), bit_count+1))
  else:
    search_lst.append((int(x[:i] + '0' + x[i+1:],2), bit_count-1))

for i in search_lst:
  print(bit_ans(i[0], i[1]))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=input()
X=[0]*n
N=0
P=[]
for i in range(1,n+1):
    cnt = 0
    while i!=0:
        if i%2==1:
            cnt += 1
        i//=2
    P.append(cnt)

for i in range(n):
    X[i]=int(x[i])
    N+=(X[i])*(2**(n-i-1))
Y=X.copy()

q=0
for i in range(n):
    if X[i]==1:
        q+=1

for i in range(n):
    Ni=0
    Y[i]=int(Y[i]==0)
    if Y[i]==1:
        Ni=N+2**(n-i-1)
        q+=1
    else:
        Ni=N-2**(n-i-1)
        q-=1
    pop=q
    cnt = 0
    while Ni!=0:
        Ni=Ni%pop
        pop=P[Ni-1]
        cnt+=1
    print(cnt)
    if Y[i]==1:
        q-=1
    else:
        q+=1
    Y[i]=int(Y[i]==0)

Submission status: Time Limit Exceeded

Solution code:
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

import copy

n=ni()
x=[_ for _ in input()]

def popcount(nn):
  ans=0
  while nn>0:
    if nn%2==1:
      ans+=1
    nn>>=1
  return ans

pc = dict()


def f(nn):
  ans=0
  while nn>0:
    ans+=1
    ppc=1
    if nn in pc:
      ppc = pc[nn]
    else:
      ppc = popcount(nn)
      pc[nn] = ppc
    nn=nn%ppc
  return ans

for i in range(n):
  num = int(''.join(x),2)
  if x[i]=='1':
    num -= 2**(n-i-1)
  else:
    num += 2**(n-i-1)
  # print(num)
  print(f(num))

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+=pow(2,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 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
    else:
        num=orig-pow(2,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 = input()
Xn = int(X, 2)
for i in range(N):
    if X[i] == "1":
        y = Xn - 2**(N-i-1)
    else:
        y = Xn + 2**(N-i-1)
    cnt = 0
    yy = y
    while y>0:
        y %= bin(y).count("1")
        cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import math
def main():
    n = int(input())
    x = input().rstrip()
    for i in range(n):
        tmp = x[:]
        tmp = list(tmp)
        if tmp[i] == '0':
            tmp[i] = '1'
        else:
            tmp[i] = '0'
        tmp = "".join(tmp)
        # print('tmp', tmp)
        print(fn(int(tmp, 2)))

def fn(x):
    # print('x',x)
    bin_x = bin(x)
    if x == 0:
        return 0
    ans = 1
    c = x % bin_x.count('1')
    while c != 0:
        x = c
        bin_x = bin(x)
        c = x % bin_x.count('1')
        ans += 1
    return ans

if __name__ == '__main__':
    main()
    # print(fn(1))

Submission status: Time Limit Exceeded

Solution code:
def main():
  from sys import stdin
  n = int(stdin.readline())
  x = stdin.readline()[:n]
  for a in range(n):
    if x[a] == '0':
      m = '0b' + x[:a] + '1' + x[a+1:]
    else:
      m = '0b' + x[:a] + '0' + x[a+1:]
    m = int(m, 0)
    c = 0
    while m != 0:
      s = 0
      for i in list(str(bin(m))[2:]):
      	s += int(i)
      m = m % s
      c += 1
    print(c)

main()

Submission status: Time Limit Exceeded

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

iti=0
zero=0
for i in x:
  if i=="1":
    iti+=1
zero=n-iti
z_flag=False
i_flag=False

for i in range(n):
  ans=0
  if x[i]=="1":
    X="0b"+x[:i]+"0"+x[i+1:]
    iti2=iti-1
  else:
    x[i]=="1"
    X="0b"+x[:i]+"1"+x[i+1:]
    iti2=iti+1
  bin_num = int(X, 0)
  while bin_num!=0:
    ans+=1
    if iti2==0:
      break
    bin_num=bin_num%iti2
    bin_num2=bin(bin_num)
    iti2=0
    for i in bin_num2:
      if i=="1":
        iti2+=1
      
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = int(input(),2)
def A(xi):
    if xi == 0:
        return 0
    else:
        return A(xi%(str(bin(xi)).count('1'))) + 1
for i in range(1,N+1):
    xi = X ^ (1<<(N-i))
    print(A(xi))

Submission status: Time Limit Exceeded

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

bit_total = 0
for i in range(n):
    if x[i] == "1":
        bit_total += 1

bin_num = int(x, 2)
L = [[0, 0] for _ in range(n)]  # [数, bit数]

for i in range(n):
    if x[i] == "1":
        L[i][0] = bin_num - 2**(n-i-1)
        L[i][1] = bit_total - 1
    else:
        L[i][0] = bin_num + 2 ** (n - i - 1)
        L[i][1] = bit_total + 1
# print(bit_total)
# print(L)

for i in range(n):
    p = L[i][0]
    d = L[i][1]
    ans = 0
    # print(p)
    if p > 0:
        ans += 1
        p %= d
        while p > 0:
            d = bin(p).count("1")
            # print(p, d)
            p %= d
            ans += 1

    print(ans)

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 = int(args[1], 2)

    ret = []
    dp = defaultdict(int)
    for i in range(n):
        m = x ^ (1 << (n-i-1))
        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:
#AIsing2020 d
 
import sys,math,collections,itertools,copy
input = sys.stdin.readline
 
 
def popcount(n):
    bin_str = bin(n)
    cou1 = bin_str.count('1')
    return cou1
 
def count(nc):
    co = 0
    while nc >0:
        cou1 = popcount(nc)
        nc = nc%cou1
        co +=1
    return co
 
N = int(input())
X = list(input().rstrip())
 
for i in range(N):
    Y = copy.copy(X)
    if Y[i] == '1':
        Y[i] = '0'
    else:
        Y[i] = '1'
    s = '0b'+"".join(Y)
    a =int(s,2)
    co = count(a)
    print(co)

Submission status: Time Limit Exceeded

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

X_10 = int("0b" + X, 0)
for i in range(N):
    num = X_10
    if X[i] == "0":
        num += int(2**(N-i-1))
    else:
        num -= int(2**(N-i-1))
    num_2 = bin(num)
    count = 0
    while True:
        count_2 = 0
        for j in range(len(num_2)):
            if num_2[j] == "1":
                count_2 += 1
        if count_2 == 0:
            break
        else:
            count += 1
        num_2 = bin(int(num_2, 0) % count_2)
    print(count)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import math

N = int(input())
X = list(input())
X = list(map(int, X))

def num_to_X(num):
    new_X = []
    new_N = int(math.log(num,2))+1
    for i in range(new_N):
        new_X.append(num>>i&1)
    return new_X[::-1]

def X_to_num(X):
    value = 0
    X = X[::-1]
    for i in range(len(X)):
        value += X[i]*pow(2,i)
    return value

def mode(X, mod):
    X = X[::-1]
    next_X = 0
    mod_2_i = 1
    for i in range(len(X)):
        next_X += X[i]*mod_2_i
        mod_2_i = (mod_2_i*2)%mod
    next_X = next_X%mod
    return next_X

def f(N, X, k):
    mod = sum(X)
    next_X = mode(X,mod)
    if next_X == 0:
        return k+1
    else:
        new_X = num_to_X(next_X)
        return f(len(new_X), new_X, k+1)

base_mod = sum(X)
# base_modが1なら, 操作は0回.
if base_mod == 1:
    for i in range(N):
        # 100 -> 000
        if X[i] == 1:
            print(0)
        # 100 -> 110
        elif i != N-1:
            print(1)
        # 100 -> 101
        else:
            print(2)
    exit(0)

plus_amari = mode(X, base_mod+1)
# print(X_to_num(X), base_mod+1, X_to_num(X)%(base_mod+1), plus_amari)
minus_amari = mode(X, base_mod-1)
# print(X_to_num(X), base_mod-1, X_to_num(X)%(base_mod-1), minus_amari)

results = []
modplus_2_i = 1
modminus_2_i = 1
X_hanten = X[::-1]

# print('----')
# print(X)
# print('----')

for i in range(N):
    # modが増えるパターン
    if X_hanten[i] == 0:
        now_num = X_to_num(X)+pow(2,i)
        now_mod = base_mod+1
        amari = (plus_amari+modplus_2_i)%(base_mod+1)
    else:
        now_num = X_to_num(X)-pow(2,i)
        now_mod = base_mod-1
        amari = (minus_amari-modminus_2_i)%(base_mod-1)
#     print(now_num, now_mod, now_num%now_mod,amari)

    if amari != 0:
        new_X = num_to_X(amari)
        results.append(f(len(new_X),new_X,1))
    else:
        results.append(1)

    modplus_2_i = (modplus_2_i*2)%(base_mod+1)
    modminus_2_i = (modminus_2_i*2)%(base_mod-1)

# print('---')
for result in results[::-1]:
    print(result)

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)
    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:
def i_input(): return int(input())
def s_input(): return input()


def f(num, one_count):
    ans = 0

    while num != 0:
        if ans == 0:
            pop_count = one_count
        else:
            pop_count = bin(num).count('1')
        num %= pop_count
        ans += 1
        
    return ans

def main():
    n = i_input()
    x = s_input()

    x10 = int(x, 2)
    one_count = x.count('1')

    for i in range(n):
        if x[i] == '0':
            num = x10 + 2 ** (n-1-i)
            print(f(num, one_count+1))
        else:
            num = x10 - 2 ** (n-1-i)
            print(f(num, one_count-1))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

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

memo = {0: 0}

# def slove(x):
#     cnt = 0
#     tmp = []
#     while x:
#         if x in memo:
#             return cnt + memo[x]
#         else:

#         x = x % popcount(x)
#         cnt += 1
#     return cnt

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:
n = int(input())
s = input()
from copy import deepcopy

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from collections import Counter
n=int(input())
x=input()
d={}
j=[]
for i in range(n-1,-1,-1):
  count=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]+count)
      break
    b=Counter(bin(a))["1"]
    if b==0 or a==0:
      d[c]=count
      j.append(count)
      break
    a%=b
    count+=1
for i in range(n-1,-1,-1):
  print(j[i])

Submission status: Time Limit Exceeded

Solution code:
import math
def bit2int(s):
    res = 0
    twin = 1
    for b in s[::-1]:
        if b==1:
            res += twin
        twin *= 2
    return res

def int2bit(x):
    if x == 1:
        return [1]
    
    dig = math.ceil(math.log2(x))
    
    res = [x >> j & 1 for j in range(dig)]
    return res


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

    baseones = 0
    for s in X:
        baseones += 1 if s == 1 else 0

    for i in range(N):
        ones = baseones + 1 if X[i]== 0 else baseones - 1
        tmp = X.copy()

        tmp[i] = 1 if X[i] == 0 else 0
        if ones == 0:
            print(0)
            continue
        val = bit2int(tmp)%ones
        
        cnt = 0
        while val > 0:
            onesbit = int2bit(val)
            
            ones = sum(onesbit)
            cnt += 1
            if ones == 0:
                break
            val %= ones
        print(cnt+1)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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


def popcount(n: int) -> int:
    return bin(n)[2:].count("1")


def f(n: int) -> int:
    i = 0
    while n > 0:
        n = n % popcount(n)
        i += 1
    return i


for i in range(N):
    _X = list(X)
    _X[i] = "0" if _X[i] == "1" else "1"
    n = int("".join(_X), 2)
    print(f(n))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = list(input())
 
 
def f(cnt):
    if (cnt > 0):
        p_count = bin(cnt).count('1')
        return f(cnt % p_count) + 1
    else:
        return 0
 
 
for i, x in enumerate(X):
    if (x == '1'):
        X[i] = '0'
        num = int(''.join(X), 2)
        print(f(num))
        X[i] = '1'
    else:
        X[i] = '1'
        num = int(''.join(X), 2)
        print(f(num))
        X[i] = '0'

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)
import string
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 + 2 ** (n - i - 1),popcount+1))
        else:
            print(countbin(xint - 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 popcount(n): 
    count = 0
    while (n): 
        count += n & 1
        n >>= 1
    return count 

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

totalpopcount = popcount(x)
for i in range(1, n + 1):
	one_shifted = (1 << n - i)
	xored = x ^ one_shifted
	if x & one_shifted and xored:
		print(f(xored % (totalpopcount - 1)) + 1)
	elif xored:
		print(f(xored % (totalpopcount + 1)) + 1)
	else:
		print(0)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N = int(input())
X = list(input())
d = defaultdict(int)

for i in range(1, N):
    c = 0
    t = 0
    k = format(i, "b")
    for j in k:
        if j == "1":
            c += 1
    d[i] = d[i%c] + 1


n = 0
for i in X:
    if i == "1":
        n += 1

p = 1
total1 = 0
total2 = 0
for i in X[::-1]:
    if i == "1":
        total1 += p % (n+1)
        if n-1 > 0:
            total2 += p % (n-1)
    p *= 2

total1 %= (n+1)
if n-1 > 0:
    total2 %= (n-1)
Ans = []
p = 1
for i in X[::-1]:
    c = 1
    if n - 1 <= 0 and i == "1":
        Ans.append(0)
    else:
        if i == "0":
            start = total1
            start += p % (n+1)
            start %= (n+1)
        else:
            start = total2
            start -= p % (n-1)
            start += n - 1
            start %= (n-1)
        Ans.append(c+d[start])
    p *= 2

for i in Ans[::-1]:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
@lru_cache(maxsize=1000)
def main():
    def popcount(n, bit, cnt):
        if n == 0:return cnt
        new = bin(n%bit).count("1")
        return popcount(n%bit, new, cnt + 1)
    
    n = int(input())
    x = input()
    cnt = x.count('1')
    num = 0
    for i in range(n):
        num += int(x[-(i + 1)]) * pow(2, i)

   
    for i in range(n):
        res = 0
        if x[i] == "1":
            temp = num - pow(2, n - i - 1)
            print(popcount(temp, cnt - 1, 0))
        else:
            temp = num + pow(2, n - i - 1)
            print(popcount(temp, cnt + 1, 0))
main()