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()

n1 = X.count("1")
Xn = int(X, 2)

Xms = (Xn % (n1 - 1)) if n1 > 1 else 0
Xml = Xn % (n1 + 1)

p2s = [1]
p2l = [1]
s2 = 1
l2 = 1
for i in range(N - 1):
    s2 = (s2 * 2) % (n1 - 1) if n1 > 1 else 0
    l2 = (l2 * 2) % (n1 + 1)
    p2s.append(s2)
    p2l.append(l2)


def f(n):
    if n == 0:
        return 0
    return f(n % bin(n).count("1")) + 1


for i in range(N):
    cnt = 0
    p2 = 2 ** (N - i - 1)
    Xim = 0

    if X[i] == "1" and n1 == 1:
        print(cnt)
        continue
    elif X[i] == "1":
        Xim = (
            Xms - p2s[-i - 1]
            if Xms - p2s[-i - 1] >= 0
            else ((n1 - 1) + (Xms - p2s[-i - 1]))
        )
    else:
        Xim = (
            Xml + p2l[-i - 1]
            if Xml + p2l[-i - 1] < (n1 + 1)
            else (Xml + p2l[-i - 1] - (n1 + 1))
        )
    print(f(Xim) + 1)

Submission status: Time Limit Exceeded

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

n1 = X.count("1")
Xn = int(X, 2)

Xms = (Xn % (n1 - 1)) if n1 > 1 else 0
Xml = Xn % (n1 + 1)

for i in range(N):
    cnt = 0
    p2 = 2 ** (N - i - 1)
    Xim = 0

    if X[i] == "1" and n1 == 1:
        print(cnt)
        continue
    elif X[i] == "1":
        p2m = p2 % (n1 - 1)
        Xim = Xms - p2m if Xms - p2m >= 0 else ((n1 - 1) + (Xms - p2m))
    else:
        p2m = p2 % (n1 + 1)
        Xim = Xml + p2m if Xml + p2m < (n1 + 1) else (Xml + p2m - (n1 + 1))

    cnt += 1
    while Xim > 0:
        Xim %= bin(Xim).count("1")
        cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
x = int(s, 2)
p = s.count("1")

nxt = [i for i in range(n+1)]
for i in range(1, n):
	nxt[i] %= bin(i).count("1")

for i in range(n):
	ans = 0
	tmp = x ^ (1 << (n-1-i))
	if tmp == 0:
		print(0)
		continue
	if tmp > x:
		ans = 1
		tmp %= p+1
	else:
		ans = 1
		tmp %= p-1
	while tmp > 0:
		ans += 1
		tmp = nxt[tmp]
	print(ans)

Submission status: Time Limit Exceeded

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

n1 = X.count("1")
Xn = int(X, 2)

Xms = (Xn % (n1 - 1)) if n1 > 1 else 0
Xml = Xn % (n1 + 1)

for i in range(N):
    cnt = 0
    p2 = 2 ** (N - i - 1)
    Xim = 0

    if X[i] == "1" and n1 == 1:
        print(cnt)
        continue
    elif X[i] == "1":
        p2m = p2 % (n1 - 1)
        Xim = Xms - p2m if Xms - p2m >= 0 else ((n1 - 1) + (Xms - p2m))
    else:
        p2m = p2 % (n1 + 1)
        Xim = Xml + p2m if Xml + p2m < (n1 + 1) else (Xml + p2m - (n1 + 1))

    cnt += 1
    while Xim > 0:
        Xim % bin(Xim).count("1")
        cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
x = int(s, 2)
p = s.count("1")

for i in range(n):
	ans = 0
	tmp = x ^ (1 << (n-1-i))
	if tmp == 0:
		print(0)
		continue
	if tmp > x:
		ans = 1
		tmp %= p+1
	else:
		ans = 1
		tmp %= p-1
	while tmp > 0:
		ans += 1
		tmp %= bin(tmp).count("1")
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
def popcount(n):
    cnt = 0
    for i in range(n):
        if ((n >> i) & 1):
            cnt +=1
    return cnt

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

def pow(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 numChange(list, num):
    i = len(list) - 1
    j = 0
    ans = 0
    while i >= 0:
        if list[i] == '1':
            ans += num[j]
        i -= 1
        j += 1
    return ans

if __name__ == "__main__":
    n = int(input())
    x = list(input())
    d = sum([y == '1' for y in x])
    num = []
    a = 1
    for i in range(n):
        num.append(a)
        a *= 2
    xNum = numChange(x, num)
    for i in range(n):
        if x[i] == "1":
            wk = xNum - num[len(x) - i - 1]
            wkd = d - 1
        else:
            wk = xNum + num[len(x) - i - 1]
            wkd = d + 1
        if wk == 0:
            print(0)
        else:
            wk %= wkd
            if wk == 0:
                print(1)
            else:
                print(f(wk))

Submission status: Time Limit Exceeded

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

n1 = X.count("1")
Xn = int(X, 2)

Xms = (Xn % (n1 - 1)) if n1 > 1 else 0
Xml = Xn % (n1 + 1)


def f(n):
    if n == 0:
        return 0
    return f(n % bin(n).count("1")) + 1


for i in range(N):
    cnt = 0
    p2 = 2 ** (N - i - 1)
    Xim = 0

    if X[i] == "1" and n1 == 1:
        print(cnt)
        continue
    elif X[i] == "1":
        p2m = p2 % (n1 - 1)
        Xim = Xms - p2m if Xms - p2m >= 0 else ((n1 - 1) + (Xms - p2m))
    else:
        p2m = p2 % (n1 + 1)
        Xim = Xml + p2m if Xml + p2m < (n1 + 1) else (Xml + p2m - (n1 + 1))
    # print("deb", Xms, Xml, p2m, Xim, n1)
    cnt = f(Xim) + 1
    print(cnt)

Submission status: Time Limit Exceeded

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

popcount = x.count('1')
p = int(x, 2) % (popcount + 1)
q = int(x, 2) % (popcount - 1) if popcount != 1 else 0
for i in range(n):
    if x[i] == '0':
        y = (p + 2**(n-i-1) % (popcount + 1)) % (popcount + 1)
    else:
        if popcount != 1:
            y = (q - 2**(n-i-1) % (popcount - 1)) % (popcount - 1)
        else:
            print(0)
            continue
    cnt = 1
    while y != 0:
        y %= bin(y).count('1')
        cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def popcount(n):
    cnt = 0
    for i in range(n):
        if ((n >> i) & 1):
            cnt +=1
    return cnt

def f(n):
    cnt = 1
    while True:
        if n == 0:
            break
        n = n % popcount(n)
        cnt += 1
    return cnt

def pow(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 numChange(list, num):
    i = len(list) - 1
    j = 0
    ans = 0
    while i >= 0:
        if list[i] == '1':
            ans += num[j]
        i -= 1
        j += 1
    return ans

if __name__ == "__main__":
    n = int(input())
    x = list(input())
    d = sum([y == '1' for y in x])
    num = []
    a = 1
    for i in range(n):
        num.append(a)
        a *= 2
    xNum = numChange(x, num)
    for i in range(n):
        if x[i] == "1":
            wk = xNum - num[len(x) - i - 1]
            wkd = d - 1
        else:
            wk = xNum + num[len(x) - i - 1]
            wkd = d + 1
        if wk == 0:
            print(0)
        else:
            wk %= wkd
            if wk == 0:
                print(1)
            else:
                print(f(wk))

Submission status: Time Limit Exceeded

Solution code:
def resolve():
  N = int(input())
  X = input()
  base_1_count = X.count("1")
  X_int = int(X, 2)

  for i in range(N):
    if X[i] == "1":
      Xi = X_int - 2**(N-i-1)
    else:
      Xi = X_int + 2**(N-i-1)
    count = 0
    while Xi != 0:
      # print(Xi)
      num_of_1 = bin(Xi).count("1")
      Xi %= num_of_1
      count += 1
    # print("~~~~~~~~~~~~~~~")
    print(count)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
def waru(a):
    onecnt = a.count('1')
    num = int(a, 2)
    return num%onecnt

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

for i in range(len(X)):
    p = X
    str_list = list(p)
    if str_list[i] == '0':
        str_list[i] = '1'
    else:
        str_list[i] = '0'
    p = "".join(str_list)

    cnt = 0
    if p.count('1') > 0:
        while (1 == 1):
            amari = waru(p)
            cnt += 1
            if amari == 0:
                break
            else:
                p = bin(amari)

    print(cnt)

Submission status: Time Limit Exceeded

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

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

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

lst = [list(x) for _ in range(N)]

for i in range(N):
    if lst[i][i] == "1":
        lst[i][i] = "0"
    else:
        lst[i][i] = "1"
    lst[i] = "".join(lst[i])

for i in range(N):
    M = int(lst[i], 2)
    print(f(M))

Submission status: Time Limit Exceeded

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


for i in range(N):
    X2 = int(X, 2)

    if X[i] == "0":
        X2 += 2 ** (N - i - 1)
    else:
        X2 -= 2 ** (N - i - 1)

    res = 0
    while X2 > 0:
        count = bin(X2).count("1")
        X2 = X2 % count
        res += 1

    print(res)

Submission status: Time Limit Exceeded

Solution code:
def f(n) :
    ans=0
    while n>0 :
        ans+=1
        n=n%bin(n).count("1")
    return ans

#----------------------------------------------------------------------------------------
#こちらで実行

def main() :
    n=int(input())
    x=input()

    c1=x.count("1")                                    #初期のpopcount(x)
    cc2=int("0b"+x,0)                                  #初期のn

    if c1==1 :
        for i in range(n) :
            if x[i]=="1" :                             #1を反転させたら1は0個
                print(0)
            else :
                print(f((pow(2,n-i-1)+cc2)%(c1+1))+1)  #あらかじめ1回はもう割っておく
        exit()
    
    for i in range(n) :
        if x[i]=="1" :
            print(f((-pow(2,n-i-1)+cc2)%(c1-1))+1)     #あらかじめ1回はもう割っておく
        else :
            print(f((pow(2,n-i-1)+cc2)%(c1+1))+1)


#----------------------------------------------------------------------------------------
#

main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
x = list(map(int, s))
pc = sum(x)
ans = [0 for i in range(n)]

def f(x):
  if x == 0:
    return 0
  return (f(x % (bin(x).count('1'))) + 1)

for b in range(2):
  npc = pc
  if b == 0:
    npc += 1
  else:
    npc -= 1
  if npc <= 0:
    continue
  r0 = int(s, 2)
  k = 1
  for i in range(n-1, -1, -1):
    if x[i] == b:
      r = r0
      if b == 0:
        r = (r + k) % npc
      else:
        r = (r - k + npc) % npc
      ans[i] = f(r) + 1
    k = (k * 2) % npc
for i in range(n):
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
x = list(map(int, s))
pc = sum(x)
ans = [0 for i in range(n)]

def pcnt(x):
  return (format(x, 'b').count('1'))

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

for b in range(2):
  npc = pc
  if b == 0:
    npc += 1
  else:
    npc -= 1
  if npc <= 0:
    continue
  r0 = int(s, 2)
  k = 1
  for i in range(n-1, -1, -1):
    if x[i] == b:
      r = r0
      if b == 0:
        r = (r + k) % npc
      else:
        r = (r - k + npc) % npc
      ans[i] = f(r) + 1
    k = (k * 2) % npc
for i in range(n):
  print(ans[i])

Submission status: Time Limit Exceeded

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

dp = {}

def popcount(n):
    if dp.setdefault(n, 0):
        return dp[n]
    b = format(n, 'b')
    dp[n] = b.count('1') 
    return dp[n]

def f(n):
    global ans
#    print(n, ans)
    if n==0:
        return 0
    ans += 1
    return f(n % popcount(n))
T = []
for i in range(len(X)):
    t = X[:]
    t[i] = '0' if t[i]=='1' else '1'
    T.append(int("".join([c for c in t]), 2))
#    print(X, t)

for t in T:
    ans = 0
    f(t)
#    print('*'*10)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def f(b):
    cnt = 0
    n = int(b, 2)
    while n != 0:
        one = b.count('1')
        n = n%one
        cnt+=1
        b = format(n, 'b')
    return cnt

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

xdec = int(x, 2)
for i in range(n):
    vs = 2**(n-1-i)
    ydec = (xdec ^ vs)
    y = format(ydec, 'b')
    cnt = f(y)
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    def popcount(n):
        flg = 0
        for mask in range(len(bin(n)) - 2):
            flg += (n >> mask) & 1
        return flg

    n = int(input())
    X = input()
    cnt_init = 0
    for i in range(n):
        if X[i] == "1":
            cnt_init += 1

    t = [1] * n
    for i in range(1, n):
        t[i] = t[i - 1] * 2

    for j in range(n):
        if X[j] == "1":
            cnt = cnt_init - 1
            x = int(X, 2) - t[n - j - 1]
        else:
            cnt = cnt_init + 1
            x = int(X, 2) + t[n - j - 1]

        res = 0
        while x:
            if res != 0:
                cnt = popcount(x)
            x %= cnt
            res += 1
        print(res)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
def f_1(b,count):
    c =bin(b)
    #print(c,end=" ")
    c1 =c.count("1")
    #print(b,c1)
    if b ==0:
        return count
    elif f[b]==0:
        q,mod =divmod(b,c1)
        count +=1
        if mod !=0:
            return f_1(mod,count)
        else:
            return count
    else:
        return count

# 初期入力
import sys
input = sys.stdin.readline
from collections import defaultdict
N = int(input())
f =defaultdict(int)
rev =[0]*N


X ="0b" +input().strip()
ans =0

for i in range(N):
    revi =["0"]*N
    revi[i]="1"
    a ="".join(revi)
    b =int(X,2) ^ int(a,2) #iだけ０・１を反転させるためXOR
    count =0
    if f[b] ==0:
        ans =f_1(b,count)
        f[b] =ans
    else:
        ans =f[b]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = str(input())
n = sum(list(map(int, X)))
for i in range(N):
  Y = ''
  m = n
  if X[i] == '0':
    Y = X[:i] + '1' + X[i+1:]
    m += 1
  else:
    Y = X[:i] + '0' + X[i+1:]
    m -= 1
  Z = int(Y, 2)
  ans = 0
  while Z != 0:
    m = sum(list(map(int, format(Z, 'b'))))
    Z %= m
    ans += 1
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
def f_1(b,count):
    c =bin(b)
    #print(c,end=" ")
    c1 =c.count("1")
    #print(b,c1)
    if b ==0:
        return count
    else:
        q,mod =divmod(b,c1)
        count +=1
        if mod !=0:
            return f_1(mod,count)
        else:
            return count

# 初期入力
import sys
input = sys.stdin.readline
from collections import defaultdict
N = int(input())
f =defaultdict(int)
rev =[0]*N


X ="0b" +input().strip()
ans =0

for i in range(N):
    revi =["0"]*N
    revi[i]="1"
    a ="".join(revi)
    b =int(X,2) ^ int(a,2) #iだけ０・１を反転させるためXOR
    count =0
    if f[b] ==0:
        ans =f_1(b,count)
        f[b] =ans
    else:
        ans =f[b]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def f_1(b,count):
    c =bin(b)
    #print(c,end=" ")
    c1 =c.count("1")
    #print(b,c1)
    if b ==0:
        return count
    else:
        q,mod =divmod(b,c1)
        count +=1
        if mod !=0:
            return f_1(mod,count)
        else:
            return count

# 初期入力
import sys
input = sys.stdin.readline
N = int(input())
rev =[0]*N


X ="0b" +input().strip()
ans =0

for i in range(N):
    revi =["0"]*N
    revi[i]="1"
    a ="".join(revi)
    b =int(X,2) ^ int(a,2) #iだけ０・１を反転させるためXOR
    count =0
    ans =f_1(b,count)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = input()
x_list = list(x)
ones = 0
for i in range(n):
  if x_list[i] == "1":
    ones += 1
result_list = [0 for  i in range(n)]
first = []
for i in range(n):
  if x_list[i] == "1":
    p = ones - 1
    if p > 0:
      ans = (int(x,2) - 2**(n-1-i)) % p
      result_list[i] += 1
      first.append(bin(ans))
    else:
      ans = 0
      first.append(bin(ans))
  else:
    p = ones + 1
    ans = (int(x,2) + 2**(n-1-i))  % p
    first.append(bin(ans))
    result_list[i] += 1  
for i in range(n):
  for j in range(6):
    x = first[i]
    ones = x.count("1")
    if ones == 0:
      break
    else:
      result_list[i] += 1
      ne = bin(int(x,2) % ones)
      first[i] = ne
for result in result_list:
  print(result)

Submission status: Time Limit Exceeded

Solution code:
def search(n):
    res = 0
    while n:
        n %= bin(n).count("1")
        res += 1
    return res


def main():
    n = int(input())
    x = list(input())
    x_decimal = int("".join(map(str, x)), 2)
    first_mod = sum(map(int, list(x)))
    increase_mod = first_mod + 1
    increase_base = x_decimal % increase_mod  # 反転させる桁が元々0だった場合
    decrease_mod = first_mod - 1
    if decrease_mod:
        decrease_base = x_decimal % decrease_mod  # 反転させる桁が元々1だった場合
    diff = pow(2, n - 1)
    for i in range(n):
        cnt = 0
        if x[i] == "1" and decrease_mod:
            cnt = 1 + search((decrease_base - diff % decrease_mod) % decrease_mod)
        elif x[i] == "0":
            cnt = 1 + search((increase_base + diff % increase_mod) % increase_mod)
        diff //= 2
        print(cnt)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

arr = [0 for _ in range(N+1)]
for i in range(1, N+1):
    cnt = bin(i).count('1')
    arr[i] = arr[i%cnt] + 1

x = int(X, 2)
pop = X.count('1')
plu = x % (pop+1)
mai = x % (pop-1) if pop>1 else 0

for i in range(N):
    bi = 1
    if X[i] == '0':
        for j in range(N-1-i):
            bi = bi * 2 % (pop+1)
        res = (plu + bi) % (pop+1)
    else:
        if pop == 1:
            print(0)
            continue
        for j in range(N-1-i):
            bi = bi * 2 % (pop-1)
        res = (mai - bi) % (pop-1)
    print(arr[res] + 1)

Submission status: Time Limit Exceeded

Solution code:
def func(nStep:int, X) -> int:
    if X == 0:
        return 0
    nStep += 1
    newX = X % bin(X).count('1')
    if newX == 0:
        return nStep
    else:
        return func(nStep, newX)

def solve():
    N = int(input())
    X = input()
    for i in range(N):
        print(func(0, int(X,2)^(1<<(N-i-1))))

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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

arr = [0 for _ in range(N+1)]
for i in range(1, N+1):
    cnt = bin(i).count('1')
    arr[i] = arr[i%cnt] + 1

x = int(X, 2)
pop = X.count('1')
plu = x % (pop+1)
mai = x % (pop-1) if pop>1 else 0

for i in range(N):
    if X[i] == '0':
        res = (plu + pow(2, N-1-i) % (pop+1)) % (pop+1)
    else:
        if pop == 1:
            print(0)
            continue
        res = (mai - pow(2, N-1-i) % (pop-1)) % (pop-1)
    print(arr[res] + 1)

Submission status: Time Limit Exceeded

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

arr = [0 for _ in range(N+1)]
for i in range(1, N+1):
    cnt = bin(i).count('1')
    arr[i] = arr[i%cnt] + 1

x = int(X, 2)
pop = X.count('1')
plu = x % (pop+1)
mai = x % (pop-1) if pop>1 else 0

for i in range(N):
    if X[i] == '0':
        res = (plu + (1 << (N-1-i)) % (pop+1)) % (pop+1)
    else:
        if pop == 1:
            print(0)
            continue
        res = (mai - (1 << (N-1-i)) % (pop-1)) % (pop-1)
    print(arr[res] + 1)

Submission status: Time Limit Exceeded

Solution code:
def search(n):
    res = 0
    while n:
        n %= bin(n).count("1")
        res += 1
    return res


def main():
    n = int(input())
    x = list(map(int, list(input())))
    first_mod = x_decimal = 0
    diff = pow(2, n - 1)
    for i in range(n):
        if x[i]:
            first_mod += 1
            x_decimal += diff
        diff //= 2
    increase_base = x_decimal % (first_mod + 1)  # 反転させる桁が元々0だった場合
    if first_mod > 1:
        decrease_base = x_decimal % (first_mod - 1)  # 反転させる桁が元々1だった場合
    diff = pow(2, n - 1)
    for i in range(n):
        cnt = 0
        if x[i] == 1 and first_mod > 1:
            cnt = 1 + search((decrease_base - diff % (first_mod - 1)) % (first_mod - 1))
        elif x[i] == 0:
            cnt = 1 + search((increase_base + diff % (first_mod + 1)) % (first_mod + 1))
        diff //= 2
        print(cnt)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

arr = [0 for _ in range(N+1)]
for i in range(1, N+1):
    cnt = bin(i).count('1')
    arr[i] = arr[i%cnt] + 1

x = int(X, 2)
pop = X.count('1')
plu = x % (pop+1)
mai = x % (pop-1) if pop>1 else 0

bi = 1 << N
for i in range(N):
    bi = bi >> 1
    if X[i] == '0':
        res = (plu + bi % (pop+1)) % (pop+1)
    else:
        if pop == 1:
            print(0)
            continue
        res = (mai - bi % (pop-1)) % (pop-1)
    print(arr[res] + 1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = int(str(input()), 2)
X_bin = format(X, '0'+str(N)+'b')

ans = [0] * N
for i in range(N):
    if X_bin[i] == '1':
        n = X - (1 << (N - 1 - i))
    else:
        n = X + (1 << (N - 1 - i))

    while n != 0:
        n = n % format(n, '0'+str(N)+'b').count('1')
        ans[i] += 1

    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = int(str(input()), 2)
X_bin = format(X, '0'+str(N)+'b')

ans = [0] * N
for i in range(N):
    if X_bin[i] == '1':
        n = X - (1 << (N - 1 - i))
    else:
        n = X + (1 << (N - 1 - i))

    while n != 0:
        n = n % format(n, '0'+str(N)+'b').count('1')
        ans[i] += 1

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

Submission status: Time Limit Exceeded

Solution code:
def get_ans(string):
    answer = 0
    number = int(string,2)
    while number>0:
        number = number % (bin(number).count('1'))
        answer+=1
    return answer

if __name__=="__main__":
    n = int(input())
    bst = input()
    for i in range(n):
        dummy = list(bst)
        if dummy[i]=='0':
            dummy[i]='1'
        else:
            dummy[i]='0'
        print(get_ans(''.join(dummy)))

Submission status: Time Limit Exceeded

Solution code:
import copy

N = int(input())
X = int(str(input()), 2)
X_bin = format(X, '0'+str(N)+'b')

ans = [0] * N
for i in range(N):
    if X_bin[i] == '1':
        n = copy.deepcopy(X) - (1 << (N - 1 - i))
    else:
        n = copy.deepcopy(X) + (1 << (N - 1 - i))

    while n != 0:
        n = n % format(n, '0'+str(N)+'b').count('1')
        ans[i] += 1

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

Submission status: Time Limit Exceeded

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

ppc = {}
ppc[0] = 0
def popcount(n):    
  if n in ppc:
    return ppc[n]  
  if n == 0:
    return 0
  b = bin(n).count('1')  
  tmp = n%b
  ppc[n] = popcount(tmp) + 1
  return ppc[n]

for i in range(2*10**5+1):
  popcount(i)
  
bit = int('0b'+x,0)
bn = x.count('1')
for i in range(n):
  if x[i] == '1':   
    bt = bn-1
    if bt == 0:
      print(0)
      continue
  else:
    bt = bn+1  
  tmp = bit ^ (1<<(n-i-1))
  print(ppc[tmp%bt]+1)

Submission status: Time Limit Exceeded

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

ppc = {}
ppc[0] = 0
def popcount(n):    
  if n in ppc:
    return ppc[n]  
  if n == 0:
    return 0
  b = bin(n).count('1')  
  tmp = n%b
  ppc[n] = popcount(tmp) + 1
  return ppc[n]

for i in range(n):
  popcount(i)

for i in range(2*10**5+1):
  popcount(i)
  
bit = int('0b'+x,0)
bn = x.count('1')
for i in range(n):
  if x[i] == '1':   
    bt = bn-1
    if bt == 0:
      print(0)
      continue
  else:
    bt = bn+1  
  tmp = bit ^ (1<<(n-i-1))
  print(ppc[tmp%bt]+1)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from functools import lru_cache
from math import factorial#, gcd
from bisect import bisect_left, bisect_right #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

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

def mn(): return -1
pops = defaultdict(mn)
dists = defaultdict(mn)

# def popcnt(n):
#     c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
#     c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
#     c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
#     c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
#     c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
#     c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
#     return c
def popcnt(n):
    return bin(n).count('1')
def myf(n):
    if pops[n] != -1:
        return pops[n]
    else:
        val = popcnt(n)
        pops[n] = val
        return n%val

@lru_cache(maxsize=None)
def saiki(n):
    if n == 0:
        return 0
    else:
        n = myf(n)
        return saiki(n) + 1

if N == 1:
    if X[0] == '0':
        print(1)
        exit()
    else:
        print(0)
        exit()

bX = int(X, 2)
pc = popcnt(bX)
for i in range(N):
    one = False
    if X[i] == '1':
        one = True
        val = bX - 2**(N-i-1)
    else:
        one = False
        val = bX + 2**(N-i-1)
    # print(' val', val)
    if val == 0:
        print(0)
        continue
    if one:
        tpc = pc-1
    else:
        tpc = pc+1
    val %= tpc
    res = saiki(val)
    print(res+1)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from functools import lru_cache
from math import factorial#, gcd
from bisect import bisect_left, bisect_right #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

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

def mn(): return -1
pops = defaultdict(mn)
dists = defaultdict(mn)

def popcnt(n):
    return bin(n).count('1')
# def myf(n):
#     if pops[n] != -1:
#         return pops[n]
#     else:
#         val = popcnt(n)
#         pops[n] = val
#         return n%val

# @lru_cache(maxsize=None)
# def saiki(n):
#     if n == 0:
#         return 0
#     else:
#         n = myf(n)
#         return saiki(n) + 1

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

if N == 1:
    if X[0] == '0':
        print(1)
        exit()
    else:
        print(0)
        exit()

bX = int(X, 2)
pc = popcnt(bX)
for i in range(N):
    one = False
    if X[i] == '1':
        one = True
        val = bX - 2**(N-i-1)
    else:
        one = False
        val = bX + 2**(N-i-1)
    # print(' val', val)
    if val == 0:
        print(0)
        continue
    if one:
        tpc = pc-1
    else:
        tpc = pc+1
    val %= tpc
    res = saiki(val)
    print(res+1)

Submission status: Time Limit Exceeded

Solution code:
def f(x):
  cnt=0
  while x!=0:
    x_bin=bin(x)
    x_bin=str(x_bin).replace('0b','')
    x_sum=list(map(int,x_bin))
    x_sum=sum(x_sum)
    x=x%x_sum
    cnt+=1
  return cnt

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

for i in range(0,N):
  if i==N-1:
    if X[-1]=='0':   
      Xi=X[:-1]+'1'
    else:
      Xi=X[:-1]+'0'
  elif i==0:
    if X[0]=='0':   
      Xi='1'+X[1:]
    else:
      Xi='0'+X[1:]
  else:
    n=i
    if X[n]=='0':
      Xi=X[:n]+'1'+X[n+1:]
    else:
      Xi=X[:n]+'0'+X[n+1:]
  res=f(int(Xi,2))
  print(res)

Submission status: Time Limit Exceeded

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


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


for i in range(n):
	x=s[:i]+ str(1-int(s[i]))+ s[i+1:]
	cnt=0
	a=int(x,2)
	while a!=0:
		a=a%pop(a)
		cnt+=1
	print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def cin():
    return input().split()
def qpow(a,b,p):
    if p == 1 or p == 0:
        return 0
    a = (a%p+p)%p
    ans = 1
    while b!=0:
        if (b&1) != 0:
            ans = (ans * a) % p
        b >>= 1
        a = a * a  % p
    return ans

def f(x):
    ans = 0
    if x == 0:
        return ans
    for i in range(31):
        if ((x>>i)&1) == 1:
            ans += 1
    return f(x%ans) + 1

n = int(input())
x = list(input())
x = x[::-1]
cnt = 0;l = len(x)
r1 = 0;r2 = 0
for i in x:
    if i == '1':
        cnt += 1
i = 0
while i < l:
    if x[i] == '1':
        r1 += qpow(2,i,cnt+1)
        r2 += qpow(2,i,cnt-1)
    i += 1
i = 0
a = []
while i < l:
    if x[i] == '0':
        t = f((r1+qpow(2,i,cnt+1))%(cnt+1))+ 1
    else:
        if cnt-1 !=  0:
            t = f((r2-qpow(2,i,cnt-1)+(cnt-1))%(cnt-1)) + 1
        else:
            t = 0
    i += 1
    a.append(t)
a = a[::-1]
for i in a:
    print(i)

Submission status: Time Limit Exceeded

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

n = int(input())
x = list(input())
bit_cnt = x.count('1')

# bitを一つ増やす場合
pos = [0] * n
pos_total = 0

# bitを一つ減らす場合
neg = [0] * n
neg_total = 0

base = 1
for i in range(n):
    pos[i] = base%(bit_cnt+1)
    if x[::-1][i] == '1':
        # 同時にmod(bit_cnt+1)の法でトータルを作成
        pos_total = (pos_total + base) % (bit_cnt+1)
    base = (base*2) % (bit_cnt+1)
pos = pos[::-1]

base = 1
if bit_cnt == 1:
    # mod取れない
    pass
else:
    for i in range(n):
        neg[i] = base%(bit_cnt-1)
        if x[::-1][i] == '1':
            # 同時にmod(bit_cnt-1)の法でトータルを作成
            neg_total = (neg_total + base) % (bit_cnt-1)
        base = (base*2) % (bit_cnt-1)
    neg = neg[::-1]

def popcount(n):
    s = list(bin(n)[2:])
    return s.count('1')

memo = {}
memo[0] = 0
def dfs(n, depth=0):
    if n in memo:
        return depth + memo[n]
    else:
        ret = dfs(n%popcount(n), depth+1)
        # memo[n] = ret
        return ret

ans = []
for i in range(n):
    if x[i] == '0':
        st = (pos_total + pos[i]) % (bit_cnt+1)
        print(dfs(st, depth=1))
    elif bit_cnt == 1:
        # コーナーケース：すべてのbitが0となる
        print(0)
    else:
        st = (neg_total - neg[i]) % (bit_cnt-1)
        print(dfs(st, depth=1))