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:
from functools import lru_cache


def popcnt(x):
    return bin(x).count("1")


@lru_cache(maxsize=None)
def rec(n):
    if n == 0:
        return 0
    else:
        return rec(n % popcnt(n)) + 1


n = int(input())
arr = input()

for i in range(n):
    x = arr[:i] + str(1 ^ int(arr[i])) + arr[i + 1:]
    print(rec(int(x, 2)))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = input()
# N = 2 * 10 ** 5
# X = "10"*(10**5)
cnt = X.count('1')

base = int(X, 2)
if cnt == 1:
    base_m1 = 0
else:
    base_m1 = base % (cnt - 1)
base_p1 = base % (cnt + 1)

c = dict()
for i in range(N):

    if (X[i] == '1') and (cnt != 1):
        bins = (base_m1 - 2 ** (N - i - 1)) % (cnt - 1)
        nc = cnt - 1
    elif (X[i] == '1') and (cnt == 1):
        bins = 0
        nc = 0
    else:
        bins = (base_p1 + 2 ** (N - i - 1)) % (cnt + 1)
        nc = cnt + 1

    c[i] = 0
    while True:
        if nc == 0:
            print(c[i])
            break
        n = bins % nc
        c[i] += 1
        if n == 0:
            print(c[i])
            break

        bins = n
        nc = bin(n).count('1')

Submission status: Time Limit Exceeded

Solution code:
LIM=200002
L=[0]*LIM

def bin_sum(Y):
    S=bin(Y)[2:]
    count=0
    for i in range(len(S)):
        count+=int(S[i])
    return count

def bin_sum2(Y):
    count=0
    for i in range(len(Y)):
        count+=int(Y[i])
    return count

for i in range(1,LIM):
    L[i]+=bin_sum(i)

def pop_num(N,b,L):
    if N==0:
        return 0
    v=N%b
    return pop_num(v,L[v],L)+1
    
M=[0]*200002
for i in range(1,200002):
    M[i]+=pop_num(i,L[i],L)
X=int(input())
Y=input()
d=bin_sum2(Y)+1
c=bin_sum2(Y)-1
e=int(Y,2)
for i in range(X):
    Y_i=Y[:i]+str(abs(int(Y[i])-1))+Y[i+1:]
    if Y_i[i]=="1":
        b=d
        f=e+2**(X-1-i)
    else:
        b=c
        f=e-2**(X-1-i)
    if f==0:
        print(0)
    else:
        print(M[f%b]+1)

Submission status: Time Limit Exceeded

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

import math
# 最初にpopcount用のリストを作成する，そもそも2**(10**5)だから圧倒的に範囲が足らなかった
L = [0 for i in range(int(math.log(N,2))+10)]
for i in range(int(math.log(N,2))+10):
    bi = list(str(bin(i)))
    bi = bi[1:]
    L[i] = bi.count('1')

# i番目のビットを反転させて,
dic={}
x0 = int(''.join(X),2)
for i in range(N):
    # ちゃんともとに戻してね，ということで本のビット
    b = int(X[i]) & 1
    bn = b ^ 1
    num = int(''.join(X),2) # できなきゃjoinで
    xi = x0 - b * pow(2,N-1-i) + bn * pow(2,N-1-i)
    num = xi
    count = 0
    while num > 0:
        bi = list(str(bin(num)))
        bi = bi[2:]
        st = ''.join(bi)
        if st in dic:
            bic = dic[st]
        else:
            bic = bi.count('1')
            dic[st] = bic
        num = num % bic
        count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
tmp = input()
x = int(tmp,2)
y = list(tmp)
zuru = [0, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 2, 3, 1, 2, 1, 2, 1, 1, 2, 3, 1, 2, 2, 3, 2, 2, 2, 2, 1, 2, 1, 2, 1, 2, 2, 3, 1, 2, 1, 3, 2, 2, 2, 2, 1, 2, 2, 3, 2, 2, 2, 1, 2, 2, 2, 2, 1, 2, 2, 3, 1, 2, 1, 2, 1, 1, 2, 3, 1, 2, 2, 3, 2, 2, 2, 2, 1, 1, 2, 3, 1, 2, 2, 2, 2, 2, 2, 2, 1, 3, 2, 3, 1, 2, 2, 3, 2, 2, 2, 3, 2, 2, 2, 2, 1, 2, 1, 3, 2, 2, 2, 1, 1, 2, 3, 3, 1, 2, 2, 3, 2, 3, 1, 2, 1, 2, 1, 2, 1, 2, 2, 3, 1, 2, 1, 3, 2, 2, 2, 3, 1, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 3, 3, 1, 2, 1, 3, 2, 2, 2, 2, 1, 2, 2, 2, 1, 3, 2, 2, 2, 2, 2, 2, 1, 2, 2, 3, 1, 1, 2, 2, 3, 3, 2, 2, 1, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 3, 1, 1, 2, 3, 2, 2, 2, 2, 1, 3, 2, 3, 1, 2, 3, 3, 1, 3, 1, 2, 2, 2, 2, 2, 1, 2, 1, 3, 1, 3, 2, 2, 2, 3, 2, 2, 1, 2, 2, 3, 2, 3, 1, 2, 3, 3, 2, 2, 1, 2, 2, 3, 1, 2, 1, 2, 1, 1, 2, 3, 1, 2, 2, 3, 2, 2, 2, 2, 1, 1, 2, 3, 1, 2, 2, 2, 2, 2, 2, 3, 1, 1, 2, 3, 1, 2, 2, 3, 2, 2, 2, 1, 2, 2, 2, 2, 1, 2, 2, 3, 2, 2, 2, 2, 1, 2, 1, 3, 1, 3, 2, 3, 2, 3, 1, 2, 1, 1, 2, 3, 1, 2, 2, 2, 2, 2, 2, 2, 1, 3, 2, 3, 1, 2, 2, 2, 1, 2, 2, 2, 1, 1, 2, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 2, 3, 3, 1, 2, 2, 3, 2, 3, 1, 3, 1, 2, 1, 3, 2, 2, 2, 2, 2, 3, 1, 2, 2, 3, 2, 3, 1, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 3, 3, 2, 2, 2, 3, 1, 1, 2, 3, 1, 2, 1, 3, 2, 3, 1, 2, 2, 2, 2, 2, 1, 2, 2, 3, 1, 1, 2, 2, 3, 3, 2, 2, 1, 3, 2, 3, 2, 3, 1, 3, 1, 3, 2, 2, 1, 2, 3, 3, 2, 2, 2, 2, 1, 3, 2, 3, 1, 2, 3, 3, 1, 3, 1, 2, 1, 1, 2, 3, 3, 2, 2, 2, 2, 3, 1, 2, 2, 2, 2, 3, 1, 2, 2, 3, 2, 3, 1, 2, 3, 3, 2, 2, 1, 3, 2, 3, 2, 3, 1, 2, 2, 2, 3, 3, 1, 2, 2, 3, 2, 3, 2, 3, 1, 2, 1, 2, 1, 2, 2, 3, 1, 2, 1, 3, 2, 2, 2, 2, 1, 2, 2, 3, 2, 2, 2, 1, 2, 2, 2, 2, 1, 2, 2, 3, 1, 2, 1, 3, 2, 2, 2, 2, 1, 2, 2, 1, 1, 2, 3, 2, 2, 2, 2, 3, 1, 1, 2, 3, 1, 2, 1, 2, 2, 3, 2, 2, 1, 2, 2, 3, 2, 2, 2, 3, 2, 2, 2, 2, 1, 2, 1, 3, 2, 2, 2, 1, 1, 2, 3, 3, 1, 2, 2, 3, 2, 3, 1, 3, 2, 2, 2, 2, 1, 3, 2, 3, 1, 2, 3, 2, 1, 3, 2, 1, 1, 1, 2, 3, 3, 3, 1, 2, 2, 3, 2, 3, 1, 1, 2, 3, 1, 2, 1, 3, 2, 2, 2, 2, 1, 2, 2, 2, 1, 3, 2, 2, 2, 2, 2, 2, 1, 2, 2, 3, 1, 1, 2, 2, 3, 3, 2, 2, 1, 2, 2, 1, 1, 2, 3, 2, 1, 2, 2, 3, 2, 2, 2, 2, 1, 2, 1, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 1, 2, 1, 3, 1, 3, 2, 2, 2, 3, 2, 3, 1, 2, 2, 3, 2, 3, 1, 2, 3, 3, 2, 3, 1, 3, 2, 3, 1, 2, 3, 2, 1, 3, 2, 2, 2, 2, 2, 3, 2, 1, 2, 3, 2, 3, 2, 2, 1, 2, 2, 3, 2, 3, 2, 3, 2, 3, 2, 2, 1, 2, 2, 3, 2, 2, 2, 1, 2, 2, 2, 2, 1, 2, 2, 3, 2, 2, 2, 2, 1, 2, 1, 3, 1, 3, 2, 3, 2, 3, 1, 2, 2, 2, 2, 3, 1, 1, 2, 3, 1, 2, 1, 2, 2, 3, 2, 3, 1, 2, 3, 3, 1, 3, 1, 2, 2, 3, 2, 2, 1, 3, 2, 3, 2, 2, 2, 1, 1, 2, 3, 3, 1, 2, 2, 3, 2, 3, 1, 1, 1, 2, 1, 3, 2, 2, 2, 2, 2, 3, 1, 3, 2, 1, 2, 3, 1, 1, 2, 3, 3, 3, 1, 3, 2, 3, 2, 1, 1, 2, 3, 3, 1, 3, 1, 2, 2, 3, 2, 3, 1, 1, 2, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 2, 2, 3, 1, 1, 2, 2, 3, 3, 2, 2, 1, 3, 2, 3, 2, 3, 1, 2, 1, 3, 2, 2, 1, 2, 2, 3, 1, 2, 1, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 3, 2, 3, 2, 3, 2, 2, 1, 2, 3, 3, 2, 2, 2, 3, 2, 3, 2, 3, 1, 2, 2, 3, 2, 3, 1, 2, 3, 3, 2, 3, 1, 1, 2, 3, 2, 3, 1, 2, 2, 2, 2, 3, 1, 3, 2, 3, 2, 3, 2, 2, 2, 3, 2, 2, 1, 3, 2, 3, 2, 1, 2, 3, 3, 3, 2, 2, 1, 2, 2, 3, 2, 3, 2, 3, 2, 2, 2, 2, 2, 2, 3, 3, 1]

_max = pow(2, n-1)
itr = 0
hoge = False
one_num = bin(x).count("1")
while 1:
  n = x ^ _max
  if y[itr] == "0":
    hoge = True
    one_num += 1
  else:
    one_num -= 1
  count = 0
  while n != 0:
    n = n % one_num
    count += 1
    if 0 <= n <=1024:
      count += zuru[n]
      break
  print(count)
  n = x ^ _max
  _max = _max // 2
  itr += 1
  if hoge is True:
    one_num -= 1
    hoge = False
  else:
    one_num += 1
  if _max == 0:
    break

Submission status: Time Limit Exceeded

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

val = 0
cnt = 0

def power(x, y) : 
    res = 1  
  
      
    if (x == 0) : 
        return 0
  
    while (y > 0) : 
        if ((y & 1) == 1) : 
            res = (res * x)
  
        y = y >> 1    
        x = (x * x)
          
    return res 
for i in range(0,n):
    if s[i] == '1':
        cnt += 1
        val += power(2,n-i-1)

def  countSetBits(n): 
    count = 0
    while (n): 
        count += n & 1
        n >>= 1
    return count

for i in range(0,n):
    vall = val
    ans = 0
    if s[i] == '0':
        o = cnt + 1
        vall += power(2,n-i-1)
        while vall != 0:
            vall = vall % (o)
            o = countSetBits(vall)
            ans += 1
    else:
        o = cnt - 1
        vall -= power(2,(n-i-1))
        while vall != 0:
            vall = vall % (o)
            o = countSetBits(vall)
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    sys.setrecursionlimit(200000)
    N = int(input())
    Y = input()
    X = int(Y,2)
    memo = {}
    Ycnt = Y.count("1")
    memo2 = [1]
    for i in range(1,N+1):
        memo2.append(memo2[-1]*2)

    def f(n,cnt):
        if n == 0:
            return 0
        if n not in memo:
            d = cnt
            nx = n%d
            binNx = bin(nx)
            nxCnt = binNx.count("1")
            memo[n] = f(nx,nxCnt)+1
        return memo[n]

    for i in range(N):
        if Y[i] == "1":
            cnt = Ycnt - 1
        else:
            cnt = Ycnt + 1
        a = N-i
        tmp = memo2[a-1]
        n = X^tmp
        print(f(n,cnt))
main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = input()
sum = x.count('1')
for i in range(n):
    if x[i]=='1':
        sum0=sum-1
        cnt=1
        str = (2**(n-1-i))^int(x,2)
        if sum0!=0:
            p = str%sum0
            while p:
                sum0 = bin(p).count('1')
                p = p%sum0
                cnt+=1
        else:
            cnt=0
    else:
        sum0=sum+1
        cnt=1
        str = (2**(n-1-i))^int(x,2)
        p = str%sum0
        while p:
            sum0 = bin(p).count('1')
            p = p%sum0
            cnt+=1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache


def popcnt(x):
    return bin(x).count("1")


@lru_cache(maxsize=None)
def rec(n):
    if n == 0:
        return 0
    else:
        return rec(n % popcnt(n)) + 1


n = int(input())
arr = input()

for i in range(n):
    x = arr[:i] + str(1 ^ int(arr[i])) + arr[i + 1:]
    print(rec(int(x, 2)))

Submission status: Time Limit Exceeded

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

n = int(input())
x = input()
z = '1' * n
o = '0' * n

if (z == x):
  u = n - 1
  d = n - 1
elif (z == o):
  u = 1
  d = 1
else:
  tmp = len(list(filter(lambda x: x == '1', x)))
  u = tmp + 1
  d = tmp - 1


def popcount(i):
  return i % len(list(filter(lambda x: x == '1', format(i, 'b'))))


def toggle(i):
  if (i == '1'):
    return '0'
  else:
    return '1'


def solve(i, count):
  if (i <= 2 * 10**5 + 1 and ans[i] != 0):
    return count + ans[i]
  elif (i == 0):
    return count
  else:
    return solve(popcount(i), count + 1)


def solve2(i, count):
  if (i <= 2 * 10**5 + 1):
    return count + ans[i]
  elif (i == 0):
    return count
  else:
    return solve(popcount(i), count + 1)


ans = [0] * (2 * 10 ** 5 + 1)
for i in range(1, 2 * 10 ** 5):
  ans[i] = solve(i, 0)
for i in range(n):
  if(i == 0):
    _x = toggle(x[0]) + x[1: n]
  elif (i == n - 1):
    _x = x[:i] + toggle(x[n - 1])
  else:
    _x = x[:i] + toggle(x[i]) + x[i + 1:n]
  print(solve2(int(_x, 2), 0))

Submission status: Time Limit Exceeded

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

def popcount(x):
    global count
    if x==0:
        return
    else:
        count += 1
        x_b = bin(x)
        popcount(x % x_b.count('1'))

for i in range(len(x)):
    if x[i]=='1':
        bin_num = x[:i]+'0'+x[i+1:]
    else:
        bin_num = x[:i]+'1'+x[i+1:]
    bin_num = int(bin_num, 2)

    count = 0
    popcount(bin_num)
    print(count)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    x = input()
    cnt,num = 0,0
    for i in range(n):
        if x[i] == '1':
            cnt += 1
            num += 2**(n-i-1)
    dp = [0 for i in range(cnt+1)]
    for i in range(1,len(dp)):
        i_ = i
        c = 0
        while i_!=0:
            m = i_%2
            if m==1:
                c += 1
            i_ = i_//2
        dp[i] = 1 + dp[i%c]
    for i in range(n):
        if x[i]=='1':
            c = cnt - 1
            n_ = num - 2**(n-i-1)
        else:
            c = cnt + 1
            n_ = num + 2**(n-i-1)
        if c==0:
            print(0)
        else:
            m = n_%c
            print(1+dp[m])

if __name__ == "__main__":
    main()

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)

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

dp = {}

def search(n):
    #print("debug: "),
    #print(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(1, 10):
    print(search(i))
"""

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
from collections import Counter

sys.setrecursionlimit(300000)

memp = {}
def popcount(n):
    if n == 0:
        return 0

    global memp
    if n not in memp:
        memp[n] = (n & 1) + popcount(n >> 1)
    return memp[n]

memf = {}
def f(x):
    if x == 0:
        return 0

    global memf
    if x not in memf:
        memf[x] = f(x % popcount(x)) + 1
    return memf[x]

n = int(input())
x = input().rstrip()

init = Counter(x)['1']
for i in range(n):
    if x[i] == '1':
        pc = init - 1
    else:
        pc = init + 1
    nn = int(x[:i] + str(1 - int(x[i])) + x[i+1:], 2)
    if nn == 0:
        print(0)
        continue

    nn = nn % pc
    ans = 1
    while nn != 0:
        nn = nn % popcount(nn)
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
##a = int(stdin.readline().rstrip())
##b, c = [int(x) for x in stdin.readline().rstrip().split()]
##s = stdin.readline().rstrip()
##a = list(set(b))  重複を削除
##a = list(map(int,[int(x) for x in stdin.readline().rstrip().split()])) a[0, 1, 2, ...]
##a = [[0] * 2 for _ in range(n)]  a[0,0]
##v = [s[i: i+2] for i in range(0, len(s), 2)]
##  s="12345678" を v=["12","34","56","78"] にするイメージ
##s = "".join(list)リストを文字列に変換[""]は区切り文字
##a.sort(key=itemgetter(1))リストをソートできるよ(from operator import itemgetterが必要)
##sort_p = sorted(p) 昇順ソート

# -*- coding: utf-8 -*-
from sys import stdin
from operator import itemgetter
from collections import deque, Counter
import math
import pprint
from functools import reduce
import random
import bisect
import copy
# stdin = open("sample.txt")


MOD = 1000000007
INF = float('inf')
alpha = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]

def keta(kazu): # 入力されたintを桁ごとに分解，リストで出力
    kazu_str = str(kazu)
    kazu_list = [int(kazu_str[i]) for i in range(0, len(kazu_str))]
    return kazu_list

def gcd(*numbers): # 最小公倍数
    return reduce(math.gcd, numbers)

def combination(m,n): # mCn
    
    if n > m:
        return 'すまん'
    return math.factorial(m) // (math.factorial(m-n) * math.factorial(n))

def pow_k(x,n):  # (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 fact(n): # nの素因数分解の結果を辞書で出力 fuct(24) → {2: 3, 3: 1}
    arr = {}
    temp = n
    for i in range(2,int(n**0.5)+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr[i] = cnt
    if temp != 1:
        arr[temp] = 1
    if arr == {}:
        arr[n] = 1
    return arr

def popcount(n):
    temp = n
    ans = 0
    while temp > 0:
        if temp % 2 == 1:
            ans += 1
        temp //= 2
    return ans

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

    
def main():
    N = int(stdin.readline().rstrip())
    X = stdin.readline().rstrip()
    Xlist = [0] * N
    for i in range(N):
        if X[i] == "1":
            if i == 0:
                now = "0" + X[1:]
            elif i == N-1:
                now = X[:-1] + "0"
            else:
                now = X[0:i] + "0" + X[i+1:]
        else:
            if i == 0:
                now = "1" + X[1:]
            elif i == N-1:
                now = X[:-1] + "1"
            else:
                now = X[0:i] + "1" + X[i+1:]
        Xlist[i] = int(now, 2)
    
    for i in range(N):
        print(f(Xlist[i]))
main()

Submission status: Time Limit Exceeded

Solution code:
import copy
from collections import Counter
n=int(input())
x=input()

sum1=0

def solve():
    ans=[]

    for i in range(len(x)):
        if x[i]=="0":
            xx=x[:i]+"1"+x[i+1:]
        else:
            xx=x[:i]+"0"+x[i+1:]
        
        num=int(xx,2) #string=>bit int
        kaisuu=0

        while(num>0):
            bit_str=bin(num)
            num_list=Counter(bit_str)
            waru=num_list['1']

            num=num%waru
            kaisuu+=1
        
        ans.append(kaisuu)


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

    
if __name__ == "__main__":
     solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

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

# N = 2 * (10 ** 5)
# X = format(1 << (N - 1), "b")

from functools import lru_cache

@lru_cache(maxsize=None)
def F(Xi):
    ans = 0
    # print("start Xi: {} {}".format(eval("0b" + Xi), Xi))
    while True:
        popcount = Xi.count("1")
        # print("popcount: {}".format(popcount))
        if popcount == 0:
            break
        # print("before: {}".format(Xi))
        Xi = eval("0b" + Xi) % popcount
        Xi = format(Xi, "b")
        # print("after: {}".format(Xi))
        # print("Xi: {} {}".format(eval("0b" + Xi), Xi))
        ans += 1
    return ans


# for i in range(1000, 1001):
#     ans = F(format(i, "b"))
#     print(ans)
# quit()

# print(bin(X))
for i in range(0, N):
    keta = i
    # print("keta: {}".format(keta))
    Xi = list(X)
    if X[keta] == "1":
        Xi[keta] = "0"
    else:
        Xi[keta] = "1"
    Xi = "".join(Xi)
    # Xi = X ^ 1 << keta
    # print("Xi: {} {}".format(eval("0b" + Xi), Xi))
    ans = F(Xi)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
X=input()
x=int(X,2)
c=X.count("1")

for i in range(N):
    if X[i]=="0":
        x2=x+2**(N-i-1)
        p=c+1
    else:
        x2=x-2**(N-i-1)
        p=c-1
    ans=0
    while x2>0:
        x2%=p
        PC=bin(x2)[2:]
        p=PC.count("1")
        ans+=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

from pprint import pprint
from collections import deque, defaultdict
import itertools
import math
import sys

sys.setrecursionlimit(10 ** 6)
INF = float('inf')


N = int(input())
X = bin(int(input(), 2))
# print(f'X = {X}')


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


def popcount(n):
    if n == 0:
        memo_p[0] = 0
        return 0
    if n == 1:
        memo_p[1] = 1
        return 1
    if n in memo_p.keys():
        return memo_p[n]
    memo_p[n] = count_bit(n)
    return memo_p[n]


def f(n):
    # print(f'called f[{n}]')
    if n == 0:
        memo_f[0] = 0
        return 0
    if n == 1:
        memo_f[1] = 1
        return 1
    if n == 2:
        memo_f[2] = 1
        return 1
    if n in memo_f.keys():
        return memo_f[n]
    # print(f'{n} is not found')
    r = n % popcount(n)
    # print(f'popcount = {popcount(n)}')
    # print(f'r = {r}')
    memo_f[n] = f(r) + 1
    return memo_f[n]


memo_p = {}
memo_f = {}

for i in range(N):
    # print(f'i = {i}')
    num = None
    if int(X, 2) & (1 << (N-1-i)):
        num = int(X, 2) - 2 ** (N-1-i)
    else:
        num = int(X, 2) + 2 ** (N-1-i)
    # print(f'num = {num}')
    print(f(num))

Submission status: Time Limit Exceeded

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


def popcount(n):
    b = bin(n)[2:]
    cnt = 0
    for e in b:
        if e == '1':
            cnt += 1
    return cnt


ans = dict()


def f(n):
    if n in ans:
        return ans[n]
    if n == 0:
        return 0
    res = 1+f(n % popcount(n))
    ans[n] = res
    return res


def main():
    n = int(si())
    s = si()[:-1]
    for i in range(n):
        if s[i] == '0':
            ns = s[:i]+'1'+s[i+1:]
        else:
            ns = s[:i]+'0'+s[i+1:]
        ns = '0b'+ns
        print(f(int(ns, 2)))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def main():
    
    n=int(input())
    x=input()
    
    def popcount(m):
        return bin(m).count("1")
    
    intx = int( "0b"+x ,0 )
    popcount0 = x.count("1")
    
    jisho = ["yet"]*n
    for i in range(n):
        if x[i]=="0":
            pop = popcount0+1
            intxi = intx+pow(2,n-i-1)
        else:
            pop = popcount0-1
            intxi = intx-pow(2,n-i-1)
            
        if intxi==0:
            print(0)
            continue
        else:
            c=0
            while intxi!=0:
                if c==0:
                    intxi=intxi%pop
                else:
                    if jisho[intxi]=="yet":
                        togo = intxi%popcount(intxi)
                        jisho[intxi]= togo
                        intxi = togo
                    else:
                        intxi =jisho[intxi]
                    
                #print(intxi)
                c+=1
            print(c)
            #print()
    #        print("f(n)=",c)
main()

Submission status: Time Limit Exceeded

Solution code:
import sys #追加

n=int(input())
sys.setrecursionlimit(10**6*2)

s=input()
X=int(s,2)
ans=[]

ans_memo=[0]*(2**10)
#print(ans_memo)
ans_memo[1]=1
ans_memo[2]=1

def DEF(x,cnt):
    global ans_memo
    #print(x,cnt,ans_memo)
    if x==0:
        return 0
    if x<2**10:    
        if ans_memo[x]!=0:
            return ans_memo[x]
        else:
            if x%(str(bin(x)).count("1"))==0:
                ans_memo[x]=1
                return 1
            else:
                tmp=DEF(x%(str(bin(x)).count("1")),cnt+1)+1
                ans_memo[x]=tmp
                return tmp
    else:
        if x%(str(bin(x)).count("1"))==0:
            return 1
        else:
            tmp=DEF(x%(str(bin(x)).count("1")),cnt+1)+1
            return tmp


ans=[]

for i in range(n):
    tmp=2**(n-i-1)
    tmp_num=X
    #1の時
    if tmp&tmp_num:
        tmp_num-=tmp
        #print(bin(tmp_num),n-i-1)
        ans.append(DEF(tmp_num,0))
        
    else:
        tmp_num+=tmp
        #print(bin(tmp_num),n-i-1)
        ans.append(DEF(tmp_num,0))

#print(ans_memo)

for item in ans:
    print(item)

Submission status: Time Limit Exceeded

Solution code:
memo = dict()
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 func(p):
    hozon = p
    r = 0
    while p > 0:
        if p in memo:
            r += memo[p]
            break
        d = popcnt(p)
        # print(p, d)
        p %= d
        r += 1

    memo[hozon] = r
    return r


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

bit_total = 0
for i in range(n):
    if x[i] == "1":
        bit_total += 1

bin_num = int(x, 2)
L = [[0, 0] for _ in range(n)]  # [数, bit数]

for i in range(n):
    if x[i] == "1":
        L[i][0] = bin_num - 2**(n-i-1)
        L[i][1] = bit_total - 1
    else:
        L[i][0] = bin_num + 2 ** (n - i - 1)
        L[i][1] = bit_total + 1
# print(bit_total)
# print(L)

for i in range(n):
    p = L[i][0]
    d = L[i][1]
    ans = 0
    # print(p)
    hozon2 = p
    if p > 0:
        ans += 1
        p %= d
        ans += func(p)

    memo[hozon2] = ans

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
d1 = {}
def popcount(n):
    if n not in d1:
        q = n
        s = 0
        while q > 0:
            q, r = divmod(q, 2)
            s += r
        d1[n] = s
    return d1[n]

d2 = {}
def f(n):
    X = [n]
    c = 0
    while n != 0:
        if n in d2:
            k = d2[n]
            break
        n %= popcount(n)
        c += 1
        X.append(n)
    else:
        k = 0
    d2.update({x:i+k for i, x in enumerate(X[::-1])})
    return c + k

n, X = open(0).read().split()
n = int(n)
x = int(X, 2)
X = list(map(int, X))
c = popcount(x)
for i in range(n):
    if X[i]:
        y = x - 2**(n-i-1)
        t = c-1
    else:
        y = x + 2**(n-i-1)
        t = c+1
    if y != 0:
        print(f(y%t) + 1)
    else:
        print(0)

Submission status: Time Limit Exceeded

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


def calc(i, count):
    if i == 0:
        return 0
    icount = bin(i).count("1")
    if icount == 0:
        return count + 1
    r = i % bin(i).count("1")
    if r != 0:
        return calc(r, count + 1)
    else:
        return count + 1


for i in range(1, N + 1):
    a = X ^ 2 ** ((N - 1) - (i - 1))
    b = calc(a, 0)
    print(b)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n = int(input())
x = list(input())
d = defaultdict(int)

for i in range(n):
    tmp = x[i]
    if int(tmp):
        x[i] = '0'
    else:
        x[i] = '1'
    num = int(''.join(x), 2)
    res = 0
    arr = []
    while num:
        if d[num]:
            res += d[num]
            break
        cnt = bin(num).count('1')
        num %= cnt
        res += 1
        arr.append(num)
    print(res)
    for a in arr:
        res -= 1
        d[a] = res

    x[i] = tmp

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=input()
xx=x.count('1')
xx2=int(x,2)
l=[0]
for i in range(1,xx+2):
    i1=bin(i).count('1')
    num=0
    while i!=0:
        i%=i1
        i1=bin(i).count('1')
        num+=1
    l.append(num)

k=2**n
for i in range(n):
    k//=2
    if x[i]=='0':
        xxx=xx+1
        xxx2=xx2+k
    else:
        xxx=xx-1
        xxx2=xx2-k
    if xxx2==0:
        print(0)
    elif xxx2%xxx==0:
        print(1)
    elif xxx2<=xx+1:
        print(l[xxx2])
    else:
        print(l[xxx2%xxx]+1)

Submission status: Time Limit Exceeded

Solution code:

N = int(input())
X = input()
ans_dic = {}

for n in range(N):
    s = list(X)
    if X[n] == "0":
        s[n:n+1] = "1" 
    else:
        s[n:n+1] = "0" 
    s = "".join(s)
    first_num  = int(s, 2)
    ans = 0
    num_list = []
    while True:
        num = int(s, 2)

        if num in ans_dic:
            ans += ans_dic[num]
            ans_dic[first_num] = ans
            break
        one = list(s).count("1")
        if one == 0:
            break

        amari = num % one
        num_list.append(num)
        if amari == 0:
            ans += 1
            for n in range(len(num_list)):
                ans_dic[num_list[n]] = ans - n
            break
        else:
            s = str(bin(amari))[2:]
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

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

X_10 = int("0b" + X, 0)
for i in range(N):
    num = X_10
    if X[i] == "0":
        num += int(2**(N-i-1))
    else:
        num -= int(2**(N-i-1))
    num_2 = bin(num)
    count = 0
    while True:
        count_2 = 0
        """
        for j in range(len(num_2)):
            if num_2[j] == "1":
                count_2 += 1
        """
        count_2 = num_2.count("1")
        if count_2 == 0:
            break
        else:
            count += 1
        num_2 = bin(int(num_2, 0) % count_2)
    print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n = int(input())
x = eval('0b' + input())

memo = {0: 0}

def solve(X):
    x = X
    stack = deque([])
    while x:
        if x in memo:
            break
        stack.append(x)
        x = x % bin(x).count("1")
    cnt = memo[x] + 1
    while stack:
        x = stack.pop()
        memo[x] = cnt
        cnt += 1
    return cnt - 1



ans = []

for i in range(n):
    y = 0
    if x & (1 << i):
        y = x - 2 ** i
    else:
        y= x + 2 ** i
    ans.append(solve(y))

for ansi in reversed(ans):
    print(ansi)

Submission status: Time Limit Exceeded

Solution code:
def popcount(x):
  c = 0
  while x > 0:
    if x % 2 == 1:
      c += 1
    x = x >> 1
  return c
  

def calc(x):
  c = 0
  while(x > 0):
    x = x % popcount(x)
    c += 1
  return c

n=int(input())
x=input()
for i in range(0,n):
  j = 0
  if x[i] == '0':
    j = 1
  k = x[:i] + str(j) + x[i+1:]
  l = int(k, 2)
  print(calc(l))

Submission status: Time Limit Exceeded

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

V = [1]*200000
for i in range (2, 200001):
    a = i
    b = str(bin(i))
    c = b.count('1')
    d = a%c
    if d ==0:
        V[i-1] = 1
    else:
        V[i-1] = V[d-1]+1

length = len(X)

binaryA = []
for i in range (0, length):
    binaryA.append(2**i)

c = X.count('1')
chungus = int(X, base = 2)

for i in range (0, length):
    e = c
    if X[i] == '0':
        e+=1
    else:
        e-=1
    a = chungus^binaryA[length-1-i]
    if a == 0:
        print(0)
    else:
        d = a%e
        if d ==0:
            print(1)
        else:
            print(V[d-1]+1)