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:
def popcount(n):
    ret = 0
    while n:
        ret += n & 1
        n >>= 1
    return ret

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

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

source_one = X.count('1')

import collections

count = collections.defaultdict(int)
count[1] = 1
count[2] = 1

source_n = int(X, 2)

kijou = 2 ** N

for i in range(N):
    kijou //= 2
    if X[i] == '1':
        one_count = source_one - 1
        original_n = source_n - kijou
    else:
        one_count = source_one + 1
        original_n = source_n + kijou

    if one_count == 0:
        count[original_n] = 0
        print(0)
        continue

    n = original_n % one_count



    count[original_n] = f(n) + 1
    print(count[original_n])

Submission status: Time Limit Exceeded

Solution code:
import sys

n = int(sys.stdin.readline().rstrip("\n"))
x = sys.stdin.readline().rstrip("\n")
pc_x = x.count('1')
for i in range(n):
    if x[i] == '0':
        xi = x[:i]+'1'+x[(i+1):]
        pc_xi = pc_x+1
    else:
        xi = x[:i]+'0'+x[(i+1):]
        pc_xi = pc_x-1
    f = 0
    xi_num = int(xi, 2)
    if xi_num == 0:
        print(0)
        continue
    pc_xi = xi.count('1')
    if xi_num % pc_xi == 0:
        f += 1
        print(f)
        continue
    else:
        f += 1
        xi_num = xi_num % pc_xi
        xi = format(xi_num, 'b')
    while True:
        xi_num = int(xi, 2)
        if xi_num == 0:
            break
        pc_xi = xi.count('1')
        if xi_num % pc_xi == 0:
            f += 1
            break
        else:
            f += 1
            xi_num = xi_num % pc_xi
            xi = format(xi_num, 'b')
    print(f)

Submission status: Time Limit Exceeded

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

one_num = X.count("1")

for i in range(N):
    target = int(X[i])
    if target == 0:
        ones = one_num + 1
        plus = pow(2,N-i-1)
        
    else:
        ones = one_num-1
        plus = -pow(2,N-i-1)
        
    Xnow = X10+plus
    count = 0
    if Xnow == 0:
        print(count)
        continue
    else:
        Xnow = Xnow%ones
        count+=1
        
        while Xnow > 0:
            Xnow2 = bin(Xnow)
            ones = Xnow2.count("1")
            Xnow = Xnow%ones
            count+=1
            
        print(count)

Submission status: Time Limit Exceeded

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

one_num = X.count("1")

for i in range(N):
    target = int(X[i])
    if target == 0:
        plus = pow(2,N-i-1)
        ones = one_num + 1
    else:
        if one_num==1:
            print(0)
            continue
        plus = -pow(2,N-i-1)
        ones = one_num-1
    Xnow = X10+plus
    count = 0
    if Xnow == 0:
        print(count)
        continue
    else:
        Xnow = Xnow%ones
        count+=1
        while Xnow > 0:
            Xnow2 = bin(Xnow)
            ones = Xnow2.count("1")
            Xnow = Xnow%ones
            count+=1
        print(count)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

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

ini_popcount=x.count('1')

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

  num=int(''.join(tx),2)

  ans=0
  while num!=0:
    if ans==0:
      if tx[i]=='1':
        popcount=ini_popcount+1
      else:
        popcount=ini_popcount-1
    else:
      popcount=bin(num).count('1')

    num=num%popcount
    ans+=1

  print(ans)

Submission status: Time Limit Exceeded

Solution code:
# TLEするはず
def main():
    N = int(input())
    X = input()
    t = X.count("1")
    V = int(X, 2)
    for i in range(N):
        x = 0
        cur_bits = 0
        if t != 1 and X[i] == "1":
            cur_bits = t - 1
            x = V ^ pow(2, N-i-1)
        elif X[i] == "0":
            cur_bits = t + 1
            x = V ^ pow(2, N-i-1)
        else:
            x = 0
        ans = 0
        while x > 0:
            x = x % cur_bits
            ans += 1
            cur_bits = "{:0b}".format(x).count("1")
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = input()
memo = [-1] * (N+1)
memo[0] = 0

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

def calc(k):
    pop = popcount(k)
    #print('  ', k, pop)
    key = k
    if memo[key] < 0:
        k %= pop
        if k == 0:
            memo[key] = 1
        else:
            memo[key] = calc(k) + 1
    return memo[key]

K = int(X, 2)
one = popcount(K)
if one == 0:
    K_MOD = K
elif one == 1:
    K_MOD   = 0
    K_MOD_M = K
else:
    K_MOD   = K % one
    K_MOD_M = K % (one-1)
K_MOD_P = K % (one+1)

T = 2**(N-1)
for i in range(N):
    if X[i] == '1':
        pop = one - 1
        k = K_MOD_M - T
    else:
        pop = one + 1
        k = K_MOD_P + T
    T //= 2

    if pop == 0:
        print(0)
    else:
        k %= pop
        print(calc(k)+1)

Submission status: Time Limit Exceeded

Solution code:
def f(n): 
    cnt = 0
    while n != 0:
        n %= popcount(n)
        cnt += 1
    return cnt    
        
def popcount(n):
    bin_n = format(n,'b')
    return bin_n.count('1')
  
N = int(input()) 
X = [int(i) for i in input()] 

for i in range(N):
    tmp = X[:]
    tmp[i] = int(not tmp[i])
    str_lst = [str(i) for i in tmp]
    b_n = "".join(str_lst)
    n = int(b_n,2)
    print(f(n))

Submission status: Time Limit Exceeded

Solution code:

def pcount(x):
    # cnt = 0
    # while x > 0:
    #     cnt += (x & 1)
    #     x = x >> 1
    # return cnt
    return bin(x).count('1')

cache = {}


def f(x):
    if x == 0:
        return 0
    if x in cache:
        return cache[x]
    cnt = f(x % pcount(x)) + 1
    cache[x] = cnt
    return cnt


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

    pcount = X.count('1')
    pcountP = pcount + 1
    pcountM = pcount - 1

    for i in range(N):
        x2 = X
        if x2[i] == "0":
            x2 = x2[0:i] + '1' + x2[i+1:]
            x = int(x2, 2) % pcountP
        else:
            x2 = x2[0:i] + '0' + x2[i+1:]
            if pcountM == 0:
                print("0")
                continue
            x = int(x2, 2) % pcountM
        print(f(x) + 1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def popcount(x):
    return bin(x).count("1")

N, X = open(0).read().split()
N = int(N)
XS = list(X)
X = int(X, 2)

p = popcount(X)
if p == 0:
    xi = xd = 0
elif p == 1:
    xi = X % 2
    xd = 0
else:
    xi = X % (p + 1)
    xd = X % (p - 1)

for i in range(0, N):
    if XS[i] == "1":
        if p == 1:
            print(0)
            continue
        else:
            k = 1 << (N - 1 - i)
            x = (xd - k) % (p - 1)
    else:
        k = 1 << (N - 1 - i)
        x = (xi + k) % (p + 1)
    ans = 1
    while x != 0:
        x %= popcount(x)
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

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

pc = x_bin.count('1')
pc_p = pc + 1
pc_m = pc - 1

d = {0: 1}
for i in range(1, n):
    d[i] = d[i-1] * 2

rest = {0: 0}
for i in range(1, pc + 1):
    rest[i] = rest[i % bin(i).count('1')] + 1

for i in range(n, 0, -1):
    if x_bin[n-i] == '1':
        if pc_m != 0:
            a = (x - d[i-1]) % pc_m
            print(rest[a] + 1)
        else:
            print(0)
    else:
        a = (x + d[i-1]) % pc_p
        print(rest[a] + 1)

Submission status: Time Limit Exceeded

Solution code:

def pcount(x):
    cnt = 0
    while x > 0:
        cnt += (x & 1)
        x = x >> 1
    return cnt

cache = {}
def f(x):
    if x == 0:
        return 0
    if x in cache:
        return cache[x]
    cnt = f(x % pcount(x)) + 1
    cache[x] = cnt
    return cnt


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

    pcount = X.count('1')
    pcountP = pcount + 1
    pcountM = pcount - 1

    for i in range(N):
        x2 = X
        if x2[i] == "0":
            x2 = x2[0:i] + '1' + x2[i+1:]
            x = int(x2, 2) % pcountP
        else:
            x2 = x2[0:i] + '0' + x2[i+1:]
            if pcountM == 0:
                print("0")
                continue
            x = int(x2, 2) % pcountM
        print(f(x) + 1)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def popcount(x):
    return bin(x).count("1")

N,X = open(0).read().split()
N = int(N)
X = int(X, 2)

p = popcount(X)
if p == 0:
    xi = xd = 0
elif p == 1:
    xi = X % 2
    xd = 0
else:
    xi = X % (p + 1)
    xd = X % (p - 1)

for i in range(0, N):
    k = 1 << (N - 1 - i)
    x = X ^ k
    if x == 0:
        print(0)
        continue

    if x > X:
        pi = p + 1
        x = (xi + k) % pi
    else:
        pd = p - 1
        x = (xd - k) % pd
    ans = 1
    while x != 0:
        x %= popcount(x)
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

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

pc = x_bin.count('1')
pc_p = pc + 1
pc_m = pc - 1

rest = {0: 0}
for i in range(1, pc + 1):
    rest[i] = rest[i % bin(i).count('1')] + 1

for i in range(n, 0, -1):
    if x_bin[n-i] == '1':
        if pc_m != 0:
            a = (x - pow(2, (i - 1))) % pc_m
            print(rest[a] + 1)
        else:
            print(0)
    else:
        a = (x + pow(2, (i - 1))) % pc_p
        print(rest[a] + 1)

Submission status: Time Limit Exceeded

Solution code:
import math

n = int(input())
x = input()
z = 0
exp_2 = [0] * (n + 1) #(2 * 10**5 + 1)

exp_2[-1] = 1

for i in range(1, n + 1):
    exp_2[- i - 1] = exp_2[- i] * 2
    z += exp_2[- i] * int(x[- i])
num_1 = x.count("1")
list_num_1 = [0] * (2*10**5+1)
index = 0
for i in range(1, 2*10**5+1):
    if math.log2(i).is_integer():
        index = 0
    list_num_1[i] = list_num_1[index] + 1
    index += 1
for i in range(n):
    if x[i] == "0":
        tmp_num_1 = num_1 + 1
        tmp_z = exp_2[i + 1] + z #modify ok
    elif x[i] == "1":
        tmp_num_1 = num_1 - 1
        tmp_z = -exp_2[i + 1] + z #modify ok
    counter = 0
    while tmp_z > 0:
        tmp_z = tmp_z % tmp_num_1
        tmp_num_1 = list_num_1[tmp_z] #modify
        counter += 1
    print(counter)

Submission status: Time Limit Exceeded

Solution code:
import copy
import numpy as np
N=int(input())
X=list(map(int,input()))
A=[]
for i in range(len(X)):
    S=copy.deepcopy(X)
    S[i]=abs(1-S[i])
    A.append(''.join(map(str,S)))
    
dp=np.array([0,1,1,2])
for i in range(24):
    dp=np.hstack([dp,dp+1])
    
for i in A:
    z=0
    while True:
        if z==0:
            n=int(i,2)
            f=dp[n]
            n=n%f
            z+=1
        else:
            f=dp[n]
            n=n%f
            z+=1
        if n==0:
            print(z)
            break

Submission status: Time Limit Exceeded

Solution code:
import copy
import numpy as np
N=int(input())
X=list(map(int,input()))
A=[]
for i in range(len(X)):
    S=copy.deepcopy(X)
    S[i]=abs(1-S[i])
    A.append(''.join(map(str,S)))
    
dp=np.array([0,1,1,2])
for i in range(25):
    dp=np.hstack([dp,dp+1])
    
for i in A:
    z=0
    while True:
        if z==0:
            n=int(i,2)
            f=dp[n]
            n=n%f
            z+=1
        else:
            f=dp[n]
            n=n%f
            z+=1
        if n==0:
            print(z)
            break

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = input()
def popcount(k):
    return bin(k).count('1')

K = int(X, 2)
one = popcount(K)
if one == 0:
    K_MOD = K
elif one == 1:
    K_MOD   = 0
    K_MOD_M = K
else:
    K_MOD   = K % one
    K_MOD_M = K % (one-1)
K_MOD_P = K % (one+1)
#memo = [-1] * (N+1)
#print('k_mod_m=', K_MOD_M)
#print('k_mod_p=', K_MOD_P)
T = 2**(N-1)
for i in range(N):
    if X[i] == '1':
        pop = one - 1
        k = K_MOD_M - T
    else:
        pop = one + 1
        k = K_MOD_P + T
    T //= 2

    if pop == 0:
        print(0)
    else:
        k %= pop
        pop = popcount(k)
        #key = k
        cnt = 1
        while k > 0:
            #print('  ', k, pop, cnt)
            #if memo[key] > 0:
            #    cnt += memo[k]
            #    break
            #else:
            k %= pop
            pop = popcount(k)
            cnt += 1
        #memo[key] = cnt
        print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    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

n=int(input())
xs=input()
lxs=list(xs)
#xj=xs.count("1")
#xj=sum([1 for l in lxs if l=="1"])

xj=0
for i in range(0,n,64):
    i64=i+64
    if i64>n:i64=n
    xj+=popcount(int(xs[i:i64],2))

x=int(xs,2)
xip=x%(xj+1)
if xj!=1:
    xim=x%(xj-1)

i1=1<<n
for i in range(n-1,-1,-1):
    i1=i1>>1
    if xs[n-1-i]=="0":
        pxi=xj+1
        xi=(xip+i1%pxi)%pxi
    elif xj==1:
        print(0)
        continue
    else:
        pxi=xj-1
        xi=(xim-i1%pxi)%pxi
    xi=xi%pxi
    if xi==0:
        print(1)
        continue
    icnt=1
    while xi>0:
#        print("i",i,"xi",xi,"icnt",icnt)
        icnt+=1
#        xi=xi%(bin(xi).count("1"))
        xi=xi%popcount(xi)
    print(icnt)

Submission status: Time Limit Exceeded

Solution code:
def popcount(x):
    return bin(x).count("1")

N,X = open(0).read().split()
N = int(N)
X = int(X, 2)

p = popcount(X)
if X == 0 or p == 1:
    for i in range(0, N):
        k = 1 << (N - 1 - i)
        x = X ^ k
        ans = 0
        while x != 0:
            x %= popcount(x)
            ans += 1
        print(ans)

else:
    xi = X % (p + 1)
    xd = X % (p - 1)
    for i in range(0, N):
        k = 1 << (N - 1 - i)
        x = X ^ k
        if x == 0:
            print(0)
            continue

        if x > X:
            pi = p + 1
            x = (xi + k) % pi
        else:
            pd = p - 1
            x = (xd - k) % pd
        ans = 1
        while x != 0:
            x %= popcount(x)
            ans += 1
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
def popcount(x):
    return bin(x).count("1")

N,X = open(0).read().split()
N = int(N)
X = int(X, 2)

p = popcount(X)
if X == 0 or p == 1:
    for i in range(0, N):
        k = 1 << (N - 1 - i)
        x = X ^ k
        ans = 0
        while x != 0:
            x %= popcount(x)
            ans += 1
        print(ans)

else:
    xi = X % (p + 1)
    xd = X % (p - 1)
    for i in range(0, N):
        k = 1 << (N - 1 - i)
        x = X ^ k
        if x == 0:
            print(0)
            continue

        if x > X:
            pi = p + 1
            x = (xi + (k % pi)) % pi
        else:
            pd = p - 1
            x = (xd - (k % pd)) % pd
        ans = 1
        while x != 0:
            x %= popcount(x)
            ans += 1
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    import sys
    
    sys.setrecursionlimit(1000000)
    readline = sys.stdin.readline

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

    def func(n: int, cnt: int):
        if n != 0:
            func(n % popcount(n), cnt + 1)
        else:
            print(cnt)

    N = int(readline())
    X = readline()

    calx = popcount(int(X, 2))
    for i in range(N):
        n = X
        if n[i] == '0':
            n = n[:i] + '1' + n[i + 1:]
            cal = int(n, 2) % (calx + 1)
        else:
            n = n[:i] + '0' + n[i + 1:]
            if '1' in n:
                cal = int(n, 2) % (calx - 1)
            else:
                print(0)
                continue
        func(cal, 1)


resolve()

Submission status: Time Limit Exceeded

Solution code:
import math

n = int(input())
x = input()
z = 0
exp_2 = [0] * (2 * 10**5 + 1)
exp_2[0] = 2**n
for i in range(1, n + 1):
    exp_2[i] = exp_2[i - 1]// 2
    z += exp_2[i]*int(x[i - 1])
num_1 = x.count("1")
list_num_1 = [0] * (2*10**5+1)

index = 0
for i in range(1, 2*10**5+1):
    if math.log2(i).is_integer():
        index = 0
    list_num_1[i] = list_num_1[index] + 1
    index += 1
    
for i in range(n):
    if x[i] == "0":
        tmp_num_1 = num_1 + 1
        tmp_z = exp_2[i + 1] + z #modify ok
    elif x[i] == "1":
        tmp_num_1 = num_1 - 1
        tmp_z = -exp_2[i + 1] + z #modify ok
    counter = 0
    while tmp_z > 0:
        tmp_z = tmp_z % tmp_num_1
        tmp_num_1 = list_num_1[tmp_z] #modify
        counter += 1
    print(counter)

Submission status: Time Limit Exceeded

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

one_num = X.count("1")

for i in range(N):
    target = int(X[i])
    if target == 0:
        plus = pow(2,N-i-1)
        ones = one_num + 1
    else:
        plus = -pow(2,N-i-1)
        ones = one_num-1
    Xnow = X10+plus
    count = 0
    if Xnow == 0:
        print(count)
        continue
    Xnow = Xnow%ones
    count+=1
    for j in range(1000):
        if Xnow == 0:
            break
        Xnow2 = bin(Xnow)
        ones = Xnow2.count("1")
        Xnow = Xnow%ones
        count+=1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
s = input()
cnt=s.count("1")
popX=[]
x=int(s,2)
X=[]
for i in range(N):
    if s[i]=="1":
        popX.append(cnt-1)
        X.append(x-2**(N-i-1))
    else:
        popX.append(cnt+1)
        X.append(x+2**(N-i-1))


for i in range(N):
    f=0
    while X[i]>0:
        X[i]=X[i]%popX[i]
        S=bin(X[i])
        S=str(S)
        popX[i]=S.count("1")
        
        f=f+1
    print(f)

Submission status: Time Limit Exceeded

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

one_num = X.count("1")

for i in range(N):
    target = int(X[i])
    if target == 0:
        plus = pow(2,N-i-1)
        ones = one_num + 1
    else:
        plus = -pow(2,N-i-1)
        ones = one_num-1
    Xnow = X10+plus
    count = 0
    if Xnow == 0:
        print(count)
        continue
    else:
        Xnow = Xnow%ones
        count+=1
        for j in range(1000):
            if Xnow == 0:
                break
            Xnow2 = bin(Xnow)
            ones = Xnow2.count("1")
            Xnow = Xnow%ones
            count+=1
        print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def main():
    def popcount(n):
        i = 2
        P = [0, 1]
        while i - 1 <= n:
            P += list(map(lambda x: x + 1, P))
            i *= 2
        return P
    def f(n):
        if n == 0:
            return 0
        if d[n] != 0:
            return d[n]
        d[n] = f(n % P[n]) + 1
    def rev(i):
        if X[i] == '0':
            b = m + j
            print(d[b % (c + 1)] + 1 if b != 0 else 0)
        else:
            b = m - j
            print(d[b % (c - 1)] + 1 if b != 0 else 0)

    n = int(input())
    X = list(input())
    d = defaultdict(int)
    P = popcount(n)
    for i in range(1, n):
        f(i)
    c = sum(list(map(int, X)))
    m = int(''.join(X), 2)
    j = 1 << n - 1
    for i in range(n):
        rev(i)
        j = j >> 1

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
s = input()
cnt=s.count("1")
popX=[]
for i in range(N):
    if s[i]=="1":
        popX.append(cnt-1)
    else:
        popX.append(cnt+1)

x=int(s,2)
X=[]
for i in range(N):
    if s[i]=="1":
        X.append(x-2**(N-i-1))
    else:
        X.append(x+2**(N-i-1))

for i in range(N):
    f=0
    while X[i]>0:
        X[i]=X[i]%popX[i]
        S=bin(X[i])
        S=str(S)
        popX[i]=S.count("1")
        
        f=f+1
    print(f)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X_2 = input()
X_10 = int(X_2, 2)

y = X_2.count('1')

a = X_10%(y+1)
if y==1:
    b = 0
else:
    b = X_10%(y-1)

for i in range(N):
    if X_2[i] == '1' and y == 1:
        print(0)
        continue
    elif X_2[i] == '1':
        c = (2**(N-1-i))%(y-1)
        x = (b-c)%(y-1)
    else:
        c = (2**(N-1-i))%(y+1)
        x = (a+c)%(y+1)
    count = 1
    while x!=0:
        x %= bin(x)[2:].count('1')
        count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys

n = int(sys.stdin.readline().rstrip("\n"))
x = sys.stdin.readline().rstrip("\n")
for i in range(n):
    if x[i] == '0':
        xi = x[:i]+'1'+x[(i+1):]
    else:
        xi = x[:i]+'0'+x[(i+1):]
    f = 0
    while True:
        xi_num = int(xi, 2)
        if xi_num == 0:
            break
        pc = xi.count('1')
        if xi_num % pc == 0:
            f += 1
            break
        else:
            f += 1
            xi_num = xi_num % pc
            xi = format(xi_num, 'b')
    print(f)

Submission status: Time Limit Exceeded

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

one_num = X.count("1")

for i in range(N):
    target = int(X[i])
    if target == 0:
        plus = pow(2,N-i-1)
        ones = one_num + 1
    else:
        plus = -pow(2,N-i-1)
        ones = one_num-1
    
    Xnow = X10+plus
    count = 0
    if Xnow == 0:
        print(count)
        continue
    else:
        Xnow = Xnow%ones
        count+=1
        while Xnow > 0:
            Xnow2 = bin(Xnow)
            ones = Xnow2.count("1")
            Xnow = Xnow%ones
            count+=1
        print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = int(input())
X = str(input())
X10 = int(X,2)

one_num = Counter(X)["1"]

for i in range(N):
    target = int(X[i])
    if target == 0:
        plus = pow(2,N-i-1)
        ones = one_num + 1
    else:
        plus = -pow(2,N-i-1)
        ones = one_num-1
    
    Xnow = X10+plus
    count = 0
    if Xnow == 0:
        print(count)
        continue
    else:
        Xnow = Xnow%ones
        count+=1
        while Xnow > 0:
            Xnow2 = format(Xnow, 'b')
            ones = 0
            for j in range(len(Xnow2)):
                if Xnow2[j] == "1":
                    ones += 1
            Xnow = Xnow%ones
            count+=1
        print(count)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    import sys

    sys.setrecursionlimit(1000000)
    readline = sys.stdin.readline

    N = int(readline())
    X = readline()

    def func(n: int, cnt: int):
        if n != 0:
            func(n % str(bin(n)).count('1'), cnt + 1)
        else:
            print(cnt)

    for i in range(N):
        n = X
        if n[i] == '0':
            n = n[:i] + '1' + n[i + 1:]
        else:
            n = n[:i] + '0' + n[i + 1:]
        func(int(n, 2), 0)

resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

n=int(input())
xs=input()
lxs=list(xs)
#xj=xs.count("1")
xj=sum([1 for l in lxs if l=="1"])

x=int(xs,2)
xip=x%(xj+1)
if xj!=1:
    xim=x%(xj-1)

def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    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

i1=1<<n
for i in range(n-1,-1,-1):
    i1=i1>>1
    if xs[n-1-i]=="0":
        pxi=xj+1
        xi=(xip+i1%pxi)%pxi
    elif xj==1:
        print(0)
        continue
    else:
        pxi=xj-1
        xi=(xim-i1%pxi)%pxi
    xi=xi%pxi
    if xi==0:
        print(1)
        continue
    icnt=1
    while xi>0:
#        print("i",i,"xi",xi,"icnt",icnt)
        icnt+=1
#        xi=xi%(bin(xi).count("1"))
        xi=xi%popcount(xi)
    print(icnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = int(input())
X = str(input())
X10 = int(X,2)

one_num = Counter(X)["1"]

for i in range(N):
    target = int(X[i])
    if target == 0:
        plus = pow(2,N-i-1)
        ones = one_num + 1
    else:
        plus = -pow(2,N-i-1)
        ones = one_num-1
    
    Xnow = X10+plus
    count = 0
    if Xnow == 0:
        print(count)
        continue
    else:
        Xnow = Xnow%ones
        count+=1
        while Xnow > 0:
            Xnow2 = format(Xnow, 'b')
            ones = Counter(Xnow2)["1"]
            Xnow = Xnow%ones
            count+=1
        print(count)

Submission status: Time Limit Exceeded

Solution code:
def popcount(x):
    return bin(x).count("1")

N,X = open(0).read().split()
N = int(N)
X = int(X, 2)

p = popcount(X)

for i in range(0, N):
    x = X ^ (1 << (N - 1 - i))
    if x == 0:
        print(0)
        continue

    if x > X:
        x %= (p + 1)
    else:
        x %= (p - 1)
    ans = 1
    while x != 0:
        x %= popcount(x)
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys


def resolve():
    from sys import setrecursionlimit
    
    setrecursionlimit(1000000)
    readline = sys.stdin.readline

    N = int(readline())
    X = readline()

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

    def func(n: int, cnt: int):
        if n != 0:
            cal = n % popcount(n)
            ncnt = cnt + 1
            func(cal, ncnt)
        else:
            print(cnt)

    for i in range(N):
        n = X
        if n[i] == '0':
            n = n[:i] + '1' + n[i + 1:]
        else:
            n = n[:i] + '0' + n[i + 1:]
        func(int(n, 2), 0)

resolve()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = str(input())
X10 = int(X,2)
one_num = X.count("1")

for i in range(N):
    target = int(X[i])
    if target == 0:
        plus = pow(2,N-i-1)
        ones = one_num + 1
    else:
        plus = -pow(2,N-i-1)
        ones = one_num-1
    
    Xnow = X10+plus
    count = 0
    if Xnow == 0:
        print(count)
        continue
    else:
        Xnow = Xnow%ones
        count+=1
        while Xnow > 0:
            Xnow2 = format(Xnow, 'b')
            ones = Xnow2.count("1")
            Xnow = Xnow%ones
            count+=1
        print(count)

Submission status: Time Limit Exceeded

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

X10 = int(X,2)
one_num = sum(X_list)
#%%
for i in range(N):
    target = X_list[i]
    if target == 0:
        plus = pow(2,N-i-1)
        ones = one_num + 1
    else:
        plus = -pow(2,N-i-1)
        ones = one_num-1
    
    Xnow = X10+plus
    count = 0
    if Xnow == 0:
        print(count)
        continue
    else:
        Xnow = Xnow%ones
        count+=1
        while Xnow > 0:
            Xnow2 = format(Xnow, 'b')
            ones = Xnow2.count("1")
            Xnow = Xnow%ones
            count+=1
        print(count)

Submission status: Time Limit Exceeded

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

a = int(X, 2)
b = X.count("1")

for i in range(N):
    if X[i] == "1":
        if b == 1:
            print(0)
            continue
        t = (a - pow(2, N-1-i, b-1)) % (b-1)
    else:
        t = (a + pow(2, N-1-i, b+1)) % (b+1)
    
    ans = 1
    while t > 0:
        t %= bin(t).count("1")
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

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

X10 = int(X,2)
one_num = sum(X_list)
#%%
for i in range(N):
    target = X_list[i]
    if target == 0:
        plus = pow(2,N-i-1)
        ones = one_num + 1
    else:
        plus = -pow(2,N-i-1)
        ones = one_num-1
    
    Xnow = X10+plus
    count = 0
    if Xnow == 0:
        print(count)
        continue
    else:
        Xnow = Xnow%ones
        count+=1
        while Xnow > 0:
            Xnow2list = list(map(int,list(format(Xnow, 'b'))))
            ones = sum(Xnow2list)
            Xnow = Xnow%ones
            count+=1
        print(count)

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':
            b = m + j
            print(d[b % (c + 1)] + 1 if b != 0 else 0)
        else:
            b = m - j
            print(d[b % (c - 1)] + 1 if b != 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)
    j = 1 << n - 1
    for i in range(n):
        rev(i)
        j = j >> 1

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

a = int(X, 2)
b = X.count("1")
k = 2 ** (N-1)

for i in range(N):
    if X[i] == "0":
        x = a + k
        y = b + 1
    else:
        x = a - k
        y = b - 1
    k //= 2

    if x == 0:
        print(0)
    else:
        ans = 1
        t = x % y
        while t > 0:
            t %= bin(t).count("1")
            ans += 1
        print(ans)

Submission status: Time Limit Exceeded

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

#N = 20000
#X = "1"*N

a = int(X, 2)
b = X.count("1")
k = 2 ** (N-1)

for i, ch in enumerate(X):
    if ch == "0":
        x = a + k
        y = b + 1
    else:
        x = a - k
        y = b - 1
    k //= 2

    if x == 0:
        print(0)
    else:
        ans = 1
        t = x % y
        while t > 0:
            t %= bin(t).count("1")
            ans += 1
        print(ans)