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

    A = [0] * n
    nx = int(x, 2)
    c1 = x.count('1')
    for i in range(n):
        c1s = c1
        nxs = nx
        if x[i] == '0':
            c1s += 1
            nxs += 2 ** (n - i - 1)
        else:
            c1s -= 1
            nxs -= 2 ** (n - i - 1)

        while c1s > 0:
            nxs %= c1s
            c1s = format(nxs, 'b').count('1')
            A[i] += 1

    for a in A:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = list(map(int, input()))

Xp = sum(X)
        
# print(Xp)
a = 0
b = 0
# c = 0
for i, x in enumerate(X):
    i_reverse = N-i-1
    if Xp > 1:
        a = (a + x * (1<<i_reverse)) % (Xp-1)
    b = (b + x * (1<<i_reverse)) % (Xp+1)
    # c = (c + x * (1<<i_reverse))
    # print(bin(c))

# print(a, b)

for i in range(N):
    i_reverse = N-i-1
    if Xp > 1:
        m = ([a, b][X[i]==0] + [-1, 1][X[i]==0] * (1<<i_reverse)) % [Xp-1, Xp+1][X[i]==0]
    else:
        if X[i]==0:
            m = (b + (1<<i_reverse)) % (Xp+1)
        else:
            print(0)
            continue
    count = 1
    # print(i, ([a, b][X[i]==0], [-1, 1][X[i]==0]*(1<<i_reverse)), [Xp-1, Xp+1][X[i]==0], X[i]==0)
    # print(m)
    while m > 0:
        p = sum([int(c) for c in str(bin(m)[2:])])
        m = m % p
        count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
import random
from collections import deque
from decimal import *
import queue

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	X = inputStr()
	X_lin = list(X)

	ans = []
	mem = {}
	for i in range(N):
		tmpX = ""
		if X[i] == "1":
			tmpX = X[:i] + "0" + X[i+1:]
		else:
			tmpX = X[:i] + "1" + X[i+1:]

		oct = int(tmpX, 2)
		oct_mae = oct

		ans_tmp = 0
		if oct in mem:
			ans_tmp = mem[oct]
		else:
			while True:
				if oct == 0:
					break
				tmp = bc(oct)
				oct = oct % tmp
				ans_tmp += 1
				if oct == 0:
					break
				if oct in mem:
					ans_tmp += mem[oct]
					break

		if oct_mae in mem:
			pass
		else:
			mem[oct_mae] = ans_tmp

		ans.append(ans_tmp)

	for i in ans:
		print(i)
	#print(mem)

def bc(x):
	return bin(x).count("1")

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[4]:


import copy


# In[48]:


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


# In[55]:


def func(N,X):
    for i in range(N):
        xi = copy.deepcopy(X)
        xi[i] = str(1-int(X[i]))
        popcount = xi.count("1")
        num = int("".join(xi),2)
        if num == 0:
            ans = 0
        else:
            ans = 1
            while num%popcount != 0:
                num = num%popcount
                popcount = format(num,"b").count("1")
                ans += 1
        print(ans)


# In[56]:


func(N,X)


# In[ ]:





# In[ ]:

Submission status: Time Limit Exceeded

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

mod = [[0, 0] for _ in range(n)]
for i in range(n):
    mod[i][0] = 2**i%(count-1) if count!=1 else 0
    mod[i][1] = 2**i%(count+1)
mod1 = num%(count-1) if count!=1 else 0
mod2 = num%(count+1)

table = [0]*(2*10**5+10)
for i in range(2*10**5+10):
    _num = i
    while True:
        _count = 0
        for c in bin(_num):
            if c == "1":
                _count += 1
        if _num == 0:
            break
        _num %= _count
        table[i] += 1

ans = [0]*n
for i in range(n):
    if x[-(i+1)] == "1":
        _num = num-2**i
        if _num == 0:
            continue
        _num = (mod1-mod[i][0])%(count-1)
    else:
        _num = num+2**i
        _num = (mod2+mod[i][1])%(count+1)
    ans[i] = 1+table[_num]
for i in range(n):
    print(ans[-(i+1)])

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 = 0
            for elem in ans2:
                if elem == '1':
                    oneCount += 1
            anscur %= oneCount
            cnt += 1
        ans += str(cnt)
        if i != N-1:
            ans += '\n'
    print(ans)
                    
main()

Submission status: Time Limit Exceeded

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

from functools import lru_cache


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


cache = dict()

@lru_cache(maxsize=200000)
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))
        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:
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
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
    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:
from functools import lru_cache


@lru_cache(maxsize=100000)
def popcount(n):
    return bin(n).count('1')


@lru_cache(maxsize=100000)
def f(n):
    if n == 0:
        return 0
    else:
        n = n % popcount(n)
        return f(n) + 1


N = int(input())
S = input()
S_int = int(S, 2)
p = popcount(S_int)
for i in range(N-1, -1, -1):
    if S_int & (1 << i):
        p_next = p - 1
    else:
        p_next = p + 1

    if (p_next == 0):
        print(0)
        continue

    target = S_int ^ (1 << i)
    print(f(target % p_next) + 1)

Submission status: Time Limit Exceeded

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

t = [0]

def count_ones_by_shift(num):
    num = (num & 0x55555555) + ((num & 0xAAAAAAAA) >> 1) 
    num = (num & 0x33333333) + ((num & 0xCCCCCCCC) >> 2)
    num = (num & 0x0F0F0F0F) + ((num & 0xF0F0F0F0) >> 4)
    num = (num & 0x00FF00FF) + ((num & 0xFF00FF00) >> 8)
    num = (num & 0x0000FFFF) + ((num & 0xFFFF0000) >> 16)
    return num

for n in range(1, N+1):
    c = count_ones_by_shift(n)
    t.append(1 + t[n%c])

base = X.count("1")
basex = int(X, 2)
for n in range(N):
    if X[n] == "0":
        c = base + 1
        x = basex + 2**(N-n-1)
    else:
        c = base - 1
        x = basex - 2**(N-n-1)
    
    if c == 0:
        print(0)
    else:
        print(1 + t[x%c])

Submission status: Time Limit Exceeded

Solution code:
f = [0 for i in range(200005)]

def num(a):
    res = 0
    while a:
        if(a&1==1): res = res+1
        a >>= 1
    return res

def pre():
    f[1] = f[2] = 1
    for i in range(1,200005):
        f[i] = 1+f[i%num(i)]

def main():
    pre()

    n = eval(input())
    s = input()
    cnt = 0
    for ch in s:
        if ch=='1': cnt = cnt+1
    for i in range(n):
        s1 = list(s)
        cnt1 = cnt
        if s1[i]=='0':
            s1[i] = '1'
            cnt1 += 1
        else:
            s1[i] = '0'
            cnt1 -= 1
        s1 = ''.join(s1)
        d = int(s1,2)
        if d < 200005: print(f[d])
        else: print(1+f[d%cnt1])

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n=int(input())
x=input()
d={}
j=[]
for i in range(n-1,-1,-1):
  count=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]+count)
      break
    b=bin(a).count("1")
    if b==0 or a==0:
      d[c]=count
      j.append(count)
      break
    a%=b
    count+=1
for i in range(n-1,-1,-1):
  print(j[i])

Submission status: Time Limit Exceeded

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

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

    ops = 1
    while n:
        bits = popcount(n)
        n = n % bits
        ops += 1
    return ops

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(fun(smi, pc))

    xs[i] ^= 1
    pc -= df

Submission status: Time Limit Exceeded

Solution code:

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

# def main():
n_ansl = [0]*(n)
for i in range(1,n):
# for i in range(1,20):
    cnt = 0
    one = bin(i).count("1")
    rem = i
    while rem != 0:
        one = bin(rem).count("1")
        rem = rem%one   
        cnt += 1
    n_ansl[i] = cnt


one_cnt = x.count('1')
# if one_cnt == 0:
#     for _ in range(n):
#         print(1)
#     exit()

c2bl = [1]*n
c2blp = [1]*n
c2blm = [1]*n

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):
    c2bl[i] = curr_2b
    c2blp[i] = curr_2b_p
    c2blm[i] = curr_2b_m
    if x[i] == '1':
        curr_sum += curr_2b
        curr_sum_p1 += curr_2b_p
        curr_sum_m1 += curr_2b_m
        if one_cnt >0:
            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
    if one_cnt > 0:
        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
        diff = (-1)*c2blm[i]
        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
        diff = c2blp[i]
        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:
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={}

for i in range(n):
    cnt=0
    new_num=num
    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

    cnt_list[i]=cnt

for l in cnt_list:
    print(l)

Submission status: Time Limit Exceeded

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

xl = list(x)
xl = [int(s) for s in xl]
m = sum(xl)

for i in range(n):
    if x[i] == '0':
        tmp = '1'
        mm =  m + 1
    else:
        tmp = '0'
        mm =  m - 1
        
    xx = x[:i] + tmp + x[i+1:]
    xx = int(xx, 2)
    
    cnt = 0
    while xx:
        xx %= mm
        xxl = list(bin(xx)[2:])
        xxl = [int(s) for s in xxl]
        mm = sum(xxl)
        cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

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

for i in range(n):
    a = int(x[i])
    if a == 1:
        a = 0
    else:
        a = 1
    ref = int(x[:i] + str(a) + x[i + 1:], 2)
    cnt = 0
    while ref > 0:
        bitcnt = bin(ref).count("1")
        ref = ref%bitcnt
        cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def calc(N):
    count = 0
    while N!=0:
        z  = bin(N).count('1')
        N = N%z
        count += 1
    return count

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


for i in range(len(A)):
    P=0
    Z = A.copy()
    Z[i] ^= 1
    c = 0
    Z.reverse()
    for j in range(0,len(Z)):
        P += Z[j]*2**j 
    print(calc(P))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter as ct
def get_p(num):
    return ct(list(format(num, 'b')))['1']

n = int(input())
x = input()
x_num = int(x, 2)
for i in range(n):
    ans = 0
    if x[i] == '0':
        x_num_tmp = x_num + 2**(n-i-1)
    else:
        x_num_tmp = x_num - 2**(n-i-1)
    while(True):
        if x_num_tmp == 0:
            break
        else:
            x_num_tmp %= get_p(x_num_tmp)
            ans += 1
            
    print(ans)

Submission status: Time Limit Exceeded

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

N = int(input())
Xb = input().rstrip()
# N = 2*10**5
# Xb = '1'*N


X = 0
t = 1
for i in range(N):
    if Xb[N-1-i]=='1':
        X += t
    t *= 2

def popcount(x):
    return bin(x).count('1')
def calc(X):
    ans = 0
    while X!=0:
        X %= popcount(X)
        ans += 1
    return ans

ret = []
t = 1
for i in range(N):
    if Xb[N-1-i]=='1':
        Xt = X - t
    else:
        Xt = X + t
    ret.append(calc(Xt))
    t *= 2

for i in range(N):
    print(ret[N-1-i])

Submission status: Time Limit Exceeded

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

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):
    co_x = X.copy()
    if co_x[i] == "1":
        co_x[i] = "0"  
    else:
        co_x[i] = "1"
    num = int("".join(co_x), 2)
    print(f_count(num))

Submission status: Time Limit Exceeded

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


def solve(N: int, X: str):
    def pc(n):
        return bin(n).count("1")

    def f(i):
        if i == 0 : return 0

        p = 0
        k = i
        while(k!= 0):
            t = k
            p+=1
            k = t % pc(t)
        
        return p
    
    x = int(X, 2)
    for i, xi in enumerate(X):
        if xi == "0":
            temp = (x + 2**(N-i-1))
        else:
            temp = (x - 2**(N-i-1))
        

        print(f(temp))

    
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = next(tokens)  # type: str
    solve(N, X)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


from functools import lru_cache

@lru_cache(maxsize=None)
def binbin(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':
            print(popcount(x + (2 ** (N - i - 1))))
        else:
            print(popcount(x - (2 ** (N - i - 1))))



    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    x = int(input(), 2)
    
    def popcount(n):
        n = format(n, 'b')
        return n.count('1')
    
    for i in range(n):
        x2 = 1 << n-1-i
        x2 = x^x2 
        ans = 0
        while x2 != 0:
            x2 = x2 % popcount(x2)
            ans += 1
        print(ans)
    
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
memo = {}
p_memo = {}

# n = int
def popcount(n):
    if n in p_memo:
        return p_memo[n]
    else:
        cnt = format(n, '08b').count("1")
        p_memo[n] = cnt
        return cnt

# n = int
def f(n):
    if n == 0:
        return 0        
    elif n in memo:
        return memo[n]
    
    cnt = f(n % popcount(n)) + 1
    memo[n] = cnt
    return cnt

def resolve():
    cnt = 0
    n = int(input())
    X = input()
    base_popcount = X.count("1")
    p_memo[int(X, 2)] = base_popcount

    x = list(X)
    for i in range(n):
        b = base_popcount
        if X[i] == "0":
            x[i] = "1"
            b += 1
        else:
            x[i] = "0"
            b -= 1

        a = int("".join(x), 2)
        p_memo[a] = b
        print(f(a))
        x[i] = X[i]

resolve()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

x = input()
ans = []


def popcount(s):
    count = 0
    binary = str(bin(s))
    for i in range(len(binary)):
        if binary[i] == "1":
            count += 1
    return count


def f(n):
    count = 0
    while(n != 0):
        pop = popcount(n)
        if pop == 0:
            break
        n = n % pop
        count += 1
    ans.append(count)


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


for i in range(len(ans)):
    print(ans[-i-1])

Submission status: Time Limit Exceeded

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

#%%
def popcount(n):
    ans = 0
    temp = format(n, "b")
    for i in temp:
        if i == "1":
            ans += 1

    return ans

def f(n):
    cnt = 0
    temp = n
    while temp != 0:
        temp = temp % popcount(temp)
        cnt += 1

    return cnt

A = []
for i in range(N):
    if X[i] == "1":
        XX = list(X)
        XX[i] = "0"
        A.append("".join(XX))

    elif X[i] == "0":
        XX = list(X)
        XX[i] = "1"
        A.append("".join(XX))

#%%
for i in A:
    ans = f(int(i, 2))
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

from functools import lru_cache

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

bit = {}
@lru_cache(maxsize=None)
def popcount2(bits):
    if bits in bit:
        return bit[bits]
    ori_bit = bits
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555)
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333)
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f)
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff)
    ans = (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff)
    bit[ori_bit] = ans
    return ans


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


def rec2(n):
    if n in memo:
        return memo[n]
    
    p = bit[n]
    new_n = n % p
    ans = memo[new_n] + 1
    memo[n] = ans
    return memo[n]


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

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

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


if __name__ == "__main__":
    submit()

Submission status: Time Limit Exceeded

Solution code:

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

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def one(y):
    ans = 0
    for i in y:
        if i == "1":
            ans += 1
    return ans

def popcount(y):
    ans = 0
    yint = int(y,2)
    while yint != 0:
        ans += 1
        count = one(bin(yint))
        yint = yint % count
    print(ans)

j = 0
for i in range(n):
    xAfter = x
    if xAfter[j] == "0":
        xAfter = x[:j] + '1' +x[j+1:]
    elif xAfter[j] == "1":
        xAfter = x[:j] + '0' +x[j+1:]
    popcount(xAfter)
    j += 1

Submission status: Time Limit Exceeded

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

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

def f(n):
    global ans
    if n==0:
        return 0
    ans += 1
    return f(n % popcount(n))

x = list(X)
for i in range(len(X)):
    ans = 0
    t = x[:]
    t[i] = '0' if t[i]=='1' else '1'
    f(int("".join([c for c in t]), 2))
    print(ans)

Submission status: Time Limit Exceeded

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

def count1(n):
    cnt = 0
    while n >= 2:
        if n%2 == 1:
            cnt += 1
        n //= 2
    if n == 1:
        cnt += 1
    return cnt

def popcount(n, cnt):
    kos = count1(n)
    if n != 0:
        return popcount(n%kos, cnt+1)
    else:
        return cnt

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from functools import lru_cache

def main():
    N = int(input())
    s = input()
    X = int(s, 2)
    popcount = Counter(bin(X)).get('1', 0)
    for i in range(N):
        if (s[i] == '0'):
            n = X + 2 ** (N - 1 - i)
            print(f(n, popcount + 1))
        else:
            n = X - 2 ** (N - 1 - i) 
            print(f(n, popcount - 1))

@lru_cache
def calcPopCount(n):
    popcount = Counter(bin(n)).get('1', 0)
    return popcount

@lru_cache(maxsize=100000000)
def f(n, popcount):
    if n == 0:
        return 0

    n = n % popcount

    return f(n, calcPopCount(n)) + 1


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def func(z,c):
    if c == 0:
        z = 0
    else:
        z = z%c
    a = bin(z)
    b = 0
    for i in range(len(a)):
        if a[i] == "1":
            b += 1
    return z,b

n = int(input())
x = input()
c = 0
for i in range(n):
    if x[i] == "1":
        c += 1
X = int(x,2)

for i in range(n):
    
    if x[i] == "0":
        d = c + 1
        z = X + pow(2,n-i-1)
    else:
        d = c - 1
        z = X - pow(2,n-i-1)
    ans = 0
    #print(z,d)
    while z:
        z,d = func(z,d)
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
FAST_IO = 1
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()

    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())
rrmm = lambda n: [rrm() for _ in xrange(n)]
def getMod(_str, n, k) :  
    pwrTwo = [0] * n  
    pwrTwo[0] = 1 % k  
    for i in range(1, n):  
        pwrTwo[i] = pwrTwo[i - 1] * (2 % k)  
        pwrTwo[i] %= k  
  
    # To store the result  
    res = 0
    i = 0
    j = n - 1
    while (i < n) :  
  
        # If current bit is 1  
        if (_str[j] == '1') :  
  
            # Add the current power of 2  
            res += (pwrTwo[i])  
            res %= k  
              
        i += 1
        j -= 1
  
    return res  

dic = {}
def f(x):
    if x in dic:
        return dic[x]
    if x== 0:
        return 0
    tmp = x% bin(x).count('1')
    dic[x] = f(tmp)+1
    return dic[x]
    
N = rri()
num = list(rr())
count = num.count('1')
dic_count = [0 for _ in range(N)]
for i in range(N):
    if num[i] =='0':
        cur_count = count+1
    else:
        cur_count =count-1
    if cur_count ==0:
        print(0)
    else:
        if num[i] =='0':
            num[i] ='1'
            cur_num = getMod(num, N, cur_count)
            print(f(cur_num)+1)
            num[i] ='0'
        else:
            num[i] ='0'
            cur_num = getMod(num, N, cur_count)
            print(f(cur_num)+1)
            num[i] ='1'

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
    
def pop_num2(N,b,L,M):
    if N==0:
        return 0
    if N<=100000:
        return M[N]
    v=N%b
    return pop_num2(v,L[v],L,M)+1

M=[0]*100001
for i in range(1,100001):
    M[i]+=pop_num(i,L[i],L)

X=int(input())
Y=input()
d=bin_sum2(Y)+1
c=bin_sum2(Y)-1
for i in range(X):
    Y_i=Y[:i]+str(abs(int(Y[i])-1))+Y[i+1:]
    if Y_i[i]=="1":
        b=d
    else:
        b=c
    print(pop_num2(int(Y_i,2),b,L,M))

Submission status: Time Limit Exceeded

Solution code:
# D Anything Goes to Zero

import copy

n = int(input())
x = input()
for i in range(n):
  xi = copy.copy(x)
  if xi[i] == "1":
    xi = xi[:i] + "0" + xi[i+1:]
  else:
    xi = xi[:i] + "1" + xi[i+1:]
  xi = int(xi, 2)

  ans = 0
  while xi != 0:
    xi = xi % bin(xi).count("1")
    ans += 1
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
History = {}

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

def AnythingGoestoZero(n):
  count = 0
  target = n
  while target != 0:
    if target in History.keys():
      count += History[target]
      break
    else:
      count += 1
    target = target % popcount(target)
  if n not in History.keys():
    History[n] = count
  return count

if __name__ == '__main__':
  N = int(input())
  X = input()
  for i in range(N):
    tmp = list(X)
    if tmp[i] == "0":
      tmp[i] = "1"
    else:
      tmp[i] = "0"
    target = "".join(tmp)
    print(AnythingGoestoZero(int(target, 2)))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200000)

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

from functools import lru_cache
@lru_cache(maxsize=200000)
def f(n):
  if n == 0:
    return 0
  if n == 1:
    return 1
  count = bin(n)[2:].count('1')
  t = n % count
  return 1 + f(t)

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