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):
n = int(input())
x = input()

f = [-1] * (n+10)
f[0] = 0

for i in range(1, n+10):
    
    f[i] = f[i % bin(i).count('1')] + 1

init_bitcount = x.count('1')


x_mod_01 = 0
for digit in x:
    x_mod_01 *= 2
    if digit == '1':
        x_mod_01 += 1
    x_mod_01 %= (init_bitcount+1)

if init_bitcount != 1:
    x_mod_10 = 0
    for digit in x:
        x_mod_10 *= 2
        if digit == '1':
            x_mod_10 += 1
        x_mod_10 %= (init_bitcount-1)



power_mod_01 = [-1] * (n+10)
power_mod_01[0] = 1
for i in range(1, n+10):
    power_mod_01[i] = power_mod_01[i-1] * 2 % (init_bitcount + 1)

if init_bitcount != 1:
    power_mod_10 = [-1] * (n+10)
    power_mod_10[0] = 1
    for i in range(1, n+10):
        power_mod_10[i] = power_mod_10[i-1] * 2 % (init_bitcount - 1)


for i in range(n):
    if x[i] == '0':
        
        first_residue = (x_mod_01 + power_mod_01[n - i - 1]) % (init_bitcount+1)
        print(f[first_residue] + 1)
    else:
        if init_bitcount == 1:
            
            print(0)
            continue
        
        first_residue = (x_mod_10 - power_mod_10[n - i - 1]) % (init_bitcount-1)
        print(f[first_residue] + 1)

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

f = [-1] * (n+10)
f[0] = 0

for i in range(1, n+10):
    
    f[i] = f[i % bin(i).count('1')] + 1

init_bitcount = x.count('1')


x_mod_01 = 0
x_mod_10 = 0
for digit in x:
    x_mod_01 *= 2
    x_mod_10 *= 2
    if digit == '1':
        x_mod_01 += 1
        x_mod_10 += 1
    x_mod_01 %= (init_bitcount+1)
    if init_bitcount != 1:
        x_mod_10 %= (init_bitcount-1)



power_mod_01 = [-1] * (n+10)
power_mod_01[0] = 1
for i in range(1, n+10):
    power_mod_01[i] = power_mod_01[i-1] * 2 % (init_bitcount + 1)

if init_bitcount != 1:
    power_mod_10 = [-1] * (n+10)
    power_mod_10[0] = 1
    for i in range(1, n+10):
        power_mod_10[i] = power_mod_10[i-1] * 2 % (init_bitcount - 1)


for i in range(n):
    if x[i] == '0':
        
        first_residue = (x_mod_01 + power_mod_01[n - i - 1]) % (init_bitcount+1)
        print(f[first_residue] + 1)
    else:
        if init_bitcount == 1:
            print(0)
            continue
        
        first_residue = (x_mod_10 - power_mod_10[n - i - 1]) % (init_bitcount-1)
        print(f[first_residue] + 1)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
read = sys.stdin.read

from collections import defaultdict

def main():
    def from10to2(p):
        res = []
        while p:
            p, t = divmod(p, 2)
            res.append(str(t))
        return "".join(res[::-1])

    def from2to10(p):
        res = 0
        num2 = 1
        for c in p[::-1]:
            if c == '1':
                res += num2
            num2 *= 2
        return res

    def f(p):
        if p == 0:
            return 0
        elif d1[p] > 0:
            return d1[p]
        else:
            ppop = from10to2(p).count('1')
            p2 = p % ppop
            fp = f(p2) + 1
            d1[p] = fp
            return fp

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

    numof1 = x.count('1')
    bin2_p = [0] * n
    num2 = 1
    for i1 in range(1, n+1):
        bin2_p[-i1] = num2
        num2 = (num2 * 2) % (numof1 + 1)

    bin2_m = [0] * n
    num2 = 1
    if numof1 == 1:
        pass
    else:
        for i1 in range(1, n+1):
            bin2_m[-i1] = num2
            num2 = (num2 * 2) % (numof1 - 1)

    xas10 = from2to10(x)
    xas10_p = xas10 % (numof1 + 1)
    if numof1 == 1:
        xas10_m = 0
    else:
        xas10_m = xas10 % (numof1 - 1)
    d1 = defaultdict(int)
    d1[0] = 0
    for j1 in range(n):
        if x[j1] == '1':
            if numof1 == 1:
                print(0)
            else:
                t0 = xas10_m - bin2_m[j1]
                t0 = t0 % (numof1 - 1)
                if t0 == 0:
                    print(1)
                else:
                    print(f(t0) + 1)
        else:
            t0 = xas10_p + bin2_p[j1]
            t0 = t0 % (numof1 + 1)
            if t0 == 0:
                print(1)
            else:
                print(f(t0) + 1)

if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
sn = input()
sr = ''.join(list(reversed(sn)))
sint = int(sn, 2)
spop = sn.count('1')

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



m1 = sint % (spop + 1)
m2 = 0 if spop <= 1 else sint % (spop - 1)

a = [0] * n
for i in range(n):
    if sr[i] == '0':
        d = pow(2, i, spop + 1)
        m = (m1 + d) % (spop + 1)
        a[i] = f(m) + 1
    elif spop != 1:
        d = pow(2, i, spop - 1)
        m = (m2 - d + spop - 1) % (spop - 1)
        a[i] = f(m) + 1
    else:
        a[i] = 0

for ans in reversed(a):
    print(ans)

Solution (Python):
def main():
    n = int(input())
    bit = input()[::-1]
    count = bit.count("1")
    count_plus = count+1
    count_minus = count-1
    pow_plus = [1 % count_plus]
    for i in range(n):
        pow_plus.append(pow_plus[-1]*2 % count_plus)
    if count_minus != 0:
        pow_minus = [1 % count_minus]
        for i in range(n):
            pow_minus.append(pow_minus[-1]*2 % count_minus)
    else:
        pow_minus = []

    bit_plus = 0
    bit_minus = 0

    for i in range(n):
        if bit[i] == "1":
            bit_plus = (bit_plus+pow_plus[i]) % count_plus
    if count_minus != 0:
        for i in range(n):
            if bit[i] == "1":
                bit_minus = (bit_minus+pow_minus[i]) % count_minus
    ans = []
    for i in range(n):
        if bit[i] == "1":
            if count_minus == 0:
                ans.append(0)
                continue
            bit_ans = (bit_minus-pow_minus[i]) % count_minus
            count = count_minus
        else:
            bit_ans = (bit_plus+pow_plus[i]) % count_plus
            count = count_plus
        cnt = 1
        while bit_ans:
            b = str(bin(bit_ans)).count("1")
            bit_ans = bit_ans % b
            cnt += 1
        ans.append(cnt)
    for i in ans[::-1]:
        print(i)


main()

Solution (Python):
import sys

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 

input = sys.stdin.readline
N = int(input())
X = input().strip()

n0 = 0
for x_i in X:
    if x_i == "1":
        n0 += 1

r_p = 0 
r_n = 0 
X = X[::-1]
for i in range(N):
    x = int(X[i])
    r_p += x * pow(2, i, n0+1)
    r_p %= (n0+1)
    if 1 < n0:
        r_n += x * pow(2, i, n0-1)
        r_n %= (n0-1)


ans = []

for i in range(N):
    count = 1
    diff = (1 if X[i] == "0"  else -1)
    
    n = n0 + diff
    if n == 0:
        ans.append(0)
        continue
    if diff == 1:
        r = r_p + (diff * pow(2, i, n))
        r %= n
    else:
        r = r_n + (diff * pow(2, i, n))
        r %= n
    
    n = r
    
    while 0 < n:
        r = popcount(n)
        count += 1
        
        if r == 0:
            break
        n = n % r
    ans.append(count)

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

Solution (Python):
import sys

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 

input = sys.stdin.readline
N = int(input())
X = input().strip()

n0 = 0
for x_i in X:
    if x_i == "1":
        n0 += 1

r_p = 0 
r_n = 0 
X = X[::-1]
for i in range(N):
    x = int(X[i])
    r_p += x * pow(2, i, n0+1)
    r_p %= (n0+1)
    if 1 < n0:
        r_n += x * pow(2, i, n0-1)
        r_n %= (n0-1)


ans = []

for i in range(N):
    count = 1
    diff = (1 if X[i] == "0"  else -1)
    
    n = n0 + diff
    if n == 0:
        ans.append(0)
        continue
    if diff == 1:
        r = r_p + (diff * pow(2, i, n))
        r %= n
    else:
        r = r_n + (diff * pow(2, i, n))
        r %= n
    
    n = r
    
    while 0 < n:
        r = popcount(n)
        count += 1
        
        if r == 0:
            break
        n = n % r
    ans.append(count)

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

Solution (Python):
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  


N = I()
X = LI2()
X.reverse()

if N == 0:
    print(1)
    exit()

A = [0]*(2*10**5+1)  
for i in range(1,2*10**5+1):
    k = 0
    for j in range(18):
        if (i >> j) & 1:
            k += 1
    A[i] = A[i % k] + 1


r = sum(X)  

if r >= 2:
    B = [1] + [0]*(N-1)  
    C = [1] + [0]*(N-1)  
    b,c = X[0],X[0]  
    for i in range(1,N):
        B[i] = (B[i-1]*2) % (r-1)
        C[i] = (C[i-1]*2) % (r+1)
        if X[i] == 1:
            b += B[i]
            b %= r-1
            c += C[i]
            c %= r+1

    for i in range(N-1,-1,-1):
        if X[i] == 0:
            print(1+A[(c+C[i]) % (r+1)])
        else:
            print(1+A[(b-B[i]) % (r-1)])

else:
    C = [1] + [0]*(N-1)  
    c = X[0]  
    for i in range(1,N):
        C[i] = (C[i-1]*2) % (r+1)
        if X[i] == 1:
            c += C[i]
            c %= r+1

    for i in range(N-1,-1,-1):
        if X[i] == 0:
            print(1+A[(c+C[i]) % (r+1)])
        else:
            print(0)

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



fac0 = [1] * (n + 1)
fac1 = [1] * (n + 1)
for i in range(1, n + 1):
    fac0[i] = fac0[i - 1] * 2 % (cnt + 1)
    if cnt > 1:
        fac1[i] = fac1[i - 1] * 2 % (cnt - 1)


all0 = 0
all1 = 0
for i in range(n):
    if s[i] == '1':
        all0 = (all0 + fac0[i]) % (cnt + 1)
        if cnt > 1:
            all1 = (all1 + fac1[i]) % (cnt - 1)


def pakuri_poppu(c):
    c = (c & 0x5555555555555555) + (c >> 1 & 0x5555555555555555)
    c = (c & 0x3333333333333333) + (c >> 2 & 0x3333333333333333)
    c = (c + (c >> 4)) & 0x0F0F0F0F0F0F0F0F
    return c * 0x0101010101010101 >> 56 & 0x7f


def bon(x):
    p = pakuri_poppu(x)
    res = 1
    while x:
        x %= p
        p = pakuri_poppu(x)
        res += 1
    return res


for i in range(n - 1, -1, -1):
    if s[i] == '0':
        print(bon((all0 + fac0[i]) % (cnt + 1)))
    else:
        if cnt == 1:
            print(0)
            continue
        print(bon((all1 - fac1[i]) % (cnt - 1)))

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))



def a_int(): return int(readline())


def ints(): return list(map(int, readline().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) 
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, readline().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return ret
    


MOD = 10**9 + 7
INF = 2**31  

from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  
from functools import reduce
from math import gcd


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


N = a_int()
X = read()[:-1]
tmp = X.count('1')  
X = list(map(int, list(X[::-1])))



Xmodpop = [0, 0, 0]
for i, x in enumerate(X):
    if x:
        Xmodpop[1] += pow(2, i, tmp + 1)
        if tmp != 1:
            Xmodpop[-1] += pow(2, i, tmp - 1)
Xmodpop[1] %= tmp + 1
if tmp != 1:
    Xmodpop[-1] %= tmp - 1

X_nex = []  
for i in range(N):
    if X[i] == 1:
        if tmp == 1:
            X_nex.append(-1)
            continue
        X_nex.append((Xmodpop[-1] - pow(2, i, tmp - 1)) % (tmp - 1))
    else:
        X_nex.append((Xmodpop[1] + pow(2, i, tmp + 1)) % (tmp + 1))


ans = []
for i in range(N):
    n = X_nex[i]
    if n == -1:
        ans.append(0)
        continue
    cnt = 1
    while n:
        popc = bin(n).count('1')
        n %= popc
        cnt += 1
    ans.append(cnt)

print(*ans[::-1], sep='\n')

Solution (Python):
from functools import lru_cache


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


@lru_cache(maxsize=None)
def rec(n):
    if n == 0:
        return 0
    else:
        return rec(n % popcnt(n)) + 1


n = int(input())
x = int(input(), 2)


cnt = popcnt(x)
init_big = x % (cnt + 1)
if cnt == 1:
    init_small = 0
else:
    init_small = x % (cnt - 1)


result = []
for i in range(n):
    if not (x >> i) & 1:
        result.append((init_big + pow(2, i, cnt + 1)) % (cnt + 1))
    elif x == 1 << i or cnt - 1 == 0:
        result.append("x")
    else:
        result.append((init_small - pow(2, i, cnt - 1)) % (cnt - 1))

ans = []
for x in result[::-1]:
    if x == "x":
        ans.append(0)
    else:
        ans.append(rec(x) + 1)

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

Solution (Python):
n=int(input())
x=list(map(int,list(input())))
def popcount(x):
  ret=0
  while x:
    if x%2==1:ret+=1
    x//=2
  return ret
def f(x):
  ret=0
  while x:
    x%=popcount(x)
    ret+=1
  return ret
from collections import Counter
xpop=Counter(x)[1]
xint_mi,xint_pl=0,0

for i,y in enumerate(x):
  if xpop>1:
    xint_mi+=(pow(2,n-i-1,xpop-1)*y)%(xpop-1)
    xint_mi%=(xpop-1)
  xint_pl+=(pow(2,n-i-1,xpop+1)*y)%(xpop+1)
  xint_pl%=(xpop+1)

for i,y in enumerate(x):
  if y and xpop>1:
    yint=xint_mi-pow(2,n-i-1,xpop-1)
    ypop=xpop-1
  else:
    yint=xint_pl+pow(2,n-i-1,xpop+1)
    ypop=xpop+1
  if y==1 and xpop==1:
    print(0)
    continue
  yint%=ypop
  
  print(f(yint)+1)

Solution (Python):
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  
def LS2(): return list(sys.stdin.readline().rstrip())  


N = I()
X = LI2()
X.reverse()

if N == 0:
    print(1)
    exit()

A = [0]*(2*10**5+1)
for i in range(1,2*10**5+1):
    k = 0
    for j in range(18):
        if (i >> j) & 1:
            k += 1
    A[i] = A[i % k] + 1


r = sum(X)

if r >= 2:
    B = [0]*N
    C = [0]*N
    b,c = 0,0
    for i in range(N):
        if i == 0:
            B[i] = 1
            C[i] = 1
            if X[i] == 1:
                b = 1
                c = 1
        else:
            B[i] = (B[i-1]*2) % (r-1)
            C[i] = (C[i-1]*2) % (r+1)
            if X[i] == 1:
                b += B[i]
                b %= r-1
                c += C[i]
                c %= r+1

    for i in range(N-1,-1,-1):
        if X[i] == 1:
            print(1+A[(b-B[i]) % (r-1)])
        else:
            print(1+A[(c+C[i]) % (r+1)])

else:
    C = [0] * N
    c = 0
    for i in range(N):
        if i == 0:
            C[i] = 1
            if X[i] == 1:
                c = 1
        else:
            C[i] = (C[i - 1] * 2) % (r + 1)
            if X[i] == 1:
                c += C[i]
                c %= r + 1

    for i in range(N - 1, -1, -1):
        if X[i] == 0:
            print(1 + A[(c + C[i]) % (r + 1)])
        else:
            print(0)

Solution (Python):
def solve(x):
    cnt = 1
    while x > 0:
        x %= bin(x).count('1')
        cnt += 1
    return cnt

n = int(input())
x = input()
one = x.count('1')
num = int(x, 2)

up = num%(one+1)
if one == 1:down = 0
else:down = num%(one-1)

for i in range(n):
    if x[i] == '1':
        if one == 1:
            print(0)
            continue
        s = (down - pow(2, n-i-1, one-1))%(one-1)
    else:
        s = (up + pow(2, n-i-1, one+1))%(one+1)
    print(solve(s))

Solution (Python):
def solve(x):
    cnt = 1
    while x > 0:
        x %= bin(x).count('1')
        cnt += 1
    return cnt

n = int(input())
x = input()
one = x.count('1')
num = int(x, 2)

up = num%(one+1)
if one == 1:down = 0
else:down = num%(one-1)

for i in range(n):
    if x[i] == '1':
        if one == 1:
            print(0)
            continue
        s = (down - pow(2, n-i-1, one-1))%(one-1)
    else:
        s = (up + pow(2, n-i-1, one+1))%(one+1)
    print(solve(s))

Solution (Python):
def solve(x):
    cnt = 1
    while x > 0:
        x %= bin(x).count('1')
        cnt += 1
    return cnt

n = int(input())
x = input()
one = sum(map(int, list(x)))
num = int(x, 2)

up = num%(one+1)
if one == 1:
    down = 0
else:
    down = num%(one-1)

for i in range(n):
    if x[i] == '1':
        if one == 1:
            print(0)
            continue
        s = (down - pow(2, n-i-1, one-1))%(one-1)
    else:
        s = (up + pow(2, n-i-1, one+1))%(one+1)
    print(solve(s))

Solution (Python):
import sys









MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

def popcount(num):
    cnt = 0
    while num > 0:
        num %= bin(num).count('1')
        cnt += 1
    return cnt

def Main():
    n = read_int()
    x = read_str()
    x_int = int(x, 2)

    cnt = x.count('1')
    minus_cnt = cnt - 1
    plus_cnt = cnt + 1
    
    minus_mod = x_int % minus_cnt if minus_cnt != 0 else 0
    plus_mod = x_int % plus_cnt

    for i in range(n):
        if x[i] == '0':
            print(popcount((plus_mod + pow(2, n - 1 - i, plus_cnt)) % plus_cnt) + 1)
        elif minus_cnt != 0:
            print(popcount((minus_mod - pow(2, n - 1 - i, minus_cnt)) % minus_cnt) + 1)
        else:
            print(0)

if __name__ == '__main__':
    Main()

Solution (Python):
N=int(input())
X=input()
num_X = int(X, base=2)
pop_x = X.count("1")
if pop_x <= 1:
    mod0 = pop_x + 1
    res0 = num_X % mod0
else:
    mod1 = pop_x - 1
    mod0 = pop_x + 1
    res1 = num_X % (mod1)
    res0 = num_X % (mod0)


for i in range(N):
    tmp = 0
    if X[i] == "0":
        
        tmp = (res0 + pow(2, N-i-1, mod0))%mod0
    else:
        if pop_x == 1:
            print(0)
            continue
        tmp = (res1 - pow(2, N-i-1, mod1))%mod1
    
    if tmp == 0:
        print(1)
        continue
    cnt = 1
    while tmp != 0:
        pop = bin(tmp).count("1")
        tmp %= pop
        cnt += 1
    print(cnt)

Solution (Python):
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  


N = I()
X = LI2()
X.reverse()

if N == 1 and len(X) == 1 and X[0] == 0:
    print(1)
    exit()


def popcount(n):
    res = 0
    m = n.bit_length()
    for i in range(m):
        res += (n >> i) & 1
    return res




F = [0]*(2*10**5)  
for i in range(1,2*10**5):
    F[i] = 1 + F[i % popcount(i)]

a = sum(X)
b = a-1
c = a+1
if a == 1:
    C = [1]  
    xc = 0  
    for i in range(N):
        if X[i] == 1:
            xc += C[-1]
            xc %= c
        C.append((2 * C[-1]) % c)

    ANS = []
    for i in range(N):
        if X[i] == 1:
            ANS.append(0)
        else:
            ANS.append(1 + F[(xc + C[i]) % c])

    ANS.reverse()
    print(*ANS, sep='\n')
    exit()

B,C = [1],[1]  
xb,xc = 0,0  
for i in range(N):
    if X[i] == 1:
        xb += B[-1]
        xc += C[-1]
        xb %= b
        xc %= c
    B.append((2*B[-1])%b)
    C.append((2*C[-1])%c)

ANS = []
for i in range(N):
    if X[i] == 1:
        ANS.append(1 + F[(xb-B[i]) % b])
    else:
        ANS.append(1 + F[(xc+C[i]) % c])

ANS.reverse()
print(*ANS,sep='\n')

Solution (Python):


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

ones=X.count("1")
high=ones+1
low=ones-1

mod_h=[1]
mod_l=[1]
for i in range(N-1):
    mod_h.append((mod_h[-1]*2)%high)
    mod_l.append((mod_l[-1]*2)%low if low!=0 else 0) 

mod_h=mod_h[::-1]
mod_l=mod_l[::-1]

ans_high=0
for i in range(N):
    if X[i] == "1":
        ans_high+=mod_h[i]
ans_high%=high

ans_low=0
for i in range(N):
    if X[i] == "1":
        ans_low+=mod_l[i]
ans_low%=low if low!=0 else 1
        
for i in range(N):
    if X[i]=="0":
        ans=ans_high
        ans+=mod_h[i]
        ans%=high
    else:
        if low==0:
            print(0)
            continue
        ans=ans_low
        ans-=mod_l[i]
        ans%=low
    
    count=1
    while ans!=0:
        ans=ans%(bin(ans).count("1"))
        count+=1
    
    print(count)

Solution (Python):
N = int(input())
X = list(input())
X = [int(x) for x in X]
popcnt = 0
for i in range(N):
    if X[i]:
        popcnt += 1

Ys = [0,0]
for i in range(N):
    if X[i]:
        Ys[0] += pow(2,N-1-i,popcnt+1)
        Ys[0] %= popcnt+1

if popcnt > 1:
    for i in range(N):
        if X[i]:
            Ys[1] += pow(2,N-1-i,popcnt-1)
            Ys[1] %= popcnt-1


for i in range(N):
    if X[i]:
        mod = popcnt-1
        if mod == 0:
            print(0)
            continue
        Y = Ys[1] - pow(2,N-1-i,mod)
    else:
        mod = popcnt+1
        Y = Ys[0] + pow(2,N-1-i,mod)
	
    Y %= mod
    ans = 1

    if Y == 0:
        print(ans)
        continue
        
    while Y > 0:
        L = Y.bit_length()
        mod = 0
        for j in range(L):
            if Y>>j&1:
                mod += 1
        Y %= mod
        ans += 1
    print(ans)

Solution (Python):
N = int(input())
S = str(input())
X = [];Bit = 0;Num = 0
for i in range(N):
  if S[i] == "1":
    Bit += 1
    Num += pow(2,N-1-i)
  X.append(int(S[i]))


MAX = 2*pow(10,5)+10
small = [-1 for _ in range(MAX)]
small[0] = 0; small[1] = 1; small[2] = 1; small[3] = 2
for i in range(4,MAX):
  ret = 0; target = i*1
  while i > 0:
    cnt = 0
    for j in range(i.bit_length()):
      if (i>>j)&1 == 1:
        cnt += 1
    i = i%cnt
    
    ret += 1
    if small[i] != -1:
      ret += small[i]
      break

  small[target] = ret

if Bit -1 != 0:
  Numm = Num%(Bit-1)
Nump = Num%(Bit+1)

ans = []
for i in range(N):
  keta = N-1-i
  if X[i] == 1:
    btemp = Bit -1
    if btemp == 0:
      ans.append(0)
      continue
    temp = (Numm - pow(2,keta,btemp))%btemp
  else:
    btemp = Bit +1
    temp = (Nump + pow(2,keta,btemp))%btemp
  ret = small[temp] + 1 
  ans.append(ret)
print(*ans,sep="\n")

Solution (Python):
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  
def LS2(): return list(sys.stdin.readline().rstrip())  


N = I()
X = LI2()
X.reverse()

if N == 1 and len(X) == 1 and X[0] == 0:
    print(1)
    exit()


def popcount(n):
    res = 0
    m = n.bit_length()
    for i in range(m):
        res += (n >> i) & 1
    return res


F = [0]*(2*10**5)
for i in range(1,2*10**5):
    F[i] = 1 + F[i % popcount(i)]

a = sum(X)
b = a-1
c = a+1
if a == 1:
    A, C = [1], [1]  
    xa, xc = 0, 0  
    for i in range(N):
        if X[i] == 1:
            xa += A[-1]
            xc += C[-1]
            xa %= a
            xc %= c
        A.append((2 * A[-1]) % a)
        C.append((2 * C[-1]) % c)

    ANS = []
    for i in range(N):
        if X[i] == 1:
            ANS.append(0)
        else:
            ANS.append(1 + F[(xc + C[i]) % c])

    ANS.reverse()
    print(*ANS, sep='\n')
    exit()

A,B,C = [1],[1],[1]  
xa,xb,xc = 0,0,0  
for i in range(N):
    if X[i] == 1:
        xa += A[-1]
        xb += B[-1]
        xc += C[-1]
        xa %= a
        xb %= b
        xc %= c
    A.append((2*A[-1])%a)
    B.append((2*B[-1])%b)
    C.append((2*C[-1])%c)

ANS = []
for i in range(N):
    if X[i] == 1:
        ANS.append(1 + F[(xb-B[i]) % b])
    else:
        ANS.append(1 + F[(xc+C[i]) % c])

ANS.reverse()
print(*ANS,sep='\n')

Solution (Python):
n=int(input())
x=input()
pc=[0]
m=2*10**5
for i in range(1,m+2):
  cnt=0
  j=i
  while i:
    cnt+=i%2
    i//=2
  pc+=[j%cnt]
f=[0]*(m+2)
for i in range(1,m+2):
  if pc[i]==0:f[i]=1
  else:f[i]=f[pc[i]]+1
cnt=x.count('1')
ix=int(x,2)
ixp=ix%(cnt+1)
ixm=ix%(cnt-1) if cnt-1 else 0
d=1<<(n-1)
for i in range(n):
  dp=pow(2,n-i-1,cnt+1)
  if cnt-1:dm=pow(2,n-i-1,cnt-1)
  if x[i]=='0':print(f[(ixp+dp)%(cnt+1)]+1)
  else:
    if cnt-1:print(f[(ixm-dm)%(cnt-1)]+1)
    else:print(0)

Solution (Python):


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


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


def solve():
    N = read_int()
    X = input()
    one_count = X.count('1')
    if one_count == 0:
        for _ in range(N):
            print(1)
        return

    new_X = [0]*N
    steps = [0]*N

    base_up = 1
    up_under_modulo = 0

    for i in range(N-1, -1, -1):
        if X[i] == '1':
            up_under_modulo = (up_under_modulo+base_up)%(one_count+1)
        if X[i] == '0':
            new_X[i] += base_up
            steps[i] = 1
        base_up = (base_up*2)%(one_count+1)

    base_down = 1
    down_under_modulo = 0

    if one_count > 1:
        for i in range(N-1, -1, -1):
            if X[i] == '1':
                down_under_modulo = (down_under_modulo+base_down)%(one_count-1)
            if X[i] == '1':
                new_X[i] -= base_down
                steps[i] = 1
            base_down = (base_down*2)%(one_count-1)

    for i in range(N):
        if X[i] == '1':
            if one_count > 1:
                new_X[i] = (new_X[i]+down_under_modulo)%(one_count-1)
        else:
            new_X[i] = (new_X[i]+up_under_modulo)%(one_count+1)

    for i in range(N):
        print(steps[i]+popcount(new_X[i]))


if __name__ == '__main__':
    solve()

Solution (Python):
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

def solve():
    N = INT()
    xbin = input()
    xdec = int(xbin, 2)
    m = xbin.count('1')

    a = xdec % (m+1)
    b = xdec % (m-1) if m > 1 else 0

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

    for i in range(N):
        if xbin[i] == '0':
            y = ( a + pow(2, N-i-1, m+1) ) % ( m+1 )
            print(num[y] + 1)
        elif m <= 1:
            print(0)
        else:
            y = ( b - pow(2, N-i-1, m-1) ) % ( m-1 )
            print(num[y] + 1)

if __name__ == '__main__':
    solve()

Solution (Python):
N = int(input())
X = input()
x = X[::-1]
one = X.count('1')
up = 0
down = 0
for i in range(N):
    up += (int(x[i]) * pow(2,i,one+1) % (one+1))
    up %= one+1
    if one > 1:
        down += (int(x[i]) * pow(2,i,one-1) % (one-1))
        down %= one-1

def f(ud,one):
    cnt = 1
    while ud != 0:
        one = format(ud,'b').count('1')
        ud = ud % one
        cnt += 1
    return cnt



for i in range(len(X)):
    if X[i] == '1':
        if one > 1:
            print(f((down - pow(2,(len(X)-1) - i, one-1)) % (one-1),one-1))
        
        else:
            print(0)

    else:
        print(f((up + pow(2,(len(X)-1) - i, one+1)) % (one+1),one+1))

Solution (Python):
N = int(input())
X = input()
x = X[::-1]
one = X.count('1')
up = 0
down = 0
for i in range(N):
    up += (int(x[i]) * pow(2,i,one+1) % (one+1))
    up %= one+1
    if one > 1:
        down += (int(x[i]) * pow(2,i,one-1) % (one-1))
        down %= one-1

def f(ud,one):
    if ud == 0:
        return 1

    cnt = 0
    while ud != 0:
        ud = ud % one
        one = format(ud,'b').count('1')
        cnt += 1
    return cnt



for i in range(len(X)):
    if X[i] == '1':
        if one > 1:
            print(f((down - pow(2,(len(X)-1) - i, one-1)) % (one-1),one-1))
        
        else:
            print(0)

    else:
        print(f((up + pow(2,(len(X)-1) - i, one+1)) % (one+1),one+1))