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 collections import defaultdict
n = int(input())
x = input()
# compute initial hamming
d = defaultdict()
d[0] = 0

def ham(n):
    c = 0
    while n:
        c += 1
        n &= n - 1
    return c

initial_ham = 0
for i in x:
    if i == '1':
        initial_ham += 1
# also compute initial evaluation
# work out the value up to initial_ham + 1

for i in range(initial_ham + 2):
    counter = 0
    fix_i = i
    cur_list = [i]
    while i not in d:
        cur_weight = ham(i)
        i %= cur_weight
        cur_list.append(i)
        counter += 1
    m = len(cur_list)
    m -= 1
    counter = 1
    for i in range(m-1,-1,-1):
        d[cur_list[i]] = d[cur_list[-1]] + counter
        counter += 1

initial_val = int(x, 2)
tmp = 1<<n
for i in range(n):
    tmp //= 2
    if x[i] == '0':
        cur_val = initial_val + tmp
        cur_ham = initial_ham + 1
    else:
        cur_val = initial_val - tmp
        cur_ham = initial_ham - 1
    
    # the modulo is always initial_ham +- 1
    cur_cur_val = cur_val
    cur_list = [cur_val]
    while cur_val not in d:
        cur_val %= cur_ham
        cur_ham = ham(cur_val)
        cur_list.append(cur_val)
    # now i need to process the list
    # now cur_val is in d
    m = len(cur_list)
    m -= 1
    counter = 1
    for i in range(m-1,-1,-1):
        d[cur_list[i]] = d[cur_val] + counter
        counter += 1
    print(d[cur_list[0]])

Submission status: Time Limit Exceeded

Solution code:
n= int(input())


ans_count={}
for i in range(1,n+1):
    b = bin(i)
    b=list(b)
    a = b.count("1")
    f = i%a
    if f == 0:
        ans_count[i]=1
    else:
        ans_count[i] = ans_count[f]+1


inp = input()
x = list(inp)

org = int(inp, 2)
if "1" in x:      
    l = x.count("1")
else:
    l = 0

ans_count[0]=0
d= ans_count



for i in range(n):
    a = x[i]
#     print(0)
    if a=="0":
        N = org+(2**(n-i-1))
        m= N%(l+1)
        print(d[m]+1)
    else:
        if l ==1:
            print(0)
        else:
            N = org-(2**(n-i-1))
            m=N%(l-1)
            print(d[m]+1)

Submission status: Time Limit Exceeded

Solution code:
def i_input(): return int(input())
def s_input(): return input()


def f(num, one_count):
    ans = 0

    while num != 0:
        if ans == 0:
            pop_count = one_count
        else:
            pop_count = bin(num).count('1')
        num %= pop_count
        ans += 1
        
    return ans

def main():
    n = i_input()
    x = s_input()

    x10 = int(x, 2)
    one_count = x.count('1')

    for i in range(n):
        if x[i] == '0':
            num = x10 + pow(2, n-1-i)
            print(f(num, one_count+1))
        else:
            num = x10 - pow(2, n-1-i)
            print(f(num, one_count-1))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

# メイン処理
def popcount(n: int) -> int:
    return bin(n).count("1")

d = {}
for n in range(1, N + 1):
    x = X ^ (1 << (N - n))
    l = [x]
    c = 0
    while x != 0:
        if x in d.keys():
            c += d[x]
            break
        x %= popcount(x)
        c += 1
        l.append(x)
    for i in range(len(l)):
        d[l[i]] = c - i
    print(c)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from collections import defaultdict, deque


def popcount(x):
    count = 0
    for i in range(int.bit_length(x)):
        count += (x >> i) & 1
    return count


def solve(*args: str) -> str:
    n = int(args[0])
    x = int(args[1], 2)

    ret = []
    dp = defaultdict(int)
    for i in range(n):
        m = x ^ (1 << (n-i-1))
        count = 0
        deq = deque()
        while m:
            deq.append(m)
            if 0 < dp[m]:
                count += dp[m]
                break

            m = m % popcount(m)
            count += 1
        ret.append(str(count))

        while deq:
            dp[deq.popleft()] = count
            count -= 1

    return '\n'.join(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Time Limit Exceeded

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

def main():
    n = int(input())
    x = eval("0b" + input())
    
    def toggl_ith_bit(num, i):
        return num ^ (1 << i)
    
    def popcount(num):
        s = 0
        b = num
        while b != 0:
            s += (b & 1 > 0)
            b >>= 1
        return s
    
    x_count = popcount(x)
    
    for i in range(n - 1, -1, -1):
        xi = toggl_ith_bit(x, i)
        if xi == 0:
            print(0)
            continue
        xi_count = x_count + 1 if (xi & (1 << i)) else x_count - 1
        cnt = 1
        xi %= xi_count
        while xi != 0:
            cnt += 1
            xi %= popcount(xi)
        print(cnt)

if __name__ == '__main__':
    main()

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
    for i, x in enumerate(X[::-1]):
        d2[x] = i+ k
    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 = input()
for i in range(N):
    str_x = X[:i] + str(1 - int(X[i])) + X[i+1:]
    x = sum(2 ** (len(str_x) - 1 - i) for i, _x in enumerate(str_x) if _x == '1')
    ans = 0
    while x > 0:
        popcount = 0
        n = bin(x)
        for _n in n:
            if _n == '1':
                popcount += 1
        x = x % popcount
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

def ppp(x):
    s = format(x, 'b')
    return s.count('1')
   

n = int(input())
x = input()
f_li = [0]
for i in range(1, x.count('1')+1):
    i = i % ppp(i)
    f_li.append(f_li[i]+1)

            

for i in range(n):
    tmp = list(x)
    tmp[i] = str((int(x[i])+1)%2)
    xi = int(''.join(tmp) , 2)
    f_li.append(xi)
    if xi==0:
        print(0)
    else:
        xi = xi%ppp(xi)
        if xi==0:
            print(1)
        else:
            print(f_li[xi]+1)

Submission status: Time Limit Exceeded

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

from functools import lru_cache


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


@lru_cache(maxsize=100000000000)
def mod(a, b):
    return a % b

@lru_cache(maxsize=1000000000000000)
def f(num):
    if num == 0:
        return 0
    else:
        # if not cache.get(num % pc, None) is None:
        #     return cache[num % pc]
        # pc = popcount('{:b}'.format(num))
        pc = popcount(''.join(sorted('{:b}'.format(num))))
        ret = 1 + f(mod(num, pc))
        # cache[num % pc] = ret
        return ret


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


answers = {}

for i in range(1, N+1):
    bits = reverse_bit(X, i)
    # pc = popcount(bits)
    # print(f'# {bits} {convert(bits)} {pc}')
    x = convert(bits)
    if not answers.get(x, None) is None:
        print(answers[x])
        continue
    ret = f(x)
    answers[x] = ret
    print(ret)

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):
  result=0
  for i in range(Y):
    result=result+Y%2
    Y=Y//2
  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:
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
        nn = int(ns, 2)
        if n in ans:
            print(ans[n])
        else:
            print(f(nn))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    X = input()
    MOD = 0
    for elem in X:
        if elem == '1':
            MOD += 1
    if MOD == 0:
        print("1" + "\n1" * (N-1))
        return 0
    if MOD == 1 and X[-1] == '1':
        print("2\n" * (N-1) + "0")
        return 0
    if MOD == 1 and X[-1] == '0':
        ans = ''
        for i in range(N):
            if X[i] == '1':
                ans += '0'
            elif i != N-1:
                ans += '1'
            else:
                ans += '2'
            if i != N-1:
                ans += '\n'
        print(ans)
        return 0
    MODP1 = MOD + 1
    MODM1 = MOD - 1
    POWEROFTWOP1 = [0] * N
    POWEROFTWOM1 = [0] * N
    POWEROFTWOP1[0] = 1
    POWEROFTWOM1[0] = 1
    for i in range(1,N):
        POWEROFTWOP1[i] = (POWEROFTWOP1[i-1] * 2) % MODP1
        POWEROFTWOM1[i] = (POWEROFTWOM1[i-1] * 2) % MODM1
    xMODP1 = 0
    xMODM1 = 0
    for i in range(N):
        if X[i] == '1':
            xMODP1 += POWEROFTWOP1[N - i - 1]
            xMODM1 += POWEROFTWOM1[N - i - 1]
    xMODP1 %= MODP1
    xMODM1 %= MODM1
    ans = ""
    for i in range(N):
        if X[i] == '0':
            anscur = xMODP1
            anscur += POWEROFTWOP1[N - i - 1]
            anscur %= MODP1
        if X[i] == '1':
            anscur = xMODM1
            anscur -= POWEROFTWOM1[N - i - 1]
            anscur %= MODM1
        cnt = 1
        while anscur != 0:
            ans2 = bin(anscur)[2:]
            oneCount = sum(map(lambda x: x == '1',ans2))
            anscur %= oneCount
            cnt += 1
        ans += str(cnt)
        if i != N-1:
            ans += '\n'
    print(ans)
                    
main()

Submission status: Time Limit Exceeded

Solution code:
import copy
from functools import lru_cache
n = int(input())
x = list(input())

@lru_cache(maxsize=1000000)
def saiki(i, count):
    if i == 0:
        return count
    else:
        count_saiki = count
        i_bin = str(bin(i))
        i_bin_one = i_bin.count("1")
        ni = i % i_bin_one
        count_saiki += 1
        return saiki(ni, count_saiki)

x_lis = []
for i in range(n):
    x_copy = copy.copy(x)
    if x[i] == "1":
        x_copy[i] = "0"
    else:
        x_copy[i] = "1"
    x_lis.append("".join(x_copy))

for xi in x_lis:
    xi_int = int(xi, 2)
    count = 0
    print(saiki(xi_int, count))

Submission status: Time Limit Exceeded

Solution code:
pcmap={}
answermap={}

def popcount(a):
    if a in pcmap.keys():
        return pcmap[a]
    else:
        s = str(bin(a))
        pcmap[a] = s.count('1')
        return pcmap[a]

def func(a):
    cnt=0
    while True:
        a2=popcount(a)
        if a2==0:
            break
        a %= a2
        cnt+=1
    return cnt

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

for i in range(n):
    x2 = list(x)
    if x[i] =='0':
        x2[i] = '1'
    else:
        x2[i] = '0'
    x3 = int("".join(x2),2)
    if x3 in answermap.keys():
        print(answermap[x3])
    else:
        ans = func(x3)
        answermap[x3] = ans
        print(ans)

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):
    if Y[i]=="0":
        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:
#!/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
from collections import defaultdict

def resolve():
    N,=pin()
    x=input()
    X=int(x,2)
    #print(+X)
    cnt=0
    memo=defaultdict(int)
    memo[0]=0
    for i in range(N):
        temp=X^(1<<(N-i-1))
        ans=[]
    #    print(temp,"::")
        for i in range(100000):
            ans.append(temp)
            
            if temp ==0:
                M=0
            #    print(ans)
                for a in range(len(ans)):
                    memo[ans[-a]]=a+M-1

                print(M+i)
                break
        
            elif temp in memo:
                M=memo[temp]
                
                for a in range(len(ans)):
                    memo[ans[-a]]=a+M-1

                print(M+i)
                break
            
            s=bin(temp).count("1")
            temp%=s
            
#%%submit!
resolve()

Submission status: Time Limit Exceeded

Solution code:
import math

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

N = 2 * 10 ** 5

lst = [0 for _ in range(N)]

def bit_ans(X, bit):
  if X == 1:
    return 1
  elif X == 0:
    return 0
  
  param = X
  counter = 0

  if X > N:
    counter += 1
    param = X % bit

  
  while True:
    if param == 0:
      break

    param = param % lst[param-1]
    counter += 1
  return counter


for i in range(N):
  k = i+1
  s = bin(k)
  lst[i] = s[2:].count('1')




val = int(x,2)

search_lst = []
bit_count = x.count('1')
for i in range(n):
  if x[i] == '0':

    search_lst.append((val + 2**(n-i-1), bit_count+1))
  else:
    search_lst.append((val - 2**(n-i-1), bit_count-1))

for i in search_lst:
  print(bit_ans(i[0], i[1]))

Submission status: Time Limit Exceeded

Solution code:
def main():
    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 = list(input())
y = int(''.join(x), 2)

memo = [0]


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


for i in range(1, n):
    tmp = i % popcount(i)
    memo.append(memo[tmp] + 1)

B = 2**(n-1)
for d in x:
    tmp = y
    if d == '0':
        tmp += B
    else:
        tmp -= B

    tmp = int(tmp)

    if tmp == 0:
        print(0)
        B = B // 2
        continue

    tmp = tmp % popcount(tmp)
    print(memo[tmp] + 1)
    B = B // 2

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=input()
xint=int(x,2)
def func(a):
  r=0
  while a!=0:
    a%=bin(a).count('1')
    r+=1
  return r
for i in range(n):
  if x[i]=='1':
    print(func(xint-2**(n-i-1)))
  else:
    print(func(xint+2**(n-i-1)))

Submission status: Time Limit Exceeded

Solution code:
def solve(N,x):
    ans = []
    cnt = 0
    for i in range(N):
        if 2**i & x != 0:
            cnt += 1

    for i in range(N):
        x ^= 2**(N-i-1)
        ans.append(cal(x,0))
        x ^= 2**(N-i-1)
    return ans

def cal(x,rec):
    cnt,dig = 0,0
    while 2**dig <= x:
        if 2**dig & x != 0:
            cnt += 1
        dig += 1

    if cnt == 0:
        return rec
    else:
        amari = 0
        for i in range(dig):
            if x & 2**i != 0:
                amari += pow(2,i,cnt)
                amari %= cnt
        return cal(amari,rec+1)

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

    x = 0
    for i in range(N):
        if X[i] == "1":
            x += pow(2,N-i-1)

    ans = solve(N,x)
    for i in range(N):
        print(ans[i])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def popcount(n):
    return bin(n).count("1")
def func(n):
    c = 0
    while n != 0:
        n= n % popcount(n)
        c += 1
    return c


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

d = {"0": "1", "1": "0"}
p = 0
for i in range(n):
    pp = list(x)
    pp[i] = d[pp[i]]
    p = "".join(pp)
    print(func(int(p, 2)))

Submission status: Time Limit Exceeded

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

import io
import sys
import math

def format_multi_line_answer(lst):
    ans = ""
    for y in lst:
        ans += f"{y}\n"
    return ans

def popcount(n):
    s = 0
    while n > 0:
        if n&1==1:
            s+=1
        n>>=1
    return s

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

def reverse_one_bit(x,x_len,i):
    ii = x_len - i
    
    return x ^ 1<<ii

def solve(n,x,x_len):
    # implement process
    ans_l = []
    for i in range(1,n+1):
        xi = reverse_one_bit(x,x_len,i)
        ans_l.append(f(xi))
    return format_multi_line_answer(ans_l)

def main():
    # input
    n = int(input())
    xs = input()
    x_len = len(xs)
    x = int(xs,2)
    
    # process
    ans = str( solve(n,x,x_len) )
    
    # output
    print(ans)
    return ans
        
### DEBUG I/O ###
_DEB = 0   # 1:ON / 0:OFF

_INPUT = """\
23
00110111001011011001110
"""
_EXPECTED = """\
2
1
2
2
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
3

"""

def logd(str):
    """usage:
    if _DEB: logd(f"{str}")
    """
    if _DEB: print(f"[deb] {str}")

### MAIN ###
if __name__ == "__main__":
    if _DEB:
        sys.stdin = io.StringIO(_INPUT)
        print("!! Debug Mode !!")

    ans = main()

    if _DEB:
        print()
        if _EXPECTED.strip() == ans.strip(): print("!! Success !!")
        else: print(f"!! Failed... !!\nANSWER:   {ans}\nExpected: {_EXPECTED}")

Submission status: Time Limit Exceeded

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


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

dp=[-1]*(n+1)

dp[0]=0
dp[1]=1
co=[-1]*(n+1)

def fun(num,step):
    num2=num%sum(list(map(int,bin(num)[2:])))
    if dp[num2]!=-1:
        dp[num]=dp[num2]+step
    else:
        fun(num2,step+1)

for i in range(2,n+1):
    fun(i,1)

num1=''.join(x)
num2=int(num1,2)
su = sum(list(map(int,x)))

for i in range(n):
    num4=num2
    su2=su
    if x[i]=='1':
        num4-=2**(n-1-i)
        su2-=1
    else:
        num4+=2**(n-1-i)
        su2+=1
    if su2 == 0:
        print('0')
    elif num4<=n:
        print(dp[num4])
    else:
        num3=num4%su2
        print(dp[num3]+1)

Submission status: Time Limit Exceeded

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

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

for i in range(N):
  if(X[i]=="0"):
    k = x + 2**(N-i-1) 
  else:
    k = x - 2**(N-i-1)
  print(func(k))

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:
from sys import stdin
N = int(stdin.readline().rstrip())
X = (stdin.readline().rstrip())
cnt = X.count("1")

X = list(X)

f = [0]*(2*10**5+1)
for i in range(1,2*10**5+1):
    f[i] = (i%bin(i).count("1"))

for i in range(1,N+1):
    tmp = X[:]
    if tmp[i-1] == "0":
        tmp[i-1] = "1"
        cnt_t = cnt + 1
    else:
        tmp[i-1] = "0"
        cnt_t = cnt - 1
    
    num = int("".join(tmp),2)
    if num == 0:
        print(0)
    else:
        amari = num % cnt_t
        ans = 1
        while amari != 0:
            amari = f[amari]
            ans += 1
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = list(input())
import copy
for i in range(N):
    n = copy.copy(X)
    if n[i] == '1':
        n[i] = '0'
    else:
        n[i] = '1'
    n = ''.join(n)
    M = int(n, 2)
    ans = 0
    while M > 0:
        ans += 1
        a = n.count('1')
        M %= a
        n = bin(M)
    print(ans)

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
    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:
import copy

def main():
    n = int(input())
    _X = input()
    X = [int(x) for x in _X]
    # print('_X', _X)
    # print('X', X)

    def fukugen(x):
        return int(x, 2)
    

    def f(x):
        cnt = 0
        while x > 0:
            y = bin(x).count('1')
            x = x % y
            cnt += 1
            if x != 0:
                f(x)
        return cnt
     
    cx = copy.deepcopy(X)
    for i in range(n):
        if X[i] == 0:
            cx[i] = 1
        else:
            cx[i] = 0
        # print(cx)
        hoge = map(str, cx)
        _X = ''.join(hoge)
        f_cx = fukugen(_X)
        # print(f_cx)
        ans = f(f_cx)
        print(ans)
        cx = copy.deepcopy(X)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = int(input(), 2)
me = {}
def popcount(n):
    if n in me:
        return me[n]
    me[n] = bin(n).count('1')
    return bin(n).count('1')
memo = {1:1}
def f_count(n):
    co_n = n
    ans = 0
    while n != 0:
        if n in memo:
            ans += memo[n]
            memo[co_n] = ans
            return ans
        n %= popcount(n)
        ans += 1
    memo[co_n] = ans
    return ans

for i in range(N):
    x = X
    if X >> (N-1 -i) & 1:
        x -= 2**(N-1 -i)
    else:
        x += 2**(N-1 -i)
    print(f_count(x))

Submission status: Time Limit Exceeded

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

#N = 23
#X = '00110111001011011001110'

mem_func = [-1 for i in range(2**N)]

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

def func(n, l):
    if mem_func[n] != -1:
        return mem_func[n] + l
    if n == 0: return l
    n = n % popcount(n)
    mem_func[n] = func(n, l)
    return func(n, l+1)

list_X = list(X)
for i in range(N):
    x = copy.copy(list_X)
    if x[i] == '0':
        x[i] = '1'
    else:
        x[i] = '0'
    z = int(''.join(x), 2)
    mem_func[z] = func(z, 0)
    print(mem_func[z])

Submission status: Time Limit Exceeded

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


def f(A):
    ans = 0
    n = int(A, 2)
    while n != 0:
        pc = bin(n).count('1')
        n = n % pc
        ans += 1
    print(ans)


N = int(input())
A = int(input().rstrip(), 2)
for i in range(N)[::-1]:
    AA = bin(A ^ (1 << i))
    f(AA)

Submission status: Time Limit Exceeded

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

d = {}
def popcount(s):
    if not s in d:
        d[s] = s.count('1')
    return d[s]

one = popcount(X)
K = int(X, 2)
for i in range(N):
    pop = one
    if X[i] == '1':
        pop -= 1
    else:
        pop += 1

    k = K
    bit = N-i-1
    if X[i] == '1':
        k -= 2**bit
    else:
        k += 2**bit
    ans = 0
    while k > 0:
        k %= pop
        pop = popcount(bin(k)[2:])
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

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

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

def toggl_ith_bit(num, i):
    return num ^ (1 << i)

def popcount(num):
    s = 0
    b = num
    while b != 0:
        s += (b & 1 > 0)
        b >>= 1
    return s

x_count = popcount(x)

for i in range(n - 1, -1, -1):
    xi = toggl_ith_bit(x, i)
    if xi == 0:
        print(0)
        continue
    xi_count = x_count + 1 if (xi & (1 << i)) else x_count - 1
    cnt = 1
    xi %= xi_count
    while xi != 0:
        cnt += 1
        xi %= popcount(xi)
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

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

ppc = {}

def popcount(n):    
  if n in ppc:
    return ppc[n]  
  if n == 0:
    return 0
  b = bin(n).count('1')  
  tmp = n%b
  ppc[n] = popcount(tmp) + 1
  return ppc[n]

bit = int('0b'+x,0)
for i in range(n,0,-1):      
  print(popcount(bit ^ (1 << (i-1))))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
X=input()
f={}
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)
    if y in f:
        print(f[y])
    else:
        ans = 0
        while y!=0:
            y = y % bin(y).count('1')
            ans += 1
        print(ans)
        f[y]=ans

Submission status: Time Limit Exceeded

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

def calc(num, cnt, ans):
  ans += 1
  if cnt == 0:
    return ans
  mod = num % cnt
  if mod == 0:
    return ans
  else:
    return(calc(mod, bin(mod).count('1'), ans))

n = int(X, 2)
c = X.count('1')
a = n % (c+1)
for i in range(1, N+1):
  if X[i-1] == '0':
    print(calc(a+2**(N-i), c+1, 0))
  else:
    if c == 1:
      print(0)
    else:
      print(calc(n-2**(N-i), c-1, 0))

Submission status: Time Limit Exceeded

Solution code:
import copy
import numpy as np

def f(X):
    count = 0
    while np.sum(X)>0:
        X = popcount(X)
        count += 1
    return count

def popcount(X):
    a = np.sum(X)
    x_10 = 0
    for i in range(len(X)):
        x_10 += X[-(i+1)]*2**i
    n = x_10 % a
    k=2
    bi=''
    while n!=0:
        bi+=str(n%abs(k))
        if k<0:n=-(-n//k)
        else:n=n//k
    bi[::-1]
    return list(map(int,list(bi[::-1])))


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

for i in range(N):
    X_i = copy.copy(X)
    if X_i[i] == 0:
        X_i[i] =1
    else:
        X_i[i] = 0
    print(f(X_i))

Submission status: Time Limit Exceeded

Solution code:
def count1(n):
    nx=bin(n)
    return nx.count('1')

N=int(input())
X=input()
'''for i in range(N):
    Ni2=X
    if X[i]=='0':
        Ni2=X[:i]+'1'+X[(i+1):] #文字列は変更できない
    else:
        Ni2=X[:i]+'0'+X[(i+1):]
    Ni=int(Ni2,2)
    ans=0
    #print(Ni)
    while Ni!=0:
        Ni=Ni%count1(Ni)
        ans+=1
    print(ans)'''

Nx=int(X,2)
for i in range(N):
    if X[i]=='0':
        Ni=Nx+2**(len(X)-i-1) #文字列は変更できない
    else:
        Ni=Nx-2**(len(X)-i-1)
    ans=0
    #print(Ni)
    while Ni!=0:
        Ni=Ni%count1(Ni)
        ans+=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=input()
clist=[0,1,1,2,1,2,1,2,1,2,1,2,1,2,2,3]
for i in range(n):
    a=x
    if a[i]=="0":
        a=a[:i] + "1" + a[i+1:]
    else:
         a=a[:i] + "0" + a[i+1:]
    a2=int(a,2)
    c=0
    b=a2
    if a2==0:
        print(0)
        continue
    while b!=0:
        if b<=15:
            c+=clist[b]
            break
        pb=list(bin(b)).count("1")
        b=b%pb
        c+=1
    print(c)