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:
def m():
    N = int(input())
    X = input()
    R = list(reversed(X))

    memo = [0] * (N+2)
    for i in range(1, N+2):
        p = 0
        k = i
        while k != 0:
            if k % 2 == 1:
                p+=1
            k //= 2
        memo[i] = p

    def f(n):
        r = 0
        while n != 0:
            n = n % memo[n]
            r += 1
        return r

    total = 0
    for i in range(N):
        total += int(R[i]) * pow(2, i)

    base = X.count('1')
    for i in range(N):
        ans = 0
        if X[i] == '1':
            tmp = total - pow(2, N - 1 - i)
            if (base-1) == 0:
                print(0)
                continue
            tmp %= (base - 1)
            ans = f(tmp) + 1
        else:
            tmp = total + pow(2, N - 1 - i)
            tmp %= (base + 1)
            ans = f(tmp) + 1
        print(ans)


m()

Submission status: Time Limit Exceeded

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

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

def fcount(x):
    c = 0
    while x != 0:
        x = x % popcount(x)
        c = c + 1
    return c

for i in range(n):
    t = x
    if t[i] == '1':
        t = t[:i]+'0'+t[i+1:]
    else:
        t = t[:i]+'1'+t[i+1:]
    e = int(t,2)
    g = fcount(e)
    
    print(g)

Submission status: Time Limit Exceeded

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

x_num = int(X, 2)

def f(cnt):
    if (cnt > 0):
        pcount = p_count(cnt)
        return f(cnt % pcount) + 1
    else:
        return 0


def p_count(x):
    cnt = 0
    while (x > 0):
        if x % 2 != 0:
            cnt += 1
        x //= 2
    return cnt


for i, x in enumerate(X):
    if (x == '1'):
        #x_num = int(''.join(X), 2)
        print(f(x_num - (2**(N-(i+1)))))
    else:
        #x_num = int(''.join(X), 2)
        print(f(x_num + (2**(N-(i+1)))))

Submission status: Time Limit Exceeded

Solution code:

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

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


#res = popcount(7)
#print(res)
#
#ans = [0] * N
#print(X)

for i in range(N):
    if X[i] == '0':
        val = X[:i] + '1' + X[i+1:]
    if X[i] == '1':
        val = X[:i] + '0' + X[i+1:]

    #print(val)

    count = 0
    val_10 = int(val, 2)
    #print(val_10)

    while val_10 != 0:
        val_10 = val_10 % popcount(val_10)
        count += 1

    print(count)

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'])


cache = dict()

@lru_cache(maxsize=1000000000)
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(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:
def f(n):
  return bin(n).count("1")

def toggleKthBit(n, k): 
    return (n ^ (1 << (k-1))) 
n,x=map(str,open(0).read().split());n=int(n)
l=[i for i in x]

for i in range(n,0,-1):
  ix=toggleKthBit(int(x,2),i)
  count=0
  while ix and n:
    ix=ix%f(ix)
    count+=1
  print(count)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n_ansl = [0]*(2*(10**5))
    for i in range(1,2*(10**5)):
    # for i in range(1,20):
        cnt = 0
        one_cnt = bin(i).count("1")
        rem = i
        while rem != 0:
            one_cnt = bin(rem).count("1")
            rem = rem%one_cnt   
            cnt += 1
        n_ansl[i] = cnt
 
    n = int(input())
    x = input()
    one_cnt = x.count('1')

    if one_cnt == 0:
        for i in range(n):
            print(1)
        exit()
    
    curr_2b = 1
    curr_2b_p = 1
    curr_2b_m = 1
    curr_sum = 0
    curr_sum_p1 = 0
    curr_sum_m1 = 0
    for i in range(n-1, -1, -1):
        if x[i] == '1':
            curr_sum += curr_2b
            curr_sum_p1 += curr_2b_p
            curr_sum_m1 += curr_2b_m
            curr_sum%=one_cnt
            curr_sum_p1%=(one_cnt+1)
            if one_cnt > 1:
                curr_sum_m1%=(one_cnt-1)
        curr_2b*=2
        curr_2b_p*=2
        curr_2b_m*=2
        curr_2b%=one_cnt
        curr_2b_p%=(one_cnt+1)
        if one_cnt > 1:
            curr_2b_m%=(one_cnt-1)
 
        
 
    curr_2b = 1
    curr_2b_p = 1
    curr_2b_m = 1
    ansl = [0]*(n)
    for i in range(n-1, -1, -1):
        if x[i] == '1':
            diff = (-1)*curr_2b_m
            if one_cnt > 1:
                ans = (curr_sum_m1 + diff)%(one_cnt-1)
                ansl[i] = n_ansl[ans]+1
            else:
                ansl[i] = 0
        else:
            diff = curr_2b_p
            ans = (curr_sum_p1 + diff)%(one_cnt+1)
            ansl[i] = (n_ansl[ans]+1)
        # curr_2b *= 2
        curr_2b*=2
        curr_2b_p*=2
        curr_2b_m*=2
        curr_2b%=one_cnt
        curr_2b_p%=(one_cnt+1)
        if one_cnt > 1:
            curr_2b_m%=(one_cnt-1)
 
 
    # print(ansl)
    for a in ansl:
        print(a)
 
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#import math
#import collections
#import bisect
#from collections import deque
#from copy import copy, deepcopy

memo_dict = {}


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


def rec(n):
    tmp = n
    if tmp in memo_dict:
        return memo_dict[tmp]
    elif tmp == 0:
        return 0
    else:
        ret = rec(tmp % popcount(tmp)) + 1
        memo_dict[n] = ret
        return ret


def main():
    N = int(input())
    X = input()
    decX = int(X, 2)

    ans = 0
    flip = 2 ** N
    memo_dict = {}
    for i in range(0, N):
        flip = flip >> 1
        tmp = flip ^ decX
        print(rec(tmp))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=input()
X=[0]*n
N=0
P=[]
for i in range(1,n+1):
    cnt = 0
    while i!=0:
        if i%2==1:
            cnt += 1
        i//=2
    P.append(cnt)

q=0
for i in range(n):
    X[i]=int(x[i])
    N+=(X[i])*(2**(n-i-1))
    if X[i]==1:
        q+=1

for i in range(n):
    Ni=0
    X[i]=int(X[i]==0)
    if X[i]==1:
        Ni=N+2**(n-i-1)
        q+=1
    else:
        Ni=N-2**(n-i-1)
        q-=1
    pop=q
    cnt = 0
    while Ni!=0:
        Ni=Ni%pop
        pop=P[Ni-1]
        cnt+=1
    print(cnt)
    if X[i]==1:
        q-=1
    else:
        q+=1
    X[i]=int(X[i]==0)

Submission status: Time Limit Exceeded

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

def popcount(n):
    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:
n = int(input())
x = input()

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

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

    count = 0
    popcount(bin_num)
    print(count)

Submission status: Time Limit Exceeded

Solution code:
def popcount(trg_num, dict):
    if trg_num in dict:
        return dict[trg_num]
    bin_str=bin(trg_num)
    popcount_num=bin_str.count("1")
    dict[trg_num]=popcount_num
    return popcount_num

n=int(input())
x=input()
num=0
for i in range(n):
    if x[n-i-1]=="1":
        num+=2**i

cnt_list=[0 for i in range(n)]
popcount_dict={}
look_table={}

for i in range(n):
    cnt=0
    new_num=num
    if new_num not in look_table:
        look_table[new_num]=i
    if x[i]=="0":
        new_num+=2**(n-i-1)
    else:
        new_num-=2**(n-i-1)
    #print(new_num)
    while new_num!=0:
        new_num%=popcount(new_num, popcount_dict)
        cnt+=1
        if new_num in look_table:
            if cnt_list[look_table[new_num]]:
                cnt+=cnt_list[look_table[new_num]]
                break

    cnt_list[i]=cnt

for l in cnt_list:
    print(l)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = int(input(), 2)
def pc(a):
    cnt = 0
    while int(a, 2) != 0:
        a = bin(int(a, 2)%a.count("1"))[2:]
        cnt += 1
    return cnt

for i in range(n):
    print(pc(bin(x^2**(n-i-1))[2:]))

Submission status: Time Limit Exceeded

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

from decimal import Decimal
from functools import lru_cache


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


cache = dict()

@lru_cache(maxsize=1000000)
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(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:
def to_int(X):
    l = len(X)
    ret = 0
    for i in range(0, l):
        ret += int(X[i:i+1]) * 2**(l-i-1)
    return(ret)


def to_x(x, i):
    if(i >= 1):
        if x & 2**i:
            x -= 2 ** i
        else:
            x += 2 ** i
    else:
        if x % 2 == 0:
            x += 1
        else:
            x -= 1
    return(x)


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


def fn(x):
    ans = 0
    while x != 0:
        x = x % popcount(x)
        ans = ans+1
    return ans


def main():
    N = int(input())
    X = input()
    len_x = len(X)
    int_x = to_int(X)
    for i in range(N, 0, -1):
        x = to_x(int_x, i - 1)
        ans = fn(x)
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = input().strip()
C = X.count("1")
D = int(X, 2)

p = [0]*(C+2)
for i in range(1, len(p)):
    n = i
    while True:
        b = bin(n).count("1")
        if b <= 0:
            break
        p[i] += 1
        n = n % b
        if p[n] > 0:
            p[i] += p[n]
            break

for i in range(1, N+1):
    d = D
    c = C
    if X[i-1] == "1":
        c -= 1
        d -= 1 << (N-i)
    else:
        c += 1
        d += 1 << (N-i)

    if c == 0:
        print(0)
    else:
        d = d % c
        print(p[d]+1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = input()
O = X.count('1')
XN = int(X, 2)

dp = [0] * (N+1)

def popcount(n):
    cnt = 0
    while n != 0:
        one = bin(n).count('1')
        n %= one
        cnt += 1
        if dp[n] > 0:
            return dp[n] + cnt
    return cnt

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

for i in range(N):
    if X[i] == '0':
        print(popcount(XN + 2**(N-i-1)))
    else:
        print(popcount(XN - 2**(N-i-1)))

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
x=input().rstrip()
def popcnt(x):
    cnt=str(bin(x)).count("1")
    x%=cnt
    return x

a=0
for i in range(n):
    if x[-i-1]=="1":
        a+=2**i
for i in range(n):
    if x[i]=="1":
        b=a-2**(n-i-1)
    else:
        b=a+2**(n-i-1)
    p=0
    while b>=1:
        b=popcnt(b)
        p+=1
    print(p)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=str(input())
for i in range(n):
    if x[i]=='0':
        tmp=x[:i]+'1'+x[(i+1):]
    elif x[i]=='1':
        tmp=x[:i]+'0'+x[(i+1):]
    cnt=0
    if tmp.count('1')==0:
        print(0)
    else:
        while True:
            r=int(tmp,2)%tmp.count('1')
            tmp='{:b}'.format(r)
            cnt+=1
            if tmp=='0':
                print(cnt)
                break

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = '0b' + input()

for i in range(n):
    lisx = list(x)
    lisx[i+2] = str(1 - int(lisx[i+2]))
    xx = ''.join(lisx)
    intx = int(xx, 2)
    len1 = xx.count('1')

    cnt = 0
    while True:
        if intx == 0:
            print(cnt)
            break
        
        intx = intx % len1
        xx = bin(intx)
        len1 = xx.count('1')
        cnt += 1

Submission status: Time Limit Exceeded

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

N = int(input())
X = list(map(int,input()))
for i in range(N):
    temp = copy.copy(X)
    if(temp[i] == 0):
        temp[i] =  1
    else:
        temp[i] =  0
    stri = ''.join(map(str, temp))
    num = int(stri, 2)
    count_1 = popcount(num)
    # print(count_1)
    # print(num,count_1)
    i = 0
    for i in range(1000000):
        if(count_1 == 0):
            i -= 1
            break
        surplus = num%count_1
        if(surplus == 0):
            break
        num = surplus
        count_1 = popcount(num)
    print(i+1)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

def hanten(num):
  if(N==1):
    if(X=="0"):
      return '1'
    else:
      return '0'
  else:
    if(num==0):
      if(X[num]=="0"):    
        s = '1' + X[i+1:]
      else:
        s = '0' + X[i+1:] 
      return s

    elif(num==N-1):
      if(X[num]=="0"):    
        s = X[:num] + '1'
      else:
        s = X[:num] + '0'
      return s
    else:
      if(X[num]=="0"):
        s = X[:num] + '1' + X[num+1:]
      else:
        s = X[:num] + '0' + X[num+1:]
      return s


def scount(num2):
  clist=list(num2)
  counter=Counter(clist)
  return counter["1"]
    
def popcount(num3,cnt):
  s=int(num3,2)%cnt
  return bin(s)

i=0

while(i<N):
  res=0
  number=X
  number=hanten(i)
#  print("hantengo:"+number)
  while(int(number,2)!=0):
    r1=scount(number)
    r2=popcount(number,r1)
    number=r2
    res+=1
#    print("next"+number)
  print(res)
  i+=1

Submission status: Time Limit Exceeded

Solution code:
def popcount(x):
    binary = bin(x)
    return sum([1 for c in binary if c == "1"])

def reverse_bin(X, ind):
    ret = ""
    for i, c in enumerate(X):
        if i == ind:
            ret += "1" if c == "0" else "0"
        else:
            ret += c

    return ret

def main():
    N = int(input())
    X_str = input()
    X = int(X_str, 2)
    for i in range(len(X_str)):
        count = 0
        X_tr = reverse_bin(X_str, i)
        x = int(X_tr, 2)
        while x != 0:
            x = x % popcount(x)
            count += 1
        print(count)
    

if __name__ == "__main__":
    main()

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):
    for j in range(i+10):
        if i < len(f_li):
            f_li.append(f_li[i]+j)
            break
        else:
            i = i % ppp(i)

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:
def popcount(n):
    return str(bin(n)).count('1')
def func(n):
    count = 0
    while n!=0:
        if n in hashmap:
            count+=hashmap[n]
            break
        n=n%popcount(n)
        count+=1
    return count

N = int(input())
st = input()
hashmap = {}
for i in range(N):
    if st[i]=='0':
        tmp = st[:i] + '1' + st[i+1:]
    else:
        tmp = st[:i] + '0' + st[i+1:]
    num = int(tmp, 2)
    ans = func(num)
    hashmap[num] = ans
    print(func(num))

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={}
for i in range(N):
    # ちゃんともとに戻してね，ということで本のビット
    b = int(X[i]) & 1
    X[i] = str(b ^ 1)
    num = int(''.join(X),2) # できなきゃjoinで
    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
    X[i] = str(b)
    print(count)

Submission status: Time Limit Exceeded

Solution code:
## xiのpopcount（1の数）はxのpopcount+1または-1
n=int(input())
x=input()
f={0:0,1:1,2:1,3:2}
for i in range(2,n):
    f[2**i]=1
# print(f)
for i in range(len(x)):
    if x[i]=='1':
        x_changed=x[:i]+'0'+x[i+1:]
    else:
        x_changed=x[:i]+'1'+x[i+1:]
    num_changed=int(x_changed,2)
    add=[]
    tmp=num_changed
    while tmp not in f:
        popcount=format(tmp,'b').count('1')
        add.append(tmp)
        tmp%=popcount
    while len(add)>0:
        cnt=f[tmp]
        tmp=add.pop()
        f[tmp]=cnt+1
    print(f[num_changed])

Submission status: Time Limit Exceeded

Solution code:
def popcount(n):
    return bin(n).count('1')
N = int(input())
X = input()
listX = list(X)
for i in range(1,N+1):
    count = 0
    
    if listX[i-1] == '0':
        listX[i-1] = '1' 
        strX = ''.join(listX) #所定位置のビットを反転させて文字列化したやつ
        listX[i-1] = '0'
        x = int(strX, 2) #10進法にしたやつ
        while x > 0:
            x = x % popcount(x)
            count += 1
        print(count)
    
    else:
        listX[i-1] = '0'
        strX = ''.join(listX)
        listX[i-1] = '1'
        x = int(strX, 2)
        while x > 0:
            x = x % popcount(x)
            count += 1
        print(count)

Submission status: Time Limit Exceeded

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


N = int(input())

AAA = [0 for x in range(2 ** N)]
for i in range(1, 2**N):
    AAA[i] = AAA[i % popcount(i)] + 1

X = int(input(), 2)

for i in range(N):
    Xi = X ^ (1 << (N-i-1))
    print(AAA[Xi])

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
X=int(input(),2)
def f(n):
    ans=0
    while n != 0:
        ans+=1
        n2=str(bin(n)[2:])
        pop=n2.count('1')
        n=n%pop
    return ans

for i in range(N-1,-1,-1):
    xi=X^2**i
    print(f(xi))

Submission status: Time Limit Exceeded

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

def pcrem(n,cnt):
  if (n==0):
    print(cnt)
    return 0
  pc = bin(n).count("1")
  pcrem(n%pc,cnt+1)

for i in range(N):
  f = X^(1<<N-i-1)
  pcrem(f,0)

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 not in f:
        ans = 0
        while y!=0:
            y = y % bin(y).count('1')
            ans += 1
        print(ans)
        f[y]=ans
    else: print(f[y])

Submission status: Time Limit Exceeded

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

for i in range(n):
  temp = list(rep)
  if temp[i] == '1':
    temp[i] = '0'
  else:
    temp[i] = '1'
  x = int(''.join(temp), 2)
  ans = 0
  while x:
    x = x % bin(x)[2:].count('1')
    ans += 1
  print(ans)

Submission status: Time Limit Exceeded

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

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    x = input()
    
    val = 0
    rui = 1
    mod = 0
    
    nagasa = 2*10**5+1
    #nagasa = 5
    d_li = [0]*(nagasa)
    
    for i in range(1,nagasa):
        t_v = i
        t_m = bin(t_v).count("1")
        ans = 0
        while t_v != 0:
            if d_li[t_v] != 0:
                ans += d_li[t_v]
                break
            ans += 1
            t_v %= t_m
            #t_m = bin(t_v).count("1")
        d_li[i] = ans
    
    #print(d_li)
    #exit()
    """
    for i in range(n):
        val += int(x[n-1-i])*rui
        rui *= 2
    """
    val = int(x, 2)
    #print(val)
    #exit()
    
    mod = bin(val).count("1")
    
    rui = pow(2,(n-1))
    ans_li = []
        
    for i in range(n):
        t_v = val
        t_m = mod
        if int(x[i]) == 1:
            t_v -= rui
            t_m -= 1
        else:
            t_v += rui
            t_m += 1
        rui //= 2
        ans = 0
        #while t_v != 0:
        if t_v != 0:
            t_v %= t_m
            ans += 1
        
        ans += d_li[t_v]
        #t_m = bin(t_v).count("1")
        #ans_li.append(ans)
        print(ans)
        #print(ans_li)
        
if __name__ == '__main__':
    main()
"""
#print(ans_li)
for i in range(n):
    print(ans_li[n-1-i])
"""

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy

def popcount(N):
  cnt = 0
  while not(N == 0 or N == 1):
    cnt += N % 2
    N = N // 2
  return cnt + N

N = int(input())
sum = int(input(), 2)
pd = dict()
cd = dict()
    
for n in range(N-1, -1, -1):
  if (sum >> n & 1) == 1:
    x = sum - 2**n
  else:
    x = sum + 2**n
  
  cnt = 0
  flag = True
  ini = deepcopy(x)
  while x != 0:
    if cd.get(x):
      flag = False
      q = cnt + cd[x]
      cd[ini] = q
      print(q)
      break
      
    cnt += 1
    if pd.get(x):
      x = x % pd[x]
    else:
      pd[x] = popcount(x)
      x = x % pd[x]
  
  if flag:
    cd[ini] = cnt
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = input()
MOD = len(list(filter(lambda x:x=='1', X)))

for i in range(N):
    c = 0
    tmp = X[:i] + ('1' if X[i] == '0' else '0') + X[i+1:]
    tmp = int(tmp, 2)
    while tmp:
        MOD = len(list(filter(lambda x:x=='1', format(tmp, 'b'))))
        tmp = tmp % MOD
        c += 1
    print(c)

Submission status: Time Limit Exceeded

Solution code:
def f(n, c_one):                                          
    cnt = 0                                               
    while n:                                              
        n = n % c_one                                     
        cnt += 1                                          
        c_one = bin(n).count('1') # ここがボトルネック             
    return cnt                                            
                                                          
                                                          
N = int(input())                                          
binary_str = str(input())                                 
# N = 2 * 10 ** 5                                         
# binary_str = '1' * (2 * 10 ** 5)                        
binary_num = int(binary_str, 2)                           
cnt_one = binary_str.count('1')                           
for i in range(N):                                        
    idx = (N - 1 - i)                                     
    if binary_str[i] == '1':                              
        print(f(binary_num - 2 ** idx, cnt_one - 1))      
    else:                                                 
        print(f(binary_num + 2 ** idx, cnt_one + 1))

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)]

divmemo = {}
def popcountdiv(n, onecount):
    if n in divmemo:
        return divmemo[n]
    myonecount = onecount
    if myonecount == -1:
        myonecount = bin(n).count("1")
    res = n % myonecount
    divmemo[n] = res
    return res

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

N = int(input())
X = input()
onecount = X.count("1")
mathX = int(X, 2)
for i in range(N):
    if X[i] == "1":
        #print(X, mathX, mathX-2**(N-(i+1)))
        print(f(mathX-2**(N-(i+1)), onecount-1))
    else:
        #print(X, mathX, mathX+2**(N-(i+1)))
        print(f(mathX+2**(N-(i+1)), onecount+1))

Submission status: Time Limit Exceeded

Solution code:
from numba import njit
"""
@njit('i8(i8)', cache=True)
def popcount(n):
    a = 0
    while n:
        a += n % 2
        n //= 2
    return a
"""
from functools import lru_cache
@lru_cache(maxsize = 10000)
def popcount(n):
    if n == 0:
        return 0
    else:
        return n % 2 + popcount(n // 2)


#@njit('i8(i8)', cache=True)
def fun(n):
    ops = 0
    while n:
        bits = popcount(n)
        n %= bits
        ops += 1
    return ops

def funwrap(n, pc):
    if n == 0:
        return 0
    return 1 + fun(n % pc)

n = int(input())
xs = list(map(int, input()))

from functools import reduce
sm = reduce(lambda x,y: x*2+y, xs)
pc = xs.count(1)

for i in range(n):
    xs[i] ^= 1
    df = 1 if xs[i] == 1 else -1
    pc += df

    dn = 1 << (n - (i + 1))
    smi = sm + dn * df

    print(funwrap(smi, pc))

    xs[i] ^= 1
    pc -= df

Submission status: Time Limit Exceeded

Solution code:

N=int(input())
X=input()
Zero="0"*N

H=X.count("1")
Z=int(X,2)
G=1<<N

A=[]
for i in range(N):
    G>>=1
    
    if X[i]=="0":
        J=H+1
    else:
        J=H-1
        
    Y=Z^G

    if Y==0:
        A.append(0)
        continue
    
    I=1
    Y=Y%J
    
    while Y!=0:
        Y=Y%bin(Y).count("1")
        I+=1
    A.append(I)

print("\n".join(map(str,A)))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n = int(input())
X = int(input(),2)

from collections import defaultdict
d = defaultdict(lambda: -1)

from functools import lru_cache
@lru_cache(None)
def dfs(X):
    if X == 0:
        return 0
    if d[X]==-1:
        popcount = bin(X).count("1")
        d[X]=popcount
    else:
        popcount = d[X]

    if popcount == 1:
        return 1
    return dfs(X%popcount)+1

for i in reversed(range(0,n)):
    print(dfs(X^(1<<i) ))