Problem:


Score : 400 points

Problem Statement

Let \mathrm{popcount}(n) be the number of 1s in the binary representation of n.
For example, \mathrm{popcount}(3) = 2, \mathrm{popcount}(7) = 3, and \mathrm{popcount}(0) = 0.

Let f(n) be the number of times the following operation will be done when we repeat it until n becomes 0: "replace n with the remainder when n is divided by \mathrm{popcount}(n)." (It can be proved that, under the constraints of this problem, n always becomes 0 after a finite number of operations.)

For example, when n=7, it becomes 0 after two operations, as follows:

\mathrm{popcount}(7)=3, so we divide 7 by 3 and replace it with the remainder, 1.

\mathrm{popcount}(1)=1, so we divide 1 by 1 and replace it with the remainder, 0.

You are given an integer X with N digits in binary.
For each integer i such that 1 \leq i \leq N, let X_i be what X becomes when the i-th bit from the top is inverted.
Find f(X_1), f(X_2), \ldots, f(X_N).

Constraints

1 \leq N \leq 2 \times 10^5

X is an integer with N digits in binary, possibly with leading zeros.

Input

Input is given from Standard Input in the following format:

N
X

Output

Print N lines. The i-th line should contain the value f(X_i).

Sample Input 1

3
011

Sample Output 1

2
1
1

X_1 = 7, which will change as follows: 7 \rightarrow 1 \rightarrow 0. Thus, f(7) = 2.

X_2 = 1, which will change as follows: 1 \rightarrow 0. Thus, f(1) = 1.

X_3 = 2, which will change as follows: 2 \rightarrow 0. Thus, f(2) = 1.

Sample Input 2

23
00110111001011011001110

Sample Output 2

2
1
2
2
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
3



Sample input:
3
011


Sample output:
2
1
1

Submission status: Time Limit Exceeded

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

def calc(z):
    ans = 0
    z_10 = int(z,2)
    while z_10 != 0:
        z_10 = int(str(z),2)
        popcount = str(z).count("1")
        if popcount == 0:
            break
        z = format(z_10 % popcount,'b')
        ans += 1
    print(ans)
    
for n in range(N):
    X_1 = list(X)
    
    if X_1[n] == "0":
        X_1[n] = "1"
    else:
        X_1[n] = "0"
    Z = "".join(X_1)

    calc(Z)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
X = str(input())
X_ten = int("0b" + X, 0)
num_one_X = X.count("1")

for i in range(N):
    diff_num = 2 ** (N - i - 1)
    diff_sign = 1 if X[i] == "0" else -1
    temp_X_ten = X_ten + (diff_num * diff_sign)
    temp_num_one_X = num_one_X + diff_sign
    temp_ans = 0
    while(temp_X_ten > 0):
        temp_X_ten = temp_X_ten % temp_num_one_X
        temp_num_one_X = bin(temp_X_ten).count("1")
        temp_ans += 1
    print(temp_ans)

Submission status: Time Limit Exceeded

Solution code:
"""
    こんにちは。これはクシャルです
    
    Author : thekushalghosh (クシャル)
    Team   : CodeDiggers
 
    I prefer Python language over the C++ language :p :D
        
    Visit my website : thekushalghosh.github.io
"""
import sys,math,cmath,time,itertools
start_time = time.time()
##########################################################################
################# ---- THE ACTUAL CODE STARTS BELOW ---- #################
a = [0] * (100000 + 1)
for i in range(1,100000):
    q = bin(i).replace("0b","")
    a[i] = a[i % q.count("1")] + 1
    
def solve():
    global a
    n = inp()
    s = insr()
    q = list(s)
    w = q.count("1")
    for i in range(n):
        if q[i] == "0":
            q[i] = "1"
            w = w + 1
        else:
            q[i] = "0"
            w = w - 1
        qw = int("".join(q),2)
        if w == 0:
            print(0)
        else:
            print(a[qw % w] + 1)
        if q[i] == "0":
            q[i] = "1"
            w = w + 1
        else:
            q[i] = "0"
            w = w - 1
    
################## ---- THE ACTUAL CODE ENDS ABOVE ---- ##################
##########################################################################
 
def main():
    global tt
    if not ONLINE_JUDGE:
        sys.stdin = open("input.txt","r")
        sys.stdout = open("output.txt","w")
    t = 1
    for tt in range(t):
        solve()
    if not ONLINE_JUDGE:
        print("Time Elapsed :",time.time() - start_time,"seconds")
        sys.stdout.close()
    
#---------------------- USER DEFINED INPUT FUNCTIONS ----------------------#
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    return(input().strip())
def invr():
    return(map(int,input().split()))
 
#------------------ USER DEFINED PROGRAMMING FUNCTIONS ------------------#
def counter(a):
    q = [0] * max(a)
    for i in range(len(a)):
        q[a[i] - 1] = q[a[i] - 1] + 1
    return(q)

def counter_elements(a):
    q = dict()
    for i in range(len(a)):
        if a[i] not in q:
            q[a[i]] = 0
        q[a[i]] = q[a[i]] + 1
    return(q)

def string_counter(a):
    q = [0] * 26
    for i in range(len(a)):
        q[ord(a[i]) - 97] = q[ord(a[i]) - 97],1
    return(q)
 
def factors(n):
    q = []
    for i in range(1,int(n ** 0.5) + 1):
        if n % i == 0: q.append(i); q.append(n // i)
    return(list(sorted(list(set(q)))))
 
def prime_factors(n):
    q = []
    while n % 2 == 0: q.append(2); n = n // 2
    for i in range(3,int(n ** 0.5) + 1,2):
        while n % i == 0: q.append(i); n = n // i
    if n > 2: q.append(n)
    return(list(sorted(q)))

def transpose(a):
    n,m = len(a),len(a[0])
    b = [[0] * n for i in range(m)]
    for i in range(m): 
        for j in range(n): 
            b[i][j] = a[j][i]
    return(b)

#-----------------------------------------------------------------------#
        
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
    input = sys.stdin.readline
main()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())

def solve():
    N = 200000
    mem = [None]*(N+1)
    mem[0] = 0
    cnt = [0]
    for _ in range(18):
        cnt = [x+i for i in range(2) for x in cnt]
    def dfs(x):
        if mem[x] is not None:
            return mem[x]
        p = cnt[x]
        res = dfs(x%p)+1
        mem[x] = res
        return res

    ans = [dfs(i) for i in range(N+1)]
    n = I()
    x = list(map(int, input()))
    cnt_x = sum(x)
    s = 0
    rp = [0]*n
    cnt_p = cnt_x+1
    sp = 0
    p = 1
    for i in range(n)[::-1]:
        xi = x[i]
        if xi:
            rp[i] = p
            sp += p
        p <<= 1
        p %= cnt_p
    sp %= cnt_p
    if cnt_x > 1:
        cnt_m = cnt_x-1
        mp = [0]*n
        p = 1%cnt_m
        sm = 0
        for i in range(n)[::-1]:
            xi = x[i]
            if xi:
                mp[i] = p
                sm += p
            p <<= 1
            p %= cnt_m
        sm %= cnt_m
    p = 1<<(n-1)
    for i in range(n):
        if x[i]:
            k = cnt_x-1
            if k == 0:
                print(0)
            else:
                a = (sm-p)%k
                print(ans[a]+1)
        else:
            k = cnt_x+1
            a = (sp+p)%k
            print(ans[a]+1)
        p >>= 1
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

N = int(input())
X = input()[:-1][::-1]
origin = 0
for i in range(len(X)):
    origin += int(X[i]) * (2**i)

dic = defaultdict(int)

def calc_(n):
    global dic
    if n == 0:
        return 0
    if dic[n]>0:
        return dic[n]
    else:
        n_next = n % bin(n).count('1')
    temp = calc_(n_next)
    dic[n] = temp+1

    return temp + 1


for i in list(range(N))[::-1]:
    ans = 0
    if origin >> i & 1 == 1:
        val = origin - 2 ** i
    else:
        val = origin + 2 ** i

    print(calc_(val))

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]

    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[bits] = ans
    return bit[bits]


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
    for i in range(1, n + 1):
        if xs[i - 1] == "0":
            xs[i - 1] = "1"
            xi = int('0b' + "".join(xs), 0)
            bit[xi] = bit[x] + 1
            xs[i - 1] = "0"
        else:
            xs[i - 1] = "0"
            xi = int('0b' + "".join(xs), 0)
            bit[xi] = bit[x] - 1
            xs[i - 1] = "1"

        ans.append(rec(xi))

    for a in ans:
        print(a)


if __name__ == "__main__":
    submit()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

def f(x, cnt):
    res = 0
    while x > 0:
        res += 1
        x %= cnt
        cnt = 0
        tmp = x
        while tmp > 0:
            cnt += tmp % 2
            tmp //= 2
    return res

N = int(stdin.readline().rstrip())
X = str(stdin.readline().rstrip())
Y = 0
cnt = 0
pow_num = 1
for i in range(N - 1, -1, -1):
    if X[i] == '1':
        Y += pow_num
        cnt += 1
    pow_num *= 2
pow_num //= 2
for i in range(0, N):
    tmp = Y
    if X[i] == '1':
        tmp -= pow_num
        cnt -= 1
    else:
        tmp += pow_num
        cnt += 1
    print(f(tmp, cnt))
    if X[i] == '1':
        tmp += pow_num
        cnt += 1
    else:
        tmp -= pow_num
        cnt -= 1
    pow_num //= 2

Submission status: Time Limit Exceeded

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

for n in range(N):
  a = 0
  Y = X
  
  if Y[n]=="0":
    Y = Y[:n]+"1"+Y[n+1:]
  else:
    Y = Y[:n]+"0"+Y[n+1:]
  
  N = int(Y,2)
  
  while N!=0:
    a+=1
    N%=str(bin(N)).count("1")
  
  print(a)

Submission status: Time Limit Exceeded

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

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

for i in range(N):
    j = 0
    n = X[i]
    if n =="0":
        n="1"
    else:
        n="0"
    n = X[:i]+n+X[i+1:]

    while 1:
        no = int(n, 2)
        if no==0:
            break
        j+=1
        no%=popcount(n)
        n = format(no, "b")
    print(j)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

n = int(input())

x = input()

c = x.count('1')

for i in range(n):
    #print(int(str(x[:i]+str((int(x[i])+1)%2)+x[i+1:]),2))
    a = int(str(x[:i]+str((int(x[i])+1)%2)+x[i+1:]),2)
    b = 0
    if x[i] == '1':
        b = c-1
    else:
        b = c+1
    cnt = 0
    h = a
    while True:
        #print(a,h,b)
        if h==0:
            
            print(cnt)
            break
        h = h%b
        b = bin(h).count('1')
        cnt += 1

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(n+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):
    num=str(bin(n))
    return num.count('1')
xx=x.count('1')
xx2=int(x,2)
for i in range(n):
    if x[i]=='0':
        xxx=xx+1
        xxx2=xx2+2**(n-1-i)
    else:
        xxx=xx-1
        xxx2=xx2-2**(n-1-i)
    count=0

    while xxx2!=0:
        xxx2%=xxx
        xxx=popcount(xxx2)
        count+=1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
from collections import Counter

N=int(input())
X=[i for i in input()]

@lru_cache(maxsize=4*(10**5))
def _f(n):
    string=bin(n)
    popcount=string.count('1')
    return n%popcount

@lru_cache(maxsize=4*(10**5))
def f(n):
    if n==0:
        return 0
    else:
        return 1+f(_f(n))

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))
#%%code

def naive(a):
    if a==0:return 0
    b=a
    for i in range(1,1000000):
        t=bin(b).count("1") #popcount
        b%=t
        if b==0:
            return i
    assert b==0
def resolve():
    N,=pin()
    x=input()
    X=int(x,2)
    #print(+X)
    cnt=0
    for i in range(N):
        temp=X^(1<<(N-i-1))
    #    print(temp,";")
        print(naive(temp))
#%%submit!
resolve()

Submission status: Time Limit Exceeded

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

for i in range(n):
    y=x[:]
    if x[i]=="1":
        y=y[:i]+"0"+y[(i+1):]
    else:
        y=y[:i]+"1"+y[(i+1):]
    
    k=0
    if int(y)==0:
        print(0)
        continue
    while y!="0b0":
        m=y.count("1")
        y=str(bin(int(y,2)%m))
        k+=1

    print(k)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline

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

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

    x = int(X, 2)
    xc = X.count("1")
    for i in range(N):
        if X[i] == '0':
            print(popcount(x + (2 ** (N - i - 1)), xc + 1))
        else:
            print(popcount(x - (2 ** (N - i - 1)), xc - 1))



    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
ans=[0 for i in range(n)]
x=int(input(),2)
num=bin(x).count("1")
for i in range(n):
  if (x>>n-i-1)&1==0:
    popc=num+1
  else:
    popc=num-1
  y=x^(1<<(n-i-1))
  #print(i,y,popc)
  cnt=0
  while y>0:
    y=y%popc
    popc=bin(y).count("1")
    #print(i,y,popc)
    cnt+=1
  ans[i]=cnt
for i in ans:
  print(i)

Submission status: Time Limit Exceeded

Solution code:

def main():
  n = int(input())
  src = input()
  base_cnt = 0
  for bit in src:
    if bit == '1':
      base_cnt += 1
  base = int(src, 2)

  dp = [None] * n
  dp[0] = 0

  def popcount(num, cnt):
    if num < n and dp[num] is not None:
      return dp[num]

    if not cnt:
      cnt = 0
      for bit in format(num, 'b'):
        if bit == '1':
          cnt += 1

    res = 1 + popcount(num % cnt, None)
    if num < n:
      dp[num] = res

    return res

  for i in range(n - 1, -1, -1):
    num, cnt = (base + 2 ** i, base_cnt + 1) if src[n - i - 1] == '0' else (base - 2 ** i, base_cnt -1)
    print(popcount(num, cnt))


main()

Submission status: Time Limit Exceeded

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

def ans(X, first_popcount):
    if X == 0: return 0
    X = X % first_popcount
    return 1+ans(X, bin(X).count('1'))

N = int(input())-1
X = input()

popcount = X.count('1')
X_int = int(X, 2)

for i, x in enumerate(X):
    if x == '0':
        print(ans(X_int + 2**(N-i), popcount+1))    
    else:
        print(ans(X_int - 2**(N-i), popcount-1))

Submission status: Time Limit Exceeded

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


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


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:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    X = input().decode()
    X = list(X)

    def popcount(x):
        # 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

    # X = ['']*N
    # for i in range(N):
    #     X[i] = str(random.randint(0, 1))
    # print("".join(X))
    C = X.count("1")

    dp = [0]*N
    dp[0] = 0
    for i in range(1, N):
        k = i % popcount(i)
        dp[i] = 1 + dp[k]

    # def solve(n, d):

    for i in range(N):
        if X[i] == "0":
            X[i] = '1'
            print(dp[int((''.join(X)), 2) % (C+1)] + 1)
            #tmp = dp[int((''.join(X)), 2) % (C+1)] + 1
            X[i] = '0'
        else:
            if C == 1:
                print(0)
                continue
            X[i] = '0'
            print(dp[int((''.join(X)), 2) % (C-1)] + 1)
            #tmp = dp[int((''.join(X)), 2) % (C-1)] + 1
            X[i] = '1'


main()
# print(dp)

Submission status: Time Limit Exceeded

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

first_cnt = X.count("1")
for i in range(N):
    tmp = int(X,2)
    cnt = first_cnt
    if X[i] == "0":
        tmp += 2**(N-1-i)
        cnt += 1
    else:
        tmp -= 2**(N-1-i)
        cnt -= 1
    # print(tmp,cnt)
    if tmp == 0:
        print("0")
        continue
    tmp %= cnt

    if tmp == 0:
        print("1")
        continue
    ans = 1
    tmp = bin(tmp)[2:]
    while True:
        if tmp == "0":
            break
        cnt = tmp.count("1")
        tmp = int(tmp,2)%cnt
        tmp = bin(tmp)[2:]
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = input()
def popcount(n):
    tmp = list(format(n, 'b'))
    cnt = 0
    for i in range(len(tmp)):
        if tmp[i] == "1":
            cnt += 1
    return cnt
for i in range(n):
    if i==0:
        s = ""
        if x[0]=="0":
            s += "1"
        else:
            x += "0"
        s += x[1:n+1]
    else:
        s = ""
        s += x[0:i]
        if x[i] == "0":
            s += "1"
        else:
            s += "0"
        s += x[i+1:n+1]
    # print(s)
    num = int(s,2)
    ans = 0
    while num > 0:
        num = num % popcount(num)
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

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


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


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


n = int(input())
x = input()
xi = int(x, base=2)

init_popcount = x.count('1')

base = 2 ** (n - 1)
for i in range(n):
    if x[i] == '0':
        v = xi + base
        print(1 + f(v % (init_popcount + 1)))
    else:
        v = xi - base
        if v == 0:
            print(0)
        else:
            print(1 + f(v % (init_popcount - 1)))
    base //= 2

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

memp = {}
def popcount(n):
    global memp
    if n in memp:
        return memp[n]

    _n = n
    a = 0
    while n > 0:
         a += n & 1
         n >>= 1
         if n in memp:
             memp[_n] = memp[n] + a
             return memp[_n]
    memp[_n] = a
    return a

memf = {}
def f(x):
    global memf

    if x in memf:
        return memf[x]

    _x = x
    a = 0
    while x != 0:
        x = x % popcount(x)
        a += 1
        if x in memf:
            memf[_x] = memf[x] + a
            return memf[_x]

    memf[_x] = a
    return a

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

ans = []
for j in range(n):
    i = n - 1 - j
    a = str(1 - int(x[i]))
    b = x[:i] + a + x[i+1:]
    ans.append(f(int(b, 2)))
for j in range(n):
    i = n - 1 - j
    print(ans[i])

Submission status: Time Limit Exceeded

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


def popcount(n): 
    count = 0
    while (n): 
        n &= (n-1)  
        count+= 1
    return count

cache = {0:0}
def f(n):
    if n not in cache:
        start = n
        t = popcount(n)
        n%=t
        ans = f(n)
        ans+=1
        cache[start] = ans
    else:
        # print("Here")
        ans = cache[n]
    return ans

# t2 = popcount(x)
for i in range(n-1,-1,-1):
    temp  = x^(1<<i)
    print(f(temp))
# print(cache)

Submission status: Time Limit Exceeded

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

d = dict()
def solve(a):
    if a in d.keys():
        return d[a]
    pc = bin(a).count('1')
    if pc == 0:
        return 0
    elif pc == 1:
        return 1
    ans = solve(a % pc) + 1
    d[a] = ans
    return ans
        
for i in reversed(range(n)):
    a = 1 << i ^ x
    print(solve(a))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = int(input(),2)
for i in range(1,N+1):
    xi = X ^ (1<<(N-i))
    ans = 0
    while xi > 0:
        xi %= (str(bin(xi)).count('1'))
        ans += 1
    print(ans)
    ans = 0

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = input()
for i in range(N):
    if X[i] == '0':
        b = int(X, 2)
        b += 2**(N-i-1)
    else:
        b = int(X, 2)
        b -= 2**(N-i-1)
    a = bin(b)
    pop = str(a).count('1')
    c = 0
    while b != 0:
        b = b%pop
        a = bin(b)
        pop = str(a).count('1')
        c += 1
    print(c)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

import copy

# 実行環境(0:vscode, 1:atcoder)
MODE = 1

# 入力の次元
DIMENSION = 1

# int型に変換
INT_TYPE = 0

if not (MODE):
    with open("input.txt", "r") as f:
        s = f.read()
else:
    s = sys.stdin.read()

if DIMENSION == 0:
    if INT_TYPE == 1:
        s = int(s)
elif DIMENSION == 1:
    if INT_TYPE == 0:
        s = s.split()
    elif INT_TYPE == 1:
        s = [int(x) for x in s.split()]
elif DIMENSION == 2:
    if INT_TYPE == 0:
        s = [x.split() for x in s.splitlines()]
    elif INT_TYPE == 1:
        s = [[int(y) for y in x.split()] for x in s.splitlines()]

N = int(s[0])
X = s[1]
X = list(X)

# print(int('10100', 2))
# print(bin(15)[2:].count("1"))
cnt = [0 for _ in range(N)]

for i in range(N):
    X_tmp = copy.copy(X)
    if X_tmp[i] == "0":
        X_tmp[i] = "1"
    else:
        X_tmp[i] = "0"
    X_tmp = "".join(X_tmp)
    tmp = int(X_tmp, 2)
    while tmp > 0:
        tmp = tmp % bin(tmp)[2:].count("1")
        cnt[i] += 1
for i in range(N):
    print(cnt[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)

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


for i in range(N):
    if bin_X[i] == "0":
        bin_new = bin_X[:i] + "1" + bin_X[i+1:]
        pop_new = pop + 1
    else:
        bin_new = bin_X[:i] + "0" + bin_X[i+1:]
        pop_new = pop - 1
    #print(bin_new)
    new = int(bin_new, 2)
    #print(new)
    if new == 0:
        ans = 0
    else:
        ans = 1
        new = new % pop_new
        while True:
            if new == 0:
                break
            ans += 1
            new = new % pop_list[new]
        
    print(ans)

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)
xmax = 0
for j in range(N):
  xmax += 2**(N-j-1)

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:
    xint = xint % popcount(xint)
    c += 1
  
  print(c)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=str(input())
s=list(s)
import copy
for i in range(len(s)):
  cnt=0
  st=copy.copy(s)
  if s[i]=="1":
    st[i]="0"
  else:
    st[i]="1"
  while True:
    temp=0
    t=st.count("1")
    if t==0:
      print(cnt)
      break
    for j in range(len(st)):
      if st[j]=="1":
        temp=temp+2**(len(st)-1-j)
    temp=temp%t
    st=list(bin(temp))
    del st[0]
    del st[0]
    cnt=cnt+1

Submission status: Time Limit Exceeded

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

def popcount(v):
    return bin(v)[2:].count('1')

def func(v):
    cnt = 0
    while v != 0:
        v = v % popcount(v)
        cnt += 1
    return cnt

for i in range(n):
    s = x
    if s[i] == '0':
        s = s[:i] + '1' + s[i+1:]
    else:
        s = s[:i] + '0' + s[i+1:]
    v = int(s, 2)
    print(func(v))

Submission status: Time Limit Exceeded

Solution code:
import sys

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

if __name__ == "__main__":
    N = int(sys.stdin.readline())
    X = sys.stdin.readline()
    X = int(X, 2)
    for i in reversed(range(N)):
        num = int(X ^ (2**i))
        count = 0
        while num != 0:
            num = num % popcount(num)
            count += 1
        print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict

N = int(input())
X = input()
x = []
for i in range(N):
    x.append(X[i])

fn = defaultdict(int)
def f(n):
    init = n
    cnt = 0
    while n != 0:
        if fn[n]:
            fn[init] = cnt + fn[n]
            return fn[init]
        n %= Counter(bin(n))['1']
        cnt += 1
    fn[init] = cnt
    return cnt

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

X = input()

pop_X = X.count('1')


for i in range(N):
    X_list = list(X)
    X_list[i] = str(int(X_list[i]) * (-1) + 1)
    X_a = ''.join(X_list)
    
    pop_X_a = pop_X + 2 * int(X_list[i]) -1
    pop_n = pop_X_a
    
    n = int(X_a, 2)
    
    count = 0
    
    while n != 0:
        
        n = n %  pop_n
        
        pop_n = bin(n).count('1')
        
        count += 1
    
    print(count)

Submission status: Time Limit Exceeded

Solution code:
def popcount(n):
    if n == 0:
        return 0
    n2 = n
    diver = 0
    while n2 != 0:
        if n2 % 2 == 1:
            diver += 1
        n2 = n2 // 2
    return diver


N = int(input())
X_in = input()
X_len = len(X_in)
X_d_r = list(X_in.lstrip('0'))[::-1]
X = 0
for i, c in enumerate(X_d_r):
    if c == '1':
        X += (1 << i)
# print('X in dec is ', X)
n_one = X_in.count('1')
for i in range(X_len-1, -1, -1):
    # print(i, X_in[-i-1])
    if X_in[-i-1] == '0':
        X_tmp = X + (1 << i)
        p = 1
    else:
        X_tmp = X - (1 << i)
        p = -1
    # print('x_tmp', X_tmp)
    if n_one + p == 0:
        print('0')
        continue
    X_tmp = X_tmp % (n_one + p)
    ans = 1
    while X_tmp != 0:
        X_tmp = X_tmp % popcount(X_tmp)
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
X=input()
x=[i for i in X]
for i in range(n):
    if x[i]=='0':
        x[i]='1'
    else:
        x[i]='0'
    num=int("".join(x),2)
    waru=x.count('1')
    count=0
    while num>0:
        num%=waru
        waru=str(bin(num)).count('1')
        count+=1
    print(count)
    if x[i]=='0':
        x[i]='1'
    else:
        x[i]='0'

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
x=input()
num=0
n=0
ans=[]
def twice(a):
    num=a
    b=0
    while a>0:
        b+=a%2
        a=a//2
    num=num%b
    return num
for i in range(N):
    num+=2**(N-1-i)*int(x[i])
    if x[i]=="1":
        n+=1
for i in range(N):
    Ans=0
    if x[i]=="0":
        Num=1+n
        A=2**(N-i-1)+num
        if Num==0:
            Ans=0
        else:
            a=A%Num
            Ans+=1
            while a>0:
                a=twice(a)
                Ans+=1
    else:
        Num=n-1
        A=num-2**(N-i-1)
        if Num==0:
            Ans=0
        else:
            a=A%Num
            Ans+=1
            while a>0:
                a=twice(a)
                Ans+=1
    ans.append(Ans)
for i in range(N):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))

n = int(input())
x = input()
s = ''
ans = [0 for _ in range(2**n + 1)]
pop = 0
for i in x:
    if i == '1': pop += 1

for i in range(n-1, -1, -1):
    if x[i] == '0':
        s = x[:i] + '1' + x[i+1:]
        pc = pop + 1
    else:
        s = x[:i] + '0' + x[i+1:]
        pc = pop - 1
    num = int(s, 2)
    cnt = 0
    while True:
        if num == 0:
            ans[int(s, 2)] = cnt
            break
        if ans[num] > 0:
            ans[int(s, 2)] = cnt + ans[num]
            break
        num = (num%pc)
        cnt += 1
        t = str(bin(num))
        pc = 0
        for j in t:
            if j == '1': pc += 1
for i in range(n):
    if x[i] == '0':
        s = x[:i] + '1' + x[i+1:]
    else:
        s = x[:i] + '0' + x[i+1:]
    print(ans[int(s, 2)])

Submission status: Time Limit Exceeded

Solution code:
def f(n):
    if n == 0:
        return 0
    else:
        count = 0
        while count < 10:
            count += 1
            r = (n % str(bin(n)).count("1"))
            if r != 0:
                n = r
            else:
                return count
            
N = int(input())
X = int(input(),2)

for i in range(N):
    print(f(X ^ (1 << (N - i - 1))))