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 = str(input())
count = X.count("1")
num, nump, numm = 0, 0, 0
now, nowp, nowm = 1, 1, 1

xx = [0] * N
x_plus = [0] * N
x_minus = [0] * N
for i in range(1, N + 1):
  if i != 1:
    if count > 0:
      now *= 2
      nowp *= 2
    
    now %= count
    nowp %= (count + 1)
    
    if count >= 2:
      nowm *= 2
      nowm %= (count - 1)
  
  else:
    if count >= 1:
      now %= count
    nowp %= (count + 1)
    if count >= 2:
      nowm %= (count - 1) 
  xx[i - 1] = now
  x_plus[i - 1] = nowp
  x_minus[i - 1] = nowm
  if X[-i] == "1":
    if count > 0:
      num += now
      num %= count
    nump += nowp
    nump %= count + 1
    if count > 1:
      numm += nowm
      numm %= count - 1
    
#print(num, xx, x_plus, x_minus)    

nextn = [0] * N
#ans = [1] * N
for i in range(N):
  if count == 0:
    nextn[i] = 0
  else:  
    if X[i] == "0":
      a = nump + x_plus[N - 1 - i]
      b = count + 1
      #print(a, b)
      nextn[i] = a % b
    else:
      #if count == 2:
      #  nextn[i] = 0
      #else:
        a = numm - x_minus[N - 1 - i]
        b = count - 1
        if b > 0:
          nextn[i] = a % b
        else:
          while True:
            a = 1
          nextn[i] = 0
        
#print(nextn)    
for i in range(N):
  if nextn[i] == 0:
    print("1")
  else:
    nownow = nextn[i]
    ans = 1
    while nownow != 0:
      alpha = bin(nownow)[2:]
      beta = str(alpha).count("1")
      nownow %= beta
      ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = input()
zero_pop = X.count('1') + 1
one_pop = X.count('1') - 1
def popcount(n):
    return bin(n).count('1')
memo = {0:0}
def f_count(n):
    if n in memo:
        return memo[n]
    memo[n] = f_count(n % popcount(n)) + 1
    return f_count(n % popcount(n)) + 1
for i in range(N):
    x = int(X, 2)
    if X[i] == '1' and X.count('1') == 1:
        print(0)
        continue
    if X[i] == '1':
        x -= 2 ** (N-1-i)
        x %= one_pop
    elif X[i] == '0':
        x += 2 ** (N-1-i)
        x %= zero_pop
    
    print(f_count(x) + 1)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache


a = int(input())
b = input()

@lru_cache(maxsize=None)
def func(c):
    c = [int(z) for z in c]
    x = int(sum(c))
    if x == 0:
        return 0
    n = 1
    nsum = 0
    for i in reversed(c):
        nsum += n * i
        n = n % x if n > x else n
        if n == 0:
            break
        n *= 2
    nsum %= x
    cans = bin(nsum).count("1")
    if cans == 0:
        return 1
    else:
        return 1 + func(bin(nsum)[2:])




for i in range(a):
    ran = list(b)
    ran[i] = "0" if ran[i] == "1" else "1"
    c = "".join(ran)
    print(func(c))

Submission status: Time Limit Exceeded

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

for i in range(1, N+1):
    count = 0
    Xi = i
    if X[i-1] == '0':
        Xi = int(X, 2) + 2 ** (N-i)
    else:
        Xi = int(X, 2) - 2 ** (N-i)
    while Xi != 0:
        popcount = str(bin(Xi)).count('1')
        Xi = Xi % popcount
        count += 1
    print(count)

Submission status: Time Limit Exceeded

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

def popcount2(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f

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

x_pop = popcount(x)
for i in reversed(range(0,n)):
    try:
        if x&(1<<i):
            tmp_pop = x_pop - 1
        else:
            tmp_pop = x_pop + 1
        tmp = (x^(1<<i)) % tmp_pop
        if tmp <= 0:
            print(1)
            continue
        cnt = 2
        tmp2 = tmp % popcount(tmp)
        while tmp2 > 0:
            tmp %= popcount(tmp)
            cnt += 1
            tmp2 %= popcount(tmp2)
        print(cnt)
    except:
        print(0)

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 m <= 0:
        return "0"

    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

precalc_str_plus = strmod(X,nbits+1)
precalc_str_minus = strmod(X,nbits-1)

precalc_plus = eval('0b'+precalc_str_plus)
precalc_minus = eval('0b'+precalc_str_minus)

# print(precalc_plus, precalc_minus)

for i in range(N):



    Y='1'+'0'*(N-i-1)
    modY_str_plus = strmod(Y,nbits+1)
    modY_str_minus = strmod(Y,nbits-1)

    modY_plus = eval('0b'+modY_str_plus)
    modY_minus = eval('0b'+modY_str_minus)

    # print("i=",i, "Y='",Y,"' ", precalc_plus, modY_plus, precalc_minus, modY_minus)

    if X[i]=='0':
        m = (precalc_plus + modY_plus) % (nbits+1)
        ans = 1
    else:
        if nbits == 1:
            m=0
            ans = 0
        else:
            m = (nbits-1 + precalc_minus - modY_minus) % (nbits-1)
            ans = 1

    while m > 0:
        # print(ans, "m=", m)
        ans += 1
        mstr = "{:b}".format(m)
        m = m % sum([int(mstr[i]) for i in range(len(mstr))])

    print(ans)

Submission status: Time Limit Exceeded

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

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

def f(x):
    #print('f(x), x: {}'.format(x))
    if x==0:
        return 0
    else:
        ans=f(x%popcount(x))+1
        #print(ans)
        return ans    

def main(n,x):
    m=x.count('1')
    #print('m: {}'.format(m))
    xint=int(x,2)
    #print('xint: {}'.format(xint))
    ans=[]
    b=2**(n-1)
    for i in range(n):
        if x[i]=='1':
            if m==1:
                ans.append(0)
            else:
                xx=(xint-b)%(m-1)
                ans.append(f(xx)+1)
        else:
            xx=(xint+b)%(m+1)
            ans.append(f(xx)+1)
        b=b//2
    return ans

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

Submission status: Time Limit Exceeded

Solution code:
# 2125
# 方針．f(n)を求めるのがlog(N)で終わりそうだから普通に素直に実装すればいいのでは？
# ただし最初だけは別に実装する必要がある
N = int(input())
X = list(input())

# i番目のビットを反転させて,
# やってることは似てるはずなのになんかうまく行かない
dic={}
bn00 = X.count('1')
x00 = int(''.join(X),2)

for i in range(N):
    # ちゃんともとに戻してね，ということで本のビット
    b = int(X[i]) & 1
    bn = b ^ 1
    if bn:
        bn0 = bn00 + 1
    else:
        bn0 = bn00 - 1
    if bn0==0: # ビットが全く立っていないつまり0の時，0%0はエラーを起こすので，n%0もエラーを起こす
        print(0)
        continue
    x0 = x00 % bn0
    if b: # もとのビットが立っている場合は減らす，ここの計算量が一番重いので計算量を削減してみる
        xi = x0 - b * pow(2,N-1-i,bn0)
    if bn:
        xi = x0 + bn * pow(2, N - 1 - i, bn0)
    xi %= bn0
    num = xi
    count = 1
    while num > 0:
        p = format(num,'b').count('1') # 10進数を２進数にかえるなら，これがいいのかも,int(str(i),2)を使うっていう手もあるけど周りくどい
        num = num % p
        count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
#AIsing2020 d

def f(n):
        cnt = 0
        while n:
            cnt+= 1
            n = n%bin(n).count('1')
        return cnt

def main():
    N = int(input())
    X = input()
    X10 = int(X,2)
    X10_num1 = X.count('1')
    X10_pulse = X10%(X10_num1+1)
    X10_ninus = X10%(X10_num1-1) if X10_num1 >1 else 0


    for i in range(N,0,-1):
        j = N-i
        if (X[j] == '1') and X10_num1 >1:
            amari = (X10_ninus - (2**(i-1))%(X10_num1-1))%(X10_num1-1)
        elif (X[j] == '1') and X10_num1 ==1:
            print(0)
            continue
        else:
            amari = (X10_pulse + (2**(i-1))%(X10_num1+1))%(X10_num1+1)

        print(1+f(amari))


main()

Submission status: Time Limit Exceeded

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

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


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


for i in range(N):
    X_i = X ^ (1<<(N-i-1))
    print(f(X_i))

Submission status: Time Limit Exceeded

Solution code:
from numba import jit
from copy import deepcopy

n = int(input())
s = input()

@jit
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:
# 2125
# 方針．f(n)を求めるのがlog(N)で終わりそうだから普通に素直に実装すればいいのでは？
N = int(input())
X = list(input())

# i番目のビットを反転させて,
# やってることは似てるはずなのになんかうまく行かない
dic={}
bn00 = X.count('1')
x00 = int(''.join(X),2)

for i in range(N):
    # ちゃんともとに戻してね，ということで本のビット
    b = int(X[i]) & 1
    bn = b ^ 1
    if bn:
        bn0 = bn00 + 1
    else:
        bn0 = bn00 - 1
    if bn0==0: # ビットが全く立っていないつまり0の時，0%0はエラーを起こすので，n%0もエラーを起こす
        print(0)
        continue
    x0 = x00 % bn0
    xi = x0 - b * pow(2,N-1-i,bn0) + bn * pow(2,N-1-i,bn0)
    xi %= bn0
    num = xi
    count = 1
    while num > 0:
        p = format(num,'b').count('1') # 10進数を２進数にかえるなら，これがいいのかも,int(str(i),2)を使うっていう手もあるけど周りくどい
        num = num % p
        count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
#AIsing2020 d

def f(n):
        cnt = 0
        while n:
            cnt+= 1
            n = n%bin(n).count('1')
        return cnt

def main():
    N = int(input())
    X = input()
    X10 = int(X,2)
    X10_num1 = X.count('1')
    X10_pulse = X10%(X10_num1+1)
    X10_ninus = X10%(X10_num1-1) if X10_num1 >1 else 0


    for i in range(N,0,-1):
        if (X10>>(i-1) & 1) and X10_num1 >1:
            amari = (X10_ninus - (2**(i-1))%(X10_num1-1))%(X10_num1-1)
        elif (X10>>(i-1) & 1) and X10_num1 ==1:
            print(0)
            continue
        else:
            amari = (X10_pulse + (2**(i-1))%(X10_num1+1))%(X10_num1+1)

        print(1+f(amari))


main()

Submission status: Time Limit Exceeded

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

def F(n:int)->int:
    res = 0
    while 0 < n:
        pop = bin(n).count('1')
        n %= pop
        res += 1
    return res

for i in range(N-1, -1, -1):
    mask = 2**i
    ans = F(X ^ mask)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
#AIsing2020 d

def f(n):
        cnt = 0
        while n:
            cnt+= 1
            n = n%bin(n).count('1')
        return cnt

def main():
    N = int(input())
    X = input()
    X10 = int(X,2)
    X10_num1 = X.count('1')
    X10_pulse = X10%(X10_num1+1)
    X10_ninus = X10%(X10_num1-1) if X10_num1 >1 else 0


    for i in range(N,0,-1):
        a = X10
        if (a>>(i-1) & 1) and X10_num1 >1:
            amari = (X10_ninus - (2**(i-1))%(X10_num1-1))%(X10_num1-1)
        elif (a>>(i-1) & 1) and X10_num1 ==1:
            print(0)
            continue
        else:
            amari = (X10_pulse + (2**(i-1))%(X10_num1+1))%(X10_num1+1)

        print(1+f(amari))


main()

Submission status: Time Limit Exceeded

Solution code:
#AIsing2020 d

def f(n):
        cnt = 0
        while n:
            cnt+= 1
            n = n%bin(n).count('1')
        return cnt

def main():
    N = int(input())
    X = input()
    X10 = int(X,2)
    X10_num1 = X.count('1')
    X10_pulse = X10%(X10_num1+1)
    X10_ninus = X10%(X10_num1-1) if X10_num1 >1 else 0


    for i in range(N,0,-1):
        a = X10
        if (a>>(i-1) & 1) and X10_num1 >1:
            a -= 2**(i-1)
            amari = (X10_ninus - (2**(i-1))%(X10_num1-1))%(X10_num1-1)

        elif (a>>(i-1) & 1) and X10_num1 ==1:
            print(0)
            continue
        else:
            a += 2**(i-1)
            amari = (X10_pulse + (2**(i-1))%(X10_num1+1))%(X10_num1+1)

        print(1+f(amari))


main()

Submission status: Time Limit Exceeded

Solution code:
#AIsing2020 d

def main():
    N = int(input())
    X = input()
    X10 = int(X,2)
    X10_num1 = X.count('1')
    X10_pulse = X10%(X10_num1+1)
    X10_ninus = X10%(X10_num1-1) if X10_num1 >1 else 0


    for i in range(N,0,-1):
        a = X10
        if (a>>(i-1) & 1) and X10_num1 >1:
            a -= 2**(i-1)
            amari = (X10_ninus - (2**(i-1))%(X10_num1-1))%(X10_num1-1)

        elif (a>>(i-1) & 1) and X10_num1 ==1:
            print(0)
            continue
        else:
            a += 2**(i-1)
            amari = (X10_pulse + (2**(i-1))%(X10_num1+1))%(X10_num1+1)
        nc = amari 
        if a ==0:
            co = 0
        else:
            co = 1
            while nc >0:
                bin_str = bin(nc)
                cou1 = bin_str.count('1')
                nc = nc%cou1
                co +=1
        
        print(co)


main()

Submission status: Time Limit Exceeded

Solution code:
#AIsing2020 d
 
N = int(input())
X = input()
X10 = int(X,2)
X10_num1 = X.count('1')
X10_pulse = X10%(X10_num1+1)
X10_ninus = X10%(X10_num1-1) if X10_num1 >1 else 0


for i in range(N,0,-1):
    a = X10
    if (a>>(i-1) & 1) and X10_num1 >1:
        a -= 2**(i-1)
        amari = (X10_ninus - (2**(i-1))%(X10_num1-1))%(X10_num1-1)

    elif (a>>(i-1) & 1) and X10_num1 ==1:
        print(0)
        continue
    else:
        a += 2**(i-1)
        amari = (X10_pulse + (2**(i-1))%(X10_num1+1))%(X10_num1+1)
    nc = amari 
    if a ==0:
        co = 0
    else:
        co = 1
        while nc >0:
            bin_str = bin(nc)
            cou1 = bin_str.count('1')
            nc = nc%cou1
            co +=1
    
    print(co)

Submission status: Time Limit Exceeded

Solution code:

from functools import lru_cache


a = int(input())
b = input()

@lru_cache(maxsize=None)
def func(c):
    x = c.count("1")
    if x == 0:
        return 0
    n = 1
    nsum = 0
    for i in reversed(range(len(c))):
        nsum += n * int(c[i])
        n = n % x if n > x else n
        if n == 0:
            break
        n *= 2
    nsum %= x
    cans = bin(nsum).count("1")
    if cans == 0:
        return 1
    else:
        return 1 + func(bin(nsum)[2:])

for i in range(a):
    s = list(b)
    s[i] = "0" if s[i] == "1" else "1"
    c = "".join(s)
    print(str(func(c)))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = input()
Y = int(X, 2)
C = X.count('1')

def popcount(n):
    if n == 0:
        return 0
    return 1 + popcount(n % bin(n).count('1'))

for i in range(N):
    if X[i] == '0':
        print(popcount(Y + pow(2, N-i-1)))
    else:
        print(popcount(Y - pow(2, N-i-1)))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache


a = int(input())
b = input()

@lru_cache(maxsize=1000)
def func(c):
    x = c.count("1")
    if x == 0:
        return 0
    n = 1
    nsum = 0
    for i in reversed(range(len(c))):
        nsum += n * int(c[i])
        n = n % x if n > x else n
        if n == 0:
            break
        n *= 2
    nsum %= x
    cans = bin(nsum).count("1")
    if cans == 0:
        return 1
    else:
        return 1 + func(bin(nsum)[2:])

for i in range(a):
    s = list(b)
    s[i] = "0" if s[i] == "1" else "1"
    c = "".join(s)
    print(str(func(c)))

Submission status: Time Limit Exceeded

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

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

def calc(num):
    ans = 1
    while num > 0:
        ans += 1
        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):
    cnt = CNT
    dec = DEC
    ans = 0
    m = 1
    if X[i] == '0':
        m = 1
    else:
        m = -1
    cnt += m
    if cnt == 0:
        print(0)
        continue
    else:
        dec = (dec + (m * (2**(N-1-i)))) % cnt
        print(calc(dec))

Submission status: Time Limit Exceeded

Solution code:
a = int(input())
b = input()

def func(c):
    x = c.count("1")
    if x == 0:
        return 0
    n = 1
    nsum = 0
    for i in reversed(range(len(c))):
        nsum += n * int(c[i])
        n = n % x if n > x else n
        if n == 0:
            break
        n *= 2
    nsum %= x
    cans = bin(nsum).count("1")
    if cans == 0:
        return 1
    else:
        return 1 + func(bin(nsum)[2:])

for i in range(a):
    s = list(b)
    s[i] = "0" if s[i] == "1" else "1"
    c = "".join(s)
    print(str(func(c)))

Submission status: Time Limit Exceeded

Solution code:
a = int(input())
b = input()

def func(c):
    x = c.count("1")
    if x == 0:
        return 0
    n = 1
    nsum = 0
    for i in reversed(range(len(c))):
        nsum += n * int(c[i])
        if n > x:
            n = n % x
        if n == 0:
            break
        n *= 2
    nsum %= x
    cans = bin(nsum).count("1")
    if cans == 0:
        return 1
    else:
        return 1 + func(bin(nsum)[2:])
def func2():
    for i in range(a):
        s = list(b)
        s[i] = "0" if s[i] == "1" else "1"
        c = "".join(s)
        print(str(func(c)))
func2()

Submission status: Time Limit Exceeded

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

#n = int(input())
#l = list(map(int, input().split()))

'''
a=[]
b=[]
for i in range():
    A, B = map(int, input().split())
    a.append(A)   
    b.append(B)'''

n=int(input())
x=list(input().strip("\n"))
cnt=0
for i in range(n):
    if x[i]=="1":
        cnt+=1

pre=int("".join(x),2)
#print(pre)
for i in range(n):
    if x[i]=="1":
        #t=-1
        ad=-2**(n-1-i)
    else:
        #t=1
        ad=2**(n-1-i)
    #cnt+=t
    now=pre+ad
    ans=0
    while now!=0:
        now%=bin(now).count("1")
        ans+=1
        
    print(ans)
    #cnt-=t

Submission status: Time Limit Exceeded

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

#n = int(input())
#l = list(map(int, input().split()))

'''
a=[]
b=[]
for i in range():
    A, B = map(int, input().split())
    a.append(A)   
    b.append(B)'''

n=int(input())
x=input().strip("\n")
cnt=0
for i in range(n):
    if x[i:i+1]=="1":
        cnt+=1

#xx=list(x)
pre=int(x,2)
#print(pre)
for i in range(n):
    if x[i:i+1]=="1":
        #t=-1
        ad=-2**(n-1-i)
    else:
        #t=1
        ad=2**(n-1-i)
    #cnt+=t
    now=pre+ad
    ans=0
    while now!=0:
        now%=bin(now).count("1")
        ans+=1
        
    print(ans)
    #cnt-=t

Submission status: Time Limit Exceeded

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

#n = int(input())
#l = list(map(int, input().split()))

'''
a=[]
b=[]
for i in range():
    A, B = map(int, input().split())
    a.append(A)   
    b.append(B)'''
from copy import copy

n=int(input())
x=input().strip("\n")
cnt=0
for i in range(n):
    if x[i:i+1]=="1":
        cnt+=1

#xx=list(x)
pre=int(x,2)
#print(pre)
for i in range(n):
    if x[i:i+1]=="1":
        t=-1
        ad=-2**(n-1-i)
    else:
        t=1
        ad=2**(n-1-i)
    cnt+=t
    now=pre+ad
    ans=0
    use=copy(cnt)
    while now>0:
        #print(now,use)
        now%=bin(now).count("1")
        ans+=1
    print(ans)
    cnt-=t

Submission status: Time Limit Exceeded

Solution code:
def input_int():
    return map(int, input().split())

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

N=one_int()
S=one_str()

bit_count = S.count("1")
S_min = int(S,2) % (bit_count-1) if bit_count-1!=0 else 0
S_plu = int(S,2) % (bit_count+1)
S_num = int(S,2)

def mods(temp, count):
    count+=1
    while temp!=0:

#         if temp in res_dict:
#             print(count, temp, res_dict[temp])
#             print("come")
#             print()
#             return count+res_dict[temp]
        
#         if calc_dict[temp]==-1:
        bits = bin(temp).count("1")
            
        temp = temp%bits
        count+=1

    return count

for i in range(len(S)):
    if S[i]=="0":
        part = (2**(N-i-1))% (bit_count+1)
        num = (S_plu + part ) % (bit_count+1)
        if num==0:
            print(1)
        else:
            print(mods(num, 0))
    else:
        if S_num == 2**(N-i-1):
            print(0)
            continue
        part = (2**(N-i-1))% (bit_count-1)
        num = (S_min - part)%(bit_count-1)
        if num==0:
            print(1)
        else:
            print(mods(num, 0))

Submission status: Time Limit Exceeded

Solution code:
a = int(input())
b = input()

def func(c):
    x = c.count("1")
    if x == 0:
        return 0
    n = 1
    nsum = 0
    for i in reversed(range(len(c))):
        nsum += n * int(c[i])
        if n > x:
            n = n % x
        if n == 0:
            break
        n *= 2
    nsum %= x
    cans = bin(nsum).count("1")
    if cans == 0:
        return 1
    else:
        return 1 + func(bin(nsum)[2:])

for i in range(a):
    s = list(b)
    s[i] = "0" if s[i] == "1" else "1"
    print(str(func("".join(s))))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

xl = np.array(list(x))
xl = xl.astype(np.int64)
m = xl.sum()

for i in range(n):
    if x[i] == '0':
        tmp = '1'
        mm =  m + 1
    else:
        tmp = '0'
        mm =  m - 1
        
    xx = x[:i] + tmp + x[i+1:]
    xx = int(xx, 2)
    
    cnt = 0
    while xx:
        xx %= mm
        xxl = np.array(list(bin(xx)[2:]))
        xxl = xxl.astype(np.int64)
        mm = xxl.sum()
        cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

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

#n = int(input())
#l = list(map(int, input().split()))

'''
a=[]
b=[]
for i in range():
    A, B = map(int, input().split())
    a.append(A)   
    b.append(B)'''
from copy import copy

n=int(input())
x=input().strip("\n")
cnt=0
for i in range(n):
    if x[i:i+1]=="1":
        cnt+=1

#xx=list(x)
pre=int(x,2)
#print(pre)
for i in range(n):
    if x[i:i+1]=="1":
        t=-1
        ad=-2**(n-1-i)
    else:
        t=1
        ad=2**(n-1-i)
    cnt+=t
    now=pre+ad
    ans=0
    use=copy(cnt)
    while now>0:
        #print(now,use)
        now%=use
        ans+=1
        use=0
        #print(bin(now)[2:])
        """for j in range(len(bin(now)[2:])):
            if bin(now)[2+j:3+j]=="1":
                use+=1"""
        bit=int(bin(now)[2:],2)
        #print(bit)
        while bit!=0:
            use+=1
            #print(bit)
            bit=bit&(bit-1)
    print(ans)
    cnt-=t

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=list(input())
num=""
ans,be,af="","",""
one,count,on=0,0,""

for i in range(n):
  
  if x[i]=="1":
    num="0"
    
  else:
    num="1"
    
  be="".join(x[:i])
  af="".join(x[i+1:])
  
  ans=be+num+af
  one=ans.count("1")
  ans=int(ans,2)
  
  while ans!=0:
    ans%=one
    on=bin(ans)
    one=on.count("1")
    ans=int(on,2)
    count+=1
    
  print(count)
  count=0

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

xl = list(x)
xl = np.array([int(s) for s in xl])
m = xl.sum()

for i in range(n):
    if x[i] == '0':
        tmp = '1'
        mm =  m + 1
    else:
        tmp = '0'
        mm =  m - 1
        
    xx = x[:i] + tmp + x[i+1:]
    xx = int(xx, 2)
    
    cnt = 0
    while xx:
        xx %= mm
        xxl = list(bin(xx)[2:])
        xxl = np.array([int(s) for s in xxl])
        mm = xxl.sum()
        cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

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

#n = int(input())
#l = list(map(int, input().split()))

'''
a=[]
b=[]
for i in range():
    A, B = map(int, input().split())
    a.append(A)   
    b.append(B)'''
from copy import copy

n=int(input())
x=input().strip("\n")
cnt=0
for i in range(n):
    if x[i:i+1]=="1":
        cnt+=1

xx=list(x)
pre=int(x,2)
#print(pre)
for i in range(n):
    if xx[i]=="1":
        xx[i]="0"
        t=-1
        ad=-2**(n-1-i)
    else:
        xx[i]="1"
        t=1
        ad=2**(n-1-i)
    cnt+=t
    #print(ad)
    now=pre+ad
    ans=0
    use=copy(cnt)
    #print(use,now)
    while now>0:
        #print(now,use)
        now%=use
        ans+=1
        use=0
        #print(bin(now)[2:])
        for j in range(len(bin(now)[2:])):
            if bin(now)[2+j:3+j]=="1":
                use+=1
        
    print(ans)
    cnt-=t

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = input()
    
cnt_1 = 0
for i in X:
    if i == '1':
        cnt_1 += 1

for i in range(N):
    if X[i] == '1':
        n = int(X, 2) - (1 << (N-i-1))
        tmp_cnt_1 = cnt_1 - 1
    else:
        n = int(X, 2) + (1 << (N-i-1))
        tmp_cnt_1 = cnt_1 + 1
        
    if n == 0:
        print(0)
        continue

    n = n % tmp_cnt_1
    cnt = 1

    while n != 0:
        c = 0
        for j in bin(n):
            c += j=='1'
        n = n % c
        cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

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

X_int = int(X, 2)
pcXi01 = bin(X_int).count('1') + 1
pcXi10 = bin(X_int).count('1') - 1
if pcXi10 < 1:
  pcXi10 = 1
Xmod01 = X_int % pcXi01
Xmod10 = X_int % pcXi10

tmp01 = [1]
tmp10 = [-1]
for i in range(N - 1):
  tmp01.append(tmp01[i]*2 % pcXi01)
  tmp10.append(tmp10[i]*2 % pcXi10)

init_n = [0] * N
next_n = [0] * N
for i in range(N):
  X_list = list(X)
  if X_list[i] == '0':
    X_list[i] = '1'
    Xi_str = ''.join(X_list)
    init_n[i] = int(Xi_str, 2)
    next_n[i] = (Xmod01 + tmp01[N - 1 - i]) % pcXi01
  else:
    X_list[i] = '0'
    Xi_str = ''.join(X_list)
    init_n[i] = int(Xi_str, 2)
    next_n[i] = (Xmod10 + tmp10[N - 1 - i]) % pcXi10

for i in range(N):
  fn = 0
  n = init_n[i]
  if n != 0:
    n = next_n[i]
    fn += 1
  while n != 0:
    n = n % bin(n).count('1')
    fn += 1
  
  print(fn)

Submission status: Time Limit Exceeded

Solution code:

a = int(input())
b = input()

def func(c):
    x = c.count("1")
    if x == 0:
        return 0
    n = 1
    nsum = 0
    for i in reversed(range(len(c))):
        if c[i] == "1":
            nsum += n
            if n > x:
                n = n % x
        if n == 0:
            break
        n *= 2
    nsum %= x
    cans = bin(nsum).count("1")
    if cans == 0:
        return 1
    else:
        return 1 + func(bin(nsum))

for i in range(a):
    s = list(b)
    s[i] = "0" if s[i] == "1" else "1"
    c = "".join(s)
    print(str(func(c)))

Submission status: Time Limit Exceeded

Solution code:

a = int(input())
b = input()

def func(c):
    x = c.count("1")
    if x == 0:
        return 0
    n = 1
    nsum = 0
    for i in reversed(range(len(c))):
        if c[i] == "1":
            nsum += n
            if n > x:
                n = n % x
        n *= 2
    nsum %= x
    cans = bin(nsum).count("1")
    if cans == 0:
        return 1
    else:
        return 1 + func(bin(nsum))

for i in range(a):
    s = list(b)
    s[i] = "0" if s[i] == "1" else "1"
    c = "".join(s)
    print(str(func(c)))

Submission status: Time Limit Exceeded

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

N = int(readline())
S = readline().decode().rstrip()
one_cnt = S.count('1')
cnt = [0]*(one_cnt+1)
pop_cnt = [0]* (N+1)
for i in range(1,one_cnt+1):
    pop_cnt[i] = pop_cnt[i//2] + i%2
    j = i % pop_cnt[i]
    cnt[i] = 1 + cnt[j] 
    
n = int(S, 2)
for i in range(N):
    if S[i] == '1':
        tmp = n - 2**(N-i-1)
        if tmp == 0:
            print(0)
        else:
            tmp %= (one_cnt-1)
            print(1+cnt[tmp])
    else:
        tmp = n + 2**(N-i-1) 
        tmp %= (one_cnt+1)
        print(1+cnt[tmp])

Submission status: Time Limit Exceeded

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

plus = bin(int(X, 2)).count('1') + 1
minus = bin(int(X, 2)).count('1') - 1
if minus < 1:
  minus = 1

init_n = [0] * N
init_X = [0] * N
for i in range(N):
  X_list = list(X)
  if X_list[i] == '0':
    X_list[i] = '1'
    first = plus
  else:
    X_list[i] = '0'
    first = minus
  X_str = ''.join(X_list)
  init_n[i] = int(X_str, 2)
  init_X[i] = init_n[i] % first

for i in range(N):
  
  fn = 0
  n = init_n[i]
  if n != 0:
    n = init_X[i]
    fn += 1
  while n != 0:
    n = n % bin(n).count('1')
    fn += 1
  
  print(fn)

Submission status: Time Limit Exceeded

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

plus = bin(int(X, 2)).count('1') + 1
minus = bin(int(X, 2)).count('1') - 1
if minus < 1:
  minus = 1

init_n = [0] * N
init_X = [0] * N
for i in range(N):
  X_list = list(X)
  if X_list[i] == '0':
    X_list[i] = '1'
    first = plus
  else:
    X_list[i] = '0'
    first = minus
  X_str = ''.join(X_list)
  init_n[i] = int(X_str, 2)
  init_X[i] = init_n[i] % first

for i in range(N):
  
  fn = 0
  n = init_n[i]
  if n != 0:
    n = init_X[i]
    fn += 1
  while n != 0:
    n = n % bin(n).count('1')
    fn += 1
  
  print(fn)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = int(input(),2)
bitx = bin(x).count('1')
 
ans = [0]*(bitx+1)
for i in range(1,bitx+1):
    ans[i] = 1 + ans[i%bin(i).count('1')]
#print(ans)
l = []
bitp = bitx + 1
bitm = bitx - 1
if bitx != 1:
    for i in range(n):
        if x>>(n-i-1)&1:
            xm = x^(1<<(n-i-1))
            xm = xm % bitm
            l.append(str(1+ans[xm]))
        else:
            xm = x%bitp
            xm = (xm + 2**(n-i-1))%bitp
            l.append(str(1+ans[xm]))

else:
    for i in range(n):
        if x>>(n-i-1)&1:
            l.append(str(0))
        else:
            xm = x%bitp
            xm = (xm + 2**(n-i-1))%bitp
            l.append(str(1+ans[xm]))

print('\n'.join(l))