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:
# D - Anything Goes to Zero
def conv_decimal(X):
  global N
  global powers
  
  pow = 1
  sum = 0
  
  for i in range(N - 1, -1, -1):
    if i < N - 1:
      pow *= 2
    
    if X[i] == '1':
      sum += pow
    
    powers.append(pow)
  
  return sum


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

from collections import deque
powers = deque()

# 2進数を10進数に変換
decimal_x = conv_decimal(X)

# Xの"1"の数をカウント
popcount_x = X.count('1')

for i in range(N):
  pow = powers.pop()
  
  if X[i] == '0':
    n = decimal_x + pow
    popcount = popcount_x + 1
  else:
    n = decimal_x - pow
    popcount = popcount_x - 1
  
  count = 0

  while popcount > 0:
    n %= popcount
    count += 1
    
    binary = bin(n)
    popcount = binary.count('1')
  
  print(count)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
X=list(input())
m=0
onecount=0
for i in range(N):
  d=N-1-i
  if X[i]=='1':
    m+=2**d
    onecount+=1

def f(x):
  result={}
  result[0]=0
  result[1]=1
  if x in result:
    return result[x]
  else:
    a=str(bin(x))
    b=a.count('1')
    d=x%b
    result[a]=f(d)+1
    return f(d)+1
  
for i in range(N):
  d=N-1-i
  if X[i]=='0':
    D=m+2**d
  else:
    D=m-2**d
  print(f(D))

Submission status: Time Limit Exceeded

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

def popcount(n):
    cnt = 0
    while n > 0:
        cnt += n & 1
        n //= 2
    return cnt

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

nX = int(X, 2)
pcnt = X.count('1')
MOD1 = pcnt + 1
MOD2 = pcnt - 1

nXp = nX % MOD1
if MOD2 != 0:
    nXm = nX % MOD2

delta = 2**(N-1)
pow1 = [1] * N
pow2 = [0] * N
for i in range(1, N):
    pow1[i] = (pow1[i-1] * 2) % MOD1
if MOD2 != 0:
    pow2[0] = 1
    for i in range(1, N):
        pow2[i] = (pow2[i-1] * 2) % MOD2

for i in range(0, N):
    if X[i] == '0':
        k = (nXp + pow1[N-1-i]) % MOD1
        print(f(k) + 1)
    else:
        if MOD2 == 0:
            print(0)
        else:
            k = (nXm - pow2[N-1-i]) % MOD2
            print(f(k) + 1)
    delta //= 2

Submission status: Time Limit Exceeded

Solution code:
import sys

N = int(sys.stdin.readline().strip())
X = sys.stdin.readline().strip()

def popcount(n):
    cnt = 0
    while n > 0:
        cnt += n & 1
        n //= 2
    return cnt

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

nX = int(X, 2)
pcnt = X.count('1')
MOD1 = pcnt + 1
MOD2 = pcnt - 1

nXp = nX % MOD1
if MOD2 != 0:
    nXm = nX % MOD2

delta = 2**(N-1)
pow1 = [1] * N
pow2 = [0] * N
for i in range(1, N):
    pow1[i] = (pow1[i-1] * 2) % MOD1
if MOD2 != 0:
    pow2[0] = 1
    for i in range(1, N):
        pow2[i] = (pow2[i-1] * 2) % MOD2

for i in range(0, N):
    if X[i] == '0':
        k = (nXp + pow1[N-1-i]) % MOD1
        print(f(k) + 1)
    else:
        if MOD2 == 0:
            print(0)
        else:
            k = (nXm - pow2[N-1-i]) % MOD2
            print(f(k) + 1)
    delta //= 2

Submission status: Time Limit Exceeded

Solution code:
import sys

N = int(sys.stdin.readline().strip())
X = sys.stdin.readline().strip()

def popcount(n):
    cnt = 0
    while n > 0:
        cnt += n & 1
        n //= 2
    return cnt

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

nX = int(X, 2)
pcnt = X.count('1')
MOD1 = pcnt + 1
MOD2 = pcnt - 1

nXp = nX % MOD1
if MOD2 != 0:
    nXm = nX % MOD2

delta = 2**(N-1)

for i in range(0, N):
    if X[i] == '0':
        k = (nXp + (delta % MOD1)) % MOD1
        print(f(k) + 1)
    else:
        if MOD2 == 0:
            print(0)
        else:
            k = (nXm - (delta%MOD2)) %MOD2
            print(f(k) + 1)
    delta //= 2

Submission status: Time Limit Exceeded

Solution code:
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby
from heapq import heapify, heappush, heappop

# sys.setrecursionlimit(5000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return map(lambda x: x + d, A)
def ldec(A, d=1): return map(lambda x: x - d, A)

popcount = lambda x: bin(x).count("1")
bitflip = lambda x, n: x ^ (1 << n)
bitflip2 = lambda x, n: x ^ (1 << (len(bin(x))-2 - (n+1)))
bits = lambda x, n = 0: bin(x)[2:].zfill(n)

N = n1()
X = list(map(int, list(s1())))

rt = [0, 0]
t = 1
p = X.count(1)
for i in range(N-1, -1, -1):
    if X[i] == 1:
        if p > 1:
            rt[0] = (rt[0] + t) % (p - 1)
        rt[1] = (rt[1] + t) % (p + 1)
    t *= 2

for i in range(N):
    if X[i] == 1 and p == 1:
        print(0)
        continue

    if X[i] == 0:
        #t = (rt[1] + 2**(N-i-1)) % (p + 1)
        t = (rt[1] + pow(2, N-i-1, p + 1)) % (p + 1)
    else:
        #t = (rt[0] - 2**(N-i-1)) % (p - 1)
        t = (rt[0] - pow(2, N-i-1, p - 1)) % (p - 1)

    ans = 1
    while t > 0:
        t %= popcount(t)
        ans += 1
    
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
#dp = { 0:0, 1:1, 2:1 }
N = int(sys.stdin.readline().strip())
X = sys.stdin.readline().strip()

def f(num, popcnt):
    #print(dp)

    if num == 0:
        return 0
    elif num == 1 or num == 2:
        return 1
    
    if popcnt == -1:
        b = bin(num)
        popcnt = b.count('1')
    
    if num % popcnt == 0:
        return 1
    else:
        return f(num % popcnt, -1) + 1

nX = int(X, 2)
pcnt = X.count('1')

for i in range(0, N):
    if X[i] == '0':
        print(f(nX + 2**(N-i-1), pcnt+1))
    else:
        print(f(nX - 2**(N-i-1), pcnt-1))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# 標準入力を取得
N = int(input())
X = int(input(), 2)

# メイン処理


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


popcount_X = popcount(X)
for n in range(1, N + 1):
    if (X >> (N - n)) & 1:
        if popcount_X == 1:
            print(0)
            continue
        x = (X - 2**(N - n)) % (popcount_X - 1)
    else:
        x = (X + 2**(N - n)) % (popcount_X + 1)
    c = 1
    while x != 0:
        x %= popcount(x)
        c += 1
    print(c)

Submission status: Time Limit Exceeded

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


def popcount(s):
    return s.count("1")


x_10 = int(x, 2)
p = popcount(x)
r_p1 = x_10 % (p + 1)
if p != 1:
    r_m1 = x_10 % (p - 1)
else:
    r_m1 = 0
# print("x_10 ={0}, p = {1}, r_p1 = {2}, r_m1 = {3}".format(x_10, p, r_p1, r_m1))

for i in range(n):
    out = 1
    # print("x[i] = {0}".format(x[i]))
    if x[i] == '1':
        if p == 1:
            m, out = 0, 0
        else:
            m = (r_m1 - ((2 ** (n - i - 1)) % (p - 1))) % (p - 1)
    else:
        m = (r_p1 + ((2 ** (n - i - 1)) % (p + 1))) % (p + 1)
    while m > 0:
        # print("m = {0}".format(m))
        m = m % popcount("{:b}".format(m))
        out += 1
    print(out)

Submission status: Time Limit Exceeded

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


def popcount(s):
    return s.count('1')


x_10 = int(x, 2)
p = popcount(x)
r_p1 = x_10 % (p + 1)
if p != 1:
    r_m1 = x_10 % (p - 1)
else:
    r_m1 = 0
# print("x_10 ={0}, p = {1}, r_p1 = {2}, r_m1 = {3}".format(x_10, p, r_p1, r_m1))

for i in range(n):
    out = 1
    # print("x[i] = {0}".format(x[i]))
    if x[i] == '1':
        if p == 1:
            m, out = 0, 0
        else:
            m = (r_m1 - ((2 ** (n - i - 1)) % (p - 1))) % (p - 1)
    else:
        m = (r_p1 + ((2 ** (n - i - 1)) % (p + 1))) % (p + 1)
    while m > 0:
        # print("m = {0}".format(m))
        m = m % popcount(format(m, 'b'))
        out += 1
    print(out)

Submission status: Time Limit Exceeded

Solution code:

import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby
from heapq import heapify, heappush, heappop

# sys.setrecursionlimit(5000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return map(lambda x: x + d, A)
def ldec(A, d=1): return map(lambda x: x - d, A)

N = n1()
X = int(s1(), 2)

def flip(n, i):
    return n ^ (1 << i)

popcount = lambda x: bin(x).count("1")
bits = lambda x, n = 0: bin(x)[2:].zfill(n)

dp = {}

def search(n):
    if n == 0:
        return 0

    if n in dp:
        return dp[n]

    m = n % popcount(n)
    t = search(m) + 1
    dp[n] = t
    return t

#for i in range(N-1, -1, -1):
#    print(search(flip(X, i)))

p = popcount(X)
r1 = X % (p + 1)
r2 = X % (p - 1) if p > 1 else 0

for i in range(N-1, -1, -1):
    Y = flip(X, i)

    if Y == 0:
        print(0)
        continue

    b = bits(X, N)[i]
    if b == 0:
        t = (r1 + pow(2, i, p+1)) % (p + 1)
    
    elif b == 1:
        t = (r2 - pow(2, i, p-1)) % (p - 1)

    print(search(Y))

Submission status: Time Limit Exceeded

Solution code:

import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby
from heapq import heapify, heappush, heappop

# sys.setrecursionlimit(5000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return map(lambda x: x + d, A)
def ldec(A, d=1): return map(lambda x: x - d, A)

N = n1()
X = int(s1(), 2)

def flip(n, i):
    return n ^ (1 << i)

popcount = lambda x: bin(x).count("1")
bits = lambda x, n = 0: bin(x)[2:].zfill(n)

dp = {}

def search(n):
    if n == 0:
        return 0

    if n in dp:
        return dp[n]

    m = n % popcount(n)
    t = search(m) + 1
    dp[n] = t
    return t

#for i in range(N-1, -1, -1):
#    print(search(flip(X, i)))

p = popcount(X)
r1 = X % (p + 1)
r2 = X % (p - 1) if p > 1 else 0

for i in range(N-1, -1, -1):
    Y = flip(X, i)

    if Y == 0:
        print(0)
        continue

    b = bits(X, N)[i]
    if b == 0:
        t = (r1 + 1 << i) % (p + 1)
    
    elif b == 1:
        t = (r2 - 1 << i) % (p - 1)

    print(search(Y))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = input()
X_arr = list(X)
N, X = int(N), int(X, 2)
MAX_N = 2 * 10 ** 5


def popcount(x):
    cnt = 0
    for i in range(x.bit_length()):
        if x & 1 << i:
            cnt += 1
    return cnt


memo = [0] * (MAX_N + 1)
for i, n in enumerate(range(1, MAX_N + 1), start=1):
    cnt = 0
    while n:
        p = popcount(n)
        n = n % p
        cnt += 1
    memo[i] = cnt


x_popcount = popcount(X)
p_upper, p_downer = x_popcount + 1, x_popcount - 1
y_upper = X % p_upper
y_downer = X % p_downer if p_downer else None

for i in range(N):
    if X_arr[i] == '0':
        z = (y_upper + pow(2, (N - i - 1)) % p_upper) % p_upper
    else:
        if not p_downer:
            print(0)
            continue
        z = (y_downer - pow(2, (N - i - 1)) % p_downer) % p_downer

    print(memo[z] + 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:
def p(x):
  return bin(x).count('1')

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

N = int(input())
X = input()
cnt = X.count('1')
x = int(X,2)
a = x % (cnt + 1)
if cnt != 1:
  b = x % (cnt - 1)

for i in range(N):
  if X[i] == '0':
    k = (a + 2**(N-i-1) % (cnt + 1))%(cnt+1)
  else:
    if cnt == 1:
      print(0)
      continue
    k = (b - 2**(N-i-1) % (cnt - 1))%(cnt-1)
  print(f(k)+1)

Submission status: Time Limit Exceeded

Solution code:
def pop(x):
    binary = []
    while True:
        if x == 1:
            binary.append(x)
            break
        q,mod = divmod(x,2)
        binary.append(mod)
        x = q
    return sum(binary)

N = int(input())
X = list(map(int,list(input())))

pop_X = sum(X)
X_10 = sum([X[i]*2**(N-i-1) for i in range(N)])


for i in range(N):
    count = 0
    Xi_10 = X_10 + 2**(N-i-1) if X[i]==0 else X_10 - 2**(N-i-1)
    pop_Xi = pop_X + 1 if X[i]==0 else pop_X -1
    if pop_Xi == 0:
        print(count)
        continue
    while True:
        r = Xi_10 % pop_Xi
        count+= 1
        if r == 0:
            break
        Xi_10 = r
        pop_Xi = pop(r)
    print(count)

Submission status: Time Limit Exceeded

Solution code:
def p(x):
  return bin(x).count('1')

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

N = int(input())
X = input()
cnt = X.count('1')
x = int(X,2)
a = x % (cnt + 1)
if cnt != 1:
  b = x % (cnt - 1)

for i in range(N):
  if X[i] == '0':
    k = (a + 2**(N-i-1) % (cnt + 1)) % (cnt + 1)
  if X[i] == '1':
    if cnt == 1:
      print(0)
      continue
    k = (b - 2**(N-i-1) % (cnt - 1)) % (cnt - 1)  
  print(f(k)+1)

Submission status: Time Limit Exceeded

Solution code:
# D - Anything Goes to Zero
def conv_decimal(X):
  global N
  global powers
  
  x = list(reversed(X))
  pow = 1
  sum = 0
  
  for i in range(N):
    if i > 0:
      pow *= 2
    
    powers.append(pow)
    
    if x[i] == '1':
      sum += pow
  
  return sum


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

powers = []

# 2進数を10進数に変換
decimal_x = conv_decimal(X)

# Xの"1"の数をカウント
popcount_x = X.count('1')

powers.reverse()

for i in range(N):
  if X[i] == '0':
    n = decimal_x + powers[i]
    popcount = popcount_x + 1
  else:
    n = decimal_x - powers[i]
    popcount = popcount_x - 1
  
  count = 0

  while popcount > 0:
    n %= popcount
    count += 1
    
    binary = bin(n)
    popcount = binary.count('1')
  
  print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = input()
# N = 3
# X = '011'
neutral_popcount = X.count('1')
X = list(map(int, list(X)))

# popcount(n) -> 1 - N の値
# 0でないとpopcount(n) = 0 にならない
# n % popcunct(n) -> N - 1の値
# N - 1までの値がどうなるかしらべておけばOK
# 011 : 3
# 111 : 7 -> 7 % 3 = 1 ->
# 001 : 1
# 010 : 2


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


P = [-1] * (10**5 * 2 + 1)
P[0] = 0
for i in range(1, len(P)):
    # print(f'{i=}')
    # print(f'{P=}')
    if P[i] != -1:
        continue
    n = i
    cnt = 0
    while True:
        cnt += 1
        n = n % popcount(i)
        # print(f'{n=}')
        if P[n] != -1:
            cnt += P[n]
            break
        if n == 0:
            break
        # exit()
    P[i] = cnt
# print(f'{P=}')

plus_x = 0
for x in X:
    plus_x = (plus_x * 2) % (neutral_popcount + 1)
    plus_x = (plus_x + x) % (neutral_popcount + 1)
minus_x = 0
if neutral_popcount != 1:
    for x in X:
        minus_x = (minus_x * 2) % (neutral_popcount - 1)
        minus_x = (minus_x + x) % (neutral_popcount - 1)
# print(f'{plus_x=}, {minus_x=}')

for bit in range(N):
    if X[bit] == 1:
        if neutral_popcount != 1:
            v = -1 * (2**(N - 1 - bit))
            v %= neutral_popcount - 1
            second_value = (minus_x + v) % (neutral_popcount - 1)
            fx = P[second_value] + 1
        else:
            fx = 0
    else:
        v = 1 * (2**(N - 1 - bit))
        v %= neutral_popcount + 1
        second_value = (plus_x + v) % (neutral_popcount + 1)
        fx = P[second_value] + 1
    print(fx)

#  (X + v) MOD (neutral_popcount ± 1)
# = X MOD (neutral_popcount ± 1) +  v (MOD neutral_popcount ± 1)
# X MOD (neutral_popcount + 1), X MOD (neutral_popcount - 1) を先に計算しておく

Submission status: Time Limit Exceeded

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

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

def f(n, count=0):
    if n == 0:
        return count
    else:
        p = popcount(n)
        if p == 1 and count == 0:
            return 1
        else:
            count += 1
            return f(n % p, count)

for i in range(N):
    mask = ['0'] * N
    mask[i] = '1'
    n = int(X, 2) ^ int(''.join(mask), 2)
    print(f(n))

Submission status: Time Limit Exceeded

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

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

def f(n, count=0):
    if n == 0:
        return count
    else:
        count += 1
        return f(n % popcount(n), count)

for i in range(N):
    mask = ['0'] * N
    mask[i] = '1'
    n = int(X, 2) ^ int(''.join(mask), 2)
    print(f(n))

Submission status: Time Limit Exceeded

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

def dec(X):
    a = ''.join(X)
    b = int(a,2)
    return b

def pc(x):
    a = x.count('1')
    return a

al = [0] * N
import copy
for i in range(N):
    ans = 0
    c = X.copy()
    if c[i] == '0':
        c[i] = '1'
    else:
        c[i] = '0'
    if pc(c) == 0:
        continue
    x = dec(c) % pc(c)
    if x == 0:
        ans += 1
    else:
        ans += 1
        while x != 0:
            xl = list(format(x,'b'))
            x = dec(xl) % pc(xl)
            ans += 1
    al[i] = ans
for i in range(N):
    print(al[i])

Submission status: Time Limit Exceeded

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

N = int(readline())
X = readline().rstrip()

X0 = int(X, 2)
count1 = X.count("1")

X0mod0to1 = X0 % (count1 + 1) # 0->1に変化した際の、X0を割った余り
if count1 > 1:
  X0mod1to0 = X0 % (count1 - 1) # 1->0に変化した際の、X0を割った余り
else:
  X0mod1to0 = 0

from collections import defaultdict
dp = defaultdict(int)
dp[0] = 0
def f(x): # 愚直にf(x)を求める式
  if x in dp:
    return dp[x]
  pc = bin(x).count("1")
  val = f(x % pc) + 1
  dp[x] = val
  return val
  
val = 1
ans = [-1] * N

for i in range(N - 1, -1, -1): # 下の桁から順に、f(Xi)の値を求める
  if X[i] == "0": # 0を1に変える場合
    pat = (X0mod0to1 + val % (count1 + 1)) % (count1 + 1)
    ans[i] = f(pat) + 1
  elif X[i] == "1": # 1を0に変える場合
    if count1 > 1:
      pat = (X0mod1to0 - val % (count1 - 1)) % (count1 - 1)
      ans[i] = f(pat) + 1
    else:
      ans[i] = 0
  val *= 2

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-


def get_input() -> tuple:
    """
    標準入力を取得する.

    Returns:\n
        tuple: 標準入力
    """
    N = int(input())
    X = int(input(), 2)

    return N, X


def popcount(n: int) -> int:
    """
    2進表記したときの"1"の個数を取得する.

    Args:\n
        n (int): 整数

    Returns:\n
        int: 2進表記したときの"1"の個数
    """
    return bin(n).count("1")


def main(N: int, X: int) -> None:
    """
    メイン処理

    Args:\n
        N (int): 整数（1 <= N <= 2*10^5）
        X (int): 整数
    """
    # 求解処理
    for n in range(1, N + 1):
        x = X ^ (1 << (N - n))
        c = 0
        while x != 0:
            x %= popcount(x)
            c += 1
        print(c)


if __name__ == "__main__":
    # 標準入力を取得
    N, X = get_input()

    # メイン処理
    main(N, X)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = input()
##for i in range(n):
#    x_lst.append(int(x)%10)
#    x //= 10
#x_lst.reverse()
for i in range(n):
    x_lst = list(x)
    if x_lst[i] == '0':
        x_lst[i] = '1'
    else:
        x_lst[i] = '0'
    x2 = str("".join(map(str, x_lst)))
    x10 = int(x2, 2)
    xcount = str(x2).count('1')
    ans = 0
    while True:
        if xcount == 0:
            break
        else:
            cnt = x10 % xcount
            if cnt == 0:
                ans += 1
                break
            else:
                x10 = cnt
                xcount = str(bin(x10)).count('1')
                ans += 1
    print(ans)

Submission status: Time Limit Exceeded

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

if __name__ == "__main__":
    import sys 

    readline = sys.stdin.readline 

    N = int(input())
    X = readline()
    bit_count = X.count('1')
    X_int = int(X, 2)


    for i in range(N):
        # ビットの反転
        bit_count_n = bit_count
        X_rest = 0
        if X[i] == '0':
            bit_count_n += 1
            X_rest = X_int + pow(2, N - 1 - i)
        else:
            bit_count_n -= 1
            X_rest = X_int - pow(2, N - 1 - i)

        if X_rest == 0:
            print(0)
        else:
            popcount_X = X_rest % bit_count_n
            counter = 1
            while popcount_X != 0:
                popcount_X %= bin(popcount_X).count('1')
                counter += 1
            print(counter)

Submission status: Time Limit Exceeded

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

if __name__ == "__main__":
    import sys 

    readline = sys.stdin.readline 

    N = int(input())
    X = readline()
    bit_count = X.count('1')
    X_int = int(X, 2)


    for i in range(N):
        # ビットの反転
        bit_count_n = bit_count
        X_rest = 0
        if X[i] == '0':
            bit_count_n += 1
            X_rest = X_int + pow(2, N - 1 - i)
        else:
            bit_count_n -= 1
            X_rest = X_int - pow(2, N - 1 - i)

        if X_rest == 0:
            print(0)
        else:
            popcount_X = X_rest % bit_count_n
            counter = 1
            while popcount_X != 0:
                popcount_X = popcount(popcount_X)
                counter += 1
            print(counter)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# 標準入力を取得
N = int(input())
X = int(input(), 2)

# メイン処理


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


for n in range(1, N + 1):
    x = X ^ (1 << (N - n))
    c = 0
    while x != 0:
        x %= popcount(x)
        c += 1
    print(c)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

bn=input()
bi=int(bn,2)
l=len(bn)
ans=[]
moto=bn.count('1')
for i in range(-1,-l-1,-1):
  mm=moto
  a=bi
  t=abs(i)-1
  if bn[i]=='0':
    a+=2**t
    mm+=1
  else:
    if mm==1:
      ans.append(0)
      continue
    a-=2**t
    mm-=1
  cnt=0
  while a>0:
    a%=mm
    mm=str(format(a,'b')).count('1')
    cnt+=1
  ans.append(cnt)
ans.reverse()
for aa in ans:
  print(aa)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = input()
a = x.count('1')
b = int(x,2)
# print (b)

ary = [None for i in range(200010)]
ary[0] = 0

def f(n):
  if ary[n] is not None:
    return ary[n]
  b = bin(n).count('1')
  r = 1 + f(n%b)
  ary[n] = r
  return ary[n]


a1 = a + 1
a0 = a - 1
for i in range(200010):
  f(i)


one = [1] * 200010
zero = [1] * 200010
for i in range(1, 200010):
    if a0 != 0:
        one[i] = one[i-1] * 2 % a0
    zero[i] = zero[i-1] * 2 % a1


ans = [0 for i in range(n)]
for i in range(n-1, -1, -1):
  if x[n-1-i] == '0':
    y = b%a1 + zero[i]
    # y = x %a1
    y %= a1
    print (ary[y]+1)
  else:
    if a0 != 0:
      y = b%a0 - one[i]
      # y = x %a0
      y %= a0
      print (ary[y]+1)
    else:
      print (0)
# ans.reverse()
# for i in ans:
#   print (i)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = input()
a = x.count('1')
b = int(x,2)
# print (b)

ary = [None for i in range(200010)]
ary[0] = 0

def f(n):
  if ary[n] is not None:
    return ary[n]
  b = bin(n).count('1')
  r = 1 + f(n%b)
  ary[n] = r
  return ary[n]


a1 = a + 1
a0 = a - 1
for i in range(200010):
  f(i)


one = [1] * 200010
zero = [1] * 200010
for i in range(1, 200010):
    if a0 != 0:
        one[i] = one[i-1] * 2 % a0
    zero[i] = zero[i-1] * 2 % a1


ans = [0 for i in range(n)]
for i in range(n-1, -1, -1):
  if x[n-1-i] == '0':
    y = b + zero[i]
    # y = x %a1
    y %= a1
    print (ary[y]+1)
  else:
    if a0 != 0:
      y = b - one[i]
      # y = x %a0
      y %= a0
      print (ary[y]+1)
    else:
      print (0)
# ans.reverse()
# for i in ans:
#   print (i)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = input()
a = x.count('1')
b = int(x,2)
# print (b)

ary = [None for i in range(200010)]
ary[0] = 0

def f(n):
  if ary[n] is not None:
    return ary[n]
  b = bin(n).count('1')
  r = 1 + f(n%b)
  ary[n] = r
  return ary[n]


a1 = a + 1
a0 = a - 1
for i in range(200010):
  f(i)


one = [1] * 200010
zero = [1] * 200010
for i in range(1, 200010):
    if a0 != 0:
        one[i] = one[i-1] * 2 % a0
    zero[i] = zero[i-1] * 2 % a1


ans = [0 for i in range(n)]
for i, j in enumerate(reversed(list(x))):
  if j == '0':
    x = b + zero[i]
    # y = x %a1
    x %= a1
    ans[i] = ary[x]+1
  else:
    if a0 != 0:
      x = b - one[i]
      # y = x %a0
      x %= a0
      ans[i] = ary[x]+1
    else:
      ans[i] = 0
ans.reverse()
for i in ans:
  print (i)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = input()
a = x.count('1')
b = int(x,2)
# print (b)

ary = [None for i in range(200010)]
ary[0] = 0

def f(n):
  if ary[n] is not None:
    return ary[n]
  b = bin(n).count('1')
  r = 1 + f(n%b)
  ary[n] = r
  return ary[n]


for i in range(200010):
  f(i)

a1 = a + 1
a0 = a - 1

ans = [0 for i in range(n)]
for i, j in enumerate(reversed(list(x))):
  if j == '0':
    x = b + pow(2,i,a1)
    # y = x %a1
    x %= a1
    ans[i] = ary[x]+1
  else:
    if a0 != 0:
      x = b - pow(2,i,a0)
      # y = x %a0
      x %= a0
      ans[i] = ary[x]+1
    else:
      ans[i] = 0
ans.reverse()
for i in ans:
  print (i)

Submission status: Time Limit Exceeded

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

pop_origin = X.count("1")
pop_one = pop_origin - 1
pop_zero = pop_origin + 1

pop_memo = [0] * N
f_cnt = [0] * N
for i in range(1, N):
    pop_memo[i] = pop_memo[i // 2] + i % 2
    f_cnt[i] = f_cnt[i % pop_memo[i]] + 1

pow_cnt = [1] * N
for i in range(1, N):
    pow_cnt[i] = pow_cnt[i - 1] * 2
pow_cnt.reverse()

X_int = int(X, 2)
for i in range(N):
    if X[i] == "1":
        temp = X_int - pow_cnt[i]
        if temp == 0:
            print(0)
        else:
            n = temp % pop_one
            print(f_cnt[n] + 1)

    elif X[i] == "0":
        temp = X_int + pow_cnt[i]
        n = temp % pop_zero
        print(f_cnt[n] + 1)

Submission status: Time Limit Exceeded

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

pop_origin = X.count("1")
pop_one = pop_origin - 1
pop_zero = pop_origin + 1

pop_memo = [0] * 220000
f_cnt = [0] * 220000
for i in range(1, 220000):
    pop_memo[i] = pop_memo[i // 2] + i % 2
    f_cnt[i] = f_cnt[i % pop_memo[i]] + 1

pow_cnt = [1] * N
for i in range(1, N):
    pow_cnt[i] = pow_cnt[i - 1] * 2
pow_cnt.reverse()

X_int = int(X, 2)
for i in range(N):
    if X[i] == "1":
        temp = X_int - pow_cnt[i]
        if temp == 0:
            print(0)
        else:
            n = temp % pop_one
            print(f_cnt[n] + 1)

    elif X[i] == "0":
        temp = X_int + pow_cnt[i]
        n = temp % pop_zero
        print(f_cnt[n] + 1)

Submission status: Time Limit Exceeded

Solution code:

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

#%%

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

pop_memo = [0] * 220000
for i in range(220000):
    pop_memo[i] = popcount(i)

pop_origin = X.count("1")
pop_one = pop_origin - 1
pop_zero = pop_origin + 1


f_cnt = [0] * 220000
for i in range(1, 220000):
    f_cnt[i] = f_cnt[i % pop_memo[i]] + 1

#pow_cnt = [0] * N
#for i in range(N):
#    pow_cnt[i] = pow(2, i)
#pow_cnt.reverse()

X_int = int(X, 2)
for i in range(N):
    if X[i] == "1":
        temp = X_int - pow(2, N - i - 1)
        if temp == 0:
            print(0)
        else:
            n = temp % pop_one
            print(f_cnt[n] + 1)

    elif X[i] == "0":
        temp = X_int + pow(2, N - i - 1)
        n = temp % pop_zero
        print(f_cnt[n] + 1)