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())
X = input()
pc = X.count('1')
nx = int(X, 2)

dp = [-1] * ((2*10**5)+1)
dp[0] = 0
dp[1] = 1

pcs = [0] * 2**16
for index in range(len(pcs)):
    pcs[index] = (index & 1) + pcs[index >> 1]
def popcnt(v):
    return (pcs[ v        & 0xffff] +
            pcs[(v >> 16) & 0xffff] +
            pcs[(v >> 32) & 0xffff] +
            pcs[(v >> 48)         ])

def f(n):
    if dp[n] >= 0:
        return dp[n]
    nn = n%popcnt(n)
    d = f(nn)+1
    dp[n] = d
    return d

tmp = pow(2, n)
for i in range(n-1, -1, -1):
    # ibit目を反転させる # つまり2**iを引く
    tmp //= 2
    if (nx>>i)&1:
        if nx-tmp == 0:
            print(0)
            continue
        r = (nx-tmp)%(pc-1)
    else:
        r = (nx+tmp)%(pc+1)

    if r > 0:
        print(f(r) + 1)
    else:
        print(1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = input()
memo = {}
X_int = int("0b"+X, 2)


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


pcf = popcount(int("0b"+X, 2))
pcm = pcf - 1
pcp = pcf + 1


def f(n: int, pc: int, ops: int):

    if n == 0:
        return ops
    else:
        if memo.get(n) is None:
            n %= pc
            ops += 1
            pc = popcount(n)
            return f(n, pc, ops)
        else:
            return memo[n]


def rev(x: str, i: int):
    x = list(x)
    if x[i] == "1":
        n = X_int - 2**(N-i-1)
        pc = pcm
    else:
        n = X_int + 2**(N-i-1)
        pc = pcp
    return (n, pc)


if __name__ == "__main__":
    for i in range(N):
        print(f(*rev(X, i), 0))

Submission status: Time Limit Exceeded

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

from collections import defaultdict

N = int(input())
X = input().strip()
L = list(X)

D = defaultdict(int)
D[0] = 0

def f(x, ans):
    ans += 1
    b = str(bin(x)[2:])
    c = b.count('1')
    m = x % c
    if m == 0:
        return ans
    return f(m, ans)


for i in range(1, 200001):
    D[i] = f(i, 0)

base = n = int(X, 2)
for i in reversed(range(N)):
    k = 1 << i
    if L[N-i-1] == '1':
        n = base - k
    else:
        n = base + k
    if n == 0:
        print(0)
    else:    
        print(f(n, 0))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python

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

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

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

t = []
for i in range(len(x)):
    tmpx = list(x)
    if tmpx[i] == '0':
        tmpx[i] = '1' 
    else:
        tmpx[i] = '0' 
    tmpx = ''.join(tmpx)    
    tmp = int(tmpx, 2)
    t.append(tmp)

for i in range(n):
    print(f(t[i]))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x_bin = input()
x = int(x_bin, 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)):
    if x_bin[n-i-1] == '1':
        a = x - pow(2, i)
        print(solve(a, pc_m))
    else:
        a = x + pow(2, i)
        print(solve(a, pc_p))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
xs=input()
xk=list(map(int,list(xs)))
xj=xk.count(1)

x=int(xs,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

for i in range(n-1,-1,-1):
    xi=x^(1<<i)
    pxi=xj
    if xk[n-1-i]==0:
        pxi=pxi+1
    else:
        pxi=pxi-1
#    print(i,xi,"pxi",pxi)
    if xi==0:
        print(0)
    else:
#        print("i",i,"xi",xi,"pxi",pxi)
        xi=xi%pxi
#        print("--i",i,"xi",xi,"pxi",pxi)
        if xi==0:
            print(1)
        else:
#            print("i",i,"xi",xi,"pxi",pxi)
#            print(i,pxi,xi,popcount(xi),xi%popcount(xi))
            icnt=1
            while xi>0:
                icnt+=1
                xi=xi%popcount(xi)
            print(icnt)

Submission status: Time Limit Exceeded

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

#N=3
#x="011"
def onecount(mojix):
    ones=0
    for j in mojix:
        if j=="1":
            ones+=1
    return ones


def popcount(X,ones,count):
    #print("popcount start",count,X,bin(X),ones)
    
    if ones==0:
        return count
    
    else:
        X=X%ones
        
        count+=1

        ones=onecount(str(bin(X)))
        
        return popcount(X,ones,count)

GroundOnes=onecount(x)
GroundX=int(x,2)

for i in range(N):
    
    if x[i]=="1":
        x_ith="0"
        ones=GroundOnes-1
        X=GroundX-2**(N-i-1)
    else:
        x_ith="1"
        ones=GroundOnes+1
        X=GroundX+2**(N-i-1)
            
    if i==0:
        new2bit=x_ith+x[i+1:]
    elif i<N-1:
        new2bit=x[:i]+x_ith+x[i+1:]
    else:
        new2bit=x[:i]+x_ith

    # print("for loop",i)
    # print("ones",ones)
    # print("new2bit",new2bit)
    # print(" ------ return --- ",popcount(X,ones,0))
    print(popcount(X,ones,0))

Submission status: Time Limit Exceeded

Solution code:
def popcount(n):
    result = 0
    while n > 0:
        n, mod = divmod(n, 2)
        result += mod
    return result


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

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

for i in range(N):
    print(func(int(X, 2) ^ (1 << (N - i - 1))))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
X = input()
pc = X.count('1')
nx = int(X, 2)

dp = [-1] * ((2*10**5)+1)
dp[0] = 0
dp[1] = 1
pcs = [-1] * ((2*10**5)+1)
pcs[0] = 0
for i in range(1, 18):
    pcs[2**i] = 1
    pcs[2**i-1] = i
def f(n):
    if dp[n] >= 0:
        return dp[n]
    if pcs[n] >= 0:
        pc = pcs[n]
    else:
        pc = bin(n).count('1')
        pcs[n] = pc
    nn = n%pc
    d = f(nn)+1
    dp[n] = d
    return d

tmp = pow(2, n)
for i in range(n-1, -1, -1):
    # ibit目を反転させる # つまり2**iを引く
    tmp //= 2
    if (nx>>i)&1:
        if nx-tmp == 0:
            print(0)
            continue
        r = (nx-tmp)%(pc-1)
    else:
        r = (nx+tmp)%(pc+1)

    if r > 0:
        print(f(r) + 1)
    else:
        print(1)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10000)

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

nbits=sum([int(X[i]) for i in range(N)])


# print(nbits)

MAXBIT=60
def strmod(bitstr,m):
    # print(bitstr, " m=", m)
    if len(bitstr)>MAXBIT:
        l = eval("0b"+bitstr[:MAXBIT])
        l_bitstr="{:b}".format(l % m)
        ans=strmod(l_bitstr+bitstr[MAXBIT:], m)
    else:
        ans="{:b}".format(eval("0b"+bitstr) % m)
    return ans

for i in range(N):

    if X[i]=='0':
        c='1'
        n = nbits + 1
    else:
        c='0'
        n = nbits - 1
    Y=X[:i]+c+X[i+1:]

    # print("Y=",Y)
    ans = 0
    while True:
        if n == 0:
            break
        ans += 1
        mstr = strmod(Y,n)
        n=sum([int(mstr[i]) for i in range(len(mstr))])
        # print(mstr, n)
        Y = mstr
    print(ans)

Submission status: Time Limit Exceeded

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

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

    X_int = int(X, 2)
    pcount_X = popcount(X_int)

    for i,bit in enumerate(X):
        Xi = X_int + 2**(N-i-1) * (-1)**int(bit)

        pcount_Xi = pcount_X + (-1)**int(bit)

        n = Xi
        pcount_n = pcount_Xi
        ans = 0
        while n > 0:
            ans += 1
            n %= pcount_n
            pcount_n = popcount(n)
        print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = int(input(), 2)
#print("X :{}".format(X))

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

def func_f(n):
    count = 0
    temp = n
    while(temp != 0):
        temp = temp % popcount(temp)
        count += 1
        
    return count


for i in range(1, N+1):
    #print(bin(X))
    #print(bin(1 << (N-i)))
    temp_x = X ^ (1 << (N-i))
    #print(temp_x)
      
    #print(bin(temp_x))

    print(func_f(temp_x))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache


def popcount(n):
    result = 0
    while n > 0:
        n, mod = divmod(n, 2)
        result += mod
    return result


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


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

for i in range(N):
    print(func(int(X, 2) ^ (1 << (N - i - 1))))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=str(input())
pop=[0]

for i in range(1,n):
    ni=0
    a=i
    while a:
        a&=(a-1)
        ni+=1
    pop.append(ni)

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
        
    count=1
    popi=0
    if xi!=0:
        xi=xi%x3
        while xi:
            xi%=pop[xi]
            count+=1
        print(count)
    else:
        print(0)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

hitCount = 0
H = {}

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

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

def pop(n):
    return "{0:b}".format(n).count('1')

def toZero(n):
    global hitCount
    global H
    if n==0:
        return 0
    if n==1:
        return 1
    if n in H:
        hitCount += 1
        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 = 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)):
    if x >> i & 1 == 1:
        a = x - pow(2, i)
        print(solve(a, pc_m))
    else:
        a = x + pow(2, i)
        print(solve(a, pc_p))

Submission status: Time Limit Exceeded

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

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

to_add = 1
tot = 0
counta = 0
for i in range(n-1,-1,-1):
    if s[i]=='1':
        tot+=to_add
        counta += 1

    to_add = 2*to_add
    
to_add = to_add//2

for i in range(n):
    if s[i]=='1':
        temp = tot-to_add
        tempa = counta-1
    else:
        temp = tot+to_add
        tempa = counta+1

    count = 0

    while temp>0:
        temp = temp%popcount(temp)
        count+=1
    print(count)
    
    to_add = to_add//2

Submission status: Time Limit Exceeded

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

s=x.count("1")
INT=int(x,2)
#print(n%s,s,INT)
for i in range(n):
    if x[i]=="0":
        S=s+1#1の数
        t=INT + 2**(n-i-1)
    else:
        S=s-1
        t=INT - 2**(n-i-1)
    if t==0:
        print(0)
        continue
    elif t%S==0:
        print(1)
        continue
    else:
        t%=S
    ans=1
    while True:
        if t==0:
            break
        t=t%(bin(t).count("1"))
        ans+=1
    print(ans)

Submission status: Time Limit Exceeded

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

def f(n):
    nn = n
    fcnt = 0
    while(nn > 0):
        nn = nn % popcont(nn)
        fcnt += 1
    return fcnt

N = int(input())
X = int(input(), 2)
for i in range(N - 1, -1, -1):
    rbx = (X & ~pow(2, i))
    rby = ~X & pow(2, i)
    rbz = bin(rbx | rby)
    print(f(int(rbz, 0)))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import sys
import itertools
import array
import textwrap
import math

N = int(input())
X = input()
temp = X.count("1")
t = [0, 0, 0]

t[0] = int(X, 2) % (temp-1) if temp != 1 else 0
# t[1] = int(X, 2) % (temp)
t[2] = int(X, 2) % (temp+1)
# print(X)
cnt = 0
# X = int(X, 2)
# print(X)
for i in range(N):
    if X[i] == "1" and temp == 1:
        print(0)
        continue
    if X[i] == "1":
        p = (1 << (N-i-1)) % (temp-1)
        a = (t[0]-p) % (temp-1)
    elif X[i] == "0":
        m = (1 << (N-i-1)) % (temp+1)
        a = (t[2]+m) % (temp+1)
    cnt = 1
    # print(a)
    while a > 0:
        a = a % format(a, 'b').count("1")
        # print(a)
        cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:


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

def f(n):
    k = n
    cnt = 0
    while k>0:
        k = k%popcnt(k)
        cnt+= 1
    return cnt

def solve(X):
    for i in reversed(range(N)):
        if P[N-1-i] == 0:
            print(0)
        else:
            K = X ^ (1 << i)
            K2 = K%P[N-1-i]
            print(f(K2) + 1)




N = int(input())
X = input()
X = X.zfill(N)
count_1 = X.count("1")

P = [0]*N
for i in range(N):
    if X[i] == "1":
        P[i] = count_1 - 1
    else:
        P[i] = count_1 + 1
Y = int(X,2)

solve(Y)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
b=int(s,2)
n=200000
b=2**200001-1
s=format(b,"b")
ls=[0]*n
bi=2**(n-1)
xf=s.count("1")
kp=b%(xf+1)
km=b%(xf-1)
for i in range(n):
  if s[i]=="1":
    k=(km-bi)%(xf-1)
  else:
    k=(kp+bi)%(xf+1)
  ans=1
  while k>0:
    x=format(k, 'b').count("1")
    k=k%x
    ans+=1
  print(ans)
  bi=bi//2

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N = int(input())
    X = input()
    count1 = X.count('1')
    X = int('0b'+X,0)

    def f(X, result):
        x = X
        count = 0
        while x > 0:
            if x % 2 == 1:
                count += 1
            x //= 2
        X = X % count
        result += 1
        if X == 0:
            return print(result)
        else:
            f(X, result)


    for i in range(N-1,-1,-1):
        x = X^(1<<i)
        if x==0:
            print(0)
        else:
            if (x>>i)&1:
                c = count1+1
            else:
                c = count1-1
            x %= c
            if x==0:
                print(1)
            else:
                f(x,1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
 
X = input()
 
pop_X = X.count('1')

X_int = int(X, 2)

X_list = list(X)

for i in range(N):
    
    a = X_list[i]
    
    pop_X_a = pop_X + int((-2) * int(a) + 1)
    pop_n = pop_X_a
    
    n = X_int + int( ((-2) * int(a) + 1) * (2 ** (N - i -1)) )
    
    count = 0
    
    while n != 0:
        
        n = n %  pop_n
        
        pop_n = bin(n).count('1')
        
        count += 1
    
    print(count)

Submission status: Time Limit Exceeded

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

def onecount(mojix):
    ones=0
    for j in mojix:
        if j=="1":
            ones+=1
    return ones


def popcount(new2bit,ones,count):
    #print("popcount start",count,new2bit,int(new2bit,2),ones)
    
    if ones==0:
        return count
    
    else:
        ten=int(new2bit,2)
        div=ten%ones
        
        count+=1
        
        new2bit=bin(div)
        ones=onecount(str(new2bit))
        
        return popcount(new2bit,ones,count)

GroundOnes=onecount(x)

for i in range(N):
    
    if x[i]=="1":
        x_ith="0"
        ones=GroundOnes-1
    else:
        x_ith="1"
        ones=GroundOnes+1
        
    if i==0:
        new2bit=x_ith+x[i+1:]
    elif i<N-1:
        new2bit=x[:i]+x_ith+x[i+1:]
    else:
        new2bit=x[:i]+x_ith

        
    #ones=onecount(new2bit)
    print(popcount(new2bit,ones,0))

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):
    ans = 0

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

    a = a % temp_num_of_1

    ans += 1 + f(a)

    print(ans)

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((x1 + z % (xc + 1)) % (xc + 1)))
        else:
            if x - z == 0:
                print(0)
            else:
                if x2 == -1:
                    print(0)
                else:
                    print(1 + popcount((x2 - z % (xc - 1)) % (xc - 1)))



    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import numpy as np


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


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


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

for i in range(N):
    print(func(int(X, 2) ^ (1 << (N - i - 1))))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

from collections import defaultdict
PCmemo = defaultdict(lambda: -1)
fnmemo = defaultdict(lambda: -1)
fnmemo[0]=0

def dfs(X):
    if fnmemo[X]==-1:
        if PCmemo[X]==-1:
            popcount = bin(X).count("1")
            PCmemo[X]=popcount
        else:
            popcount = PCmemo[X]

        if popcount == 1:
            fnmemo[X]=1
            return 1

        fnmemo[X] = dfs(X%popcount)+1

    return fnmemo[X]

Xpopcount = bin(X).count("1")

for i in reversed(range(n)):
    neX = X^(1<<i)

    if X & (1 << i):
        PCmemo[neX] = Xpopcount-1
    else:
        PCmemo[neX] = Xpopcount+1

    if neX==0:
        ans=0
    else:
        ans=dfs(neX%PCmemo[neX])+1
    fnmemo[neX]=ans
    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 = bin(tmp).count('1')
    ans+=1
    tmp = tmp%cnt
#print(pre)

X = int(input(),2)
S = bin(X).count('1')

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:
N = int(input())
 
X = input()
 
pop_X = X.count('1')

X_int = int(X, 2)

for i in range(N):
    X_list = list(X)

    pop_X_a = pop_X + int((-2) * int(X_list[i]) + 1)
    pop_n = pop_X_a
    
    n = X_int + int( ((-2) * int(X_list[i]) + 1) * (2 ** (N - i -1)) )
    
    count = 0
    
    while n != 0:
        
        n = n %  pop_n
        
        pop_n = bin(n).count('1')
        
        count += 1
    
    print(count)

Submission status: Time Limit Exceeded

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

  for i in range(N):
    tar_X = list(X)
    tar_X[i] = "0" if tar_X[i] == "1" else "1"
    target_int = int(''.join(tar_X), 2)
    count = 0
    while target_int != 0:
      num_of_1 = bin(target_int).count("1")
      tmp = target_int % num_of_1
      # print("{0} % {1} = {2}".format(target_int, num_of_1, tmp))
      target_int = tmp
      count += 1
    print(count)

if __name__ == "__main__":
  resolve()

Submission status: Time Limit Exceeded

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

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

X_int = int(X, 2)
pcount_X = popcount(X_int)

for i,bit in enumerate(X):
    mask_list = ['0']*N
    mask_list[i] = '1'
    mask_int = int(''.join(mask_list), 2)
    Xi = X_int ^ mask_int

    pcount_Xi = pcount_X + (-1)**int(bit)
    
    n = Xi
    pcount_n = pcount_Xi
    ans = 0
    while n > 0:
        ans += 1
        n %= pcount_n
        pcount_n = popcount(n)
    print(ans)

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] % popcount(start[k])

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

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import numpy as np


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

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

for i in range(N):
    print(func(int(X,2)^(1<<(N-i-1))))

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 = 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):
    ans = 0

    if x[i] == "0":
        temp_num_of_1 = num_of_1 + 1
        a = first + 2 ** (n - i - 1)
    else:
        temp_num_of_1 = num_of_1 - 1
        a = 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())
n = 2 * 10**5

# s = input()
s = ''.join(['1' for i in range(n)])


bin = int(s, 2)
originalPopCount = s.count('1')
memo = dict()

def popCount(value):

    count = 1
    current = value

    while current != 0:
        if current in memo:
            return count + memo[current]
        pop = format(current, 'b').count('1')
        m = current % pop
        current = m
        count += 1
    return count

result = []
p1 = bin % (originalPopCount + 1)
m1 = bin % (originalPopCount - 1)

for i in range(n):

    if s[i] == '1':
        rep = '0'
        currentPop = originalPopCount - 1
        m_base = m1
    else:
        rep = '1'
        currentPop = originalPopCount + 1
        m_base = p1

    pop2 = 2 ** (n - 1 - i) % currentPop

    m = (m_base + pop2) % currentPop

    if m == 0:
        result.append(1)
        continue

    val = m

    result.append(popCount(val))

print(*result, sep='\n')

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':
        ctmp = cnt - 1
        if ctmp == 0:
            print(0)
            continue
        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:
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 + 2 ** (n - i - 1),popcount+1))
        else:
            print(countbin(xint - 2 ** (n - i - 1),popcount-1))
if __name__ == "__main__":
    main() #endline===============================================