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:
##a = int(stdin.readline().rstrip())
##b, c = [int(x) for x in stdin.readline().rstrip().split()]
##s = stdin.readline().rstrip()
##a = list(set(b))  重複を削除
##a = list(map(int,[int(x) for x in stdin.readline().rstrip().split()])) a[0, 1, 2, ...]
##a = [[0] * 2 for _ in range(n)]  a[0,0]
##v = [s[i: i+2] for i in range(0, len(s), 2)]
##  s="12345678" を v=["12","34","56","78"] にするイメージ
##s = "".join(list)リストを文字列に変換[""]は区切り文字
##a.sort(key=itemgetter(1))リストをソートできるよ(from operator import itemgetterが必要)
##sort_p = sorted(p) 昇順ソート

# -*- coding: utf-8 -*-
from sys import stdin
from operator import itemgetter
from collections import deque, Counter
import math
import pprint
from functools import reduce
import numpy as np
import random
import bisect
import copy
# stdin = open("sample.txt")


MOD = 1000000007
INF = float('inf')
alpha = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]

def keta(kazu): # 入力されたintを桁ごとに分解，リストで出力
    kazu_str = str(kazu)
    kazu_list = [int(kazu_str[i]) for i in range(0, len(kazu_str))]
    return kazu_list

def gcd(*numbers): # 最小公倍数
    return reduce(math.gcd, numbers)

def combination(m,n): # mCn
    
    if n > m:
        return 'すまん'
    return math.factorial(m) // (math.factorial(m-n) * math.factorial(n))

def pow_k(x,n):  # (x**n)の計算の高速化
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
    return K * x

def fact(n): # nの素因数分解の結果を辞書で出力 fuct(24) → {2: 3, 3: 1}
    arr = {}
    temp = n
    for i in range(2,int(n**0.5)+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr[i] = cnt
    if temp != 1:
        arr[temp] = 1
    if arr == {}:
        arr[n] = 1
    return arr

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

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

    
def main():
    N = int(stdin.readline().rstrip())
    X = stdin.readline().rstrip()
    Xlist = [0] * N
    for i in range(N):
        if X[i] == "1":
            if i == 0:
                now = "0" + X[1:]
            elif i == N-1:
                now = X[:-1] + "0"
            else:
                now = X[0:i] + "0" + X[i+1:]
        else:
            if i == 0:
                now = "1" + X[1:]
            elif i == N-1:
                now = X[:-1] + "1"
            else:
                now = X[0:i] + "1" + X[i+1:]
        Xlist[i] = int(now, 2)
    
    for i in range(N):
        print(f(Xlist[i]))
main()

Submission status: Time Limit Exceeded

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

def f(x):
    count = 0
    while x != 0:
        count += 1
        x %= popcount(x)
    return count

N = int(input())
X = "0b"+input()
X10 = int(X, 2)

for i in range(1, N+1):
    if X[i+1] == "0":
        diff = pow(2, N-i)
    else:
        diff = -pow(2, N-i)
    ans = f(X10 + diff)
    print(ans)

Submission status: Time Limit Exceeded

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

x = list(map(int, X))

num = int(X, 2)

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

def popcount(n):
    if n > 5000:
        nb = str(bin(n))
        xpop = list(map(int, nb[2:]))
        cpop = xpop.count(1)

        return n % cpop

    else:
        return popres[n-1]


for i in range(N):
    numt = num
    if x[i] == 0:
        numt += 2 ** (N - i - 1)
    else:
        numt -= 2 ** (N - i - 1)

    res = 0
    while numt > 0:
        numt = popcount(numt)
        res += 1
    print(res)

Submission status: Time Limit Exceeded

Solution code:
import math

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

N = 2 * 10 ** 5

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

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

  if X > N:
    counter += 1
    param = X % bit
  
  while True:
    if param == 0:
      break

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


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

val = int(x,2)

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

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

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=input()
t=int(x,2)
c=x.count('1')
m=[0]*n
k=1
while k<n: m[k]=1; k*=2
def popcount(x):
  x = x - ((x >> 1) & 0x5555555555555555)
  x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
  x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
  x = x + (x >> 8)
  x = x + (x >> 16)
  x = x + (x >> 32)
  return x & 0x0000007f
def f(x):
  if x==0: return 0
  if m[x]: return m[x]
  return f(x%popcount(x))+1
for i in range(n):
  if int(x[i]):
    d=c-1
    if d<1: print(0)
    else: print(f((t-pow(2,n-i-1,d))%d)+1)
  else:
    d=c+1
    print(f((t+pow(2,n-i-1,d))%d)+1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
X = str(input())
X_ten = int("0b" + X, 0)
num_one_X = X.count("1")

def get_mod_binary_shift_m(a, b, m):
    """
    :param a: dividend
    :param b: divisor
    :param m: maximum bit capacity
    :return: quotient
    """
    if a < b:
        return 0
    if b == 0:
        raise ZeroDivisionError

    q = 0
    sb = b << m
    rem = a  # remainder (init is dividend)
    while rem >= b:
        while sb > rem:
            sb = sb >> 1
            m = m - 1

        q = q + (1 << m)
        rem = rem - sb

    return rem

for i in range(N):
    diff_num = 2 ** (N - i - 1)
    diff_sign = 1 if X[i] == "0" else -1
    temp_X_ten = X_ten + (diff_num * diff_sign)
    temp_num_one_X = num_one_X + diff_sign
    temp_ans = 0
    while(temp_X_ten > 0):
        temp_X_ten = get_mod_binary_shift_m(temp_X_ten, temp_num_one_X, N - i)
        temp_num_one_X = bin(temp_X_ten).count("1")
        temp_ans += 1
    print(temp_ans)

Submission status: Time Limit Exceeded

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


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


dp = [0] * 1000000
an = []
for i in range(n - 1, -1, -1):
    num = (2 ** i) ^ x
    ans = 0
    bit_count_init = bc(num)
    while True:
        bit_count = bc(num)
        if num == 0:
            an.append(ans)
            dp[bit_count_init] = ans
            break
        num %= bit_count
        ans += 1
        if dp[num] != 0:
            an.append(dp[num] + ans)
            break

for i in an:
    print(i)

Submission status: Time Limit Exceeded

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

def f(n):
    return int(''.join(n),2)%(n.count("1"))

for i in range(N):
    ans = 0
    Xi = list(X)
    if Xi[i]=="0":
        Xi[i]="1"
    else:
        Xi[i]="0"
    # pc = Xi.count("1")
    while(Xi.count("1")!=0):
        Xi = format(f(Xi),'b')
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
counts=[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, 2, 2, 2, 3, 2, 2, 2, 2, 1, 2, 1, 3, 2, 2, 2, 1, 1, 2, 3, 3, 1, 2, 2, 3, 2, 3, 1, 2, 1, 2, 1, 2, 1, 2, 2, 3, 1, 2, 1, 3, 2, 2, 2, 3, 1, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 3, 3, 1, 2, 1, 3, 2, 2, 2, 2, 1, 2, 2, 2, 1, 3, 2, 2, 2, 2, 2, 2, 1, 2, 2, 3, 1, 1, 2, 2, 3, 3, 2, 2, 1, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 3, 1, 1, 2, 3, 2, 2, 2, 2, 1, 3, 2, 3, 1, 2, 3, 3, 1, 3, 1, 2, 2, 2, 2, 2, 1, 2, 1, 3, 1, 3, 2, 2, 2, 3, 2, 2, 1, 2, 2, 3, 2, 3, 1, 2, 3, 3, 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, 3, 1, 1, 2, 3, 1, 2, 2, 3, 2, 2, 2, 1, 2, 2, 2, 2, 1, 2, 2, 3, 2, 2, 2, 2, 1, 2, 1, 3, 1, 3, 2, 3, 2, 3, 1, 2, 1, 1, 2, 3, 1, 2, 2, 2, 2, 2, 2, 2, 1, 3, 2, 3, 1, 2, 2, 2, 1, 2, 2, 2, 1, 1, 2, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 2, 3, 3, 1, 2, 2, 3, 2, 3, 1, 3, 1, 2, 1, 3, 2, 2, 2, 2, 2, 3, 1, 2, 2, 3, 2, 3, 1, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 3, 3, 2, 2, 2, 3, 1, 1, 2, 3, 1, 2, 1, 3, 2, 3, 1, 2, 2, 2, 2, 2, 1, 2, 2, 3, 1, 1, 2, 2, 3, 3, 2, 2, 1, 3, 2, 3, 2, 3, 1, 3, 1, 3, 2, 2, 1, 2, 3, 3, 2, 2, 2, 2, 1, 3, 2, 3, 1, 2, 3, 3, 1, 3, 1, 2, 1, 1, 2, 3, 3, 2, 2, 2, 2, 3, 1, 2, 2, 2, 2, 3, 1, 2, 2, 3, 2, 3, 1, 2, 3, 3, 2, 2, 1, 3, 2, 3, 2, 3, 1, 2, 2]

n=int(input())
X=input()
num=int(X,2)
c=X.count('1')
for i in range(n):
    tmpn=num
    tmp1=c
    if X[i]=='0':
        tmpn+=2**(n-i-1)
        tmp1+=1
    else:
        tmpn-=2**(n-i-1)
        tmp1-=1
    count=0
    while tmpn>0:
        if tmpn<501:
            count+=counts[tmpn]
            break
        tmpn%=tmp1
        tmp1=bin(tmpn).count("1")
        count+=1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = int(input(),2)
for i in range(1,n+1):
    y = (2**(n-i))^x
    p = 0
    while(y != 0):
        z = bin(y)
        q = len(str(bin(y)))
        r = 0
        for j in range(2,q):
            if(z[j] == '1'):
                r += 1
        y %= r
        p += 1
    print(p)

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

value_x= int(x, 2)
#print('!!', value_x)
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:
import copy
N = int(input())
X = list(input())
def popf(num):
    count = 0
    bin_str = bin(num)
    for i in range(len(bin_str)):
        if bin_str[i] == '1':
            count += 1
    return num % count
for i in range(N):
    Y = copy.copy(X)
    if Y[i] == '1':
        Y[i] = '0'
    else:
        Y[i] = '1'
    bn = ''.join(Y)
    num = int(bn, 2)
    count = 0
    while num != 0:
        num = popf(num)
        count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
X=input()
xx=int(X)
xxx=str(xx)
sa=N-len(xxx)
X_len=len(X)
a=0
for i in range(sa,N):
    a=int(X[i])*(2**(N-i-1))+a





fx=[-1]*(2*(10**5))
for i in range(X_len):
    ans=0
    if(X[i]=='0'):
        b=a+2**(X_len-i-1)
    else:
        b=a-2**(X_len-i-1)

    while(b!=0):

        fx=b%str(format(b,'b')).count('1')
        ans=ans+1
        b=fx

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input().strip())
X = [int(v) for v in input().strip()]



def popcount(bins):
    return sum(bins)


def f(bins):
    # print(bins)
    count = 0
    x = get_num(bins)
    while x != 0:
        pc = popcount([int(v) for v in bins])
        x = x % pc
        bins = get_bin(x)
        count += 1
    return count

def get_bin(n):
    return bin(n)[2:]


def get_num(bins):
    bins = "".join([str(v) for v in bins])
    return int(bins, 2)


for i in range(N):
    # print(X)
    X[i] = int(not(X[i]))

    print(f(X))

    X[i] = int(not(X[i]))

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
    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))
        ans += 1
    return ans

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

Submission status: Time Limit Exceeded

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

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

    popcount = mozi.count('1')
    num = int(mozi, 2)
    while num != 0:
        num = num % popcount
        popcount = (str(bin(num))).count('1')
        cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def func(X):
    cnt = 0
    while int(X) != 0:
        cnt += 1
        X =bin(int(X,2) % X.count('1'))[2:]
    return cnt

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

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

Submission status: Time Limit Exceeded

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

d = {}
def popcount(s):
    if not s in d:
        cnt = 0
        for c in s:
            if c == '1':
                cnt += 1
        d[s] = cnt
    return d[s]

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

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

Submission status: Time Limit Exceeded

Solution code:
import copy
n=int(input())
x=list(input())
b=[]
for i in range(2**19):
  b.append(format(i,'0'+str(19)+'b'))
ct=[0]*(n+1)
for i in range(1,n):
  ct1=0
  for j in range(len(b[i])):
    if b[i][j]=='1':
      ct1+=1
  ct[i]=i%ct1

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

moda=[1]
modb=[1]
modc=[1]
for i in range(n-1):
  if CT>=2:
    moda.append(moda[-1]*2%(CT-1))
  if CT>=1:
    modb.append(modb[-1]*2%CT)
  modc.append(modc[-1]*2%(CT+1))


x.reverse()
za=0
zb=0
zc=0
for i in range(n):
  if x[i]=='1':
    if CT>=2:
      za+=moda[i]
      za%=(CT-1)
    if CT>=1:
      zb+=modb[i]
      zb%=CT
    zc+=modc[i]
    zc%=(CT+1)
x.reverse()
moda.reverse()
modc.reverse()

for i in range(n):
  y=copy.copy(x)
  y2=y[i]
  y[i]=str(1-int(y[i]))
  ct1=0
  for j in range(n):
    if y[j]=='1':
      ct1+=1
  if ct1==0:
    print(0)
  else:
    if y2=='1':
      z=za
      z-=moda[i]
      z%=ct1
    else:
      z=zc
      z+=modc[i]
      z%=ct1
    
    ans=1
    while z!=0:
      z=ct[z]
      ans+=1
    print(ans)