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):
def p(x):
  return bin(x).count('1')

def f(x):
  if x == 0:
    return 0
  return f(x%p(x)) + 1

N = int(input())
X = input()
cnt = X.count('1')
x = int(X,2)
a = x % (cnt + 1)
if cnt != 1:
  b = x % (cnt - 1)

for i in range(N):
  if X[i] == '0':
    k = a
    k += pow(2,N-i-1,cnt+1)
    k %= cnt+1
  else:
    if cnt == 1:
      print(0)
      continue
    k = b
    k -= pow(2,N-i-1,cnt-1) 
    k %= cnt-1  
  print(f(k)+1)

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

l = [int(i) for i in s2]
p = sum(l)
s10 = int(s2,2)
if p == 1:
    ans1 = s10%(p+1)
    l1 = [0]*(n+1)
    l1[0] = 1
    for i in range(1,n+1):
        l1[i] = (l1[i-1]*2)%(p+1)
    for i in range(n):
        if l[i]:
            print(0)
        else:
            first = (ans1 + l1[n-i-1])%(p+1)
            ans = 1
            while first:
                mod = 0
                for j in range(len(bin(first))-2):
                    mod += first >> j & 1
                first %= mod
                ans += 1
            print(ans)
    quit()
if p == 0:
    for i in range(n):
        print(1)
    quit()

ans1 = s10%(p+1)
ans2 = s10%(p-1)
l1 = [0]*(n+1)
l2 = [0]*(n+1)
l1[0] = 1
l2[0] = 1
for i in range(1,n+1):
    l1[i] = (l1[i-1]*2)%(p+1)
    l2[i] = (l2[i-1]*2)%(p-1)
first = []
for i in range(n):
    if l[i]:
        first.append((ans2-l2[n-i-1])%(p-1))
    else:
        first.append((ans1+l1[n-i-1])%(p+1))


for i in range(n):
    if first[i] == 0:
        print(1)
        continue
    x = first[i]
    ans = 1
    while x:
        mod = 0
        for j in range(len(bin(x))-2):
            mod += x >> j & 1
        x = x%mod
        ans += 1
    print(ans)

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


n=int(input())
x=input()
num=int(x,2)
cnt=popcount(num)

mod1=num%(cnt+1)
mod2=num%(cnt-1) if cnt-1!=0 else 0

for i in range(n):
    if x[i]=="0":
        ans=(mod1+pow(2,n-i-1,cnt+1))%(cnt+1)
    else:
        if cnt-1==0:
            print(0)
            continue
        else:
            ans=(mod2-pow(2,n-i-1,cnt-1))%(cnt-1)
    point=1
    while ans!=0:
        ans %=popcount(ans)
        point +=1
    print(point)

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

c = x.count('1')
cp = c+1
cn = c-1

rp = [0] * n
if cp > 1:
    rp[0] = 1
rn = [0] * n
if cn > 1:
    rn[0] = 1
for i in range(1, n):
    rp[i] = (rp[i-1] * 2) % cp
    if cn > 0:
        rn[i] = (rn[i-1] * 2) % cn

xp = 0
xn = 0
for i in range(n):
    xx = x[i]
    if xx == '1':
        xp = (xp + rp[n-i-1]) % cp
        if cn > 0:
            xn = (xn + rn[n-i-1]) % cn

for i in range(n):
    o = 1
    if x[i] == '1':
        if cn == 0:
            print(0)
            continue
        xx = (xn-rn[n-i-1]) % cn
    else:
        xx = (xp+rp[n-i-1]) % cp
    while xx > 0:
        cc = bin(xx)[2:].count('1')
        xx = xx % cc
        o += 1
    print(o)

Solution (Python):
N = int(input())
X = input()
val = int(X,2)
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()


def f(x):
  if x==0: return 0
  return 1 + f(x % bin(x).count("1"))


Y = val%(C+1)
if C-1 != 0:
  Z = val%(C-1)
else:
  Z = 0

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

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()

n=int(input())
xs=input()
xj=xs.count("1")

x=int(xs,2)
xip=x%(xj+1)
if xj!=1:
    xim=x%(xj-1)

for i in range(n-1,-1,-1):
    if xs[n-1-i]=="0":
        pxi=xj+1
        i2=pow(2,i,pxi)
        xi=(xip+i2)%pxi
    elif xj==1:
        print(0)
        continue
    else:
        pxi=xj-1
        i2=pow(2,i,pxi)
        xi=(xim-i2)%pxi
    xi=xi%pxi
    if xi==0:
        print(1)
        continue
    icnt=1
    while xi>0:

        icnt+=1
        xi=xi%(bin(xi).count("1"))
    print(icnt)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()

n=int(input())
xs=input()
xj=xs.count("1")

x=int(xs,2)
xip=x%(xj+1)
if xj!=1:
    xim=x%(xj-1)

for i in range(n-1,-1,-1):
    if xs[n-1-i]=="0":
        pxi=xj+1
        i2=pow(2,i,pxi)
        xi=(xip+i2)%pxi
    elif xj==1:
        print(0)
        continue
    else:
        pxi=xj-1
        i2=pow(2,i,pxi)
        xi=(xim-i2)%pxi
    xi=xi%pxi
    if xi==0:
        print(1)
        continue
    icnt=1
    while xi>0:

        icnt+=1
        xi=xi%(bin(xi).count("1"))
    print(icnt)

Solution (Python):
import sys
read = sys.stdin.read
from collections import defaultdict
def main():
    n = int(input())
    x = list(input())
    
    if n == 1:
        if x[0] == '1':
            print(0)
        else:
            print(1)
        sys.exit()
    
    x10 = int("".join(x), 2)
    xcount1 = x.count('1')
    
    mod2plus = [0] * n
    mod2plus[0] = (1 % (xcount1+1)) 
    for j1 in range(1, n):
        mod2plus[j1] = (mod2plus[j1 - 1] * 2) % (xcount1+1)
    mod2minus = [0] * n
    if xcount1 > 1:
        mod2minus[0] = 1
        for j1 in range(1, n):
            mod2minus[j1] = (mod2minus[j1 - 1] * 2) % (xcount1-1)
    
    modx_plus = x10 % (xcount1 + 1)
    if xcount1 == 1:
        modx_minus = 0
    else:
        modx_minus = x10 % (xcount1 - 1)
    popcount = defaultdict(int)
    for i1 in range(n):
        if x[i1] == '1':
            if xcount1 == 1:
                print(0)
                continue
            else:
                x3 = modx_minus - mod2minus[n - 1 - i1]
                if x3 < 0:
                    x3 += (xcount1 - 1)
                elif x3 > (xcount1 - 1):
                    x3 -= (xcount1 - 1)
                elif x3 == (xcount1 - 1):
                    print(1)
                    continue
        else:
            x3 = modx_plus + mod2plus[n - 1 - i1]
            if x3 < 0:
                x3 += (xcount1 + 1)
            elif x3 > (xcount1 + 1):
                x3 -= (xcount1 + 1)
            elif x3 == (xcount1 + 1):
                print(1)
                continue
        r = 1
        while x3:
            r += 1
            if popcount[x3] == 0:
                p = bin(x3).count('1')
                popcount[x3] = p
                x3 = x3 % p
            else:
                x3 = x3 % popcount[x3]
        print(r)

if __name__ == '__main__':
    main()

Solution (Python):


N = int(input())
X = input()
popcount_X = X.count('1')
X_ = int(X, 2)

X_mod_minus = X_%(popcount_X-1) if popcount_X > 1 else -1
X_mod_plus = X_%(popcount_X+1)
for i in range(N):
    if X[i] == '0':
        popcount = popcount_X+1
        X_i = (X_mod_plus + pow(2, N-i-1, popcount))%(popcount)
    else:
        if X_mod_minus == -1:
            print(0)
            continue
        popcount = popcount_X-1
        X_i = (X_mod_minus - pow(2, N-i-1, popcount))%(popcount)
    ans = 1
    while X_i > 0:
        X_i %= bin(X_i).count('1')
        ans += 1
    print(ans)

Solution (Python):
n = int(input())
s = input()
int_s = [int(i) for i in s]
pc = s.count('1')

def f(x):
    bi = bin(x)
    pc = bi.count('1')
    cnt = 1
    while True:
        if x == 0:
            break
        x = x % pc
        bi = bin(x)
        pc = bi.count('1')
        cnt += 1
    return cnt

num_pl = 0
for i in range(n):
    num_pl = (num_pl*2) % (pc+1)
    num_pl += int_s[i]

num_mi = 0
for i in range(n):
    if pc-1 <= 0:
        continue
    num_mi = (num_mi*2) % (pc-1)
    num_mi += int_s[i]

ans = [0]*n
pc_pl, pc_mi = pc+1, pc-1
r_pl, r_mi = 1, 1
for i in range(n-1, -1, -1):
    if int_s[i] == 0:
        num = num_pl
        num = (num+r_pl) % pc_pl
    else:
        num = num_mi
        if pc_mi <= 0:
            continue
        num = (num-r_mi+pc_mi) % pc_mi

    ans[i] = f(num)
    r_pl = (r_pl*2) % pc_pl
    if pc_mi <= 0:
        continue
    r_mi = (r_mi*2) % pc_mi
     
print(*ans, sep='\n')

Solution (Python):
def popcount(n):
    ret = 0
    while n > 0:
        ret += n & 1
        n >>= 1
    return ret

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

def mod(x, d):
    '''
    x % d where x: string, d: int
    '''
    rem = 0
    for i in range(len(x)):
        divd = (rem << 1) + int(x[i], 2)
        rem = divd % d

    return rem

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

popx = X.count('1')
qp = mod(X, popx + 1)  
if popx - 1 > 0:
    qm = mod(X, popx - 1)   

ans = []
pow2p = pow2m = 1
for i in range(N):
    if X[N - 1 - i] == '1':
        if popx == 1: 
            ans.append(0)
        else:
            next = (qm - pow2m) % (popx - 1)
            ans.append(1 + f(next))
    else:  
        next = (qp + pow2p) % (popx + 1)
        ans.append(1 + f(next))

    pow2p = pow2p * 2 % (popx + 1)
    if popx > 1:
        pow2m = pow2m * 2 % (popx - 1)

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

Solution (Python):
def popcount(n):
    bit_count = bin(n).count('1')
    n = n % bit_count 
    return n

if __name__ == "__main__":
    import sys 

    readline = sys.stdin.readline 

    N = int(input())
    X = readline()
    bit_count = X.count('1')
    mod1 = int(X, 2) % (bit_count + 1)
    mod2 = int(X, 2) % (bit_count - 1) if (bit_count - 1) != 0 else 0

    for i in range(N):
        if X[i] == '0':
            X_rest = (mod1 + pow(2, N - 1 - i, bit_count + 1)) % (bit_count + 1)
        else:
            if bit_count - 1 != 0:
                X_rest = (mod2 - pow(2, N - 1 - i, bit_count - 1)) % (bit_count - 1)
            else:
                print(0)
                continue

        counter = 1
        while X_rest != 0:
            X_rest = popcount(X_rest)
            counter += 1
        print(counter)

Solution (Python):
import sys
readline = sys.stdin.readline

N = int(readline())
X = readline().rstrip()

X0 = int(X, 2)
count1 = X.count("1")

X0mod0to1 = X0 % (count1 + 1) 
if count1 > 1:
  X0mod1to0 = X0 % (count1 - 1) 
else:
  X0mod1to0 = 0

from collections import defaultdict
dp = defaultdict(int)
dp[0] = 0
def f(x): 
  if x in dp:
    return dp[x]
  pc = bin(x).count("1")
  val = f(x % pc) + 1
  dp[x] = val
  return val
  
val0to1 = 1
val1to0 = 1
ans = [-1] * N

for i in range(N - 1, -1, -1): 
  if X[i] == "0": 
    pat = (X0mod0to1 + val0to1 % (count1 + 1)) % (count1 + 1)
    ans[i] = f(pat) + 1
  elif X[i] == "1": 
    if count1 > 1:
      pat = (X0mod1to0 - val1to0 % (count1 - 1)) % (count1 - 1)
      ans[i] = f(pat) + 1
    else:
      ans[i] = 0
  val0to1 = val0to1 * 2 % (count1 + 1)
  if count1 != 1:
    val1to0 = val1to0 * 2 % (count1 - 1)

print(*ans, sep = "\n")

Solution (Python):
import sys
readline = sys.stdin.readline

N = int(readline())
X = readline().rstrip()

X0 = int(X, 2)
count1 = X.count("1")

X0mod0to1 = X0 % (count1 + 1) 
if count1 > 1:
  X0mod1to0 = X0 % (count1 - 1) 
else:
  X0mod1to0 = 0

from collections import defaultdict
dp = defaultdict(int)
dp[0] = 0
def f(x): 
  if x in dp:
    return dp[x]
  pc = bin(x).count("1")
  val = f(x % pc) + 1
  dp[x] = val
  return val
  
val0to1 = 1
val1to0 = 1
ans = [-1] * N

for i in range(N - 1, -1, -1): 
  if X[i] == "0": 
    pat = (X0mod0to1 + val0to1 % (count1 + 1)) % (count1 + 1)
    ans[i] = f(pat) + 1
  elif X[i] == "1": 
    if count1 > 1:
      pat = (X0mod1to0 - val1to0 % (count1 - 1)) % (count1 - 1)
      ans[i] = f(pat) + 1
    else:
      ans[i] = 0
  val0to1 = val0to1 * 2 % (count1 + 1)
  if count1 != 1:
    val1to0 = val1to0 * 2 % (count1 - 1)

print(*ans, sep = "\n")

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

n = int(input())
s = input()

num = int(s, 2) 
opc = s.count('1') 


if opc > 1:
    num1 = num % (opc - 1)
else:
    num1 = 0
num0 = num % (opc + 1)

for i in range(n):
    if s[i] == '1':
        if opc == 1:
            print(0)
            continue
        tmp = (num1 - pow(2, n - 1 - i, opc - 1)) % (opc - 1)
    else:
        tmp = (num0 + pow(2, n - 1 - i, opc + 1)) % (opc + 1)

    
    ans = 1
    while tmp > 0:
        tmp %= bin(tmp).count('1')
        ans += 1
    print(ans)

Solution (Python):
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
s0 = int(x,2)%(c+1)
if c <= 1:
    s1 = 0
else:
    s1 = int(x,2)%(c-1)
for i in range(n):
    sw = 0
    if x[i] == "0":
        d = c + 1
        z = (s0 + pow(2,n-i-1,d))%d
    else:
        d = c - 1
        if d == 0:
            z = 0
            sw = 1
        else:
            z = (s1 - pow(2,n-i-1,d))%d
    ans = 1
    p = bin(z)
    e = 0
    for A in str(p):
        if A == "1":
            e += 1
    d = e
    if sw == 1:
        ans = 0
    else:
        while z:
            z,d = func(z,d)
            ans += 1
    print(ans)

Solution (Python):
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def f(N):
    res = 0
    while N != 0:
        b = format(N, "b").count("1")
        N %= b
        res += 1
    return res


def main():
    N = int(input())
    X = input().strip()
    K = X.count("1")

    A = [(1, 1)]
    for i in range(N):
        a, b = A[-1]
        A.append(((a * 2) % (K - 1) if K != 1 else 0, (b * 2) % (K + 1)))

    B = [0, 0]
    for i, b in enumerate(X[::-1]):
        if b == "0":
            continue
        if K != 1:
            B[0] += A[i][0]
            B[0] %= K - 1
        B[1] += A[i][1]
        B[1] %= K + 1

    res = [0] * N
    for i, b in enumerate(X[::-1]):
        if b == "0":
            res[i] = (B[1] + A[i][1]) % (K + 1)
        else:
            if K == 1:
                res[i] = 0
                continue
            res[i] = (B[0] - A[i][0]) % (K - 1)
        res[i] = f(res[i]) + 1

    for r in res[::-1]:
        print(r)


if __name__ == "__main__":
    main()

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

count = x.count('1')
one_count = count - 1
zero_count = count + 1

one_mod = 0
zero_mod = 0
for b in x:
    if one_count:
        one_mod = (one_mod * 2 + int(b)) % one_count
    zero_mod = (zero_mod * 2 + int(b)) % zero_count

f = [0] * 2000001
pop_count = [0] * 200001
for i in range(1, 200001):
    pop_count[i] = pop_count[i//2] + i % 2
    f[i] = f[i % pop_count[i]] + 1

for i in range(n):
    if x[i] == '1':
        if one_count:
            nxt = one_mod
            nxt -= pow(2, n-i-1, one_count)
            nxt %= one_count
            print(f[nxt] + 1)
        else:
            print(0)
    if x[i] == '0':
        nxt = zero_mod
        nxt += pow(2, n-i-1, zero_count)
        nxt %= zero_count
        print(f[nxt] + 1)

Solution (Python):
n = int(input())
x = input()
a = x.count('1')
b = int(x,2)

ary = [None for i in range(200010)]
ary[0] = 0

def f(n):
  if ary[n] is not None:
    return ary[n]
  b = bin(n).count('1')
  r = 1 + f(n%b)
  ary[n] = r
  return ary[n]

a1 = a + 1
a0 = a - 1
for i in range(200010):
  f(i)








c1 = b%a1
if a0 != 0:
  c0 = b%a0
for i in range(n-1, -1, -1):
  if x[n-1-i] == '0':
    
    y = c1 + pow(2,i,a1)
    y %= a1
    print (ary[y]+1)
  else:
    if a0 != 0:
      y = c0 - pow(2,i,a0)
      y %= a0
      print (ary[y]+1)
    else:
      print (0)

Solution (Python):
n = int(input())
x = input()
a = x.count('1')
b = int(x,2)


ary = [None for i in range(200010)]
ary[0] = 0

def f(n):
  if ary[n] is not None:
    return ary[n]
  b = bin(n).count('1')
  r = 1 + f(n%b)
  ary[n] = r
  return ary[n]


a1 = a + 1
a0 = a - 1
for i in range(200010):
  f(i)


one = [1] * 200010
zero = [1] * 200010
for i in range(1, 200010):
    if a0 != 0:
        one[i] = one[i-1] * 2 % a0
    zero[i] = zero[i-1] * 2 % a1


ans = [0 for i in range(n)]
c1 = b%a1
if a0 != 0:
  c0 = b%a0
for i in range(n-1, -1, -1):
  if x[n-1-i] == '0':
    y = c1 + zero[i]
    
    y %= a1
    print (ary[y]+1)
  else:
    if a0 != 0:
      y = c0 - one[i]
      y %= a0
      print (ary[y]+1)
    else:
      print (0)

Solution (Python):

import sys


buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_str():
    return readline().strip()


def slv(N, X):
    C = X.count('1')
    cmr = 0
    cpr = 0
    for b in X:
        b = int(b)
        cpr = ((cpr * 2) + b) % (C+1)
        if C-1 != 0:
            cmr = ((cmr * 2) + b) % (C-1)

    ans = []
    for i in range(N):
        t = 1
        if X[i] == '0':
            x = (cpr + pow(2, N-i-1, C+1)) % (C+1)
        elif X[i] == '1' and C-1 != 0:
            x = (cmr - pow(2, N-i-1, C-1)) % (C-1)
        else:
            x = 0
            t = 0

        while x != 0:
            x %= bin(x).count('1')
            t += 1

        ans.append(t)

    return ans


def main():
    N = read_int()
    X = read_str()
    print(*slv(N, X), sep='\n')


if __name__ == '__main__':
    main()

Solution (Python):

import sys


buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_str():
    return readline().strip()


def slv(N, X):
    C = X.count('1')
    cmr = 0
    cpr = 0
    for b in X:
        b = int(b)
        cpr = ((cpr * 2) + b) % (C+1)
        if C-1 != 0:
            cmr = ((cmr * 2) + b) % (C-1)

    ans = []
    for i in range(N):
        t = 0
        if X[i] == '0':
            x = (cpr + pow(2, N-i-1, C+1)) % (C+1)
            t += 1
        elif X[i] == '1' and C-1 != 0:
            x = (cmr - pow(2, N-i-1, C-1)) % (C-1)
            t += 1
        else:
            x = 0

        while x != 0:
            x %= bin(x).count('1')
            t += 1

        ans.append(t)

    return ans


def main():
    N = read_int()
    X = read_str()
    print(*slv(N, X), sep='\n')


if __name__ == '__main__':
    main()

Solution (Python):

import sys


buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_str():
    return readline().strip()


def slv(N, X):
    C = X.count('1')
    cmr = 0
    cpr = 0
    for b in X:
        b = int(b)
        cpr = ((cpr * 2) + b) % (C+1)
        if C-1 != 0:
            cmr = ((cmr * 2) + b) % (C-1)

    ans = []
    for i in range(N):
        t = 0
        if X[i] == '0':
            x = (cpr + pow(2, N-i-1, C+1)) % (C+1)
            t += 1
        elif X[i] == '1' and C-1 != 0:
            x = (cmr - pow(2, N-i-1, C-1)) % (C-1)
            t += 1
        else:
            x = 0

        while x != 0:
            x = x % bin(x).count('1')
            t += 1

        ans.append(t)

    return ans


def main():
    N = read_int()
    X = read_str()
    print(*slv(N, X), sep='\n')


if __name__ == '__main__':
    main()

Solution (Python):

import sys


buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_str():
    return readline().strip()


def slv(N, X):
    C = X.count('1')
    cmr = 0
    cpr = 0
    for b in X:
        b = int(b)
        cpr = ((cpr * 2) + b) % (C+1)
        if C-1 != 0:
            cmr = ((cmr * 2) + b) % (C-1)

    ans = []
    for i in range(N):
        t = 1
        if X[i] == '0':
            x = (cpr + pow(2, N-i-1, C+1)) % (C+1)
        elif X[i] == '1' and C-1 != 0:
            x = (cmr - pow(2, N-i-1, C-1)) % (C-1)
        else:
            x = 0
            t = 0

        while x != 0:
            x = x % bin(x).count('1')
            t += 1

        ans.append(t)

    return ans


def main():
    N = read_int()
    X = read_str()
    print(*slv(N, X), sep='\n')


if __name__ == '__main__':
    main()

Solution (Python):

import sys


buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_str():
    return readline().strip()


def slv(N, X):
    C = X.count('1')
    cmr = 0
    cpr = 0
    for b in X:
        cpr = ((cpr * 2) + int(b)) % (C+1)

    for b  in X:
        if C-1 != 0:
            cmr = ((cmr * 2) + int(b)) % (C-1)

    ans = []
    for i in range(N):
        t = 1
        if X[i] == '0':
            x = (cpr + pow(2, N-i-1, C+1)) % (C+1)
        elif X[i] == '1' and C-1 != 0:
            x = (cmr - pow(2, N-i-1, C-1)) % (C-1)
        else:
            x = 0
            t = 0

        while x != 0:
            x = x % bin(x).count('1')
            t += 1

        ans.append(t)

    return ans


def main():
    N = read_int()
    X = read_str()
    print(*slv(N, X), sep='\n')


if __name__ == '__main__':
    main()

Solution (Python):

import sys


buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_str():
    return readline().strip()


def slv(N, X):
    C = X.count('1')
    cmr = 0
    cpr = 0
    for b in X:
        if C-1 != 0:
            cmr = ((cmr * 2) + int(b)) % (C-1)
        cpr = ((cpr * 2) + int(b)) % (C+1)

    ans = []
    for i in range(N):
        t = 1
        if X[i] == '0':
            x = (cpr + pow(2, N-i-1, C+1)) % (C+1)
        elif X[i] == '1' and C-1 != 0:
            x = (cmr - pow(2, N-i-1, C-1)) % (C-1)
        else:
            x = 0
            t = 0

        while x != 0:
            x = x % bin(x).count('1')
            t += 1

        ans.append(t)

    return ans


def main():
    N = read_int()
    X = read_str()
    print(*slv(N, X), sep='\n')


if __name__ == '__main__':
    main()

Solution (Python):

import sys
sys.setrecursionlimit(10**6)

buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, X):
    C = X.count('1')
    cmr = 0
    cpr = 0
    for b in X:
        if C-1 != 0:
            cmr = ((cmr * 2) + int(b)) % (C-1)
        cpr = ((cpr * 2) + int(b)) % (C+1)

    ans = []
    for i in range(N):
        t = 1
        if X[i] == '0':
            x = (cpr + pow(2, N-i-1, C+1)) % (C+1)
        elif X[i] == '1' and C-1 != 0:
            x = (cmr - pow(2, N-i-1, C-1)) % (C-1)
        else:
            x = 0
            t = 0

        while x != 0:
            x = x % bin(x).count('1')
            t += 1

        ans.append(t)

    return ans


def main():
    N = read_int()
    X = read_str()
    print(*slv(N, X), sep='\n')


if __name__ == '__main__':
    main()

Solution (Python):

import sys
sys.setrecursionlimit(10**6)

buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, X):
    C = X.count('1')
    cmr = 0
    cpr = 0
    for b in X:
        if C-1 != 0:
            cmr *= 2
            cmr += int(b)
            cmr %= C - 1
        cpr *= 2
        cpr += int(b)
        cpr %= C + 1

    for i in range(N):
        t = 1
        if X[i] == '0':
            x = (cpr + pow(2, N-i-1, C+1)) % (C+1)
        elif X[i] == '1' and C-1 != 0:
            x = (cmr - pow(2, N-i-1, C-1)) % (C-1)
        else:
            x = 0
            t = 0
        while x != 0:
            x = x % bin(x).count('1')
            t += 1
        print(t)


def main():
    N = read_int()
    X = read_str()
    slv(N, X)


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
s = input()
x = [int(i) for i in s]
pc = s.count('1')

def popcnt(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
    return f(x % popcnt(x)) + 1

ans = [0]*n
for a in range(2):
    npc = pc
    if a == 0:
        npc += 1
    else:
        npc -= 1
    
    if npc <= 0:
        continue
    
    r0 = 0
    for i in range(n):
        r0 = (r0*2) % npc
        r0 += x[i]

    k = 1
    for i in range(n-1, -1, -1):
        if x[i] == a:
            r = r0
            if a == 0:
                r = (r+k) % npc
            else:
                r = (r-k+npc) % npc
            ans[i] = f(r) + 1
        k = (k*2) % npc

for i in ans:
    print(i)

Solution (Python):
def f(n):
    ret = 1
    while n > 0:
        n %= bin(n).count('1')
        ret += 1
    return ret

if __name__ == "__main__":
    n = int(input())
    x = input()
    cnt = x.count('1')

    if cnt == 1:
        for k in x[:-1]:
            if k == '0':
                print(1)
            else:
                print(0)
        if x[-1] == '1':
            print(0)
        else:
            print(2)
        exit()

    xNum = 0
    for k in x:
        xNum <<= 1
        if k == '1':
            xNum += 1
    ans = []
    p = xNum % (cnt + 1)
    m = xNum % (cnt - 1)

    for i in range(n):
        if x[i] == '0':
            ans.append(f((p + pow(2, n - i - 1, cnt + 1)) % (cnt + 1)))
        else:
            ans.append(f((m - pow(2, n - i - 1, cnt - 1)) % (cnt - 1)))
    print(*ans, sep='\n')

Solution (Python):
N = int(input())
S = input()
X = list(int(x) for x in S)


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


def f(x):
    if x == 0:
        return 0
    return f(x % popcount(x)) + 1


MAX = 2 * 10 ** 5 + 5


pc = sum(X)  

ans = [0] * (N + 1)
for b in range(2):
    npc = pc  
    if b == 0:
        npc += 1
    else:
        npc -= 1
    if npc <= 0:
        continue
    
    r0 = 0
    for i in range(N):
        r0 = (r0 * 2) % npc
        r0 += X[i]
    k = 1
    for i in reversed(range(N)):
        if X[i] == b:  
            r = r0  
            if b == 0:
                r = (r + k) % npc
            else:
                r = (r - k + npc) % npc
            
            ans[i] = f(r) + 1
        k = (k * 2) % npc

for i in range(N):
    print(ans[i])

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")

INF = float("inf")


N = int(input())
S = list(input())[:-1]
table = [0]*(N+5)
table[1] = 1
for i in range(2,N+3):
    num = i
    cnt = 0
    while num != 0:
        a = num % 2
        num = num // 2
        cnt += a
    p = i % cnt
    table[i] = table[p]+1
c = 0
for s in S:
    if s == "1":
        c += 1
p = 0
q = 0

for i in range(N):
    ss = S[N-1-i]
    p += int(ss)*pow(2,i,c+1)
    if c != 1:
        q += int(ss)*pow(2,i,c-1)
    p %= (c+1)
    if c != 1:
        q %= (c-1)
for i in range(N):
    ss = S[i]
    if ss == "0":
        ans = (p+pow(2,N-1-i,c+1))%(c+1)
        print(table[ans]+1)
    else:
        if c == 1:
            print(0)
        else:
            if c != 1:
                ans = (q-pow(2,N-1-i,c-1))%(c-1)
                print(table[ans]+1)
            else:
                print(0)

Solution (Python):
import sys
from functools import lru_cache
 
sys.setrecursionlimit(4100000)
 
@lru_cache(maxsize=None)
def f(n):
    if n == 0:
        return 0

    return f(n % bin(n).count('1')) + 1

def main():
    N = int(input())
    X = list(input())
    pc = X.count('1')
    now = 0
    for i in range(N):
        if X[i] == '1':
            now += pow(2,N-i-1)

    ac = pc + 1
    dc = pc - 1
    ac_now = now % ac
    if dc:
        dc_now = now % dc
    for i in range(N):
        cnt = 0
        if X[i] == '1' and dc:
            tmp = (dc_now - pow(2, N-i-1, dc)) % dc
            cnt = 1 + f(tmp)
        elif X[i] == '0':
            tmp = (ac_now + pow(2, N-i-1, ac)) % ac
            cnt = 1 + f(tmp)

        print(cnt)



if __name__ == "__main__":
    main()