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 = list(input())
y = x.count("1")
s, t = y - 1, y + 1
p = [1] * 20
for i in range(1, 20):
    p[i] = p[i - 1] * 2
p.sort(reverse = True)
a, b, u, v = 1 / 2, 1 / 2, 0, 0
m1, m2 = [0] * n, [0] * n
if not s == 0:
    for i in range(1, n + 1):
        a += a
        a %= s
        b += b
        b %= t
        m1[i - 1] = a
        m2[i - 1] = b
        if x[-i] == "1":
            u += a
            v += b
else:
    for i in range(1, n + 1):
        b += b
        b %= t
        m2[i - 1] = b
        if x[-i] == "1":
            v += b
ans = [1] * n
if not s == 0:
    for i in range(1, n + 1):
        if x[-i] == "1":
            j = (u - m1[i - 1]) % s
        else:
            j = (v + m2[i - 1]) % t
        if not j == 0:
            while not j == 0:
                ans[-i] += 1
                l = j
                cnt = 0
                for k in p:
                    if l == 0:
                        break
                    if k <= l:
                        cnt += 1
                        l -= k
                j = j % cnt
else:
    for i in range(1, n + 1):
        if x[-i] == "1":
            ans[-i] = 0
        else:
            j = (v + m2[i - 1]) % t
            if not j == 0:
                while not j == 0:
                    ans[-i] += 1
                    l = j
                    cnt = 0
                    for k in p:
                        if l == 0:
                            break
                        if k <= l:
                            cnt += 1
                            l -= k
                    j = j % cnt
for i in ans:
    print(i)

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
X = input().strip()

def solve(N,X):
    if not '1' in X:
        for i in range(N):
            print(1)
        exit()

    def popcount(n):
        t = 0
        while n > 0:
            k = bin(n).count('1')
            n %= k
            t += 1
        return t

    X1 = X.count('1')

    Rp1 = []
    Rm1 = []
    Bp1 = []
    Bm1 = []

    for i, x in enumerate(list(X[::-1])):
        tp1 = pow(2,i,X1+1)
        if X1-1 > 0:
            tm1 = pow(2,i,X1-1)
        else:
            tm1 = 0
        Bp1.append(tp1)
        Bm1.append(tm1)
        if x == '1':
            Rp1.append(tp1)
            Rm1.append(tm1)
        else:
            Rp1.append(0)
            Rm1.append(0)

    basep1 = sum(Rp1) % (X1+1)
    if X1-1 > 0:
        basem1 = sum(Rm1) % (X1-1)
    else:
        basem1 = 0
    Rp1 = Rp1[::-1]
    Rm1 = Rm1[::-1]
    Bp1 = Bp1[::-1]
    Bm1 = Bm1[::-1]

    
    
    for bp1,bm1,x in zip(Bp1,Bm1,X):
        if x == '1':
            t = basem1 - bm1
            MOD = X1 - 1
            if MOD <= 0:
                print(0)
                continue
        else:
            t = basep1 + bp1
            MOD = X1 + 1
        
        
        print(popcount(t % MOD) + 1)

solve(N,X)

Solution (Python):


'''
Author: andyli
Time: 2020-07-11 19:58:49
'''

def main():
    n = int(input())
    x = input()
    popcounts = x.count('1')
    if popcounts == 1:
        for i in range(n):
            if x[i] == '1':
                print(0)
                continue
            if (i == n-1 and x[-1] == '0') or (i != n-1 and x[-1] == '1'):
                print(2)
            else:
                print(1)
        return
    if popcounts == 0:
        for i in range(n):
            print(1)
        
        return
    modmi = [0 for i in range(n+2)]
    modpl = [0 for i in range(n+2)]
    s = 1
    for i in range(0,n+2):
        s %= (popcounts-1)
        modmi[i] = s
        s <<= 1
    s = 1
    for i in range(0,n+2):
        s %= (popcounts+1)
        modpl[i] = s
        s <<= 1
    demodmi = int(x,base=2)%(popcounts-1)
    demodpl = int(x,base=2)%(popcounts+1)
    def count(n):
        ans = 0
        while n > 0:
            n %= bin(n).count('1')
            ans += 1
        return ans
    
    for i in range(n):
        if x[i] == '0':
            demodmi = (demodmi + modmi[(n-i-1)]) % (popcounts-1)
            demodpl = (demodpl + modpl[(n-i-1)]) % (popcounts+1)
            pass
        else:
            demodmi = (demodmi - modmi[(n-i-1)]) % (popcounts-1)
            demodpl = (demodpl - modpl[(n-i-1)]) % (popcounts+1)
            pass
        mod = demodmi if x[i] == '1' else demodpl
        
        print(1 + count(mod))
        if x[i] == '1':
            demodmi = (demodmi + modmi[(n-i-1)]) % (popcounts-1)
            demodpl = (demodpl + modpl[(n-i-1)]) % (popcounts+1)
            pass
        else:
            demodmi = (demodmi - modmi[(n-i-1)]) % (popcounts-1)
            demodpl = (demodpl - modpl[(n-i-1)]) % (popcounts+1)
            pass

    return

if __name__ == "__main__":
    main()

Solution (Python):
def base10toN(num, base):
    converted_string, modstring = "", ""
    currentnum = num
    if not num:
        return '0'
    while currentnum:
        mod = currentnum % base
        currentnum = currentnum // base
        converted_string = chr(48 + mod + 7*(mod > 10)) + converted_string
    return converted_string
n=int(input())
pop=[0]*(2*10**5+1)
for i in range(1,2*10**5+1):
  temp=base10toN(i,2)
  ans=0
  for j in range(len(temp)):
    if temp[j]=='1':
      ans+=1
  r=i%ans
  pop[i]=pop[r]+1
x=input()
ones=0
ans1=[]
for i in range(n):
  if x[i]=='1':
    ones+=1
dividemore=0
divideless=0
for i in range(n):
  if x[i]=='1':
    dividemore=(pow(2,n-1-i,ones+1)+dividemore)%(ones+1)
    if ones>=2:
      divideless=(pow(2,n-1-i,ones-1)+divideless)%(ones-1)
for i in range(n):
  counter=0
  if x[i]=='0':
    temp=(dividemore+pow(2,n-1-i,ones+1))%(ones+1)
  else:
    if ones==1:
      ans1.append('0')
      continue
    else:
      temp=(divideless-pow(2,n-1-i,ones-1))%(ones-1)
  ans1.append(str(pop[temp]+1))
print(' '.join(ans1))

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

X_pc = X.count("1")
X_res_m1 = 0
X_res_p1 = 0
for i, s in enumerate(reversed(X)):
    if s == "1":
        if X_pc > 1:
            X_res_m1 += pow(2, i, X_pc - 1)
            X_res_m1 %= X_pc - 1

        X_res_p1 += pow(2, i, X_pc + 1)
        X_res_p1 %= X_pc + 1

f = [-1] * (X_pc + 1)
f[0] = 0
for n in range(1, X_pc + 1):
    pc = format(n, "b").count("1")
    f[n] = f[n % pc] + 1

ans = []
for i, s in enumerate(reversed(X)):
    if s == "1":
        if X_pc > 1:
            fx = (X_res_m1 - pow(2, i, X_pc - 1)) % (X_pc - 1)
            ans.append(f[fx] + 1)
        else:
            ans.append(0)

    else:
        fx = (X_res_p1 + pow(2, i, X_pc + 1)) % (X_pc + 1)
        ans.append(f[fx] + 1)

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

Solution (Python):
n = int(input())
x = input()
 
from collections import Counter
import sys
 
up = [0]*n
do = [0]*n
 
b = Counter(x)
 
if b["1"] >= 2:
    pr = b["1"]
    a = 1
    for i in range(n):
        up[n-1-i] = a
        a = a*2 % (pr+1)
    
    a = 1
    for i in range(n):
        do[n-1-i] = a
        a = a*2 % (pr-1)
        
    upsum,dosum = 0,0
    for i in range(n):
        upsum = (upsum + (int(x[i]) * up[i])) % (pr+1)
        dosum = (dosum + (int(x[i]) * do[i])) % (pr-1)
        
    pop = [0] * (n+1)
    for i in range(1,n+1):
        xx = bin(i)[2:]
        c = Counter(xx)
        pop[i] = i % c["1"]
        
    for i in range(n):
        if x[i] == "0":
            ss = (upsum + up[i]) % (pr+1)
            
            aa = 0
            for j in range(400):
                if ss == 0:
                    break
                else:
                    ss = pop[ss]
                    aa += 1
                    
            print(aa+1)
            
        elif x[i] == "1":
            ss = (dosum + (pr-1) - do[i]) % (pr-1)
            
            aa = 0
            for j in range(400):
                if ss == 0:
                    break
                else:
                    ss = pop[ss]
                    aa += 1
                    
            print(aa+1)
            
else:
    pr = b["1"]
    a = 1
    for i in range(n):
        up[n-1-i] = a
        a = a*2 % (pr+1)
 
    upsum = 0
    for i in range(n):
        upsum = (upsum + (int(x[i]) * up[i])) % (pr+1)
 
    pop = [0] * (n+1)
    for i in range(1,n+1):
        xx = bin(i)[2:]
        c = Counter(xx)
        pop[i] = i % c["1"]
    
    for j in range(n):
        if x[j] == "1":
            print(0)
        else:
            ss = (upsum + up[j]) % (pr+1)
            
            aa = 0
            for k in range(400):
                if ss == 0:
                    break
                else:
                    ss = pop[ss]
                    aa += 1
                    
            print(aa+1)

Solution (Python):


'''
Author: andyli
Time: 2020-07-11 19:58:49
'''

import os
from io import BytesIO, IOBase
import sys


def main():
    n = int(input())
    x = input()
    popcounts = x.count('1')
    if popcounts == 1:
        for i in range(n):
            if x[i] == '1':
                print(0)
                continue
            if (i == n-1 and x[-1] == '0') or (i != n-1 and x[-1] == '1'):
                print(2)
            else:
                print(1)
        return
    if popcounts == 0:
        for i in range(n):
            print(1)
        
        return
    modmi = [0 for i in range(n+2)]
    modpl = [0 for i in range(n+2)]
    s = 1
    for i in range(0,n+2):
        s %= (popcounts-1)
        modmi[i] = s
        s <<= 1
    s = 1
    for i in range(0,n+2):
        s %= (popcounts+1)
        modpl[i] = s
        s <<= 1
    demodmi = int(x,base=2)%(popcounts-1)
    demodpl = int(x,base=2)%(popcounts+1)
    def count(n):
        ans = 0
        while n > 0:
            n %= bin(n).count('1')
            ans += 1
        return ans
    
    for i in range(n):
        if x[i] == '0':
            demodmi = (demodmi + modmi[(n-i-1)]) % (popcounts-1)
            demodpl = (demodpl + modpl[(n-i-1)]) % (popcounts+1)
            pass
        else:
            demodmi = (demodmi - modmi[(n-i-1)]) % (popcounts-1)
            demodpl = (demodpl - modpl[(n-i-1)]) % (popcounts+1)
            pass
        mod = demodmi if x[i] == '1' else demodpl
        
        print(1 + count(mod))
        if x[i] == '1':
            demodmi = (demodmi + modmi[(n-i-1)]) % (popcounts-1)
            demodpl = (demodpl + modpl[(n-i-1)]) % (popcounts+1)
            pass
        else:
            demodmi = (demodmi - modmi[(n-i-1)]) % (popcounts-1)
            demodpl = (demodpl - modpl[(n-i-1)]) % (popcounts+1)
            pass

    return



BUFSIZE = 1048576


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda: self.buffer.read().decode('ascii')
        self.readline = lambda: self.buffer.readline().decode('ascii')


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
def input(): return sys.stdin.readline().rstrip('\r\n')




if __name__ == '__main__':
    main()

Solution (Python):
def g(n):
    c = 0
    while n > 0:
        p = 0
        n2 = n
        while n2 > 0:
            if n2%2 == 1:
                p += 1

            n2 //= 2

        n %= p
        c += 1

    return c


def modPow(a, b, mod):
    x = 1
    
    while b > 0:
        if b & 1:
            x = (x*a)%mod

        a = (a**2)%mod
        b //= 2

    return x










def f(N, X):
    b = sum(1 if x == '1' else 0 for x in X)

    Xplus = 0
    Xminus = 0

    for x in X:
        Xplus = (Xplus*2 + (1 if x == '1' else 0))%(b+1)
        
        if b > 1:
            Xminus = (Xminus*2 + (1 if x == '1' else 0))%(b-1)

    for i in range(N):
        if X[i] == '0':

            X2 = (Xplus + modPow(2, N-i-1, b+1))%(b+1)
            print(g(X2) + 1)
        elif b > 1:

            X2 = (Xminus - modPow(2, N-i-1, b-1))%(b-1)
            print(g(X2) + 1)
        else:
            print(0)


N = int(input())
X = input()
f(N, X)

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [-int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    N = NI()
    X = SI()

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

    xc = X.count('1')
    xp = 0
    xm = 0
    xpb = 1
    xmb = 1
    for i in range(N-1,-1,-1):
        xp = (xp + int(X[i]) * xpb) % (xc+1)
        if xc > 1:
            xm = (xm + int(X[i]) * xmb) % (xc-1)
            xmb = (xmb * 2) % (xc - 1)
        else:
            xm = 0
            xmb = 0
        xpb = (xpb * 2) % (xc+1)

    for i in range(N):
        if X[i] == '0':
            x = (xp + pow(2,N-i-1,xc+1)) % (xc+1)
        else:
            if xc > 1:
                x = (xm - pow(2,N-i-1,xc-1)) % (xc-1)
            else:
                x = -1
        if x < 0:
            print(0)
        else:
            print(cnt[x]+1)



if __name__ == '__main__':
    main()

Solution (Python):
def main():

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

    p = 0
    for i in range(n):
        if x[i] == '1':
            p += 1

    if p == 0:
        ans = [1]*n
        for i in range(n):
            print(ans[i])
        exit()

    if p == 1:
        ans = [0]*n
        for i in range(n):
            if x[i] == '1':
                ans[i] = 0
            else:
                if i != n-1:
                    if x[-1] != 1:
                        ans[i] = 1
                    else:
                        ans[i] = 2
                else:
                    ans[i] = 2
        for i in range(n):
            print(ans[i])
        exit()

    def power(a, n, mod):
        bi=str(format(n,"b")) 
        res=1
        for i in range(len(bi)):
            res=(res*res) %mod
            if bi[i]=="1":
                res=(res*a) %mod
        return res

    X1 = 0
    X2 = 0
    import copy
    s = copy.copy(x)
    s.reverse()
    
    for i in range(n):
        if s[i] == '1':
            X1 += power(2, i, p+1)
            X2 += power(2, i, p-1)

    
    
    
    ans = [0]*n
    for i in range(n):
        if x[i] == '0':
            temp = X1
            temp += power(2, n-1-i, p+1)
            temp %= (p+1)
            if temp == 0:
                ans[i] = 1
                continue
            cnt = 0
            d = p+1
            while temp:
                cnt += 1
                temp %= d
                b = format(temp, 'b')
                d = 0
                for j in range(len(b)):
                    if b[j] == '1':
                        d += 1
        else:
            temp = X2
            temp -= power(2, n-1-i, p-1)
            temp %= (p-1)
            if temp == 0:
                ans[i] = 1
                continue
            cnt = 0
            d = p-1
            while temp:
                cnt += 1
                temp %= d
                b = format(temp, 'b')
                d = 0
                for j in range(len(b)):
                    if b[j] == '1':
                        d += 1
        ans[i] = cnt
    
    for i in range(n):
        print(ans[i])

if __name__ == '__main__':
    main()

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

pop = [0]*(N+1)
amari = [0]*(N+1)
for i in range(1,N+1):
    pop[i]=pop[i-(i&(-i))]+1
    amari[i] = amari[i%pop[i]]+1

cnt1 = 0
for i in range(N):
    if X[i]=="1":
        cnt1+=1
Y = cnt1+1
Z = cnt1-1

baseY = 0
baseZ = 0
for i in range(N):
    K = int(X[N-1-i])
    if K==1:
        baseY += pow(2,i,Y)
        if Z!=0:
            baseZ += pow(2,i,Z)
        else:
            baseZ =-1
baseY = baseY%Y
if Z!=0:
    baseZ = baseZ%Z
else:
    baseZ = -1

for i in range(N):
    if X[i]=="0":
        out = (baseY + pow(2,N-1-i,Y))%Y
        print(amari[out]+1)
    elif X[i]=="1":
        if Z!=0:
            out = (baseZ - pow(2,N-1-i,Z))%Z
            print(amari[out]+1)
        else:
            print(0)

Solution (Python):
N = int(input())
X = list(map(int, list(input())))
X.reverse()
def int2bit(n):
	ret = [0 for i in range(18)]
	cnt = 0
	i = 0
	while n > 0:
		ret[i] = n % 2
		cnt += n % 2
		n = n // 2
		i += 1
	return (ret, cnt)

def func(bit, popcount):
	ret = 0
	base = 1
	for b in bit:
		ret = (ret + base*b) % popcount
		base = (base * 2) % popcount
	return ret

def func2(n):
	(bit, popcount) = int2bit(n)
	return func(bit, popcount)

F = [0 for _ in range(N+1)]

for n in range(1, N+1):
	a = func2(n)
	F[n] = 1 + F[a]
P = sum(X)

f_1 = func(X, P+1)
f_0 = func(X, max(1, P-1))

base_1 = [1]
base_0 = [1]
for i in range(N-1):
	base_1.append((base_1[i] * 2) % (P+1))
	base_0.append((base_0[i] * 2) % max(1, P-1))
for i in range(N):
	idx = N - 1 - i
	if X[idx] == 0:
		print(1 + F[(f_1 + base_1[idx]) % (P+1)])
	if X[idx] == 1:
		if P == 1:
			print(0)
		else:
			print(1 + F[(f_0 - base_0[idx]) % (P-1)])

Solution (Python):
def popcount(n):
    ans=0
    for i in range(20):
        if n>>i & 1:
            ans+=1
    return ans

N=int(input())
X=input()
n=0

for i in range(N):
    if X[i]=='1':
        n+=1
np1=0
nm1=0
temp1=1
temp2=1
nm=n-1
if nm==0:
    nm=1
for i in range(N-1,-1,-1):
    if X[i]=='1':
        np1=(np1+temp1)%(n+1)
        nm1=(nm1+temp2)%nm
    temp1=(temp1*2)%(n+1)
    temp2=(temp2*2)%nm
    
for i in range(N):
    ans=1
    if X[i]=='1':
        if n==1:
            print(0)
            continue
        temp=(nm1-pow(2,(N-1-i),n-1))%(n-1)
        while temp>0:
            pop_n=popcount(temp)
            temp=temp%pop_n
            ans+=1
    elif X[i]=='0':
        temp=(np1+pow(2,(N-1-i),n+1))%(n+1)
        while temp>0:
            pop_n=popcount(temp)
            temp=temp%pop_n
            ans+=1
    print(ans)

Solution (Python):


import sys
stdin = sys.stdin

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def popcount(m):
    res = 0
    while m:
        if m & 1:
            res += 1
        m //= 2
    return res
def f(m):
    cnt = 0
    while m:
        
        m = m % popcount(m)
        cnt += 1
    return cnt

def main():
    n = ni()
    x = ns()
    pop0 = x.count("1") + 1
    pop1 = x.count("1") - 1
    y0 = 0; y1 = 0
    for i, xi in enumerate(x):
        r = n - i - 1
        if xi == "1":
            y0 += pow(2, r, pop0)
            y0 %= pop0
            if pop1 != 0:
                y1 += pow(2, r, pop1)
                y1 %= pop1

    for i, xi in enumerate(x):
        r = n - i - 1
        if xi == "0":
            m = (y0 + pow(2, r, pop0)) % pop0
            print(f(m) + 1)
        else:
            if pop1 == 0:
                print(0)
                continue
            m = (y1 - pow(2, r, pop1)) % pop1
            print(f(m) + 1)

if __name__ == "__main__":
    main()

Solution (Python):


N = int(input())

X = input()
one = 0
intX = 0
bitnow = 1
for i in reversed(range(len(X))):
    if X[i] == '1':
        one += 1
        intX += bitnow
    bitnow *= 2
hi = one + 1
lo = one - 1
hirembase = intX % hi
lorembase = 0
if lo != 0:
    lorembase = intX % lo





bo = []
for i in range(200010):
    num = 0
    while i != 0:
        bit = bin(i)
        bitnum = 0
        for j in range(len(bit)):
            if j == 0 or j == 1:
                continue
            if bit[j] == '1':
                bitnum += 1
        i = i % bitnum
        num += 1
    bo.append(num)
ans = []
hirem = 1
lorem = 1
for i in reversed(range(len(X))):
    if X[i] == '0':
        num = (hirembase + hirem + hi) % hi
        ans.append(bo[num] + 1)
    else:
        if one == 1:
            ans.append(0)
        else:
            num = (lorembase - lorem + lo) % lo
            ans.append(bo[num] + 1)
    hirem = (hirem * 2) % hi
    if one != 1:
        lorem = (lorem * 2) % lo


for i in reversed(range(len(ans))):
    print(ans[i])

Solution (Python):
N = int(input())
X = input()
popcount_X = X.count('1')
numX = int(X, 2)
a, b = numX % (popcount_X + 1), numX % (popcount_X - 1) if popcount_X != 1 else 0
for i, x in enumerate(X, 1):
    if x == '1' and popcount_X == 1:
        print(0); continue
    ans = 1
    if x == '1':
        temp = (b - pow(2, N - i, popcount_X - 1)) % (popcount_X - 1)
    else:
        temp = (a + pow(2, N - i, popcount_X + 1)) % (popcount_X + 1)
    while temp:
        p = format(temp, 'b').count('1')
        temp %= p
        ans += 1
    print(ans)

Solution (Python):
def main():
    import sys
    N=int(sys.stdin.readline())
    X=sys.stdin.readline()

    no=X.count('1')
    np=no+1
    nm=no-1
    nm_flag=bool(nm)

    np_mods=[-1]*N
    nm_mods=[-1]*N
    
    np_mods[0]=1
    nm_mods[0]=1
    
    for i in range(1,N):
        np_mods[i]=(np_mods[i-1]*2)%np
        if nm_flag:
            nm_mods[i]=(nm_mods[i-1]*2)%nm

    np_mods.reverse()
    nm_mods.reverse()
    
    np_mods_sum=0
    nm_mods_sum=0
    for i in range(N):
        if X[i]=='1':
            np_mods_sum+=np_mods[i]
            nm_mods_sum+=nm_mods[i]

    for i in range(N):
        if X[i]=='0':
            n=(np_mods_sum+np_mods[i])%np

        else:
            if nm_flag:
                n=(nm_mods_sum-nm_mods[i])%nm
            else:
                print(0)
                continue
        if n==0:
            print(1)
            continue
        count=1
        while True:
            bs=str(bin(n))[2:]
            k=bs.count('1')
            n=n%k
            count+=1
            if n==0:
                break
        print(count)

main()

Solution (Python):
N = int(input())
X = input()
tmp = sum(X[i] == '1' for i in range(N))

for_zero = tmp + 1
for_one = tmp - 1
zero_S = 0
one_S = 0


numbers = [0] * N
counts = [1] * N

if tmp == 1:
    for i in range(N):
        if X[i] == '1':
            counts[i] = 0
    
    tmp_zero = 1
    for i in range(N):
        if X[-i - 1] == '1':
            zero_S += tmp_zero
            zero_S %= for_zero
        tmp_zero *= 2
        tmp_zero %= for_zero

    
    tmp_zero = 1
    for i in range(N):
        if X[-i - 1] == '1':
            pass
        else:
            numbers[-i - 1] = (zero_S + tmp_zero) % for_zero
        tmp_zero *= 2
        tmp_zero %= for_zero

else:
    
    tmp_zero = 1
    tmp_one = 1
    for i in range(N):
        if X[-i - 1] == '1':
            one_S += tmp_one
            one_S %= for_one
            zero_S += tmp_zero
            zero_S %= for_zero
        tmp_zero *= 2
        tmp_zero %= for_zero
        tmp_one *= 2
        tmp_one %= for_one

    
    tmp_zero = 1
    tmp_one = 1
    for i in range(N):
        if X[-i - 1] == '1':
            numbers[-i - 1] = (one_S - tmp_one) % for_one
        else:
            numbers[-i - 1] = (zero_S + tmp_zero) % for_zero
        tmp_zero *= 2
        tmp_zero %= for_zero
        tmp_one *= 2
        tmp_one %= for_one




def solution(number):
    loop = 0
    while number != 0:
        popcount = 0
        for i in range(30):
            if (1 << i) & number:
                popcount += 1
        number %= popcount
        loop += 1
    return loop

for i in range(N):
    counts[i] += solution(numbers[i])

print(*counts, sep='\n')

Solution (Python):


import sys
input=sys.stdin.readline


LEN=2*10**5+10

moves=[0]*LEN
for i in range(1,LEN):
  tmp=i
  cnt=0
  while tmp!=0:
    popcount=0
    for j in range(20):
      if tmp&(1<<j):
        popcount+=1
    tmp%=popcount
    cnt+=1
  moves[i]=cnt

n=int(input())
x=input()
k=x.count('1')
if k==0:
    for i in range(n):
        print(1)
elif k==1:
    pos=x.index('1')
    for i in range(n):
        if i==pos:
            print(0)
        else:
            if pos==n-1:
                print(2)
            else:
                if i==n-1:
                    print(2)
                else:
                    print(1)
else:
    sum1=0
    sum2=0
    tmp1=1
    tmp2=1
    for i in range(n-1,-1,-1):
        if x[i]=='1':
            sum1+=tmp1
            sum1%=k+1
            sum2+=tmp2
            sum2%=k-1
        tmp1*=2
        tmp1%=k+1
        tmp2*=2
        tmp2%=k-1
    for i in range(n):
        if x[i]=='0':
            tmp=sum1+pow(2,n-i-1,k+1)
            tmp%=k+1
            print(moves[tmp]+1)
        else:
            tmp=sum2-pow(2,n-i-1,k-1)
            tmp%=k-1
            print(moves[tmp]+1)

Solution (Python):

import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
X=input()
XX=int(X,2)
m=X.count('1')
if m-1>0:
    l=[XX%(m+1),(XX%(m-1))]
else:
    l=[XX%(m+1),0]
for i in range(N):
    if X[i]=='0':
        n=l[0]+pow(2,(N-1)-i,m+1)
        n%=m+1
    else:
        if m-1==0:
            print(0)
            continue
        n=l[1]-pow(2,(N-1)-i,m-1)
        n%=m-1
    ans=1
    while n>0:
        n%=bin(n).count('1')
        ans+=1
    print(ans)

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

def main():
    from sys import stdin, stdout
    input = stdin.readline
    print = stdout.write
    n = int(input())
    x = input().rstrip()
    pc = sum(1 for i in x if i == '1')
    xint = int(x, 2)
    lpc = [1 for i in range(n)]
    upc = [1 for i in range(n)]
    dp = [1 for i in range(n+1)]
    for i in range(1, n+1):
        dp[i] = dp[i % popcount(i)] + 1
    lmod = xint % (pc - 1) if pc >= 2 else -1
    rmod = xint % (pc + 1)
    if pc >= 2:
        for i in range(1, n):
            lpc[i] = (lpc[i - 1] * 2) % (pc - 1)
    for i in range(1, n):
        upc[i] = (upc[i - 1] * 2) % (pc + 1)
    for i in range(n - 1, -1, -1):
        if x[n-1-i] == '1':
            if pc == 1:
                print('0\n')
            else:
                print('%d\n' % (dp[(lmod - lpc[i]) % (pc-1)]))
        else:
            print('%d\n' % (dp[(rmod + upc[i]) % (pc+1)]))

main()

Solution (Python):
n = int(input())
x = list(input())
c1 = x.count("1")+1
c2 = c1-2

now1 = 0
now2 = 0

for i in range(n):
    if x[-1-i] == "1":
        now1 += pow(2,i,c1)
        if c2 != 0:
            now2 += pow(2,i,c2)
        
    now1 %= c1
    if c2 != 0:
        now2 %= c2

for i in range(n):
    if x[i] == "1":
        
        if c2 == 0:
            print(0)
            continue
        now = (now2-pow(2,n-1-i,c2))%c2
        
        count = 1
        while now > 0:
            q = bin(now)
            y = q.count("1")
            now %= y
            count += 1
        print(count)
    else:
        
        now = (now1+pow(2,n-1-i,c1))%c1
        
        count = 1
        while now > 0:
            q = bin(now)
            y = q.count("1")
            now %= y
            count += 1
        print(count)

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

def okikae(n):
    kaisu = 0
    if n == 0:
        return 0
    while 1:
        P = popcnt1(n)
        n %= P
        kaisu += 1
        if n == 0:
            return kaisu

OKI = [okikae(i) for i in range(200001)]
X = int(input())
Norig = input()
N = int(Norig,2)
Npop = Norig.count("1")
F = Npop + 1
H = Npop - 1
if H == 0:
    H = -1
FueAmari = N%(Npop + 1)
if Npop != 1:
    HeruAmari = N%(Npop - 1)
else:
    HeruAmari = -1
Fues = []
Herus = []
fue = 1
heru = 1
for i in range(2*(10**5+1)):
    fue %= F
    heru %= H
    Fues.append(fue)
    Herus.append(heru)
    fue *= 2
    heru *= 2
RNorig = reversed(Norig)
Results = []
Zougen = []
Kaisu = [0] * X

for n,bit in enumerate(Norig):
    if bit == "0":
        Zougen.append(True)
        print(1+OKI[(FueAmari + Fues[X-1-n] )% F])
    else:
        if H == -1:
            print(0)
            continue
        Zougen.append(False)
        print(1+OKI[(HeruAmari - Herus[X-1-n]) % H])