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 copy
n=int(input())
x=list(input())
b=[]
for i in range(2**18):
  b.append(format(i,'0'+str(18)+'b'))
  if i>n+1:
    break
ct=[0]*(n+1)
for i in range(1,n):
  ct1=0
  for j in range(len(b[i])):
    if b[i][j]=='1':
      ct1+=1
  ct[i]=i%ct1

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

moda=[1]
modb=[1]
modc=[1]
for i in range(n-1):
  if CT>=2:
    moda.append(moda[-1]*2%(CT-1))
  if CT>=1:
    modb.append(modb[-1]*2%CT)
  modc.append(modc[-1]*2%(CT+1))


x.reverse()
za=0
zb=0
zc=0
for i in range(n):
  if x[i]=='1':
    if CT>=2:
      za+=moda[i]
      za%=(CT-1)
    if CT>=1:
      zb+=modb[i]
      zb%=CT
    zc+=modc[i]
    zc%=(CT+1)
x.reverse()
moda.reverse()
modc.reverse()

for i in range(n):
  y=copy.copy(x)
  y2=y[i]
  y[i]=str(1-int(y[i]))
  ct1=0
  if y2=='1':
    ct1=CT-1
  else:
    ct1=CT+1
  if ct1==0:
    print(0)
  else:
    if y2=='1':
      z=za
      z-=moda[i]
      z%=ct1
    else:
      z=zc
      z+=modc[i]
      z%=ct1
    
    ans=1
    while z!=0:
      z=ct[z]
      ans+=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


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


def mod(n, cnt):
    if n == 0:
        return cnt
    n = n % popcnt(n)
    cnt += 1
    return mod(n, cnt)


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

for i in range(n):
    b = x
    # print(b)
    if b[i] == "0":
        b[i] = "1"
    elif b[i] == "1":
        b[i] = "0"
    # print(''.join(b))
    # print(popcnt(''.join(b)))
    num = int(''.join(b), 2)
    # print(''.join(b), num)
    t = mod(num, 0)
    print(t)
    if b[i] == "0":
        b[i] = "1"
    elif b[i] == "1":
        b[i] = "0"

Submission status: Time Limit Exceeded

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

memo_list = [0 for i in range(n+1)]

for i in range(n):
    if i==0:
        y = str((int(x[i])*(-1) + 1)) + x[i+1:]
    elif i<n-1:
        y = x[:i] + str((int(x[i])*(-1) + 1)) + x[i+1:]
    else:
        #i==n-1
        y = x[:i] + str((int(x[i])*(-1) + 1))
    k = y.count("1")
    z = int(y, 2)
    #print("z, k", z, k, end=", ")
    count = 0
    tmp_memo_dict = {}
    while z!=0:
        if z<n+1 and 0<memo_list[z]:
            count += memo_list[z]
            break
        z = z%k
        k = str(bin(z))[2:].count("1")
        count+=1
        tmp_memo_dict.update({z: count})
        #print(z, k, count, end=", ")
    print(count)
    for z2, count2 in tmp_memo_dict.items():
        memo_list[z2] = count - count2

Submission status: Time Limit Exceeded

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

S=sum(X)

def bd(X):
    ans=0
    for n in reversed(range(len(X))):
        ans+=2**(len(X)-1-n)*X[n]
    return ans

def db(N):
    s=[]
    div=N
    fin=False
    while fin==False:
        mod=div%2
        div=div//2
        s.append(mod)
        if div==0:
            fin=True
    return s[::-1]

def rec(X,dec):
    n=dec
    if dp.get(n)!=None or n==0:
        return dp[n]
    else:
        n%=sum(X)
        X=db(n)
        return rec(X,n)+1

d=bd(X)
dp={}
dp[0]=0
dp[1]=1

for n in range(N):
    if X[n]==0:
        X[n]=1
        d+=2**(N-1-n)
        tmp=rec(X,d)
        dp[d]=tmp
        X[n]=0
        d-=2**(N-1-n)
    else:
        X[n]=0
        d-=2**(N-1-n)
        tmp=rec(X,d)
        dp[d]=tmp
        X[n]=1
        d+=2**(N-1-n)
    print(tmp)

Submission status: Time Limit Exceeded

Solution code:
import copy as cp
def popcount(x):
  xbin = list(bin(x))
  p = xbin.count('1')
  return p
  
N = int(input())
X = input()

x = list(X)
P = [0 for _ in range(2**N)]

x = list(X)
if x[0] == '0':
  x[0] = '1'
else:
  x[0] = '0'
xint = 0
for j in range(N):
  xint += 2**(N-j-1)*int(x[j])

xint2 = cp.copy(xint)

c = 0
while xint2 > 0:
  if P[xint2] == 0:
    P[xint2] = popcount(xint2)
    
  xint2 = xint2 % P[xint2]
  c += 1
  
print(c)

x = list(X)
for i in range(N)[1:]:
  if x[i] == '1':
    xint = xint - 2**(N-i-1)
    if x[i-1] == '1':
      xint = xint + 2**(N-i)
    else:
      xint = xint - 2**(N-i)
  else:
    xint = xint + 2**(N-i-1)
    if x[i-1] == '1':
      xint = xint + 2**(N-i)
    else:
      xint = xint - 2**(N-i)
  
  xint2 = cp.copy(xint)

  c = 0
  while xint2 > 0:
    if P[xint2] == 0:
      P[xint2] = popcount(xint2)
    
    xint2 = xint2 % P[xint2]
    c += 1
  
  print(c)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

s = int(input(), 2)


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

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

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

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


def popcnt3(n):
    c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c >> 8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c >> 16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c >> 32) & 0x00000000ffffffff)
    return c


for i in range(n):
    ss = s ^ (1 << (n-i-1))
    c = 0
    t = bin(ss).count('1')
    while ss != 0:
        ss -= t*(ss//t)
        t = bin(ss).count('1')
        c += 1
    # print(ss, popcnt5(ss), c)
    print(c)

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:
a = input()
s = input()
n = int(s, 2)

for i in range(len(s)):
    x = n ^ (1 << len(s) - 1 - i)
    cnt = 0
    while x != 0:
        ss = bin(x)[2:]
        cnt += 1
        num1 = ss.count("1")
        rs = ss[::-1]
        res = 0
        for j in range(len(rs)):
            if rs[j] == "1":
                res += pow(2, j, num1)
                res %= num1
        x = res
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def divbin(s,res):
  if int(s,2)==0:
    v=res
    return v
  # ss=int(s)
  val=int(s,2)
  count=bin(val).count("1")
  val%=count
  # t_str=bin(str(count))
  t_str=bin(val)
  t_str=t_str.replace("0b","")
  res+=1
  return divbin(t_str,res)

from copy import deepcopy
n=int(input())
x=input()

# c=str(bin(n))
# c=c.replace("0b","")
s=x

p=int(x)
cnt=bin(p).count("1")
x=list(x)
# print(cnt)
for i in range(len(x)):
  tmp=cnt
  ts=""
  vv=int(s,2)
  if x[i]=="1":
    vv-=2**(len(x)-1-i)
  else:
    vv+=2**(len(x)-1-i)
  # ans=0
  # global ans
  ts=bin(vv)
  ts=ts.replace("0b","")
  ans=0
  ans=divbin(ts,ans)
  print(ans)

Submission status: Time Limit Exceeded

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

dp = [-1] * 200001
dp[0] = 0
dp[1] = 1
dp[2] = 1
dp[3] = 2
dp[4] = 1
dp[5] = 2
dp[6] = 1
dp[7] = 2
dp[8] = 1
dp[9] = 2
dp[10] = 1


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 dp[tmp] != -1:
                print(count + dp[tmp])
                break
            else:
                count += 1
                tmp = tmp % popcount(tmp)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import math
count = 1
def count_ones_by_bin(num):
    bin_num = bin(num)[2:]
    count2 = 0
    for i in bin_num:
            count2 += int(i)
    return count2

def propcount(n):
  global count
  
  nextn = count_ones_by_bin(n)
  if (nextn == 0):
    print(count)
    return count
  else:
    count += 1
    propcount(n%nextn)
    
N = int(input())
X = "0b"+str(input())
intX=int(X,2)
start = bin(2**(N-1))

for num in range(N):
  count = 0
  next = bin(2**(N-num-1)^intX)
  new = int(next,2)
  c = propcount(new)

Submission status: Time Limit Exceeded

Solution code:
def GCDC(A,B):
    Count = 0
    while A!=0:
        Count += 1
        A = A%B
        B = AX[A]
    return Count
N  = int(input())
X  = input()
BX = int(X,2)
LX = [int(T) for T in X]
PX = sum(LX)

AX = [0]*(N+1)
for T in range(0,N):
    AX[T] = sum([int(S) for S in format(T,'b')])
Pr = [0]*N
for T in range(0,N):
    if LX[T]==1:
        Num   = BX-pow(2,N-T-1)
        Pop   = PX-1
        Pr[T] = GCDC(Num,Pop)
    else:
        Num   = BX+pow(2,N-T-1)
        Pop   = PX+1
        Pr[T] = GCDC(Num,Pop)
print('\n'.join(str(X) for X in Pr))

Submission status: Time Limit Exceeded

Solution code:
import copy

n = int(input())
x = [int(s) for s in list(input())]

def popcount(num):
  t2 = 2
  d = []
  while t2 <= num:
    d.append(num % t2)
    t2 *= 2
  d = [i for i in d if i != 0]
  return(len(set(d))+1)
def as_n(l):
  le = len(l)
  a = 0
  for b in range(le):
    a += (2**b) *l[le-1-b]
  return(a)

for a in range(n):
  y = copy.copy(x)
  y[a] = 1-x[a]
  ans = 0
  den = as_n(y)
  while den != 0:
    den = den % popcount(den)
    ans += 1
    
  print(ans)

Submission status: Time Limit Exceeded

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

    n = int(input())
    X = list(input())
    d = defaultdict(int)
    d[0] = 0
    for i in range(1, n):
        f(i)
    c = sum(list(map(int, X)))
    m = int(''.join(X), 2)
    for i in range(n):
        rev(i)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy
N=int(input())
Z=list(map(int,input()))
ans={}
for i in range(N):
    X=copy.copy(Z)
    cnt=0
    cnt2=0
    if X[i]==1:
        X[i]=0
    else:
        X[i]=1
    X=list(reversed(X))
    for i in range(len(X)):
        cnt+=X[i]*(2**i)
        if X[i]==1:
            cnt2+=1
    ans[cnt]=cnt2
for k in ans.keys():
    Z=ans[k]
    cnt3=0
    while k>0:
        cnt4=bin(k)
        cnt4=str(cnt4)
        cnt5=0
        for u in range(2,len(cnt4)):
            if cnt4[u]=='1':
                cnt5+=1
        k%=cnt5
        cnt3+=1
    print(cnt3)

Submission status: Time Limit Exceeded

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

d = {}
def popcount(s):
    if not s in d:
        d[s] = s.count('1')
    return d[s]

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

    ans = 0
    while k > 0:
        k %= pop
        pop = popcount(bin(k)[2:])
        ans += 1
    print(ans)
    T //= 2

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = input()
for j in range(n):
    c=0
    if x[j] == '1':
        y = x[0:j]+'0'+x[j+1:]
    elif x[j] == '0':
        y = x[0:j]+'1'+x[j+1:]
    #print(y)
    num = int(y,2)
    #print(num)
    i = y.count('1')
    while num>0:
        c += 1
        num = num%i
        b = bin(num)[2:]
        #print(b)
        i = b.count("1")
    print(c)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=str(input())
pop=[0]
a=1
b=0
count=1
for i in range(1,n):
    ni=0
    a=i
    while a:
        a&=(a-1)
        ni+=1
    pop.append(ni)
x1=0
for i in range(n):
    if int(x[i])&1:
        x1+=2**(n-1-i)
for i in range(n):
    xi=(2**(n-1)>>i)^x1
    count=1
    popi=0
    if xi!=0:
        a=xi
        while a:
            a&=(a-1)
            popi+=1
        xi%=popi
        while xi:
            xi%=pop[xi]
            count+=1
        print(count)
    else:
        print(0)

Submission status: Time Limit Exceeded

Solution code:
def m():
    N = int(input())
    X = input()
    R = list(reversed(X))

    memo = [-1] * (N+2)
    for i in range(1, N+2):
        p = 0
        k = i
        while k != 0:
            if memo[k] != -1:
                p += memo[k]
                break

            if k % 2 == 1:
                p+=1
            k //= 2
        memo[i] = p

    def f(n):
        r = 0
        while n != 0:
            n = n % memo[n]
            r += 1
        return r

    memo2 = [0] * (N+2)
    for i in range(1, N+2):
        memo2[i] = f(i)


    total = 0
    for i in range(N):
        total += int(R[i]) * pow(2, i)

    base = X.count('1')
    for i in range(N):
        ans = 0
        if X[i] == '1':
            tmp = total - pow(2, N - 1 - i)
            if (base-1) == 0:
                print(0)
                continue
            tmp %= (base - 1)
            ans = memo2[tmp] + 1
        else:
            tmp = total + pow(2, N - 1 - i)
            tmp %= (base + 1)
            ans = memo2[tmp] + 1
        print(ans)


m()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    X = input()
    MOD = sum(map(lambda x: x == '1',X))
    if MOD == 0:
        print("1" + "\n1" * (N-1))
        return 0
    if MOD == 1 and X[-1] == '1':
        print("2\n" * (N-1) + "0")
        return 0
    if MOD == 1 and X[-1] == '0':
        ans = ''
        for i in range(N):
            if X[i] == '1':
                ans += '0'
            elif i != N-1:
                ans += '1'
            else:
                ans += '2'
            if i != N-1:
                ans += '\n'
        print(ans)
        return 0
    MODP1 = MOD + 1
    MODM1 = MOD - 1
    POWEROFTWOP1 = [0] * 200001
    POWEROFTWOM1 = [0] * 200001
    POWEROFTWOP1[0] = 1
    POWEROFTWOM1[0] = 1
    for i in range(1,N):
        POWEROFTWOP1[i] = (POWEROFTWOP1[i-1] * 2) % MODP1
        POWEROFTWOM1[i] = (POWEROFTWOM1[i-1] * 2) % MODM1
    xMODP1 = 0
    xMODM1 = 0
    for i in range(N):
        if X[i] == '1':
            xMODP1 += POWEROFTWOP1[N - i - 1]
            xMODM1 += POWEROFTWOM1[N - i - 1]
    xMODP1 %= MODP1
    xMODM1 %= MODM1
    ans = ""
    for i in range(N):
        if X[i] == '0':
            anscur = xMODP1
            anscur += POWEROFTWOP1[N - i - 1]
            anscur %= MODP1
        if X[i] == '1':
            anscur = xMODM1
            anscur -= POWEROFTWOM1[N - i - 1]
            anscur %= MODM1
        cnt = 1
        while anscur != 0:
            ans2 = bin(anscur)[2:]
            oneCount = sum(map(lambda x: x == '1',ans2))
            anscur %= oneCount
            cnt += 1
        ans += str(cnt)
        if i != N-1:
            ans += '\n'
    print(ans)
                    
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 <= 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, count, d):
  if (i <= 2 * 10**5):
    return count + ans[i]
  elif (i == 0):
    return count
  else:
    return solve2(i % d, count + 1, d)


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]
  if(x[i] == '0'):
    print(solve2(int(_x, 2), 0, u))
  else:
    print(solve2(int(_x, 2), 0, d))

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(1024)]
    # ts = {}
    # for i in range(2*10**5+1):
        # ts[i] = f(i)
    # for i in range(2*10**5+1):
        # ts[i] = f(i)



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

        if temp == 0:
            print(0)
        else:
            temp_ = temp % l
            if temp_ == 0:
                print(1)
            else:
                temp = temp_ % bin(temp_).count("1")
                print(ts[temp]+2)
    
    return


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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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


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

Submission status: Time Limit Exceeded

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

    for i in range(N):
        count = 0
        if X[i] == "1":
            nX = int(X, 2) - 2 ** (N-1-i)
        if X[i] == "0":
            nX = int(X, 2) + 2 ** (N-1-i) 
        for j in range(N):
            if nX == 0:
                break
            else:
                nX %= bin(nX).count("1")              
                count += 1
        print(count)
resolve()

Submission status: Time Limit Exceeded

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

maxbit = x.count("1")

box = [0] * (maxbit + 1)

def f(i):
  cnt = 0
  while i > 0:
    if box[i] != 0:
      return box[i] + cnt
    i %= bin(i).count("1")
    cnt += 1
  return cnt

for i in range(1, min(maxbit + 1, 200000)):
  box[i] = f(i)

for i in range(lenx):
  if x[i] == "0":
    mb = maxbit + 1
    t = x10 + 2 ** (lenx - 1 - i)
  else:
    mb = maxbit - 1
    t = x10 - 2 ** (lenx - 1 - i)
  # print(t, mb)
  if t == 0:
    print(0)
  else:
    t %= mb 
    if t == 0:
      print(1)
    else:
      ans = f(t) + 1 
      box[t] = ans - 1
      print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = input()
lisX = list(X)
binX = int(X,2)
chk = 2 ** (N - 1)
for n in range(N):
  x = binX ^ chk >> n
  i = 0
  while x != 0:
    i += 1
    x = x % list(bin(x)).count("1")
  print(i)

Submission status: Time Limit Exceeded

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

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

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

    count = 0
    popcount(bin_num)
    print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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


def calc(i, count):
    if i == 0:
        return 0
    icount = bin(i).count("1")
    if icount == 0:
        return count + 1
    r = i % bin(i).count("1")
    if r != 0:
        return calc(r, count + 1)
    else:
        return count + 1


def calc2(i):
    if i == 0:
        return 0
    icount = bin(i).count("1")
    if icount == 0:
        return 1
    return i % icount


for i in range(1, N + 1):
    a = X ^ 2 ** ((N - 1) - (i - 1))
    count = 0
    while a != 0:
        a = calc2(a)
        count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout

int_in = lambda: int(stdin.readline())
arr_in = lambda: [int(x) for x in stdin.readline().split()]
mat_in = lambda rows: [arr_in() for _ in range(rows)]
str_in = lambda: stdin.readline().strip()
out = lambda o: stdout.write("{}\n".format(o))
arr_out = lambda o: out(" ".join(map(str, o)))
bool_out = lambda o: out("YES" if o else "NO")
tests = lambda: range(1, int_in() + 1)
case_out = lambda i, o: out("Case #{}: {}".format(i, o))


cache = {}
def popcount(n):
    if n in cache:
        return cache[n]
    pop = bin(n).count("1")
    result = popcount(n % pop) + 1
    cache[n] = result
    return result


def mod(x, y):
    power_of_two = [0] * len(x)
    power_of_two[0] = 1 % y
    for i in range(1, len(x)):
        power_of_two[i] = power_of_two[i - 1] * (2 % y)
        power_of_two[i] %= y
    result = 0
    i = 0
    j = len(x) - 1
    while i < len(x):
        if x[j] == 1:
            result += power_of_two[i]
            result %= y
        i += 1
        j -= 1
    return result

def thing(x):
    x = [int(y) for y in bin(x)[2:]]
    ones = x.count(1)
    if ones == 0:
        return 0
    else:
        next_num = mod(x, ones)
        return thing(next_num) + 1


def solve(n, x):
    cache[0] = 0
    ones = x.count(1)
    for i in range(n):
        # flip bits
        old = x[i]
        x[i] = 1 if old == 0 else 0

        curr_ones = ones + (1 if old == 0 else -1)
        if curr_ones == 0:
            yield 0
        else:
            next_num = mod(x, curr_ones)
            yield thing(next_num) + 1

        # reset
        x[i] = old

if __name__ == "__main__":
    n = int_in()
    x = [int(y) for y in str_in()]
    result = solve(n, x)
    for item in result:
        out(item)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=list(input())
y=0
lis=[0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2]
for i in range(n):
    y+=int(x[i])

#print(y)

for i in range(n):
    tempx=x
    tempx[i]=str(int(x[i]) ^ 1)
    if tempx[i]=='1':
        tempy=y+1
    else:
        tempy=y-1
    if i>0:
        tempx[i-1]=str(int(tempx[i-1]) ^ 1)

    #print(tempx,x)
    tempx="".join(tempx)

    #print(tempx)
    cnt=0

    while True:
        if int(tempx)==0:
            print(cnt)
            break
        tempx=format(int(tempx,2)%tempy,'b')
        #print(len(tempx))
        tempy=0
        #print(tempx,'koko')
        #print(type(tempx),len(tempx))
        for j in range(len(tempx)):
            tempy+=int(tempx[j])
        cnt+=1

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
n=int(input())
dic={i:str(bin(i)).count('1') for i in range(n+1)}
bi=input()
for i in range(n):
  tmp=list(bi)
  if tmp[i]=='1':
    tmp[i]='0'
  else:
    tmp[i]='1'
  tmp=''.join(tmp)
  d=int(tmp,2)
  c=tmp.count('1')
  t=0
  while d > 0:
    d %= c
    c = dic[d]
    t+=1
  print(t)

Submission status: Time Limit Exceeded

Solution code:
def f(L):
    X=0
    T=1
    for x in L[::-1]:
        X+=T*x
        T*=2
    return X

N=int(input())
X=input()
Zero="0"*N

X=list(map(int,X))

H=X.count(1)
Z=f(X)
G=1<<N

A=[]
for i in range(N):
    G>>=1
    
    if X[i]==0:
        J=H+1
    else:
        J=H-1
        
    Y=Z^G

    if Y==0:
        A.append(0)
        continue
    
    I=1
    Y=Y%J
    try:
        while True:
            Y=Y%bin(Y).count("1")
            I+=1
    except ZeroDivisionError:
        A.append(I)

print("\n".join(map(str,A)))

Submission status: Time Limit Exceeded

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

    def popcount(num):
        return bin(num).count("1")
    popc_X = popcount(X)
    pop_table = {i: [popcount(i), 0, 0] for i in range(1, N+1)}
    
    
    def f(x, factor):
        temp = x
        count = 0
        visited = []
        while temp > 0:
            if temp > N:
                # print(temp, popc_X)
                temp = temp % (popc_X + factor)
                count += 1
                # print(temp)
                continue
            if pop_table[temp][1] == 0:
                pop_table[temp][1] = count
            else:
                if pop_table[temp][2]:
                    count += pop_table[temp][1]
                    break
                # count_ans = pop_table[temp][1]
            if pop_table[temp][2] == 0:
                visited.append(temp)
            temp = temp % pop_table[temp][0]
            count += 1

        for v in visited:
            pop_table[v][1] = count - pop_table[v][1]
            pop_table[v][2] = 1
        return count
    
    ans = [0]*N
    for i in range(0, N):
        xi = X ^ (1 << i)
        # print(xi, "xi")
        if xi & (1<<i):
            factor = 1
        else:
            factor = -1
        ans[N-i-1] = f(xi, factor)
    for a in ans:
        print(a)
main()

Submission status: Time Limit Exceeded

Solution code:
MAX = 2*(10**5) + 1
N = int(input())
X = input()

c = [0] * MAX
for i in range(MAX):
    c[i] = bin(i).count("1")

def calc(num, cnt2):
    ans = 0
    while num > 0:
        ans += 1
        if ans == 1:
            num = num % cnt2
        else:
            if num < MAX:
                num = num % c[num]
            else:
                num = num % bin(num).count("1")
    return ans

dec = int(X, 2)
cnt = bin(dec).count("1")

for i in range(N):
    cnt2 = cnt
    dec2 = dec
    if X[i] == '0':
        cnt2 += 1
        dec2 += 2**(N-1-i)
    else:
        cnt2 -= 1
        dec2 -= 2**(N-1-i)
    print(calc(dec2, cnt2))

Submission status: Time Limit Exceeded

Solution code:
def popcount(x):
  bin_x = bin(x)[2:]
  return bin_x.count("1")
 
N = int(input())
X = input()
 
for i in range(N):
  temp = []
  ans = 0
  for d in X:
    temp.append(d)
  #i番目のビット反転
  if temp[i] == "1":
    temp[i] = "0"
  else:
    temp[i] = "1"
  
  #10進数に変換(str -> int)
  bin_n = str("".join(map(str, temp)))
  int_n = int(bin_n,2)
  #print("int_n = " + str(int_n))
 
  while int_n > 0:
    ans += 1
    j = popcount(int_n)
    int_n = int_n % j
 
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

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


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

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

Submission status: Time Limit Exceeded

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

for n in range(N):
    tmp = (1 << ((N - 1) - n))
    X_n = X ^ tmp    
    str_X_n = format(X_n, 'b')
    
    count_popcount = 0
    tmp_str = str_X_n
    while(1):
        count_1 = tmp_str.count('1')
        if(count_1 != 0):
            amari = int(tmp_str, 2) % count_1
            if(amari == 0):
                count_popcount += 1
                break
            else:
                count_popcount += 1
                tmp_str = format(amari, 'b')
        else:
            break
    print(count_popcount)