Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3

from pprint import pprint
from collections import deque, defaultdict
import itertools
import math
import sys

sys.setrecursionlimit(10 ** 6)
INF = float('inf')


N = int(input())
X = bin(int(input(), 2))
# print(f'X = {X}')


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


def popcount(n):
    if n == 0:
        memo_p[0] = 0
        return 0
    if n == 1:
        memo_p[1] = 1
        return 1
    if n in memo_p.keys():
        return memo_p[n]
    memo_p[n] = count_bit(n)
    return memo_p[n]


def f(n):
    # print(f'called f[{n}]')
    if n == 0:
        memo_f[0] = 0
        return 0
    if n == 1:
        memo_f[1] = 1
        return 1
    if n == 2:
        memo_f[2] = 1
        return 1
    if n in memo_f.keys():
        return memo_f[n]
    # print(f'{n} is not found')
    r = n % popcount(n)
    # print(f'popcount = {popcount(n)}')
    # print(f'r = {r}')
    memo_f[n] = f(r) + 1
    return memo_f[n]


memo_p = {}
memo_f = {}

for i in range(N):
    # print(f'i = {i}')
    num = None
    if int(X, 2) & (1 << (N-1-i)):
        num = int(X, 2) - 2 ** (N-1-i)
    else:
        num = int(X, 2) + 2 ** (N-1-i)
    # print(f'num = {num}')
    print(f(num))


Fixed submission:
#!/usr/bin/env python3

from pprint import pprint
import sys

sys.setrecursionlimit(10 ** 6)
INF = float('inf')


n = int(input())
x = input()
x_pc = x.count('1')
x_pc_plus = x_pc + 1
x_pc_minus = x_pc - 1

# 2 ** i % x_pc_plus, 2 ** i % x_pc_minus を予め計算しておく
r_plus_list = [pow(2, i, x_pc_plus) for i in range(n+1)]
r_minus_list = [0] * (n+1)
if x_pc_minus > 0:
    r_minus_list = [pow(2, i, x_pc_minus) for i in range(n+1)]

x = x[::-1]
r_plus = 0
r_minus = 0
for i in range(n):
    if x[i] == '1':
        r_plus += r_plus_list[i]
        r_minus += r_minus_list[i]

for i in range(n-1, -1, -1):
    if x[i] == '0':
        diff = (r_plus + r_plus_list[i]) % x_pc_plus
    elif x_pc_minus >= 1:
        diff = (r_minus - r_minus_list[i]) % x_pc_minus
    else:
        print(0)
        continue
    ans = 1
    while diff > 0:
        diff = diff % bin(diff).count('1')
        ans += 1
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3

from pprint import pprint
from collections import deque, defaultdict
import itertools
import math
import sys

sys.setrecursionlimit(10 ** 6)
INF = float('inf')


N = int(input())
X = bin(int(input(), 2))
# print(f'X = {X}')


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


def popcount(n):
    if n == 0:
        memo_p[0] = 0
        return 0
    if n == 1:
        memo_p[1] = 1
        return 1
    if n in memo_p.keys():
        return memo_p[n]
    memo_p[n] = count_bit(n)
    return memo_p[n]


def f(n):
    # print(f'called f[{n}]')
    if n == 0:
        memo_f[0] = 0
        return 0
    if n == 1:
        memo_f[1] = 1
        return 1
    if n == 2:
        memo_f[2] = 1
        return 1
    if n in memo_f.keys():
        return memo_f[n]
    # print(f'{n} is not found')
    r = n % popcount(n)
    # print(f'popcount = {popcount(n)}')
    # print(f'r = {r}')
    memo_f[n] = f(r) + 1
    return memo_f[n]


memo_p = {}
memo_f = {}

for i in range(N):
    # print(f'i = {i}')
    num = None
    if int(X, 2) & (1 << (N-1-i)):
        num = int(X, 2) - 2 ** (N-1-i)
    else:
        num = int(X, 2) + 2 ** (N-1-i)
    # print(f'num = {num}')
    print(f(num))


Fixed submission:
#!/usr/bin/env python3

from pprint import pprint
import sys

sys.setrecursionlimit(10 ** 6)
INF = float('inf')


n = int(input())
x = input()
x_pc = x.count('1')
x_pc_plus = x_pc + 1
x_pc_minus = x_pc - 1

# 2 ** i % x_pc_plus, 2 ** i % x_pc_minus を予め計算しておく
r_plus_list = [pow(2, i, x_pc_plus) for i in range(n+1)]
r_minus_list = [0] * (n+1)
if x_pc_minus > 0:
    r_minus_list = [pow(2, i, x_pc_minus) for i in range(n+1)]

x = x[::-1]
r_plus = 0
r_minus = 0
for i in range(n):
    if x[i] == '1':
        r_plus += r_plus_list[i]
        r_minus += r_minus_list[i]

for i in range(n-1, -1, -1):
    if x[i] == '0':
        diff = (r_plus + r_plus_list[i]) % x_pc_plus
    elif x_pc_minus >= 1:
        diff = (r_minus - r_minus_list[i]) % x_pc_minus
    else:
        print(0)
        continue
    ans = 1
    while diff > 0:
        diff = diff % bin(diff).count('1')
        ans += 1
    print(ans)