Problem:
 Score : 400 points    Problem Statement Let \mathrm{popcount}(n) be the number of 1 s 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

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count




N = I()
S = S()

from functools import lru_cache
def count(X):
  if X == 0:
    return 0
  else:
    return count(X%count_bit(X))+1


MOD = 0
for i in range(N):
  if S[i] == "1":
    MOD += 1

FUEAMARI = 0
HERIAMARI = 0
for i in range(N):
  if S[i] == "1":
    FUEAMARI += pow(2,N-1-i,MOD+1)
    if MOD!=1:
      HERIAMARI += pow(2,N-1-i,MOD-1)
for i in range(N):
  if S[i] == "1":
    if MOD!=1:
      X = (HERIAMARI-pow(2,N-1-i,MOD-1))%(MOD-1)
      print(count(X)+1)
    else:
      print(0)
  else:
    X = (FUEAMARI+pow(2,N-1-i,MOD+1))%(MOD+1)
    print(count(X)+1)

Solution (Python):
import sys

def popcount(i):
    K = i
    d = 0
    while K > 0:
        d += K % 2
        K //= 2
    return d

def solve():
    input = sys.stdin.readline
    N = int(input())
    X = input().strip("\n")
    countOne = X.count("1")
    modM = [0] * N
    modP = [0] * N
    minusS, plusS = 0, 0
    for i in range(N):
        if X[N-i-1] == "1":
            if countOne > 1: 
                modM[i] = pow(2, i, countOne - 1)
                minusS += modM[i]
                minusS %= (countOne - 1)
            modP[i] = pow(2, i, countOne + 1)
            plusS += modP[i]
            plusS %= (countOne + 1)
    Ans = [0] * N
    for i in range(N):
        if X[i] == "0":
            start = (plusS + pow(2, N - i - 1, countOne + 1)) % (countOne + 1)
            Ans[i] = 1
            while start > 0:
                d = popcount(start)
                Ans[i] += 1
                start %= d
        else:
            if countOne > 1:
                start = (minusS - modM[N - i -1]) % (countOne - 1)
                Ans[i] = 1
                while start > 0:
                    d = popcount(start)
                    Ans[i] += 1
                    start %= d
    print(*Ans, sep = "\n")

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
n = int(input())
s = input()
x = int(s, 2)

popcnt = 0
for c in s:
    if c == '1':
        popcnt += 1

if popcnt == 0:
    for i in range(n):
        print(1)
    exit()
if popcnt == 1:
    if s[-1] == '0':
        for i in range(n - 1):
            if s[i] == '1':
                print(0)
            else:
                print(1)
        print(2)
    else:
        for i in range(n - 1):
            print(2)
        print(0)
    exit()

xm = x % (popcnt - 1)
xp = x % (popcnt + 1)


def pp(k):
    cnt = 0
    while k > 0:
        cnt += k & 1
        k >>= 1
    return cnt


for i in range(n):
    if s[i] == '0':
        
        rem = xp + pow(2, n - 1 - i, popcnt + 1)
        rem %= popcnt + 1
        cnt = 1
        while rem != 0:
            rem %= pp(rem)
            cnt += 1
        print(cnt)
    else:
        
        rem = xm - pow(2, n - 1 - i, popcnt - 1)
        rem %= popcnt - 1
        cnt = 1
        while rem != 0:
            rem %= pp(rem)
            cnt += 1
        print(cnt)

Solution (Python):
n = int(input())
x = input()
val = int(x, 2)

cnt1 = x.count("1")
p_cnt = cnt1 + 1
m_cnt = cnt1 - 1
p_amari = val % (cnt1 + 1)
if cnt1 - 1 != 0:
    m_amari = val % (cnt1 - 1)
else:
    m_amari = 0


for i in range(n):
    ans = 0
    if x[i] == "0":
        
        amari = p_amari + pow(2, n - i - 1, p_cnt)
        amari %= p_cnt
        ans += 1
    elif x[i] == "1":
        
        if cnt1 - 1 == 0:
            print(0)
            continue
        amari = m_amari - pow(2, n - i - 1, m_cnt)
        amari %= m_cnt
        ans += 1
    while amari != 0:
        amari %= bin(amari).count("1")
        ans += 1
    print(ans)

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


def count(n):
    ans = 0
    while n:
        ans += n % 2
        n //= 2
    return ans


ma = 5*10**5
dp = [0] * ma
for i in range(1, ma):
    dp[i] = dp[i % count(i)]+1

c = x.count("1")
a = int(x, 2) % (c+1)

if c==1:
    for i in range(n):
        if x[i] == "0":
            print(dp[(a + pow(2, n-i-1, c+1)) % (c+1)] + 1)
        else:
            print(0)
    exit()

b = int(x, 2) % (c-1)
for i in range(n):
    if x[i] == "0":
        print(dp[(a + pow(2,n-i-1,c+1))%(c+1)] + 1)
    else:
        print(dp[(b - pow(2, n-i-1, c-1)) % (c-1)] + 1)

Solution (Python):
N=int(input())
X=input()
Y=int(X,2)
Z=Y
C=X.count('1')
if C==1:
  for i in range(N):
    if X[i]=='1':
      print(0)
    elif i==N-1:
      print(2)
    else:
      print(1)
  exit()
Y,Z=Y%(C+1),Z%(C-1)
def f(x):
  if x==0:
    return 0
  return 1+f(x%bin(x).count('1'))

for i in range(N):
  if X[i]=='1':
    print(1+f((Z-pow(2,N-i-1,C-1))%(C-1)))
  else:
    print(1+f((Y+pow(2,N-i-1,C+1))%(C+1)))

Solution (Python):
n = int(input())
x = list(reversed(list(map(int, input()))))
s = sum(x)
md = [s + 1, s - 1]
bs = [0, 0]
for i in range(2):
    if not md[i]:
        continue
    t = 1
    for j in range(n):
        if x[j]:
            bs[i] = (bs[i] + t) % md[i]
        t = t * 2 % md[i]
def solve(u):
    ans = 0
    while u:
        u = u % bin(u).count('1')
        ans += 1
    return ans
for i in range(n - 1, -1, -1):
    if not md[x[i]]:
        print(0)
        continue
    dt = pow(2, i, md[x[i]]) * (-1 if x[i] else 1)
    print(solve((bs[x[i]] + dt) % md[x[i]]) + 1)