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:
import sys
import copy
from collections import deque
import collections
stdin = sys.stdin

mod = 10**9+7

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
x = ns()
num = int(x, 2)
dp = {0:0}


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

def f_first(p, c):
    if p in dp:
        return dp[p]
    pop = c
    r = p%pop
    if r > 0:
        dp[p] = f(r) + 1
    else:
        dp[p] = 1
    return dp[p]

def f(p):
    if p in dp:
        return dp[p]
    pop = popcount(p)
    r = p%pop
    if r > 0:
        dp[p] = f(r) + 1
    else:
        dp[p] = 1
    return dp[p]

xc = popcount(num)
for i in range(n):
    if x[i]=='0':
        k = num + pow(2, n-i-1)
        print(f_first(k, xc+1))
    else:
        k = num - pow(2, n-i-1)
        print(f_first(k, xc-1))

Submission status: Time Limit Exceeded

Solution code:


n=int(input())

ans=[0]*n
for i in range(n):
    x=i
    cnt=0
    while x>0:
        cnt+=1
        r = 0
        for j in range(19):
            if (x>>j)&1:
                r+=1
            if x>>j==0:
                break
        x=x%r
    ans[i]=cnt

s=input()
l=[0]*(n+1)
rem=[0]*30
num=0
def al(x):
    pop=0
    k=1
    while x>=k:
        if x&k: pop+=1
        k<<=1
    return pop
temp=0
k=1
for i in reversed(range(0,n)):
    if int(s[i]):
        num+=k
        temp+=1
    k<<=1
k=1
for i in reversed(range(1,n+1)):
    num1=num^k
    if num1:
        l[i]+=1
        num1%=temp+(1 if num1>num else -1)
    l[i]+=ans[num1]
    k<<=1
for i in range(1,n+1):
    print(l[i])

Submission status: Time Limit Exceeded

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

n = int(input())
x = input()
z = '1' * n
o = '0' * n
X = int(x, 2)

if (z == x):
  u = n - 1
  d = n - 1
elif (o == x):
  u = 1
  d = 1
else:
  tmp = len(list(filter(lambda x: x == '1', x)))
  u = tmp + 1
  d = tmp - 1


def popcount(i):
  return i % len(list(filter(lambda x: x == '1', format(i, 'b'))))


def toggle(i):
  if (i == '1'):
    return '0'
  else:
    return '1'


def solve(i, count):
  if (i <= 2 * 10**5 and ans[i] != 0):
    return count + ans[i]
  elif (i == 0):
    return count
  else:
    return solve(popcount(i), count + 1)


def solve2(i, div):
  if (i <= 2 * 10**5):
    return ans[i]
  else:
    return ans[i % div] + 1


ans = [0] * (2 * 10 ** 5 + 1)
for i in range(1, 2 * 10 ** 5 + 1):
  ans[i] = solve(i, 0)
for i in range(n):  
  if(x[i] == '0'):
    print(solve2(X + 2 ** (n-i-1), u))
  else:
    print(solve2(X - 2 ** (n-i-1), d))

Submission status: Time Limit Exceeded

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

    ans_dict = {}
    for i in range(10**3):
        ans_dict[i] = cal(i,0,{})

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

def cal(x,rec,ans_dict):
    if x in ans_dict:
        return ans_dict[x] + rec
    else:
        cnt,dig = 0,0
        while 2**dig <= x:
            if 2**dig & x != 0:
                cnt += 1
            dig += 1

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

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

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

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
MAX = (10**6) + 1
N = int(input())
X = input()

c = [0] * MAX
for i in range(MAX):
    c[i] = bin(i).count("1")

def calc(num, cnt2):
    ans = 0
    while num > 0:
        ans += 1
        if ans == 1:
            num = num % cnt2
        else:
            if num < MAX:
                num = num % c[num]
            else:
                num = num % bin(num).count("1")
    return ans

dec = int(X, 2)
cnt = bin(dec).count("1")

for i in range(N):
    cnt2 = cnt
    dec2 = dec
    if X[i] == '0':
        cnt2 += 1
        dec2 += 2**(N-1-i)
    else:
        cnt2 -= 1
        dec2 -= 2**(N-1-i)
    print(calc(dec2, cnt2))

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 F2(Xi):
    popcount = Xi.count("1")
    if popcount == 0:
        return True, Xi
    Xi = eval("0b" + Xi) % popcount
    Xi = format(Xi, "b")
    return False, Xi

@lru_cache(maxsize=None)
def F(Xi):
    ans = 0
    # print("start Xi: {} {}".format(eval("0b" + Xi), Xi))
    while True:
        is_end, Xi = F2(Xi)
        if is_end:
            break
        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:
n = int(input())
xo = input()
output = []
import copy
fn = {}

for i in range(n):
  x = copy.copy(xo)
  if x[i] == "0":
    x = x[:i] + "1" + x[i+1:]
  else:
    x = x[:i] + "0" + x[i+1:]
  x = bin(int(x,2))
  counter = int(copy.copy(x),2)
  outi = 0
  while counter != 0:
    cop =  bin(counter).count("1")
    counter = counter%cop
    outi += 1
    if counter in fn.keys():
      outi += fn[counter]
      counter = 0
  output.append(str(outi))

print("\n".join(output))

Submission status: Time Limit Exceeded

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

x = int(x,2)
y = '1' + ('0' * (n))
y = int(y,2)

for i in range(n):
    y = y >> 1
    xx = x ^ y
    cnt = 0
    while xx != 0:
        buf = bin(xx).count('1')
        xx = xx % buf
        cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

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


def popcount(n):
    s = str(bin(n))[2:]
    return s.count("1")


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


def rev(s, i):
    result = s[:i]
    if s[i] == "0":
        result += "1"
    else:
        result += "0"

    if len(s) > i + 1:
        result += s[i + 1 :]
    return result


for i in range(N):
    print(func(int(rev(X, i), 2)))

Submission status: Time Limit Exceeded

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

def popcount(n):
  c = format(n,"b").count("1")
  if c ==None:
    return 0
  else:
    return c

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


for i in range(N):
  if x[i] == '0':
    print(f(int(x[:i] + "1" + x[i+1:],2)))
  elif x[i] == '1':
    print(f(int(x[:i] + "0" + x[i+1:],2)))

Submission status: Time Limit Exceeded

Solution code:
a = [0]*(2*10**5+1)
for i in range(1,2*10**5):
  t=0
  j = i
  while j != 0:
    t+=j-(j>>1)*2
    j=j>>1
  a[i]+=t
n = int(input())
x = input()
cnt=0
for i in x:
  if i=='1':
    cnt+=1
d =int(x, 2)
for i in range(n):
  if x[i] =='1':
    e=d-2**(n-i-1)
    c = cnt-1
  else:
    e=d+2**(n-i-1)
    c= cnt+1
  if e==0:
    print(0)
  elif e%c ==0:
    print(1)
  else:
    ans=1
    e= e%c
    c = a[e]
    while c!=0:
      e=e%c
      c = a[e]
      ans+=1
    print(ans)

Submission status: Time Limit Exceeded

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

    def popcount(num):
        return bin(num).count("1")
    
    popc_X = popcount(X)
    pop_table = {i: [popcount(i), 0, 0] for i in range(1, N+1)}
    
    def f(x, factor):
        temp = x
        count = 0
        visited = []
        while temp > 0:
            if temp > N:
                # print(temp, popc_X)
                temp = temp % (popc_X + factor)
                count += 1
                # print(temp)
                continue

            if pop_table[temp][1] == 0:
                pop_table[temp][1] = count
            else:
                if pop_table[temp][2]:
                    count += pop_table[temp][1]
                    break

            if pop_table[temp][2] == 0:
                visited.append(temp)
            temp = temp % pop_table[temp][0]
            count += 1

        for v in visited:
            pop_table[v][1] = count - pop_table[v][1]
            pop_table[v][2] = 1
        return count
    

    # ans = [0]*N
    for i in range(N-1, -1, -1):
        xi = X ^ (1 << i)
        # print(xi, "xi")
        if X & (1<<i):
            factor = -1
        else:
            factor = 1
        print(f(xi, factor))
    # for a in ans:
    #     print(a)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    X = input()
    lowNumber = []
    for i in range(N):
        anscur = i
        cnt = 1
        while anscur != 0:
            ans2 = bin(anscur)[2:]
            oneCount = sum(map(lambda x: x == '1',ans2))
            anscur %= oneCount
            cnt += 1
        lowNumber.append(cnt)
    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] * 200001
    POWEROFTWOM1 = [0] * 200001
    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]
            xMODP1 %= MODP1
            xMODM1 += POWEROFTWOM1[N - i - 1]
            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
        ans += str(lowNumber[anscur])
        if i != N-1:
            ans += '\n'
    print(ans)
                    
main()

Submission status: Time Limit Exceeded

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

import math
def solve(x):
    ans = 0
    while x != 0:
        tmp = x
        count = 0
        while x > 0:
            if x & 1 == 1:
                count += 1
            x >>= 1
        x = tmp%count
        ans += 1
    return ans

def solve2(x):
    tmp = X_list.copy()
    if tmp[x] == 1:
        tmp[x] = 0
    else:
        tmp[x] = 1
    num = 1
    ans = 0
    for i in range(N-1,-1,-1):
        ans += tmp[i]*num
        num = num*2
        
    return ans   

for i in range(N):
    tmp = solve2(i)
    ans = solve(tmp)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))

# ===CODE===

eps = 10 ** (-9)


def main():
    def popcounter(n):
        cnt = 0
        if n == 0:
            return 0
        for _ in range(INF):
            tmp = bin(n).count("1")
            n = n % tmp
            cnt += 1
            if n == 0:
                return cnt

    n = ni()
    x = sys.stdin.readline()
    x_1 = x.count("1")

    num = int(x, 2)
    num1 = num % (x_1 - 1) if x_1 - 1 > 0 else 0
    num0 = num % (x_1 + 1)

    ans = []
    for i in range(n):
        if x[n - 1 - i] == "1":
            if x_1 - 1 < 1:
                ans.append(0)
                continue
            else:
                tmp_n = (num1 - pow(2, i)) % (x_1 - 1)
        else:
            tmp_n = (num0 + pow(2, i)) % (x_1 + 1)
        ans.append(popcounter(tmp_n) + 1)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=str(input())
pop=[0]
a=1
b=0
for i in range(1,n):
    ni=0
    a=i
    while a:
        a&=(a-1)
        ni+=1
    pop.append(ni)
x1=0
for i in range(n):
    if int(x[i])&1:
        x1+=2**(n-1-i)

a=x1
popi=0
while a:
    a&=(a-1)
    popi+=1
x2=popi

for i in range(n):
    xi=(2**(n-1)>>i)^x1
    if (2**(n-1)>>i)&x1:
        x3=x2-1
    else:
        x3=x2+1
        
    count=1
    popi=0
    if xi!=0:
        xi=xi%x3
        while xi:
            xi%=pop[xi]
            count+=1
        print(count)
    else:
        print(0)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
from collections import Counter

sys.setrecursionlimit(300000)

memp = {}
def popcount(n):
    if n == 0:
        return 0

    global memp
    if n not in memp:
        memp[n] = (n & 1) + popcount(n >> 1)
    return memp[n]

memf = {}
def f(x):
    if x == 0:
        return 0

    global memf
    if x not in memf:
        memf[x] = f(x % popcount(x)) + 1
    return memf[x]

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

init = Counter(x)['1']
for i in range(n):
    if x[i] == '1':
        pc = init - 1
    else:
        pc = init + 1
    nn = int(x[:i] + str(1 - int(x[i])) + x[i+1:], 2)
    if nn == 0:
        print(0)
        continue

    nn = nn % pc
    ans = 1 + f(nn)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def popcount(x):
    return bin(x).count("1")

N,X = open(0).read().split()
N = int(N)
X = int(X, 2)
cache = {}

for i in range(0, N):
    x = X
    x = x ^ (1 << (N - 1 - i))
    x_ = x
    ans = 0
    while x != 0:
        if x in cache:
            ans += cache[x]
            break
        y = popcount(x)
        x = x % y
        ans += 1
    cache[x_] = ans
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
import copy
n = int(input())
k = input()
xnum = int(k,2)

def f(x):
    a = bin(x)
    a = a[2:]
    num = a.count('1')
    ans = 1
    if num != 0:
        hantei = x % num
    else:
        hantei =  0
        ans = 0
    while hantei != 0:
        ans += 1
        a = bin(hantei)
        a = a[2:]
        num = a.count('1')
        if num != 0:
            hantei = hantei % num
        else:
            hantei =  0
    return ans

z = []
for i in range(n):
    y = copy.deepcopy(k)
    if y[i] == '1':
        ynum = xnum - 2 ** (n-i-1)
        z.append(ynum)
    else:
        ynum = xnum + 2 ** (n-i-1)
        z.append(ynum)

for j in z:
    ans = f(j)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = input()
import copy
def f(n, pop):
  return n%pop
for i in range(n):
  x2 = copy.deepcopy(x)
  if x[i] == "0":
    x2 = x2[:i]+"1"+x2[i+1:]
  else:
    x2 = x2[:i]+"0"+x2[i+1:]
  #print(x2)
  #print(pop)
  y = int(x2, 2)
  #print(y)
  count=0
  while y != 0:
    pop = x2.count("1")
    y = int(x2, 2)
    y = f(y, pop)
    #print(y)
    count+=1
    x2 = bin(y)
  print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = input()
memo = {}


def popcount(x: str):
    return x.count("1")


def f(x: str):
    n = int("0b"+x, 2)
    ops = 0
    while n != 0:
        if memo.get(x) is None:
            pc = popcount(x)
            n %= pc
            memo[x] = n
        else:
            n = memo[x]
        # print(f"popcount({n}) = {pc} => n%{pc} = {n%pc}")
        ops += 1
        x = bin(n)[2:]
    return ops


def rev(x: str, i: int):
    x = list(x)
    if x[i] == "1":
        x[i] = "0"
    else:
        x[i] = "1"
    return "".join(x)


if __name__ == "__main__":
    for i in range(N):
        print(f(rev(X, i)))

Submission status: Time Limit Exceeded

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))

# ===CODE===

eps = 10 ** (-9)


def main():
    def popcounter(n):
        cnt = 0
        if n == 0:
            return 0
        for _ in range(INF):
            tmp = bin(n).count("1")
            n = n % tmp
            cnt += 1
            if n == 0:
                return cnt

    n = ni()
    x = input()
    x_1 = x.count("1")

    num = int(x, 2)
    num1 = num % (x_1 - 1) if x_1 - 1 > 0 else 0
    num0 = num % (x_1 + 1)

    ans = []
    for i in range(n):
        if x[n - 1 - i] == "1":
            if x_1 - 1 < 1:
                ans.append(0)
                continue
            else:
                tmp_n = (num1 - pow(2, i)) % (x_1 - 1)
        else:
            tmp_n = (num0 + pow(2, i)) % (x_1 + 1)
        ans.append(popcounter(tmp_n) + 1)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
import math  # gcdもあるよ
from collections import deque
from collections import defaultdict
from copy import deepcopy
from itertools import accumulate #リストを与えると累積和を返す
def input(): return sys.stdin.readline().rstrip()
from functools import lru_cache #メモ化
import time
count = 0

@lru_cache(maxsize=None)
def popcount(n):
    n = bin(n)
    n_out = n.count("1")
    return n_out

def f_count(n):
    #print(n, type(n))
    global count
    if n != 0:
        count += 1
        f_count(n % (popcount(n)))
    return 0

def main():
    n = int(input())
    x = input()

    #x_10 = int(x, 2)
    for i in range(n):
        x_check = list(deepcopy(x))
        if x_check[i] == '1':
            x_check[i] = '0'
        else:
            x_check[i] = '1'
        x_check_10 = int(''.join(x_check), 2)
        #print("x = {:}".format(x_check_10))
        global count
        count = 0
        f_count(x_check_10)
        print(count)
    
    return 0
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy
from collections import deque
import collections
stdin = sys.stdin

mod = 10**9+7

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
x = ns()
num = int(x, 2)
dp = {0:0}


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

def f(p):
    if p in dp:
        return dp[p]
    pop = popcount(p)
    r = p%pop
    if r > 0:
        dp[p] = f(r) + 1
    else:
        dp[p] = 1
    return dp[p]

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

Submission status: Time Limit Exceeded

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


def onecount(mojix):
    ones=0
    for j in mojix:
        if j=="1":
            ones+=1
    return ones


def popcount(new2bit,ones,count):
    #print("popcount start",new2bit,ones,count)
    
    if ones==0:
        return count
    
    else:
        ten=int(new2bit,2)
        div=ten%ones
        
        count+=1
        
        new2bit=bin(div)
        ones=onecount(str(new2bit))
        
        return popcount(new2bit,ones,count)

ones=onecount(x)

for i in range(N):
    
    
    if x[i]=="1":
        x_ith="0"

    else:
        x_ith="1"
        
    if i==0:
        new2bit=x_ith+x[i+1:]
    elif i<N-1:
        new2bit=x[:i]+x_ith+x[i+1:]
    else:
        new2bit=x[:i]+x_ith

    ones=onecount(new2bit)    
    # print("for loop",i)
    # print("ones",ones)
    # print("new2bit",new2bit)
    # print(" ------ return --- ",popcount(new2bit,ones,0))
    print(popcount(new2bit,ones,0))

Submission status: Time Limit Exceeded

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


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


N = int(input())
A = int(input().rstrip(), 2)

for i in range(N)[::-1]:
    AA = bin(A ^ (1 << i))
    f(AA)

Submission status: Time Limit Exceeded

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

n = int(input())
x = input()
z = '1' * n
o = '0' * n

if (z == x):
  u = n - 1
  d = n - 1
elif (z == o):
  u = 1
  d = 1
else:
  tmp = len(list(filter(lambda x: x == '1', x)))
  u = tmp + 1
  d = tmp - 1


def popcount(i):
  return i % len(list(filter(lambda x: x == '1', format(i, 'b'))))


def toggle(i):
  if (i == '1'):
    return '0'
  else:
    return '1'


def solve(i, count):
  if (i <= 2 * 10**5 and ans[i] != 0):
    return count + ans[i]
  elif (i == 0):
    return count
  else:
    return solve(popcount(i), count + 1)


def solve2(i, div):
  if (i <= 2 * 10**5):
    return ans[i]
  else:
    return ans[i % div] + 1


ans = [0] * (2 * 10 ** 5 + 1)
for i in range(1, 2 * 10 ** 5 + 1):
  ans[i] = solve(i, 0)
for i in range(n):
  if(i == 0):
    _x = toggle(x[0]) + x[1: n]
  elif (i == n - 1):
    _x = x[:i] + toggle(x[n - 1])
  else:
    _x = x[:i] + toggle(x[i]) + x[i + 1 :n]
  if(x[i] == '0'):
    print(solve2(int(_x, 2), u))
  else:
    print(solve2(int(_x, 2), d))

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
N = int(input())
X = input()
#L, R, d=map(int,input().split())
#C = []
# for i in range(N):
#    C.append((input().replace(".","0").replace("#","1")))
# S=list(map(int,input().split()))
# B=list(map(int,input().split()))
def calc(n,x):
    if n!=0:
        return calc(n%str(bin(n))[2:].count("1"),x+1)
    elif n<=0:
        return x

for i in range(0,N):
    X2 = X[:]
    if X2[i]=="0":
        a = list(X2)
        a[i]="1"
        X2="".join(a)

    else:
        a = list(X2)
        a[i]="0"
        X2="".join(a)
    print(calc(int(X2,2),0))

Submission status: Time Limit Exceeded

Solution code:
import copy
POPCOUNT_TABLE16 = [0] * (2*10**5+1)
for index in range(len(POPCOUNT_TABLE16)):
    POPCOUNT_TABLE16[index] = (index & 1) + POPCOUNT_TABLE16[index >> 1]

def popcnt(v):
    return (POPCOUNT_TABLE16[ v        & 0xffff] +
            POPCOUNT_TABLE16[(v >> 16) & 0xffff] +
            POPCOUNT_TABLE16[(v >> 32) & 0xffff] +
            POPCOUNT_TABLE16[(v >> 48)         ])
N = int(input())
X = list(input())
X_int = 0
Xf = [[0 for i in range(2)] for i in range(2*(10**5))]

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

for i in range(N):
    if X[i] == '1':
        X[i] = '0'
        Xf[i][1] = SUM - 1
        X_c = copy.copy(X)
        Xf[i][0] = int(''.join(X_c), 2)
        X[i] = '1'
    elif X[i] == '0':
        X[i] = '1'
        Xf[i][1] = SUM + 1
        X_c = copy.copy(X)
        Xf[i][0] = int(''.join(X_c), 2)
        X[i] = '0'
    
for i in range(N):
    ans = 0
    flg = 0
    while Xf[i][0] > 0:
        ans += 1
        if flg == 0:
            Xf[i][0] = Xf[i][0] % Xf[i][1]
            flg =1
        else:
             Xf[i][0]= Xf[i][0]%popcnt(Xf[i][0])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import random
import time

# Use a constant see to ensure that we see
# the same pseudo-random numbers each time
# we run the loop.
# random.seed(time.time())

def countBitSet(n):
    c = 0
    while n:
        c += n % 2
        n >>= 1
    return c

def calc(n, k):
    c = 0
    while n > 0:
        n = n % k
        c += 1
        k = countBitSet(n)
    return c
        

N = int(input())
s = input()
a = int(s, 2)
# M = a
p = s.count('1')
# i = 0
# while i < N and s[i] == '1':
#     i += 1
# if i < N:
#     M |= 1 << (N - 1 - i)


i = 0
while i < N:
    if s[i] == '0':
        t = a | (1 << (N-1-i))
        print(calc(t, p + 1))
    else:
        t = a & ~(1 << (N - 1 - i))
        print(calc(t, p - 1))
    i += 1

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 = list(input())
    one_cnt = x.count('1')

    if one_cnt == 0:
        for i in range(n):
            print(1)
        exit()
    
    curr_2b_p = 1
    curr_2b_m = 1
    curr_sum_p1 = 0
    curr_sum_m1 = 0
    for i in range(n-1, -1, -1):
        if x[i] == '1':
            curr_sum_p1 += curr_2b_p
            curr_sum_m1 += curr_2b_m
            curr_sum_p1%=(one_cnt+1)
            if one_cnt > 1:
                curr_sum_m1%=(one_cnt-1)
        curr_2b_p*=2
        curr_2b_m*=2
        curr_2b_p%=(one_cnt+1)
        if one_cnt > 1:
            curr_2b_m%=(one_cnt-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_p*=2
        curr_2b_m*=2
        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 sys
import numpy as np
import math  # gcdもあるよ
from collections import deque
from collections import defaultdict
from copy import deepcopy
from itertools import accumulate #リストを与えると累積和を返す
def input(): return sys.stdin.readline().rstrip()
from functools import lru_cache #メモ化
import time
count = 0

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

def f_count(n):
    #print(n, type(n))
    global count
    if n != 0:
        count += 1
        f_count(n % (popcount(n)))
    return 0

def main():
    n = int(input())
    x = input()

    #x_10 = int(x, 2)
    for i in range(n):
        x_check = list(deepcopy(x))
        if x_check[i] == '1':
            x_check[i] = '0'
        else:
            x_check[i] = '1'
        x_check_10 = int(''.join(x_check), 2)
        #print("x = {:}".format(x_check_10))
        global count
        count = 0
        f_count(x_check_10)
        print(count)
    
    return 0
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def main():
    def f(n):
        if n == 0:
            return 0
        if d[n] != 0:
            return d[n]
        d[n] = f(n % sum(list(map(int, bin(n)[2:])))) + 1
    def rev(i, j):
        if X[i] == '0':
            print(d[b % (c + 1)] + 1 if (b := m + j) != 0 else 0)
        else:
            print(d[b % (c - 1)] + 1 if (b := m - j) != 0 else 0)

    n = int(input())
    X = list(input())
    d = defaultdict(int)
    d[0] = 0
    for i in range(1, n):
        f(i)
    c = sum(list(map(int, X)))
    m = int(''.join(X), 2)
    j = 1 << n - 1
    for i in range(n):
        rev(i, j)
        j = j >> 1

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy
from collections import deque
import collections
stdin = sys.stdin

mod = 10**9+7

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
x = ns()
dp = {0:0}


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

def f(p):
    if p in dp:
        return dp[p]
    pop = popcount(p)
    r = p%pop
    if r > 0:
        dp[p] = f(r) + 1
    else:
        dp[p] = 1
    return dp[p]

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
N = int(input())
X = input()

x_num = int(X, 2)
cnt1 = X.count('1')


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


def f1(x):
    cnt = 0
    while (x > 0):
        x %= bin(x).count('1')
        cnt += 1
    return cnt


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