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

def popcount(n):
    bin_n=bin(n)[2:]
    count=0
    for i in bin_n:
        count+=int(i)
    return count

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

for i in range(n):
    inv=str(int(not bool(int(x[i]))))
    i_10=int((x[0:i]+ inv+x[i+1:n]),2)
    print(f(i_10))

Submission status: Time Limit Exceeded

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

def popcount(n):
    bin_n=bin(n)[2:]
    count=0
    for i in bin_n:
        count+=int(i)
    return count

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

x_inv_list=[]
for i in range(n):
    inv=str(int(not bool(int(x[i]))))
    x_inv_list.append((x[0:i]+ inv+x[i+1:n]))
    
for i in x_inv_list:
    i_10=int(i,2)
    print(f(i_10))

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache
 
sys.setrecursionlimit(4100000)
 
@lru_cache(maxsize=None)
def f(n):
    if n == 0:
        return 0

    return f(n % bin(n).count('1')) + 1

def main():
    N = int(input())
    X = list(input())
    pc = X.count('1')
    now = 0
    for i in range(N):
        if X[i] == '1':
            now += pow(2,N-i-1)

    ac = pc + 1
    dc = pc - 1
    for i in range(N):
        cnt = 0
        if X[i] == '1' and dc:
            tmp = (now - pow(2, N-i-1, dc)) % dc
            cnt = 1 + f(tmp)
        elif X[i] == '0':
            tmp = (now + pow(2, N-i-1, ac)) % ac
            cnt = 1 + f(tmp)

        print(cnt)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    def f(n):
        if n == 0: return 0
        return f(n % bin(n).count('1')) + 1
    n = int(input())
    X = list(input())
    c = sum(list(map(int, X)))
    m = int(''.join(X), 2)
    mp, mm = m % (c + 1), m % (c - 1) if c - 1 != 0 else 0
    j = 1 << n - 1
    for i in range(n):
        if X[i] == '0':
            mod = c + 1
            print(f((mp + j % mod) % mod) + 1)
        else:
            print(f((mm - j % mod + mod) % mod) + 1 if (mod := c - 1) != 0 else 0)
        j = j >> 1

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
X=input()
def popcount(n):
    s=str(bin(n))
    return len([i for i in s if i=='1'])
def f(n,P):
    c=0
    while n!=0:
        n=n%P
        P=popcount(n)
        c=c+1
    return c
x=int(X,2)
P=popcount(x)
for i in range(N):
    F=list(X)
    if F[i]=='1':
        F[i]='0'
        Q=P-1
        y=x-2**(N-i-1)
    else:
        F[i]='1'
        Q=P+1
        y=x+2**(N-i-1)
    print(f(y,Q))

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 % bin(n).count('1')) + 1
    n = int(input())
    X = list(input())
    d = defaultdict(int)
    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):
        if X[i] == '0':
            print(d[b % (c + 1)] + 1 if (b := m + j) != 0 else 0)
        else:
            print(d[b % (c - 1)] + 1 if (b := m - j) != 0 else 0)
        j = j >> 1

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# -*- coding: UTF-8 -*-

import sys


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


def f2(n, d):
    count = 0
    new_d = dict()

    while 1:
        if n == 0:
            d.update(new_d)
            return count, d

        if n in d.keys():
            for k in new_d:
                new_d[k] += d[n]
            d.update(new_d)
            return count + d[n], d

        if n not in new_d.keys() and count > 0:
            new_d[n] = 0

        n = n % popcount(n)
        count += 1
        for k in new_d:
            new_d[k] += 1


def not_n(x, n, N):
    mask = 1
    mask <<= (N-n-1)
    return x ^ mask


def std_in():
    return sys.stdin.readline().strip()


def _main():
    N = int(std_in())
    X = std_in()

    d = dict()
    X = int("0b" + X, 0)

    n = [0] * N

    for i in reversed(range(N)):
        Xn = not_n(X, i, N)

        n[i], d = f2(Xn, d)

    print(*n, sep="\n")


if __name__ == "__main__":
    _main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# -*- coding: UTF-8 -*-

import sys


def popcount(n):
    b = bin(n)
    s = str(b)
    return s.count("1")


def mod_popcount(n):
    return n % popcount(n)


def f(n):
    count = 0
    while 1:
        if n == 0:
            return count
        n = mod_popcount(n)
        count += 1


def not_n(x, n, N):
    mask = 1
    mask <<= (N-n-1)
    return x ^ mask


def std_in():
    return sys.stdin.readline().strip()


def _main():
    N = int(std_in())
    X = std_in()

    X = int("0b" + X, 0)

    n = [0] * N

    for i in range(N):
        Xn = not_n(X, i, N)

        n[i] = f(Xn)

    print(*n, sep="\n")


if __name__ == "__main__":
    _main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
from functools import lru_cache

sys.setrecursionlimit(4100000)

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

def main():
    N = int(input())
    X = input()
    O = int(X, 2)
    pc = X.count('1')
    Y = list(X)
    ans = [0] * N
    pre = 1
    for i in range(N-1,-1,-1):
        if pc - 1 <= 0:
            break
        if Y[i] == '1':
            tmp = (O - pre + pc - 1) % (pc - 1)
            ans[i] = f(tmp) + 1
        pre *= 2
        pre %= (pc - 1)
    pre = 1
    for i in range(N-1,-1,-1):
        if Y[i] == '0':
            tmp = (O + pre) % (pc + 1)
            ans[i] = f(tmp) + 1
        pre *= 2
        pre %= (pc + 1)

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# -*- coding: UTF-8 -*-

import sys


def popcount(n):
    b = bin(n)
    s = str(b)
    return s.count("1")


def mod_popcount(n):
    return n % popcount(n)


def f(n):
    count = 0
    while 1:
        if n == 0:
            return count
        n = mod_popcount(n)
        count += 1


def not_n(X, n):
    if X[n] == "1":
        X = X[:n] + "0" + X[n+1:]
    else:
        X = X[:n] + "1" + X[n+1:]
    return X


def std_in():
    return sys.stdin.readline().strip()


def _main():
    N = int(std_in())
    X = std_in()

    for n in range(N):
        Xn = not_n(X, n)
        Xn = int("0b" + Xn, 0)
        print(f(Xn))


if __name__ == "__main__":
    _main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
X = str(input())
num_one = X.count("1")

dp = [-1] * N
dp[0] = 0
def dfs(n):
    if dp[n] == -1:
        dp[n] = 1 + dfs(n % bin(n).count('1'))
    return dp[n]

num_one = X.count("1")
zero_ver = np.array([pow(2,  i, num_one + 1) for i in range(N)])
one_ver = np.array([-1])
if num_one != 1:
    one_ver = np.array([pow(2,  i, num_one - 1) for i in range(N)])
bool_arr = np.array([True if X[N-i-1] == "1" else False for i in range(N)])
for i in range(1,N+1):
    tmp_bool = bool_arr.copy()
    start = 0
    if tmp_bool[N-i] == False:
        tmp_bool[N-i] = True
        start = sum(zero_ver[tmp_bool]) % (num_one + 1)
        print(dfs(start)+1)
    else:
        if sum(one_ver) == -1:
            print(0)
        else:
            tmp_bool[N-i] = False
            start = sum(one_ver[tmp_bool]) %  (num_one - 1)
            print(dfs(start)+1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
X = str(input())
num_one = X.count("1")
def func(x):
    if x == 0:
        return 0
    else:
        counter = 0
        x_tmp = x
        while x > 0:
            if x % 2 == 1:
                counter += 1
            x = x >> 1
        return func(x_tmp % counter) + 1

num_one = X.count("1")
zero_ver = np.array([pow(2,  i, num_one + 1) for i in range(N)])
one_ver = np.array([-1])
if num_one != 1:
    one_ver = np.array([pow(2,  i, num_one - 1) for i in range(N)])
bool_arr = np.array([True if X[N-i-1] == "1" else False for i in range(N)])
for i in range(1,N+1):
    tmp_bool = bool_arr.copy()
    start = 0
    if tmp_bool[N-i] == False:
        tmp_bool[N-i] = True
        start = sum(zero_ver[tmp_bool]) % (num_one + 1)
        print(func(start)+1)
    else:
        if sum(one_ver) == -1:
            print(0)
        else:
            tmp_bool[N-i] = False
            start = sum(one_ver[tmp_bool]) %  (num_one - 1)
            print(func(start)+1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
X = str(input())
num_one = X.count("1")
def func(x):
    if a[x] != -1:
        return a[x]
    else:
        counter = 0
        x_tmp = x
        while x > 0:
            if x % 2 == 1:
                counter += 1
            x = x >> 1
        a[x_tmp] = func(x_tmp % counter) + 1
        return func(x_tmp % counter) + 1

    

a = [-1] * (2 * 10 ** 5)
a[0] = 0
num_one = X.count("1")
zero_ver = np.array([pow(2,  i, num_one + 1) for i in range(N)])
one_ver = np.array([-1])
if num_one != 1:
    one_ver = np.array([pow(2,  i, num_one - 1) for i in range(N)])
bool_arr = np.array([True if X[N-i-1] == "1" else False for i in range(N)])
for i in range(1,N+1):
    tmp_bool = bool_arr.copy()
    start = 0
    if tmp_bool[N-i] == False:
        tmp_bool[N-i] = True
        start = sum(zero_ver[tmp_bool]) % (num_one + 1)
        print(func(start)+1)
    else:
        if sum(one_ver) == -1:
            print(0)
        else:
            tmp_bool[N-i] = False
            start = sum(one_ver[tmp_bool]) %  (num_one - 1)
            print(func(start)+1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
from functools import lru_cache

sys.setrecursionlimit(4100000)

@lru_cache(maxsize=None)
def f(x):
    if x == 0:
        return 0
    
    mod = x % (bin(x).count('1'))
    return f(mod) + 1


def main():
    N = int(input())
    X = input()
    O = int(X, 2)
    pc = X.count('1')
    Y = list(X)
    ans = [0] * N
    pre = 1
    for i in range(N-1,-1,-1):
        if pc - 1 <= 0:
            break
        if Y[i] == '1':
            tmp = (O - pre + pc - 1) % (pc - 1)
            ans[i] = f(tmp) + 1
        pre *= 2
        pre %= (pc - 1)
    pre = 1
    for i in range(N-1,-1,-1):
        if Y[i] == '0':
            tmp = (O + pre) % (pc + 1)
            ans[i] = f(tmp) + 1
        pre *= 2
        pre %= (pc + 1)

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def e(x, y):
    if y <= 0: return -1
    res = 0
    z = 1
    for i in range(len(x) - 1, -1, -1):
        if x[i] == '1':
            res = (res + z) % y
        z = (z << 1) % y
    return res

def popcount(x):
    x = (x & 0x5555555555555555) + (x >> 1 & 0x5555555555555555)
    x = (x & 0x3333333333333333) + (x >> 2 & 0x3333333333333333)
    x = x + (x >> 4) & 0x0f0f0f0f0f0f0f0f
    x += x >> 8
    x += x >> 16
    x += x >> 32
    return x & 0x7f

fm = [-1] * (2 * (10 ** 5) + 1)
fm[0] = 0
def f(x):
    if fm[x] >= 0: return fm[x]
    fm[x] = 1 + f(x % popcount(x))
    return fm[x]


pc = X.count('1')
s0 = e(X, pc + 1)
s1 = e(X, pc - 1)

for i in range(N):
    t = 0
    if X[i] == '0':
        t = (s0 + e('1' + '0' * (N - i - 1), pc + 1)) % (pc + 1)
    else:
        if pc == 1:
            print(0)
            continue
        t = (s1 - e('1' + '0' * (N - i - 1), pc - 1)) % (pc - 1)
    print(1 + f(t))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
a = 0
pw, pw1, pw2 = [0] * n, [0] * n, [0] * n
pw[0], pw1[0], pw2[0] = 1, 1, 1
v = 0
for i in range(n):
    if s[i] == '1':
        v += 1
for i in range(1, n):
    pw[i] = int(pw[i - 1] * 2)
    pw1[i] = int(pw1[i - 1] * 2) % (v + 1)
    if v >= 2:
        pw2[i] = int(pw2[i - 1] * 2) % (v - 1)
for i in range(n):
    if s[i] == '1':
        a += pw[n - i - 1]        
mod1 = a % (v + 1)
mod2 = 0
if v >= 2:
    mod2 = a % (v - 1)
for i in range(n):
    copy = 0
    x = v
    cnt = 1
    if s[i] == '0':
        x += 1
        copy = (mod1 + pw1[n - i - 1]) % x
    else:
        x -= 1
        if x >= 1:
            copy = (mod2 - pw2[n - i - 1]) % x
        else:
            copy = -1
    if copy == -1:
        print(0)
    else:
        x = bin(copy).count('1')
        while copy > 0:
            copy %= x
            x = bin(copy).count('1')
            cnt += 1
        print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
b = input()
xin = int(b,2)
for i in range(1,n+1):
    x = xin ^ (1 << (n-i))
    count = 0
    while x > 0:
        bx = format(x,'b')
        pc = bx.count('1')
        x %= pc
        count+=1
    print(count)

Submission status: Time Limit Exceeded

Solution code:

import sys
input = sys.stdin.readline

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

  if N == 1:
    if X.count("1"):
      print(0)
    else:
      print(1)
    return True

  base_1_count = X.count("1")
  if base_1_count == 0:
    for _ in range(N):
      print(1)
    return True

  X_int = int(X, 2)
  X_int_p = X_int%(base_1_count + 1)

  # RE 対策
  if base_1_count == 1:
    for i in range(N):
      if X[i] == "1":
        print(0)
      else:
        if i == N - 1:
          Xi = X_int_p + 1
        else:
          Xi = X_int_p
        count = 1
        while Xi != 0:
          Xi %= bin(Xi).count("1")
          count += 1
        print(count)
    return True

  X_int_m = X_int%(base_1_count - 1)
  for i in range(N):
    # 初期値計算を高速にやる
    if X[i] == "1":
      temp_1_count = base_1_count-1
      pow_2 = 2**(N-i-1)%(base_1_count-1)
      if X_int_m <= pow_2:
        Xi = X_int_m - pow_2 + base_1_count-1
      else:
        Xi = X_int_m - pow_2
    else:
      temp_1_count = base_1_count+1
      Xi = X_int_p + 2**(N-i-1)%(base_1_count+1)
      while Xi >= base_1_count+1:
        Xi %= base_1_count+1

    # print("1_c={0}".format(temp_1_count))
    if temp_1_count == Xi:
      print(1)
      continue

    count = 1
    while Xi != 0:
      num_of_1 = bin(Xi).count("1")
      Xi %= num_of_1
      count += 1
    print(count)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

  if N == 1:
    if X.count("1"):
      print(0)
    else:
      print(1)
    return True

  base_1_count = X.count("1")
  if base_1_count == 0:
    for _ in range(N):
      print(1)
    return True

  X_int = int(X, 2)
  X_int_p = X_int%(base_1_count + 1)

  # RE 対策
  if base_1_count == 1:
    for i in range(N):
      if X[i] == "1":
        print(0)
      else:
        if i == N - 1:
          Xi = X_int_p + 1
        else:
          Xi = X_int_p
        count = 1
        while Xi != 0:
          Xi %= bin(Xi).count("1")
          count += 1
        print(count)
    return True

  X_int_m = X_int%(base_1_count - 1)
  for i in range(N):
    # 初期値計算を高速にやる
    if X[i] == "1":
      temp_1_count = base_1_count-1
      pow_2 = 2**(N-i-1)%(base_1_count-1)
      if X_int_m <= pow_2:
        Xi = X_int_m - pow_2 + base_1_count-1
      else:
        Xi = X_int_m - pow_2
    else:
      temp_1_count = base_1_count+1
      Xi = X_int_p + 2**(N-i-1)%(base_1_count+1)
      while Xi >= base_1_count+1:
        Xi %= base_1_count+1

    # print("1_c={0}".format(temp_1_count))
    if temp_1_count == Xi:
      print(1)
      continue

    count = 1
    while Xi != 0:
      num_of_1 = bin(Xi).count("1")
      Xi %= num_of_1
      count += 1
    print(count)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

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

  if N == 1:
    if X.count("1"):
      print(0)
    else:
      print(1)
    return True

  base_1_count = X.count("1")
  if base_1_count == 0:
    for _ in range(N):
      print(1)
    return True

  X_int = int(X, 2)
  X_int_p = X_int%(base_1_count + 1)

  # RE 対策
  if base_1_count == 1:
    for i in range(N):
      if X[i] == "1":
        print(0)
      else:
        if i == N - 1:
          Xi = X_int_p + 1
        else:
          Xi = X_int_p
        count = 1
        while Xi != 0:
          Xi %= bin(Xi).count("1")
          count += 1
        print(count)
    return True

  X_int_m = X_int%(base_1_count - 1)
  for i in range(N):
    # 初期値計算を高速にやる
    if X[i] == "1":
      temp_1_count = base_1_count-1
      pow_2 = 2**(N-i-1)%(base_1_count-1)
      if X_int_m <= pow_2:
        Xi = X_int_m - pow_2 + base_1_count-1
      else:
        Xi = X_int_m - pow_2
    else:
      temp_1_count = base_1_count+1
      Xi = X_int_p + 2**(N-i-1)%(base_1_count+1)
      while Xi >= base_1_count+1:
        Xi %= base_1_count+1

    # print("1_c={0}".format(temp_1_count))
    if temp_1_count == Xi:
      print(1)
      continue

    count = 1
    while Xi != 0:
      num_of_1 = bin(Xi).count("1")
      Xi %= num_of_1
      count += 1
    print(count)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

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

  if N == 1:
    if X.count("1"):
      print(0)
    else:
      print(1)
    return True

  base_1_count = X.count("1")
  if base_1_count == 0:
    for _ in range(N):
      print(1)
    return True

  X_int = int(X, 2)
  X_int_p = X_int%(base_1_count + 1)

  # RE 対策
  if base_1_count == 1:
    for i in range(N):
      if X[i] == "1":
        print(0)
      else:
        if i == N - 1:
          Xi = X_int_p + 1
        else:
          Xi = X_int_p
        count = 1
        while Xi != 0:
          Xi %= bin(Xi).count("1")
          count += 1
        print(count)
    return True

  X_int_m = X_int%(base_1_count - 1)
  for i in range(N):
    # 初期値計算を高速にやる
    if X[i] == "1":
      temp_1_count = base_1_count-1
      pow_2 = 2**(N-i-1)%(base_1_count-1)
      if X_int_m <= pow_2:
        Xi = X_int_m - pow_2 + base_1_count-1
      else:
        Xi = X_int_m - pow_2
    else:
      temp_1_count = base_1_count+1
      Xi = X_int_p + 2**(N-i-1)%(base_1_count+1)
      while Xi >= base_1_count+1:
        Xi %= base_1_count+1

    # print("1_c={0}".format(temp_1_count))
    if temp_1_count == Xi:
      print(1)
      continue

    count = 1
    while Xi != 0:
      num_of_1 = bin(Xi).count("1")
      # print("Xi={0}".format(Xi))
      Xi %= num_of_1
      count += 1
    print(count)
    # print("==")

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

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

  if N == 1:
    if X.count("1"):
      print(0)
    else:
      print(1)
    return True

  base_1_count = X.count("1")
  if base_1_count == 0:
    for _ in range(N):
      print(1)
    return True

  X_int = int(X, 2)
  X_int_p = X_int%(base_1_count + 1)

  # RE 対策
  if base_1_count == 1:
    for i in range(N):
      if X[i] == "1":
        print(0)
      else:
        if i == N - 1:
          Xi = X_int_p + 1
        else:
          Xi = X_int_p
        count = 1
        while Xi != 0:
          Xi %= bin(Xi).count("1")
          count += 1
        print(count)
    return True

  X_int_m = X_int%(base_1_count - 1)
  for i in range(N):
    # 初期値計算を高速にやる
    if X[i] == "1":
      temp_1_count = base_1_count-1
      pow_2 = 2**(N-i-1)%(base_1_count-1)
      if X_int_m <= pow_2:
        Xi = (X_int-2**(N-i-1))%(base_1_count-1)
      else:
        Xi = X_int_m - pow_2
    else:
      temp_1_count = base_1_count+1
      Xi = X_int_p + 2**(N-i-1)%(base_1_count+1)
      while Xi >= base_1_count+1:
        Xi %= base_1_count+1

    # print("1_c={0}".format(temp_1_count))
    if temp_1_count == Xi:
      print(1)
      continue

    count = 1
    while Xi != 0:
      num_of_1 = bin(Xi).count("1")
      # print("Xi={0}".format(Xi))
      Xi %= num_of_1
      count += 1
    print(count)
    # print("==")

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import copy

def popcount(n):
    count = 0
    j = -1
    while len(bin(n))-2 != j:
        j += 1
        if ((n>>j) & 1):
            count += 1
    return count
def f(x):
    c = 0
    while x != 0:
        k= popcount(x)
        p = x%k
        x = p
        c += 1
    return c
N = int(input())
row = list(input())

for i in range(N):
    li = copy.deepcopy(row)
    if li[i] == '0':li[i] = '1'
    else:li[i] = '0'
    li = ''.join(li)
    k = int(li,2)
    print(f(k))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
a = 0
pw = [0] * n
pw[0] = 1
for i in range(1, n):
    pw[i] = pw[i - 1] * 2
for i in range(n):
    if s[i] == '1':
        a += int(pw[n - i - 1])
v = bin(a).count('1')
for i in range(n):
    add = int(pw[n - i - 1])
    if s[i] == '1':
        add *= -1
    copy = a + add
    x = v
    if s[i] == '1':
        x -= 1
    else:
        x += 1
    cnt = 1
    if copy == 0:
        cnt = 0
    while x > 0 and copy % x != 0:
        copy %= x
        x = bin(copy).count('1')
        cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
a = 0
for i in range(n):
    if s[i] == '1':
        a += int(pow(2, n - i - 1))
v = bin(a).count('1')
for i in range(n):
    add = int(pow(2, n - i - 1))
    if s[i] == '1':
        add *= -1
    copy = a + add
    x = v
    if s[i] == '1':
        x -= 1
    else:
        x += 1
    cnt = 1
    if copy == 0:
        cnt = 0
    while x > 0 and copy % x != 0:
        copy %= x
        x = bin(copy).count('1')
        cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
X=input()
def popcount(n):
    s=str(bin(n))
    return len([i for i in s if i=='1'])
def f(n):
    c=0
    while n!=0:
        n=n%popcount(n)
        c=c+1
    return c
for i in range(N):
    F=list(X)
    if F[i]=='1':
        F[i]='0'
    else:
        F[i]='1'
    s=''
    for d in F:
        s=s+d
    print(f(int(s,2)))

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)
  X_int_p = X_int%(base_1_count + 1)
  X_int_m = 1

  if base_1_count > 1:
    X_int_m = X_int%(base_1_count - 1)

# 低速バージョン
  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:
n = int(input())
xs = input()

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

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

x = 0
for i in xs:
  x = x*2 + int(i)

for i in range(n):
  t = x + (1 << (n - 1 - i)) * (-1 if xs[i] == "1" else 1)
  print(f(t))

Submission status: Time Limit Exceeded

Solution code:
from logging import *
basicConfig(level=DEBUG, format='%(levelname)s: %(message)s')
# disable(CRITICAL)

n = int(input())
X = input()
debug('n {}'.format(n))
debug('X {}'.format(X))
po = X.count('1')

# if po == 0:
#     print(0)
#     exit()

pp = po + 1
pm = max(1, po - 1)

rp = 0
rm = 0
for x in X:
    rp = (rp*2 + int(x)) % pp
    rm = (rm*2 + int(x)) % pm

bp = [0]*(n) # 2^i % (po+1)
bm = [0]*(n) # 2^i % (po-1)
bp[n-1] = 1 % pp
bm[n-1] = 1 % pm
for i in range(n-1,0,-1):
    bp[i-1] = bp[i]*2 % pp
    bm[i-1] = bm[i]*2 % pm

debug('po {}'.format(po))
debug('pp {}'.format(pp))
debug('pm {}'.format(pm))
debug('rp {}'.format(rp))
debug('rm {}'.format(rm))
debug('bp {}'.format(bp))
debug('bm {}'.format(bm))
debug('===')

def popcount(x):
    c = 0
    while x > 0:
        if x & 1: c += 1
        x //= 2
    return c

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

for i in range(n):
    if X[i] == '0':
        ri = (rp + bp[i]) % pp
    else: # '1'
        if po-1 != 0: ri = (rm - bm[i]) % pm
        else:
            print(0)
            continue
    debug('i {} ri {}'.format(i,ri))
    c = f(ri) + 1
    debug('c {}'.format(c))
    print(c)

Submission status: Time Limit Exceeded

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


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


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

Submission status: Time Limit Exceeded

Solution code:
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


dp = [0] * ((10 ** 5) * 2 + 1)
for i in range(1, len(dp)):
    dp[i] = f(i)


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

    if X[i] == "1" and n1 == 1:
        print(cnt)
    elif X[i] == "1":
        print(dp[(Xms - pow(2, N - i - 1, n1 - 1)) % (n1 - 1)] + 1)
    else:
        print(dp[(Xml + pow(2, N - i - 1, n1 + 1)) % (n1 + 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


dp = [0] * ((10 ** 5) * 2 + 1)
for i in range(1, len(dp)):
    dp[i] = f(i)


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

    if X[i] == "1" and n1 == 1:
        print(cnt)
    elif X[i] == "1":
        print(dp[(Xms - p2s[-i - 1]) % (n1 - 1)] + 1)
    else:
        print(dp[(Xml + p2l[-i - 1]) % (n1 + 1)] + 1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import collections
import decimal
import itertools
from collections import deque
from functools import reduce
import heapq
import copy
n = int(input())
#l, r, d = map(int, sys.stdin.readline().split())
#s = input()
#a = list(map(int, sys.stdin.readline().split()))

X = input()
for i in range(n):
    ans = 0
    x = X
    if x[i] == "0":
        x = x[:i] + "1" + x[i+1:]
    else:
        x = x[:i] + "0" + x[i+1:]
    
    a = int(x, 2)

    while (a != 0):    
        b = x.count("1")
        a %= b
        ans += 1
        x = bin(a)
        x = x[2:]

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = int(input(), 2)
dp = [0]*N
dp[0] = 0
checked = [False]*N
for i in range(1, N):
    c = bin(i).count("1")
    dp[i] = dp[i%c] + 1
for i in range(N):
    Xi = X^2**(N-i-1)
    C = bin(Xi).count("1")
    if C == 0:
        print(0)
    else:
        print(dp[Xi%C]+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import collections
import decimal
import itertools
from collections import deque
from functools import reduce
import heapq
import copy
n = int(input())
#l, r, d = map(int, sys.stdin.readline().split())
#s = input()
#a = list(map(int, sys.stdin.readline().split()))

X = input()
for i in range(n):
    ans = 0
    x = X
    if x[i] == "0":
        x = x[:i] + "1" + x[i+1:]
    else:
        x = x[:i] + "0" + x[i+1:]
    
    a = int(x, 2)

    while (a != 0):    
        b = 0
        for j in range(len(x)):
            if x[j] == "1":
                b += 1

        a %= b
        ans += 1
        x = bin(a)
        x = x[2:]

    print(ans)

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+10)]
for i in range(1, n+10):
	nxt[i] %= bin(i).count("1")

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = input()
fn = {0: 0}
fn_keys = {0}

def culc_fn(n, fn, fn_keys):
    if not n in fn_keys:
        popcount = bin(n).count('1')
        tmp = n%popcount
        fn[n] = culc_fn(tmp, fn, fn_keys) + 1
        fn_keys.add(n)
    return fn[n]

culc_fn(int('1'*N), fn, fn_keys)

for i in range(N):
    tmp = int(X[:i] + ('0' if X[i] == '1' else '1') + X[i+1:], 2)
    popcount = bin(tmp).count('1')
    if popcount > 0:
        print(culc_fn(tmp%popcount, fn, fn_keys)+1)
    else:
        print(0)

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)

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

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