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 math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def powmod(x, n, k):
    if k == 0:
        return 1

    ans = 1
    while(n > 0):
        if(bin(n & 1) == bin(1)):
            ans = ans*x
            ans %= k
        x = x*x
        x %= k
        n = n >> 1
    return ans % k

def popcnt(n):
    return bin(n).count("1")

def main():
    N = I()
    X = S()
    cnt = 0
    for i in range(len(X)):
        if int(X[i]) & 1  == 1:
            cnt += 1
    a = cnt + 1
    b = cnt - 1

    pow2a = [0] * (N+2)
    pow2b = [0] * (N+2) 

    suma = 0
    sumb = 0
    dX = X[::-1]
    for i in range(N+1):
        pow2a[i] = powmod(2, i, a)
        pow2b[i] = powmod(2, i, b)
        if i >= len(dX):
            continue
        if b == 0:
            sumb = 0
            continue
        if int(dX[i]) == 1:
            suma += pow2a[i]
            sumb += pow2b[i]
            suma %= a
            sumb %= b
    
    X = X[::-1]
    
    
    subx = []
    ans = [1] * N
    for i in range(len(X)):
        cp_suma = suma
        cp_sumb = sumb
        if int(X[i]) == 0:
            
            
            cp_suma += pow2a[i]
            cp_suma %= a
            res = cp_suma
        else:
            
            if b == 0:
                ans[N-1-i] -= 1
                subx.append(0)
                continue
            cp_sumb -= pow2b[i]
            cp_sumb %= b
            res = cp_sumb
        subx.append(res)

    subx = subx[::-1]
    for i, a in enumerate(subx):
        while a > 0:
            a %= popcnt(a)
            ans[i] += 1
    for a in ans:
        print(a)


main()

Solution (Python):


def ans(X):
    if X == 0: return 0
    X = X % (bin(X).count('1'))
    return 1+ans(X)


if False:
    import random
    X = ''.join(random.choice("1") for _ in range(2*10**5))
    N = len(X)
    
    
else:
    N = int(input())
    X = input()

N = N-1

popcount = X.count('1')
X_int = int(X, 2)

import array

two_pow_mod_pc_plus = array.array('i', [0]*(N+1))
two_pow_mod_pc_minus = array.array('i', [0]*(N+1))

two_pow_mod_pc_plus[0] = 1 % (popcount+1)
if popcount <= 1:
    two_pow_mod_pc_minus[0] = 0
else:
    two_pow_mod_pc_minus[0] = 1 % (popcount-1)

for i in range(1, len(two_pow_mod_pc_plus)):
    two_pow_mod_pc_plus[i] = (2*two_pow_mod_pc_plus[i-1]) % (popcount+1)

for i in range(1, len(two_pow_mod_pc_minus)):
    if popcount <= 1:
        two_pow_mod_pc_minus[i] == 1
    else:
        two_pow_mod_pc_minus[i] = (2*two_pow_mod_pc_minus[i-1]) % (popcount-1)

X_mod_pc_plus = X_int % (popcount+1)
if popcount <= 1:
    X_mod_pc_minus = 0
else:
    X_mod_pc_minus = X_int % (popcount-1)

for i, x in enumerate(X):
    
    if x == '0':
        r = 1 + ans((X_mod_pc_plus + two_pow_mod_pc_plus[N-i]) % (popcount+1))
    else:
        if popcount == 1:
            print(0)
            continue
        else:
            r = 1 + ans((X_mod_pc_minus - two_pow_mod_pc_minus[N-i]) % (popcount-1))
    print(r)

Solution (Python):
from __future__ import print_function
import sys


if sys.subversion[0] == "PyPy":
    import io, atexit

    sys.stdout = io.BytesIO()
    atexit.register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))

    sys.stdin = io.BytesIO(sys.stdin.read())
    input = lambda: sys.stdin.readline().rstrip()
RS = raw_input
RA = lambda x=int: map(x, RS().split())
RN = lambda x=int: x(RS())


def solve():
    n1 = sum([int(i) for i in list(x)])
    if n1 > 1:
        sums = [n1 - 1, n1 + 1]
    else:
        sums = [None, n1 + 1]
    ns = len(sums)
    remainders = [[0] * n for _ in range(len(sums))]
    total_remainder = [0] * ns
    for i in range(ns):
        if sums[i] != None:
            remainders[i][0] = 1 % sums[i]
            if x[-1] == "1":
                total_remainder[i] = remainders[i][0]
            for j in range(1, n):
                remainders[i][j] = remainders[i][j-1] * 2 % sums[i]
                if x[-1-j] == "1":
                    total_remainder[i] = (total_remainder[i] +  remainders[i][j]) % sums[i]
                    
    for i in reversed(range(n)):
        if n1 == 1 and x[-1 -i] == "1":
            print(0)
            continue
        if x[-1 -i] == "1":
            rm = (total_remainder[0] - remainders[0][i]) % sums[0]
        else:
            rm = (total_remainder[1] + remainders[1][i]) % sums[1]
        if rm == 0:
            print(1)
            continue
        ans = 1
        while rm != 0:
            
            rm = rm % countbin(rm)
            ans += 1
        print(ans)



    return

def countbin(num):
    return sum([int(i) for i in list(bin(num)[2:])])



n = RN()
x = RS()
solve()

Solution (Python):
import sys
import numpy as np
import numba
from numba import njit
i8 = numba.int64

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8, ), cache=True)
def popcount(n):
    ret = 0
    while n:
        ret += n & 1
        n >>= 1
    return ret


@njit((i8, ), cache=True)
def f(n):
    t = 0
    while n:
        t += 1
        n %= popcount(n)
    return t

@njit((i8[:], ), cache=True)
def main(X):
    N = len(X)
    popX = X.sum()
    MOD1 = popX + 1
    MOD2 = popX - 1
    if popX == 1:
        MOD2 = 1
    pow1 = np.ones_like(X)
    pow2 = np.ones_like(X)
    for n in range(1, N):
        pow1[n] = 2 * pow1[n - 1] % MOD1
        pow2[n] = 2 * pow2[n - 1] % MOD2

    X1, X2 = 0, 0
    for x in X:
        X1 = (2 * X1 + x) % MOD1
        X2 = (2 * X2 + x) % MOD2

    ans = np.empty(N, np.int64)
    for i in range(N):
        x = X[N - 1 - i]
        if x == 0:
            nxt = (X1 + pow1[i]) % (popX + 1)
            ans[i] = 1 + f(nxt)
        elif x == 1:
            if popX == 1:
                ans[i] = 0
            else:
                nxt = (X2 - pow2[i]) % (popX - 1)
                ans[i] = 1 + f(nxt)
    return ans[::-1]

N = int(readline())
X = np.array(list(read().rstrip()), np.int64) - ord('0')
ans = main(X)
print('\n'.join(map(str, ans.tolist())))

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
Xs = list(map(int, list(input())))
rXs = Xs[::-1]

num = sum(Xs)
pos = 0
neg = 0

pow_pos = [0]*N
pow_neg = [0]*N
dic = {0: 0, 1: 1, 2: 1, 3: 2, 4: 1, 5: 2, 6: 1, 7: 2, 8: 1}

for m in range(1, num+2):
    c = bin(m)[2:].count('1')
    dic[m] = dic[m%c]+1
    
for i in range(N):
    pow_pos[i] = pow(2, i, num+1)
    if not num==1:
        pow_neg[i] = pow(2, i, num-1)

for i, x in enumerate(rXs):
    if x==0:
        continue
    pos += pow_pos[i]
    if not num==1:
        neg += pow_neg[i]

anss = []
for i, x in enumerate(rXs):
    if num==1 and x==1:
        anss.append(0)
        continue
    if x==0:
        mod = num+1
        tmp = (pos+pow_pos[i])%mod
    else:
        mod = num-1
        tmp = (neg-pow_neg[i])%mod
    ans = dic[tmp]+1
    anss.append(ans)

for ans in anss[::-1]:
    print(ans)

Solution (Python):
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return map(int, sys.stdin.readline().split())
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())


def FLIST(n):
    res = [1]
    for i in range(1, n+1):
        res.append(res[i-1]*i % DVSR)
    return res


N = II()
ST = input()
ST = ST[::-1]



popcnt = 0

for i in range(N):
    popcnt += ST[i] == '1'

NUM1 = 0
NUM2 = 0
pop_1 = popcnt-1
pop_2 = popcnt+1
for i in range(N):
    if ST[i] == '1':
        if pop_1 > 0:
            NUM1 += pow(2, i, pop_1)
            NUM1 %= pop_1
        if pop_2 <= N:
            NUM2 += pow(2, i, pop_2)
            NUM2 %= pop_2




for i in range(N):
    cnt = 1
    i = N-i-1
    if ST[i] == '1':
        
        if pop_1 != 0:
            value = NUM1 - pow(2, i, pop_1)
            value %= pop_1
            while value:
                value %= bin(value).count("1")
                cnt += 1
            print(cnt)
        else:
            print(0)
    else:
        
        value = NUM2 + pow(2, i, pop_2)
        value %= pop_2
        while value:
            value %= bin(value).count("1")
            cnt += 1
        print(cnt)

Solution (Python):
n = int(input())
x = [int(x) for x in list(input())]

x_cnt = 0
for i, y in enumerate(x):
    if y == 1:
        x_cnt += 1

aa = x_cnt + 1
bb = x_cnt - 1

a = [1 % aa]
if bb > 0:
    b = [1 % bb]
else:
    bb = 1
    b = [0]

for _ in range(n-1):
    a.append(a[-1]*2 % aa)
    b.append(b[-1]*2 % bb)

a = a[::-1]
b = b[::-1]

x_ps = 0
x_ng = 0
for i, val in enumerate(x):
    if val == 1:
        x_ps += a[i]
        x_ng += b[i]

for i in range(n):
    ans = 0
    if x[i] == 0:
        cnt = x_cnt + 1
        val = (x_ps + a[i]) % cnt
    else:
        cnt = x_cnt - 1
        if cnt == 0:
            print(ans)
            continue
        val = (x_ng - b[i]) % cnt
    ans += 1

    tmp = val
    cnt = 0
    while tmp > 0:
        if tmp & 1:
            cnt += 1
            tmp = (tmp-1) // 2
        else:
            tmp = tmp // 2

    if cnt == 0:
        print(ans)
        continue

    while val > 0:
        ans += 1
        val = val % cnt
        tmp = val % cnt
        cnt = 0
        while tmp > 0:
            if tmp & 1:
                cnt += 1
                tmp = (tmp-1) // 2
            else:
                tmp = tmp // 2
    print(ans)

Solution (Python):
memo = {}
def f(x):
    if x==0:
        return 0
    if x==1:
        return 1
    if x in memo:
        return memo[x]
    k = sum(list(map(int,list(bin(x)[2:]))))
    memo[x] = 1+f(x%k)
    return memo[x]
    
N = int(input())
X = input().strip()
n = sum(list(map(int,list(X))))
if n==0:
    for i in range(N):
        print(1)
elif n==1:
    D = {i:0 for i in range(N)} 
    D[0] = 1
    for i in range(1,N):
        D[i] = (D[i-1]*2)%(n+1)
    cnt1 = 0
    for i in range(N):
        if X[i]=="1":
            print(0)
        else:
            a = (cnt1+D[N-1-i])%(n+1)
            print(1+f(a))
else:
    C = {i:0 for i in range(N)}  
    C[0] = 1
    for i in range(1,N):
        C[i] = (C[i-1]*2)%(n-1)
    D = {i:0 for i in range(N)} 
    D[0] = 1
    for i in range(1,N):
        D[i] = (D[i-1]*2)%(n+1)
    cnt0 = 0
    cnt1 = 0
    for i in range(N):
        if X[i]=="1":
            cnt0 = (cnt0+C[N-1-i])%(n-1)
            cnt1 = (cnt1+D[N-1-i])%(n+1)
    for i in range(N):
        if X[i]=="1":
            a = (cnt0-C[N-1-i])%(n-1)
            print(1+f(a))
        else:
            a = (cnt1+D[N-1-i])%(n+1)
            print(1+f(a))

Solution (Python):
"""
                            pppppppppppppppppppp
                         ppppp  ppppppppppppppppppp
                      ppppppp    ppppppppppppppppppppp
                      pppppppp  pppppppppppppppppppppp
                      pppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppppp
       ppppppppppppppppppppppppppppppppppppppppppppppp  pppppppppppppppppppp
      pppppppppppppppppppppppppppppppppppppppppppppppp  ppppppppppppppppppppp
     ppppppppppppppppppppppppppppppppppppppppppppppppp  pppppppppppppppppppppp
    ppppppppppppppppppppppppppppppppppppppppppppppp    pppppppppppppppppppppppp
   pppppppppppppppppppppppppppppppppppppppppppppp     pppppppppppppppppppppppppp
  ppppppppppppppppppppppppppppppppppppppppppppp      pppppppppppppppppppppppppppp
  pppppppppppppppppppppppppppppppp               pppppppppppppppppppppppppppppppp
  pppppppppppppppppppppppppppp     pppppppppppppppppppppppppppppppppppppppppppppp
  ppppppppppppppppppppppppppp    pppppppppppppppppppppppppppppppppppppppppppppppp
    pppppppppppppppppppppppp  pppppppppppppppppppppppppppppppppppppppppppppppppp
     ppppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppppppp
      pppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppppp
       ppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppppp
                              pppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppp  pppppppp
                              ppppppppppppppppppppp    ppppppp
                                 ppppppppppppppppppp  ppppp
                                    pppppppppppppppppppp
"""


import sys
def data(): return sys.stdin.readline().strip()
def out(var): sys.stdout.write(str(var))
def outa(*var, end="\n"): sys.stdout.write(' '.join(map(str, var)) + end)
def l(): return list(sp())
def sp(): return map(int, data().split())


def calculate(string):
    result = 0
    while string:
        c = bin(string)[2:].count('1')
        string = string % c
        result += 1
    return result


n = int(data())
s = list(data())
ones = []
powers = []
for i in range(n):
    if s[i] == '1':
        ones.append(i)
length = len(ones)
powers = [[0, 0] for i in range(n)]
for i in range(n):
    if length - 1 > 0:
        powers[i][0] = pow(2, i, length-1)
    powers[i][1] = pow(2, i, length + 1)
powers = powers[::-1]
s1, s2 = 0, 0
for i in ones:
    if length - 1 > 0:
        s1 = (s1 + powers[i][0])
    s2 = (s2 + powers[i][1])
for i in range(n):
    if s[i] == '1':
        if length - 1 <= 0:
            out("0\n")
            continue
        temp = s1
        temp = (temp - powers[i][0] + length - 1) % (length - 1)
    else:
        temp = s2
        temp = (temp + powers[i][1]) % (length + 1)
    out(str(calculate(temp)+1)+"\n")

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

n = int(input())
x = input()
px = x.count("1")
a = px + 1
b = px - 1
tmpa = 0
tmpb = 0

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

    for i in range(1, n + 1):
        count = 1
        if x[i - 1] == "1":  
            print(0)
            continue

        else:  
            y = tmpa + pow(2, n - i, a)
            y %= a
        while y:
            y %= popcount(y)
            count += 1
        print(count)

else:
    for i in range(n):
        if x[i] == "1":
            tmpa += pow(2, n - i - 1, a)
            tmpa %= a
            tmpb += pow(2, n - i - 1, b)
            tmpb %= b

    for i in range(1, n + 1):
        count = 1
        if x[i - 1] == "1":  
            y = tmpb - pow(2, n - i, b)
            y %= b
        else:  
            y = tmpa + pow(2, n - i, a)
            y %= a
        while y:
            y %= popcount(y)
            count += 1
        print(count)

Solution (Python):
n = int(input())
s = input()[::-1]
cnt = s.count('1')

p1 = sum(pow(2, i, cnt+1) * (s[i] == '1') for i in range(n))
if cnt > 1:
    m1 = sum(pow(2, i, cnt-1) * (s[i] == '1') for i in range(n))

def op(n):
    popcnt = bin(n).count('1')
    return n%popcnt

pre = [0]*1000000
for i in range(1,1000000):
    pre[i] = pre[op(i)] + 1

def solve(i):
    if s[-i] == '0':
        r = (p1 + pow(2, n-i, cnt+1))%(cnt+1)
    else:
        if cnt == 1:
            return 0
        r = (m1 - pow(2, n-i, cnt-1))%(cnt-1)
    return 1 + pre[r]

for i in range(n):
    print(solve(i+1))

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

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

a = X.count("1")
ap, am = a+1, a-1
Flag = True

if am == 0:
  Flag = False
  am += 1

Ap = [1]
Am = [1]

for i in range(N-1):
  Ap.append(Ap[-1]*2%ap)
  Am.append(Am[-1]*2%am)

Aps = 0
Ams = 0

for i in range(N):
  if X[-1-i] == "1":
    Aps += Ap[i]
    Aps %= ap
    Ams += Am[i]
    Ams %= am 

for i in range(N):
  cnt = 1
  if X[i] == "1":
    if Flag:
      p = Ams - Am[-1-i]
      p %= am
    else:
      cnt -= 1
      p = 0
  else:
    p = Aps + Ap[-1-i]
    p %= ap
  temp = p
  while temp > 0:
    temp %= popcount(temp)
    cnt += 1
  print(cnt)

Solution (Python):

def resolve():
    import copy
    n = int(input())
    x = input()
    ones = x.count("1")
    dones = ones - 1
    iones = ones + 1

    def counter(n):
        ans = 0
        while n > 0:
            n = n % bin(n).count("1")
            ans  += 1
        return(ans)

    modd = 0

    modi = 0
    for i in reversed(range(n)):
        if x[i] == "1":
            if dones != 0:
                modd += pow(2,n-i-1,dones)
            modi += pow(2,n-i-1,iones)

    for i in range(n):
        ans = 0
        if x[i] == "0":
            w = (modi + pow(2,n-i-1, iones))%iones
            ans += 1
            print(ans + counter(w))

        else:
            if dones == 0:
                print(0)
                continue
            else:
                w = (modd-pow(2,n-i-1, dones) + dones)%dones
                ans += 1
                print(ans + counter(w))
resolve()

Solution (Python):
import collections
memo = collections.defaultdict(int)
memo[0] = 0
memo[1] = 1


def f(x):
    if x in memo:
        return memo[x]
    else:
        y = x % bin(x).count('1')
        ret = 1 + f(y)
        memo[x] = ret
        return ret


N = int(input())
sX = input()
modX = sX.count('1')
if modX == 0:
    for _ in range(N):
        print(1)
elif modX == 1:
    sX = sX[::-1]
    for i, b in enumerate(sX):
        if b == '1':
            break
    
    if i == 0:
        ans = [0] + [2] * (N - 1)
        ans = ans[::-1]
    else:
        ans = [1] * N
        ans[-1] = 2
        ans[-i - 1] = 0
    print('\n'.join(map(str, ans)))
else:
    modp = modX + 1
    modm = modX - 1
    sX = sX[::-1]
    Xmodp = 0
    Xmodm = 0
    for i, b in enumerate(sX):
        if b == '1':
            Xmodp += pow(2, i, modp)
            Xmodp %= modp
            Xmodm += pow(2, i, modm)
            Xmodm %= modm
    s = []
    for i, b in enumerate(sX):
        if b == '1':
            s += [(Xmodm - pow(2, i, modm)) % modm]
        else:
            s += [(Xmodp + pow(2, i, modp)) % modp]
    ans = []
    for k in s[::-1]:
        ans += [1 + f(k)]
    print('\n'.join(map(str, ans)))

Solution (Python):
import math
def popcount(x):
    s=0
    y=int(math.log2(x))+2
    for i in range(y):
        if(x>>i)&1:
            s+=1
    return x%s
n=int(input())
x=input()[::-1]

c=x.count("1")



if c!=1:
    m=[[1%(c-1),1%(c+1)]]
    for i in range(n-1):
        m.append([(2*m[-1][0])%(c-1),(2*m[-1][1])%(c+1)])
    l=[0,0]
    for i in range(n):
        if x[i]=="1":
            l[0]+=m[i][0]
            l[1]+=m[i][1]
            l[0]%=(c-1)
            l[1]%=(c+1)
else:
    m=[[1%(c+1),1%(c+1)]]
    for i in range(n-1):
        m.append([(2*m[-1][0])%(c+1),(2*m[-1][1])%(c+1)])
    l=[0,0]
    for i in range(n):
        if x[i]=="1":
            l[0]+=m[i][0]
            l[1]+=m[i][1]
            l[0]%=(c+1)
            l[1]%=(c+1)



ans=[0]*n
for i in range(n):
    if x[i]=="1":
        if c-1==0:
            ans[i]=0
            continue
        p=(l[0]+(c-1)-m[i][0])%(c-1)
        ans[i]+=1
        while p!=0:
            p=popcount(p)
            ans[i]+=1
    else:
        p=(l[1]+m[i][1])%(c+1)
        ans[i]+=1
        while p!=0:
            p=popcount(p)
            ans[i]+=1
ans=ans[::-1]
for i in range(n):
    print(ans[i])

Solution (Python):
N=int(input())
Xl=list(map(int,list(input())))



def func(x):
  cnt=0
  while x>0:
    num1=0
    xcopy=x
    while xcopy:
      if xcopy&1:
        num1+=1
      xcopy>>=1
      
    
    x=x%num1
    cnt+=1
  return cnt

func_dic={}
for i in range(N+1):
  func_dic[i]=func(i)


num1_X=Xl.count(1)


mod_nminus=0
mod_nplus=0
for i in range(N):
  if num1_X-1>0:
    mod_nminus*=2
  mod_nplus*=2  
  if Xl[i]==1:
    mod_nminus+=1
    mod_nplus+=1

  if num1_X-1>0:
    mod_nminus%=num1_X-1
  mod_nplus%=num1_X+1
  


answer_list=[]
modpow_plus=1
modpow_minus=1
for i in reversed(range(N)):
  if Xl[i]==0:
    mod=(mod_nplus+modpow_plus)%(num1_X+1)
    answer_list.append(func_dic[mod]+1)
  else:
    if num1_X-1==0:
      answer_list.append(0)
    else:
      mod=(mod_nminus-modpow_minus)%(num1_X-1)
      answer_list.append(func_dic[mod]+1)
  
  modpow_plus*=2  
  modpow_plus%=num1_X+1
  if num1_X-1>0:
    modpow_minus*=2
    modpow_minus%=num1_X-1
  
for i in reversed(range(N)):
  print(answer_list[i])

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *



N = INT()
X = input()

def popcount(n):
	if n == 0:
		return 0
	else:
		cnt = 0
		while 0 < n:
			cnt += 1
			p = "{:b}".format(n).count("1")
			n %= p
		return cnt

n = X.count("1")

n1 = n-1
n2 = n+1

q_1 = [0]*N
q_2 = [0]*N
for i in range(N):
	if n1 != 0:
		q_1[i] = pow(2, i, n1)
	if n2 != 0:
		q_2[i] = pow(2, i, n2)

mod_sum_1 = 0
mod_sum_2 = 0

for i in range(N):
	if X[-i-1] == "1":
		mod_sum_1 += q_1[i]
		mod_sum_2 += q_2[i]

q_1 = q_1[::-1]
q_2 = q_2[::-1]


if n1 == 0:
	for i in range(N):
		if X[i] == "1":
			print(0)
		else:
			m = n2
			mod_sum = mod_sum_2 + q_2[i]
			print(popcount(mod_sum%m)+1)
else:
	for i in range(N):
		if X[i] == "1":
			m = n1
			mod_sum = mod_sum_1 - q_1[i]
		else:
			m = n2
			mod_sum = mod_sum_2 + q_2[i]

		print(popcount(mod_sum%m)+1)

Solution (Python):


def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    def popcount(x):
        '''xの立っているビット数をカウントする関数
        (xは64bit整数)'''

        
        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
    
    N=I()
    Xst=input()
    
    
    dp=[0]*(N+5)
    for i in range(1,N+5):
        X=i
        X=X%popcount(X)
        dp[i]=dp[X]+1 
       
    a=Xst.count("1")
    
    if a==0:
        for i in range(N):
            print(1)
        exit()
    elif a==1:
        for i in range(N):
            if Xst[i]=="1":
                print(0)
            else:
                if i!=(N-1):
                    print(1)
                else:
                    if Xst[-1]=="0":
                        print(2)
        exit()
    
    remp=[0]*(N+1)
    remm=[0]*(N+1)
    
    remp[0]=1%(a+1)
    remm[0]=1%(a-1)
    
    for i in range(1,N+1):
        remp[i]=(2*remp[i-1])%(a+1)
        remm[i]=(2*remm[i-1])%(a-1)
    
    Xremp=0
    Xremm=0
    for i in range(N):
        if Xst[i]=="1":
            Xremp+=remp[N-i-1]
            Xremm+=remm[N-i-1]
    Xremp%=(a+1)
    Xremm%=(a-1)
    
    
    
    for i in range(N):
        if Xst[i]=="0":
            Xrem2=(Xremp+remp[N-i-1])%(a+1)
        else:
            Xrem2=(Xremm-remm[N-i-1])%(a-1)
        
        print(dp[Xrem2]+1)
    
    
    
        

main()

Solution (Python):
from collections import Counter
N=int(input())
X=input()

value = int(X,2)

TFlist =[]
for i in range(N):
  if X[i] == '0':
  	TFlist.append(False)
  else:
    TFlist.append(True)

p = sum(TFlist)


def count_ones_by_bin(num):
    bin_num = bin(num)[2:]
    count = 0
    for i in bin_num:
            count += int(i)
    return count
  
def popcount(n):
 
  return (n  % count_ones_by_bin(n))

for i in range(N):

  cnt = 0
  tmp = 0
  if p != 1 or (not TFlist[i]):
    if TFlist[i]: tmp = (value % (p-1) - (pow(2,(N-i-1), (p-1)))) % (p-1)
    else: tmp = (value % (p+1) + (pow(2,(N-i-1) , (p+1) ) ) ) % (p+1)    
    cnt += 1
  while tmp != 0:
    cnt+= 1
    tmp = popcount(tmp)
  print(cnt)

Solution (Python):


import sys

class DAnythingGoesToZero:
    def solve(self, tc=0):
        n = int(input())
        
        x = input().strip()
        cache = [-1] * (n + 1)
        cache[0] = 0
        for nb in range(n + 1):
            v = 0
            i = nb
            while cache[i] == -1:
                i %= bin(i).count('1')
                v += 1

            cache[nb] = v + cache[i]

        

        def brem(N, D):
            n = len(N)
            R = 0
            for i in range(n - 1, -1, -1):
                R <<= 1
                R |= int(N[n - 1 - i])
                if R >= D:
                    R -= D
            return R

        x = list(x)
        ones = x.count('1')
        r1 = brem(x, ones + 1)
        r2 = brem(x, ones - 1) if ones > 1 else 0
        for i in range(n):
            if x[i] == '0':
                
                print(cache[(r1 + pow(2, n - 1 - i, ones + 1)) % (ones + 1)] + 1)
            else:
                if ones == 1:
                    print(0)
                    continue
                print(cache[(r2 - pow(2, n - 1 - i, ones - 1)) % (ones - 1)] + 1)
            
            
            

solver = DAnythingGoesToZero()
input = sys.stdin.readline

solver.solve()

Solution (Python):
def main():
    N = int(input())
    S = input()
    X = int(S, 2)
    C = S.count('1')
    xc0 = X % (C + 1)
    xc1 = X % (C - 1) if C > 1 else 0

    def f(x):
        c = 0
        while x:
            c += 1
            x = x % bin(x).count('1')
        return c

    for i, s in enumerate(S):
        k = N - 1 - i
        if s == '0':
            print(f((xc0 + pow(2, k, C + 1)) % (C + 1)) + 1)
        else:
            if C > 1:
                print(f((xc1 - pow(2, k, C - 1)) % (C - 1)) + 1)
            else:
                print(0)


main()

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

su = s.count('1')
sun = int(s,2)

sun_plus = sun % (su + 1)
sun_minus = 0 if su - 1 == 0 else sun % (su - 1)


table = [0]*200001
table[1] = 1
for i in range(2,200001):
    table[i] = 1 + table[i % bin(i).count('1')]

def pow(n,e,mod):
    ret=1
    b=n
    while e > 0:
        if e % 2 == 1:
            ret = ret * b % mod
        b = b * b % mod
        e = e//2
    return ret

for i in range(n):
    if s[i] == '0':
        print(1+table[(sun_plus+pow(2,n-1-i,su+1))%(su+1)])
    else:
        if su-1 == 0:
            print(0)
        else:
            print(1+table[(sun_minus-pow(2,n-1-i,su-1)+su-1)%(su-1)])

Solution (Python):
ma = lambda :map(int,input().split())
ni = lambda:int(input())
import collections
import math
import itertools
gcd = math.gcd
n = ni()
x = input()
xr = x[::-1]
px = x.count("1")
def solve(t):
    ret = 1 
    while t>0:
        p = bin(t).count("1")
        t %=p
        ret +=1
    return ret
x_tp = 0
x_tm = 0

for i in range(n):
    x_tp = (x_tp + int(xr[i])*pow(2,i,px+1) ) %(px+1) 
if px>1:
    for i in range(n):
        x_tm = (x_tm + int(xr[i])*pow(2,i,px-1) ) %(px-1) 
ans = []

for i in range(n):
    if xr[i] =="0":
        x_tmp = (x_tp + pow(2,i,px+1) ) %(px+1)
    else:
        if px==1:
            ans.append(0)
            continue
        x_tmp = (x_tm - pow(2,i,px-1)) %(px-1)
    t = solve(x_tmp)
    ans.append(t)
for i in range(n-1,-1,-1):
    print(ans[i])

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

def calc(S, L):
    cnt = 0
    for i in range(L):
        if S[i] == "1":
            cnt += 1

    a_1 = 1
    r_1 = [0] * (L+1)
    for i in reversed(range(L)):
        r_1[i] = (r_1[i+1] + int(S[i]) * a_1) % cnt
        a_1 = (a_1 * 2) % cnt

    return r_1[0]

def calc_first(S, L):
    cnt = 0
    for i in range(L):
        if S[i] == "1":
            cnt += 1

    a_1 = 1
    a_2 = 1
    r_1 = [0] * (L+1)
    r_2 = [0] * (L+1)
    for i in reversed(range(L)):
        r_1[i] = (r_1[i+1] + int(S[i]) * a_1) % (cnt+1)
        if cnt-1 > 0:
            r_2[i] = (r_2[i+1] + int(S[i]) * a_2) % (cnt-1)

        a_1 = (a_1 * 2) % (cnt + 1)
        if cnt-1 > 0:
            a_2 = (a_2 * 2) % (cnt - 1)

    for i in range(L):
        if S[i] == "0":
            ans = (r_1[0] - r_1[i] + r_1[i+1] + pow(2, N-i-1, (cnt+1))) % (cnt+1)
        else:
            if cnt == 1:
                print(0)
                continue
            else:
                ans = (r_2[0] - r_2[i] + r_2[i+1]) % (cnt-1)

        cnt_ans = 1
        while ans > 0:
            ans = calc(str(bin(ans))[2:], len(str(bin(ans))[2:]))
            cnt_ans += 1
        print(cnt_ans)

calc_first(X, N)