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 popcount(x):
	count=0
	for digit in str(bin(x))[2:]:
		if digit=='1':
			count+=1
	return count

f_memo={0:0}
def f(x):
	if x in f_memo:
		return f_memo[x]
	else:
		ans= 1+f(x%popcount(x))
		f_memo[x]=ans
		return ans

n= int(input())
x= list(input())
#print(x)
for i in range(len(x)):
	x[i]=str(int(x[i])^1)
	test= ''.join(x)
	print(f(int(test,2)))
	x[i]=str(int(x[i])^1)

'''
value_x= int(x, 2)

for i in range(n):
	test= value_x^(2**(n-i-1))
	print(f(test))
'''




#print(f(n))

Submission status: Time Limit Exceeded

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

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

def popcount(pop: int, cnt: int):
    val = 0
    if cnt == 0:
        return 0
    while True:
        val += 1
        pop = pop % cnt
        cnt = bin(pop).count('1')
        if pop == 0:
            return val

init_cnt1 = bin(int(X, 2)).count('1')
for i in range(N):
    cnt1 = init_cnt1
    if X[i] == '0':
        cnt1 += 1
    else:
        cnt1 -= 1        

    reverse_bitX = toggle_nth_bit(int(X, 2), len(X)-i-1)
    print(popcount(reverse_bitX, cnt1))

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    X = input()
    MOD = sum(map(lambda x: x == '1',X))
    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:
#!/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)):
                    if ans[a] in memo:
                        break
                    memo[ans[a]]=len(ans)-a+M-1


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

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

Submission status: Time Limit Exceeded

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

def pop(x): #10進数
    ret=0
    while x>0:
        ret+=x%2
        x//=2
    return ret

def solve(x): #10進数
    ret=0
    while x>0:
        pop_c=pop(x)
        x%=pop_c
        ret+=1
    return ret

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from collections import Counter

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



n=int(input())
x=input()
d={}
j=[]
for i in range(n):
  ans=0
  if x[i]=="1":
    y=x[:i]+"0"+x[i+1:]
  else:
    y=x[:i]+"1"+x[i+1:]
  c=int(y,2)
  a=int(y,2)

  while True:
    if a in d:
      j.append(d[a]+ans)
      print(d[a]+ans)
    b=count_ones_by_bin(a)
    if b==0 or a==0:
      d[c]=ans
      j.append(ans)
      print(ans)
      break
    a%=b
    ans+=1

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, 1, 2, 1, 2, 1, 1, 2, 3, 1, 2, 2, 3, 2, 2, 2, 2, 1, 2, 1, 2, 1, 2, 2, 3, 1, 2, 1, 3, 2, 2, 2, 2, 1, 2, 2, 3, 2, 2, 2, 1, 2, 2, 2, 2, 1, 2, 2, 3, 1, 2, 1, 2, 1, 1, 2, 3, 1, 2, 2, 3, 2, 2, 2, 2, 1, 1, 2, 3, 1, 2, 2, 2, 2, 2, 2, 2, 1, 3, 2, 3, 1, 2, 2, 3]
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<=99:
            c+=clist[b]
            break
        pb=list(bin(b)).count("1")
        b=b%pb
        c+=1
    print(c)

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


X = int(input(), 2)

for i in range(N):
    Xi = X ^ (1 << (N-i-1))
    ans = 0
    while (Xi > 0):
        Xi = Xi % popcount(Xi)
        ans += 1
    print(ans)

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)
    fnlist = [0] * 101
    for i in range(1, 101):
        fnlist[i] = fn(i)
    for i in range(N, 0, -1):
        x = to_x(int_x, i - 1)
        if x <= 100:
            print(fnlist[x])
        else:
            ans = fn(x)
            print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from math import *
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
x = input()
c = x.count('1')

y = 0
for i in range(n):
    y += int(x[i])*2**(n-1-i)
a = [-1]*10000
a[0] = 0
a[1] = 1

for i in range(n):
    ans = 0
    if x[i] == '0':
        c_tmp = c + 1
        y_tmp = y + 2**(n-1-i)
    else:
        c_tmp = c - 1
        y_tmp = y - 2**(n-1-i)
    reg = y_tmp
    while y_tmp != 0:
        ans += 1
        y_tmp = y_tmp % c_tmp
        c_tmp = format(y_tmp,'b').count('1')
        try:
            if 0 < y_tmp < n and a[y_tmp] != -1:
                ans += a[y_tmp]
                break
        except:
            continue
    print(ans)
    try:
        a[reg] = ans
    except:
        continue

Submission status: Time Limit Exceeded

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

def initMemo(n):
    memo = {}
    for i in range(1, n):
        memo[i] = popcount_1(i)
    return memo

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

def popcount_2(n):
    cnt = 0
    while n != 0:
        cnt += 1
        n = n % bin(n).count('1')
        if n in memo:
            cnt += memo[n]
            break
    return cnt

memo = initMemo(N)
# print(memo)

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

Submission status: Time Limit Exceeded

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

import io
import sys
import math
from functools import lru_cache

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

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

@lru_cache(maxsize=None)
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:
def popcount(n):
    ans = 0
    while (n > 0):
        ans += n % 2
        n = n // 2
    return ans


N = int(input())

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

X = int(input(), 2)

for i in range(N):
    Xi = X ^ (1 << (N-i-1))
    ans = 0
    while (Xi > 0):
        Xi = Xi % popcount(Xi)
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = int(input(), 2)
c = -1
for i in range(n):
    ans = 0
    t = x
    if (t >> (n - i - 1)) & 1 :
        t -= 1 << (n - i - 1)
    else :
        t += 1 << (n - i - 1)
    while bin(t).count('1') != 0 :
        c = bin(t).count('1')
        t %= c
        ans = ans + 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys #追加

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

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

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

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


ans=[]

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

#print(ans_memo)

for item in ans:
    print(item)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


from functools import lru_cache

binarr = [0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, 5, 6, 6, 7, 6, 7, 7, 8, 6, 7, 7, 8, 7, 8, 8, 9, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, 5, 6, 6, 7, 6, 7, 7, 8, 6, 7, 7, 8, 7, 8, 8, 9, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, 5, 6, 6, 7, 6, 7, 7, 8, 6, 7, 7, 8, 7, 8, 8, 9, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, 5, 6, 6, 7, 6, 7, 7, 8, 6, 7, 7, 8, 7, 8, 8, 9, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, 5, 6, 6, 7, 6, 7, 7, 8, 6, 7, 7, 8, 7, 8, 8, 9, 5, 6, 6, 7, 6, 7, 7, 8, 6]



@lru_cache(maxsize=None)
def binbin(binn):
    if binn <= 1000:
        return binarr[binn]
    return bin(binn).count("1")

@lru_cache(maxsize=None)
def popcount(n):
    if n == 0:
        return 0
    return 1 + popcount(n % binbin(n))

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

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



    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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

from functools import lru_cache

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


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

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

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

d={}

for i in range(n):
  tx=x[:]
  if tx[i]=='0':
    tx[i]='1'
  else:
    tx[i]='0'

  tx=''.join(tx)
  num=int(tx,2)
#  print(num)
  cp_num=num

  l=[]

  ans=0
  while num!=0:
    l.append(num)
    popcount=bin(num).count('1')
    num=num%popcount
    ans+=1
    if num in d:
      ans+=d[num]
      break

  d[cp_num]=ans

  print(ans)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
def myf(s):
  cnt = 0
  while int(s, 0) != 0:
    s = bin(int(s, 0) % s.count('1'))
    cnt += 1
  return cnt

n = int(input())
x = '0b' + input()
lst = ['1', '0']
for j in range(n):
  z = x[:j + 2] + lst[int(x[j + 2])] + x[j + 3:]
  print(myf(z))

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    X = int(input(),2)
    LIST = []
    PM = [-1]*N
    ANS = [0]*N
    TEMP = [0]*N
    CHAIND = [0]*N
    bit = 1
    for i in range(N):
        LIST.append(X^bit)
        PM[i] += (X & bit == 0)*2
        bit = bit<<1

    cnt = count_ones_by_bitmask(X)
    for i in range(N):
        if LIST[i]!=0:
            TEMP[i] += LIST[i] % (cnt+PM[i])
            ANS[i] += 1

    CHA = list(set(TEMP))

    for i in range(len(CHA)):
        an = 0
        cha = CHA[i]
        cnt = count_ones_by_bitmask(CHA[i])
        while cnt>0:
            an += 1
            cha = cha%cnt
            cnt = count_ones_by_bitmask(cha)
        CHAIND[CHA[i]] = an

    for i in reversed(range(N)):
        print(ANS[i]+CHAIND[TEMP[i]])


def count_ones_by_bitmask(num):
    count = 0
    while num:
        count += num & 1
        num >>= 1
    return count

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
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-=pow(2,(n-1-i))
        su2-=1
    else:
        num4+=pow(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 = list(input())
x = 0
for i in range(n-1, -1, -1):
    x += int(_x[i]) * (2**(n-i-1))

def popcount(n):
    c = 0
    while(n != 0):
        n = n%str(bin(n)[2:]).count('1')
        c += 1
    return c

for i in range(n):
    if ('{:' + str(n) + 'b}').format(x)[i] == '1':
        print(popcount(int(x - 2**(n-i-1))))
    else:
        print(popcount(int(x + 2**(n-i-1))))

Submission status: Time Limit Exceeded

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

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

intx = int( "0b"+x ,0 )
popcount0 = x.count("1")

jisho = ["yet"]*n
pow2i = pow(2,n)

for i in range(n):
    pow2i //=2
    if x[i]=="0":
        pop = popcount0+1
        intxi = intx+pow2i
    else:
        pop = popcount0-1
        intxi = intx-pow2i
        
    if intxi==0:
        print(0)
        continue
    else:
        c=0
        while intxi!=0:
            if c==0:
                intxi=intxi%pop
            else:
                if jisho[intxi]=="yet":
                    togo = intxi%popcount(intxi)
                    jisho[intxi]= togo
                    intxi = togo
                else:
                    intxi =jisho[intxi]
                
            #print(intxi)
            c+=1
        print(c)
        #print()
#        print("f(n)=",c)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
x = input()
c = x.count('1')

y = 0
for i in range(n):
    y += int(x[i])*2**(n-1-i)
a = [-1]*10000
a[0] = 0
a[1] = 1

for i in range(n):
    ans = 0
    if x[i] == '0':
        c_tmp = c + 1
        y_tmp = y + 2**(n-1-i)
    else:
        c_tmp = c - 1
        y_tmp = y - 2**(n-1-i)
    reg = y_tmp
    while y_tmp != 0:
        ans += 1
        y_tmp = y_tmp % c_tmp
        c_tmp = format(y_tmp,'b').count('1')
        try:
            if 0 < y_tmp < n and a[y_tmp] != -1:
                ans += a[y_tmp]
                break
        except:
            continue
    print(ans)
    try:
        a[reg] = ans
    except:
        continue

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = input()
d = {'1':1, '':0}

def popcount(x):
    x = x.lstrip('0')
    if x in d:
        return d[x]
    else:
        n1 = x.count('1')
        num = int(x, base=2)
        if num % n1 == 0:
            return 1
        else:
            return popcount(bin(num % n1)[2:]) + 1
    
def trans(x,n):
    if x[n] == '1':
        return x[:n] + '0' + x[n+1:]
    else:
        return x[:n] + '1' + x[n+1:]
    
for i in range(n):
    ix = trans(x,i)
    print(popcount(ix))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
X=input()
def popcount(x):
    return sum([i == '1' for i in bin(x)])
def func(n):
  ans=0
  x=n
  while x!=0:

    x=x%popcount(x)
    ans+=1
  return ans
base=int(X,2)
for i in range(N):
  kari=base
  if X[i]=="0":
    kari+=2**(N-i-1)
  else:
    kari-=2**(N-i-1)
  print(func(kari))

Submission status: Time Limit Exceeded

Solution code:
save_list = [idx for idx in range(200010)]

def cal_nums(number, flag=0):
    if number == 0:
        return 0
    if number <= 200000 and flag==1:
        return number % save_list[number]
    cp = number
    cnt = 0
    pos = 0
    # print(num_one)
    while cp != 0:
        cnt += cp % 2
        cp //= 2
    # print(cnt)
    
    return number % cnt

def func(number, flag=0):
    # print(num_one)
    if number == 0:
        return 0
    cnt = 0
    tmp = number
    while(1):
        cnt += 1
        tmp = cal_nums(tmp, flag)
        if tmp == 0:
            break
    return cnt

# print('ok')
for idx in range(1, 200000):
    # print('!')
    save_list[idx] = func(idx)
    # print(save_list[idx])
    # print('??')
    # print(save_list[idx])

# print('ok')

n = int(input())
string = input()
length = len(string)
tmp = 0
for i in range(length):
    tmp *= 2
    if string[i] == '1':
        tmp += 1

cnt_0 = 0
cnt_1 = 0

for idx in range(length):
    if string[idx] == '0':
        cnt_0 += 1
    else:
        cnt_1 += 1

# print('ok')
for idx in range(length):
    if string[idx] == '0':
        # print(tmp+(1<<(length-idx-1)))
        print(func(tmp+(1<<(length-idx-1)), 1))
        # print(tmp+(1<<(length-idx-1)))
    else:
        # print(tmp+(1<<(length-idx-1)))
        print(func(tmp-(1<<(length-idx-1)), 1))
        # print(tmp-(1<<(length-idx-1)))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = input()
pc = 0
for i in range(len(x)):
    if x[i]=='1':
        pc += 1
def popcount(s):
    c = 0
    for i in range(len(s)):
        if s[i]=='1':
            c += 1
    return c
d = dict()
d[1] = 1
d[0] = 0

        
for i in range(len(x)):
    X = x[0:i] + ('0' if x[i]=='1' else '1') + x[i+1:len(x)]
    if x[i]=='1':
        pop = pc-1
    else:
        pop = pc+1
    v = int('0b'+X, 0)
    if pop==0:
        print('0')
        continue
    new = v % pop
    if new == 0:
        print('1')
        continue
    counter = 1
    while True:
        counter += 1
        new = new % popcount(str(bin(new)))
        if new == 0:
            print(counter)
            break

Submission status: Time Limit Exceeded

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


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

Submission status: Time Limit Exceeded

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


def popcount(n: int) -> int:
    return bin(n)[2:].count("1")


def f(n: int) -> int:
    i = 0
    while n > 0:
        n = n % popcount(n)
        i += 1
    return i


for i in range(N):
    rev = "0" if X[i] == "1" else "1"
    _X = X[:i] + rev + X[i+1:]
    n = int(_X, 2)
    print(f(n))

Submission status: Time Limit Exceeded

Solution code:
def func(x):
    cnt = 0
    while x > 0:
        val = str(bin(x)).count('1')
        x %= val
        cnt += 1
    return cnt
 
def main():
    N = int(input())
    s = input()
    ans = []
    for i in range(N):
        if s[i] == "0":
            str_x = s[:i] + '1' + s[(i+1):]
        else:
            str_x = s[:i] + '0' + s[(i+1):]
        ans.append(func(int(str_x, 2)))
    for n in ans:
        print(n)
 
if __name__ == '__main__':
    main()