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

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

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

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

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

bX = int(X, 2)
for i in range(N):
    if X[i] == '1':
        val = bX - 2**(N-i-1)
    else:
        val = bX + 2**(N-i-1)
    res = saiki(val)
    print(res)

Submission status: Time Limit Exceeded

Solution code:
def sol():
    n=int(input())
    x=input()
    chk=0
    for i,j in enumerate(x[::-1]):
        if j=="1":
            chk+=2**i
    c={}
    d={}
    ans=[]
    for i,j in enumerate(x[::-1]):
        p=pow(2,i)
        if j=="1":
            t=chk-p
        else:
            t=chk+p
        s=t
        cnt=0
        while t:
            if t not in c:
                pc=bin(t).count("1")
                c[t]=pc
            else:
                pc=c[t]
            t%=pc
            cnt+=1
            if t in d:
                cnt+=d[t]
                break
        if s not in d:
            d[s]=cnt
        ans.append(cnt)
    for i in ans[::-1]:
        print(i)

if __name__=="__main__":
    sol()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = list( i for i in str(input()))


def nisin(a, I):
  a = a.copy()
  if a[I] == '0':
    a[I] =  '1'
  elif a[I] == '1':
    a[I] = '0'
    
  return int(''.join(a), 2)

def solve(kazu):
  cnt = 0
  
  while True:
    if kazu == 0:
      break
    cnt += 1
    kazu2 = format(kazu,'b')
    c = kazu2.count('1')
    if kazu % c == 0:
      break
    kazu = kazu % c
  return cnt

for i in range(N):
  print(solve(nisin(X, i)))

Submission status: Time Limit Exceeded

Solution code:
def popcount(n):
    bin_n = format(n, "b")
    ans = 0
    for e in bin_n:
        if e=="1":
            ans += 1
    return ans

N = int(input())
bin_X = input()

max_pop = 200000
pop_list = [0] * (max_pop+1)
for i in range(1, max_pop+1):
    pop_list[i] = popcount(i)

ans_list = [0] * (max_pop+1)
for i in range(1, max_pop+1):
    new = i
    ans = 0
    while True:
        if new == 0:
            break
        ans += 1
        new = new % pop_list[new]
    ans_list[i] = ans

pop = 0
for e in bin_X:
    if e=="1":
        pop += 1

X = int(bin_X, 2)

for i in range(N):
    if bin_X[i] == "0":
        new = X + 2**(N-i-1)
        pop_new = pop + 1
    else:
        new = X - 2**(N-i-1)
        pop_new = pop - 1
    #print(new)
    if new == 0:
        ans = 0
    else:
        new = new % pop_new
        ans = ans_list[new] + 1
        
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def popcount(n):
    ans = 0
    while (n > 0):
        ans += n % 2
        n = n // 2
    return ans


def arrayTo2(A):
    ans = 0
    l = len(A)
    for i in range(l):
        if (A[i] == '1'):
            ans += 2 ** (l-i-1)

    return ans


N = int(input())

#popcountA = [0]*(2**N)
popcountA = [0 for x in range(2**N)]

for i in range(1, 2**N):
    popcountA[i] = popcount(i)


X = input()

for i in range(N):
    Xi = []
    for j in range(N):
        if (i == j):
            if (X[i] == '0'):
                Xi.append('1')
            else:
                Xi.append('0')
        else:
            Xi.append(X[j])

    ans = 0
    n = arrayTo2(Xi)
    while (n > 0):
        n = n % popcountA[n]
        ans += 1

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=str(input())
def f(n, cnt):
  if n==0:
    return(cnt)
  else:
    n=n%bin(n).count("1")
    return f(n, cnt+1)
for i in range(n):
  x2=x
  if x2[i]=="0":
    x2=x2[:i]+"1"+x2[i+1:]
  else:
    x2=x2[:i]+"0"+x2[i+1:]
  print(f(int(x2, 2), 0))

Submission status: Time Limit Exceeded

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

def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f

def solve(N, X):
    X_oct = int(X, 2)
    X_one_count = X.count("1")
    # X_one_count = popcount(X)

    memo = {}
    for i, x in enumerate(X):
        if x == '1':
            X_current = X_oct - 2 ** (N-1-i)
            X_one_current = X_one_count - 1
        elif x == '0':
            X_current = X_oct + 2 ** (N - 1 - i)
            X_one_current = X_one_count + 1

        if X_one_current == 0:
            print(0)
            continue

        count = 0
        while True:
            X_current = X_current % X_one_current
            X_one_current = popcount(X_current)
            count += 1

            if X_current == 0:
                break

            if X_current in memo:
                count += memo[X_current]
                break

        print(count)

    return

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
x = eval('0b' + input())

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

memo = {}

# def slove(x):
#     cnt = 0
#     tmp = []
#     while x:
#         if x in memo:
#             return cnt + memo[x]
#         else:

#         x = x % popcount(x)
#         cnt += 1
#     return cnt

def solve(x, cnt):
    if x == 0:
        return cnt

    if x in memo:
        return cnt + memo[x]
    else:
        ans = solve(x % popcount(x), cnt + 1)
        memo[x] = ans - cnt
        return ans


px = popcount(x)
ans = []

for i in range(n):
    y = 0
    if x & (1 << i):
        y = x & ~(1 << i)
    else:
        y= x | (1 << i)
    ans.append(solve(y, 0))

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

Submission status: Time Limit Exceeded

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


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


for i in range(N):
    count = 0
    if X[i] == '1':
        tmp = int(X)
        tmp -= 10 ** (N - i - 1)
    else:
        tmp = int(X)
        tmp += 10 ** (N - i - 1)

    tmp = int(str(tmp), 2)
    origin = tmp

    while True:
        if tmp == 0:
            print(count)
            break
        elif tmp == 1:
            print(count + 1)
            break
        elif tmp == 2:
            print(count + 1)
            break
        else:
            count += 1
            tmp = tmp % popcount(tmp)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = list(input())
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]

for i in range(len(x)):
  y = x.copy()
  if x[i] == "0":
    y[i] = "1"
  else:
    y[i] = "0"
  n = int("".join(y), 2)
  count = 0
  while n != 0:
    if 0 <= n <=1024:
      count += zuru[n]
      break
    one_num = bin(n)
    n = n % one_num.count("1")
    count += 1
  print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = int(input(), 2)
def popcount(n, cnt):
    kosuu = 0
    for i in str(bin(n))[2:]:
        if i == "1":
            kosuu += 1
    if n != 0:
        return popcount(n%kosuu, cnt+1)
    else:
        return cnt

for i in range(1, N+1):
    mask = 1<<N-i
    x = X ^ mask
    print(popcount(x, 0))

Submission status: Time Limit Exceeded

Solution code:

def popcount(N):
    cnt = 0
    while N > 0:
        N = N % int(str(bin(N)).count('1'))
        cnt += 1
    return cnt
def main():
    n = int(input())
    x = input()

    for i in range(1,n+1):
        xa = '0'
        if x[i-1] == '0':
            xa = '1'
        else:
            xa = '0'
        xx = x[:i-1] +xa+ x[i:]
        xi = int('0b'+xx,0)
        print(popcount(xi))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
x=input()
z=[]
for i in range(len(x)):
  z.append(x[i])
def pop(Y):
  listy=[]
  for i in range(Y):
    listy.append(Y%2)
    Y=Y//2
  result=listy.count(1)
  return result
def times(A):
  count=0
  while A!=0:
    A=A%pop(A)
    count=count+1
  return count
for i in range(N):
  w=z.copy()
  w[i]=str((int(w[i]))*(-1)+1)
  sum=0
  for j in range(len(w)):
    sum=sum+(int(w[j]))*(2**(len(w)-j-1))
  print(times(sum))

Submission status: Time Limit Exceeded

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

def popcount(num):
    sum_ = sum(map(int, str(bin(num)).lstrip('0b')))
    return sum_

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

def calc(idx, xx):
    xx = ''.join([str(1-int(c)) if i == idx-1 else c for i, c in enumerate(xx)])
    num = int(xx, 2)
    return fn(num)
    
for i in range(1, N+1):
    print(calc(i, x))

Submission status: Time Limit Exceeded

Solution code:
def popcount(x):
  xbin = list(bin(x))
  p = 0
  for i in range(len(xbin)):
    if xbin[i] == '1':
      p += 1
  
  return p
      
import copy as cp
N = int(input())
X = input()

x = list(X)
P = [0 for _ in range(2**N)]

for i in range(N):
  x = list(X)
  if x[i] == '0':
    x[i] = '1'
  else:
    x[i] = '0'
  
  xint = 0
  for j in range(N):
    xint += 2**(N-j-1)*int(x[j])

  c = 0
  while xint > 0:
    if P[xint] == 0:
      P[xint] = popcount(xint)
    
    xint = xint % P[xint]
    c += 1
  
  print(c)

Submission status: Time Limit Exceeded

Solution code:
def func(n, s):
    v = list("1" + "0" * n)
    x = int(s, 2)
    x ^= int("".join(v), 2)
    cnt = 0
    while x > 0:
        val = str(bin(x)).count('1')
        x %= val
        cnt += 1
    return cnt

def main():
    N = int(input())
    s = input()
    index = list(range(N))[::-1]
    for n in index:
        print(func(n, s))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    X = input()
    X_count = X.count("1")
    X = int(X, 2)
    ans = []
    
    def popcount(x):
        '''xの立っているビット数をカウントする関数
        (xは64bit整数)'''

        # 2bitごとの組に分け、立っているビット数を2bitで表現する
        x = x - ((x >> 1) & 0x5555555555555555)

        # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
        x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

        x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
        x = x + (x >> 8) # 16bitごと
        x = x + (x >> 16) # 32bitごと
        x = x + (x >> 32) # 64bitごと = 全部の合計
        return x & 0x0000007f

    for i in range(N-1, -1, -1):
        count = 1
        target = 1 << i
        Xi = X ^ target

        if X_count == 1 and target & X:
            ans.append(0)
            continue

        if target & X:
            Xi %= (X_count - 1)
        else:
            Xi %= (X_count + 1)

        # process
        # Xi はN-1以下
        while Xi:
            count += 1
            Xi %= popcount(Xi)

        ans.append(count)
    
    print(*ans, sep="\n")
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
X = input()
#N = 2 * 100000
#X = "0" * N
def hanten(a,i):
    if a[i] == "0":
        return(a[:i] + "1"+ a[i+1:])
    else:
        return(a[:i] + "0"+ a[i+1:])

#def hanten(num, n):
#    print(1 << n, num ^ (1 << n))
#    return num ^ (1 << n)
#print('\n'.join(X))
for i in range(N):
    hantened = int(hanten(X,i),2)
    #print(hantened)
    cnt = 0
    while (hantened > 0):
        hantened = hantened % bin(hantened).count("1")
        cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = input()
xlis = []
for i in range(n):
    xlis.append(x[i])
xi = []
def flip(m):
    if m == "1":
        return "0"
    else:
        return "1"
for i in range(n):
    if i == 0:
        xlis[i] = flip(xlis[i])
        xi.append("".join(xlis))
    else:
        xlis[i-1] = flip(xlis[i-1])
        xlis[i] = flip(xlis[i])
        xi.append("".join(xlis))
def popcount(m):
    return bin(m).count("1")
for i in range(len(xi)):
    xi[i] = int(xi[i], 2)
for i in range(len(xi)):
    m = xi[i]
    ans = 0
    while m != 0:
        m %= popcount(m)
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

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


def popcount(num):
    num = format(num, 'b')
    return num.count('1')


for i in range(N):
    X2 = list(X)
    count = 0
    work = X[i]
    if work == "0":
        X2[i] = '1'
    else:
        X2[i] = '0'
    n = ''.join(X2)
    n = int(n, 2)
    while n != 0:
        n = n % popcount(n)
        count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

from functools import lru_cache

def popcount1(n):
    ans = 0
    while n > 0:
        ans += n & 1
        n //= 2
    return ans

bit = {}
@lru_cache(maxsize=None)
def popcount2(bits):
    if bits in bit:
        return bit[bits]
    ori_bit = bits

    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555)
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333)
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f)
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff)
    ans = (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff)
    bit[ori_bit] = ans
    return ans


memo = {0: 0}
@lru_cache(maxsize=None)
def rec(n):
    if n in memo:
        return memo[n]
    
    p = popcount2(n)
    new_n = n % p
    ans = rec(new_n) + 1
    memo[n] = ans
    return memo[n]


def submit():
    n = int(input())
    xs = list(input())
    x = int('0b' + "".join(xs), 0)

    # 前準備
    for i in range(1, 200001):
        rec(i)

    ans = []
    base_bit = popcount1(x)
    bit[x] = base_bit
    mask = 1 << (n - 1)
    for i in range(1, n + 1):
        if xs[i - 1] == "0":
            xi = x + mask
            bit[xi] = bit[x] + 1
            xs[i - 1] = "0"
        else:
            xs[i - 1] = "0"
            xi = x - mask
            bit[xi] = bit[x] - 1
            xs[i - 1] = "1"
        ans.append(rec(xi))
        mask >>= 1

    for a in ans:
        print(a)


if __name__ == "__main__":
    submit()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
#N, K = (int(i) for i in input().split())
#B = [int(x) for x in input().split()]
#A = [[int(i) for i in input().split()] for i in range(N)]

def popcountdiv(n):
    return n % (bin(n).count("1"))

memo = {}
def f(n):
    if n == 0:
        return 0
    if n in memo:
        return memo[n]
    else:
        res = f(popcountdiv(n))
        memo[n] = res+1
        return 1 + res

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

for i in range(N):
    print(f(int(X[:i] + str((int(X[i])+1)%2)+ X[i+1:] , 2)))

Submission status: Time Limit Exceeded

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue
#import numpy as np
# sympy as syp(素因数分解とか)
Mod = 1000000007
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1] 
for i in range(2, 10**5 + 1):
    fact.append((fact[-1] * i) % Mod)
    inv.append((-inv[Mod % i] * (Mod // i)) % Mod)
    factinv.append((factinv[-1] * inv[-1]) % Mod)
    
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % p
    
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[y] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)
import string
def main():  #startline-------------------------------------------
    n = int(input())
    x = input()
    xint = int(x,2)
    def countbin(i): #f(x)を求める関数
        bin_i = bin(i)
        popcount = bin_i.count("1")
        cnt = 0
        while i != 0:
            i = i % popcount
            cnt += 1
            popcount = bin(i).count("1")
        return cnt
    for i in range(len(x)):
        if x[i] == "0":
            print(countbin(xint + 2 ** (n - i - 1)))
        else:
            print(countbin(xint - 2 ** (n - i - 1)))

if __name__ == "__main__":
    main() #endline===============================================

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=[0]*(n+1)
s=input()
num=0
def al(x):
    pop=0
    k=1
    while x>=k:
        if x&k: pop+=1
        k<<=1
    return pop
for i in reversed(range(0,len(s))):
    num+=int(s[i])*(1<<(len(s)-i-1))
k=1
for i in reversed(range(1,n+1)):
    num1=num^k
    while num1:
        l[i]+=1
        num1%=al(num1)
    k<<=1
for i in range(1,n+1):
    print(l[i])

Submission status: Time Limit Exceeded

Solution code:
#AIsing2020 d

import sys,math,collections,itertools,copy
input = sys.stdin.readline


def popcount(n):
    cou1 = 0
    while n>0:
        cou1+=n%2
        n = n//2
    return cou1

def count(nc):
    co = 0
    while nc >0:
        cou1 = popcount(nc)
        nc = nc%cou1
        co +=1
    return co

N = int(input())
X = list(input().rstrip())

for i in range(N):
    Y = copy.copy(X)
    if Y[i] == '1':
        Y[i] = '0'
    else:
        Y[i] = '1'
    s = '0b'+"".join(Y)
    a =int(s,2)
    co = count(a)
    print(co)

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(500000)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def inot(X, i, N):
    return int(X, base=2)^(1<<N-1-i)

@lru_cache(None)
def f(n):
    if n == 0:
        return 0
    else:
        return 1+f(n%bin(n).count('1'))

def main():
    N = ii()
    X = input()
    dic = {}
    for i in range(N):
        Xi = inot(X, i, N)
        print(f(Xi))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

#print(x)

def popcount(x):
    #print()
    return bin(x).count("1")

#dic[num] = f(num)
dic = {0: 0, 1: 1, 2: 1}

def f(x):
    #print(x)
    if x in dic:
        return dic[x]
    else:
        next_x = x % popcount(x)
        return f(next_x) + 1

for i in range(n):
    keta = n - i - 1
    bit = 2 ** keta
    trans_num = num ^ bit
    #print(bin(num), bin(bit), bin(trans_num))
    #print("ans", f(trans_num))
    print(f(trans_num))


"""
for i in range(1000):
    print("i", i, "pop", popcount(i))
"""

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

def popcount(a):
    return Counter(list(bin(a)))['1']

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

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

Submission status: Time Limit Exceeded

Solution code:
def popcount(n):
  res = 0
  for i in str(bin(n))[2:]:
    if i == '1': res += 1
  return res

def toggle_nth_bit(num, n):
  return num ^ (1<<n)

n = int(input())
x = int('0b' + input(), 0)
l = []

for i in range(n):
  cnt = 0
  tmp = toggle_nth_bit(x, n-1-i)
  while tmp:
    tmp = tmp % popcount(tmp)
    cnt += 1
  l.append(cnt)
for i in l:
  print(i)

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'))
    if mod == 0:
        return 1

    return f(mod) + 1


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

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy

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

if __name__ == "__main__":
    N = int(input())
    X = list(input())

    for i in range(N):
        Xn = copy.copy(X)
        if Xn[i] == '1':
            Xn[i] = '0'
        else:
            Xn[i] = '1'
        pop = int(''.join(Xn), 2)
        f = 0
        while pop!=0:
            f += 1
            pop = pop % popcount(pop)

        print(f)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
X=input()
for i in range(N):
    x=''
    for j in range(N):
        if i == j:
            x+='1'
        else:
            x+='0'
    y=int(X,2) ^ int(x,2)
    ans = 0
    while y!=0:
        y = y % bin(y).count('1')
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

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

def popcount(n):
    cnt = 0
    while n != 0:
        cnt += 1
        n = n % bin(n).count('1')
        
    return cnt

for i in range(N):
    temp_X = [l for l in X]
    if temp_X[i] == '0':
        temp_X[i] = '1'
    else:
        temp_X[i] = '0'
    temp_X = ''.join(temp_X)
    
    n = int(temp_X, 2)
    
    print(popcount(n))

Submission status: Time Limit Exceeded

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

from functools import lru_cache


def popcount(bits: str):
    return len([elm for elm in bits if elm == '1'])


@lru_cache(maxsize=20000)
def f(num):
    if num == 0:
        return 0
    else:
        pc = popcount('{:b}'.format(num))
        return 1 + f(num % pc)


def reverse_bit(bits: str, digit):
    def toggle(a):
        if a == '1':
            return '0'
        else:
            return '1'

    ret = list(bits)
    ret[digit-1] = toggle(bits[digit-1])
    return ''.join(ret)

def convert(x: str):
    ans = 0
    i = 0
    for elm in list(x)[::-1]:
        if elm == '1':
            ans += 2 ** i
        i += 1
    return ans


for i in range(1, N+1):
    bits = reverse_bit(X, i)
    pc = popcount(bits)
    # print(f'# {bits} {convert(bits)} {pc}')
    print(f(convert(bits)))

Submission status: Time Limit Exceeded

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

cw = len(x)-len(x.replace("1",""))

for i in range(n):
    ans = 0
    if x[i]=="1":
        nx = int(x, 2) - 2**(n-i-1)
    else:
        nx = int(x, 2) + 2**(n-i-1)
    while nx > 0:
        ans += 1
        cx = bin(nx)
        nx = nx%(len(cx)-len(cx.replace("1","")))
    print(ans)

Submission status: Time Limit Exceeded

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

def f(num):
    if num in dp:
        return dp[num]
    b = bin(num)
    popcount = b.count('1')
    if num % popcount == 0:
        dp[num] = 1
    else:
        dp[num] = 1 + f(num % popcount)

    return dp[num]

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = input()
B = X.count('1')
#print(B, 'B')

base_mod_1 = [1 for i in range(N)] # 2^i mod B+1
if B > 1:
  base_mod_2 = [1 for i in range(N)] # 2^i mod B-1

for i in range(1, N):
  base_mod_1[i] = (base_mod_1[i-1] * 2) % (B+1)
  if B > 1:
    base_mod_2[i] = (base_mod_2[i-1] * 2) % (B-1)

def num(A):
  b = 1
  r = 0
  for i in range(len(A)):
    r += b * int(A[-i-1])
    b *= 2
  return r

def f(n):
  global call
  call += 1
  bit = 0
  m = n
  while m > 0:
    if m % 2 == 1:
      bit += 1
    m //= 2
  next_n = n % bit
  if next_n > 0:
    f(next_n)

x = num(X)
#print(x, 'x')

for i in range(N):
  call = 0
  if X[i] == '0':
    y = (x + base_mod_1[-i-1]) % (B+1)
    R = B + 1
    call = 1
  else:
    if B > 1:
      y = (x - base_mod_2[-i-1]) % (B-1)
      R = B - 1
      call = 1
    else:
      y = 0
#  print(y, '+', call)
  if y > 0:
    f(y)
  print(call)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = input()
d = {}
onenumlist = []
onenum = 0
for i in range(N):
  if(X[i]=="1"):
    onenum += 1

for i in range(N):
  r = X[:i]
  l = X[i+1:]
  if(X[i]=="1"):
    tempx = r + "0" + l
    onenumlist.append(onenum - 1)
  else:
    tempx = r + "1" + l
    onenumlist.append(onenum + 1)
  tempx = int(tempx, 2)
  if(tempx not in d):
    ans = 0
    n = tempx
    pathlist = [tempx]
    while(n>0):
      if(n in d):
        ans += d[n]
        break
      else:
        n = n % bin(n).count("1")
        pathlist.append(n)
        ans += 1
    for j in range(len(pathlist)):
      if(pathlist[j] != 0 and pathlist[j] not in d):
        d[pathlist[j]] = ans - j
    print(ans)
  else:
    print(d[tempx])