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):
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

pc_memo = defaultdict(int)
memo = defaultdict(int)


def to_next(x):
    if x not in pc_memo.keys():
        pc_memo[x] = x % "{:b}".format(x).count('1')
    return pc_memo[x]


def f(x):
    if x == 0:
        return 0
    if x not in memo.keys():
        memo[x] = f(to_next(x))+1
    return memo[x]


for i in range(2*10**5):
    f(i)

n = int(input())
x = input().rstrip()
one_cnt = x.count('1')

mod_minus = 0
mod_plus = 0
for i, a in enumerate(reversed(x)):
    if a == '1':
        if 0 < one_cnt-1:
            mod_minus += pow(2, i, one_cnt-1)
            mod_minus %= one_cnt-1
        mod_plus += pow(2, i, one_cnt+1)
        mod_plus %= one_cnt+1


for i in range(n):
    if x[i] == '0':
        nx = mod_plus+pow(2, n-i-1, one_cnt+1)
        nx %= one_cnt+1
        print(f(nx)+1)
    else:
        if 0 < one_cnt-1:
            nx = mod_minus-pow(2, n-i-1, one_cnt-1)
            nx %= one_cnt-1
            print(f(nx)+1)
        else:
            print(0)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
N = int(input())
X = input()
if X == '0':
    for _ in range(N):
        print(1)
        exit()

mem = [None] * (200005)
mem[0] = 0
def f(n):
    if mem[n] is not None: return mem[n]
    c = bin(n).count('1')
    r = 1 + f(n%c)
    mem[n] = r
    return r

for i in range(200005):
    f(i)

cnt = X.count('1')
a,b = cnt+1, cnt-1

ans = [None] * N
x = int(X,2)

n = x % a
for i,c in reversed(list(enumerate(X))):
    if c=='1': continue
    ans[i] = mem[(n+pow(2,N-i-1,a))%a] + 1

if b:
    n = x % b
    for i,c in reversed(list(enumerate(X))):
        if c=='0': continue
        ans[i] = mem[(n-pow(2,N-i-1,b))%b] + 1
else:
    for i in range(N):
        if ans[i] is None:
            ans[i] = 0

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

Solution (Python):
n,x=int(input()),input()
o=x.count("1")
if o==1:
    for i,v in enumerate(x):
        if v=="1":print(0)
        else:
            if i!=n-1:
                if x[-1]=="0":print(1)
                else:print(2)
            else:print(2)

else:
    m=o-1
    M=o+1
    mp,mm={0:1},{0:1}
    for i in range(1,n):
        mp[i]=mp[i-1]*2%M
        mm[i]=mm[i-1]*2%m
    A=int(x,2)
    a=A%m
    b=A%M
    rest={0:0}
    for i in range(1,o+1):
        rest[i]=1+rest[i%bin(i).count("1")]
    for i,v in enumerate(x):
        if v=="1":
            print(1+rest[(a-mm[n-i-1])%m])
        else:
            print(1+rest[(b+mp[n-i-1])%M])

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

a = int(X, 2)
b = X.count("1")

if b > 1:
    a1 = a % (b-1)
else:
    a1 = 0
a0 = a % (b+1)

for i in range(N):
    if X[i] == "1":
        if b == 1:
            print(0)
            continue
        t = (a1 - pow(2, N-1-i, b-1)) % (b-1)
    else:
        t = (a0 + pow(2, N-1-i, b+1)) % (b+1)
    
    ans = 1
    while t > 0:
        t %= bin(t).count("1")
        ans += 1
    print(ans)

Solution (Python):


import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    N = int(input())
    S = input()
    cnt0 = S.count("1")

    if cnt0 == 0:
        print(*[1]*N, sep="\n")
        return

    X = int(S, 2)

    def f2():
        cache = [-1] * max(9, cnt0+1)
        cache[0] = 0
        for i in range(4): cache[1<<i] = 1
        def f2(x):
            if cache[x] != -1:
                return cache[x]

            y = bin(x).count("1")
            z = 1 + f2(x % y)
            cache[x] = z

            return z
        f2.cache = cache
        return f2
    f2 = f2()

    dc = {}
    for k, v in (("0", 1), ("1", -1)):
        x = cnt0 + v
        y = X % x if x else 0
        dc[k] = (x, v, y, [1, N-1])

    ans = [0] * N
    for i in reversed(range(N)):
        si = S[i]
        cnt, v, n, m1 = dc[si]

        if cnt == 0:
            ans[i] = 0
            continue

        m2 = (m1[0]<<(m1[1]-i)) % cnt
        n = (n + v*m2) % cnt
        m1[0], m1[1] =  m2, i

        ans[i] = 1 + f2(n)

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


if __name__ == "__main__":
    resolve()

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

x_num = int(X, 2)
cnt1 = X.count('1')

p_zero = x_num % (cnt1 + 1)
p_one = (x_num % (cnt1 - 1) if cnt1 - 1 > 0 else 1)


def f(cnt):
    if (cnt > 0):
        pcount = p_count(cnt)
        return f(cnt % pcount) + 1
    else:
        return 0


def p_count(x):
    cnt = 0
    while (x > 0):
        if x % 2 != 0:
            cnt += 1
        x //= 2
    return cnt


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


for i, x in enumerate(list(X)):
    if (x == '1'):
        
        if cnt1 - 1 > 0:
            xxx = (p_one - pow(2, (N - (i + 1)), cnt1 - 1)) % (cnt1 - 1)
            xxx += cnt1 - 1 if xxx < 0 else 0
            print(f(xxx) + 1)
        else:
            print(0)
    else:
        
        xxx = (p_zero + pow(2, (N - (i + 1)), cnt1 + 1)) % (cnt1 + 1)
        xxx += cnt1 + 1 if xxx < 0 else 0
        print(f(xxx) + 1)

Solution (Python):
n=int(input())
x=list(input())
def str2int(z):
  flag=1
  a=0
  for i in reversed(x):
    if i=='1':a+=flag
    flag*=2
  return a
 
popc=x.count('1')
z=str2int(x)
if popc-1!=0:
  fl_1=z%(popc-1)
fl_0=z%(popc+1)

for i in range(n):
  if x[i]=='1':
    if popc-1==0:
      print(0)
      continue
    mod=(fl_1-pow(2,n-1-i,popc-1))%(popc-1)
  else:mod=(fl_0+pow(2,n-1-i,popc+1))%(popc+1)
  
  cnt=1
  while mod!=0:
    pp=bin(mod).count("1")
    mod%=pp
    cnt+=1
  print(cnt)

Solution (Python):

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

x_num = int(X, 2)
cnt1 = X.count('1')

p_zero = x_num % (cnt1 + 1)
p_one = (x_num % (cnt1 - 1) if cnt1 - 1 > 0 else 1)


def f(cnt):
    if (cnt > 0):
        pcount = p_count(cnt)
        return f(cnt % pcount) + 1
    else:
        return 0


def p_count(x):
    cnt = 0
    while (x > 0):
        if x % 2 != 0:
            cnt += 1
        x //= 2
    return cnt


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


for i, x in enumerate(list(X)):
    if (x == '1'):
        
        if cnt1 - 1 > 0:
            xxx = (p_one - pow(2, (N - (i + 1)), cnt1 - 1)) % (cnt1 - 1)
            xxx += cnt1 - 1 if xxx < 0 else 0
            print(f1(xxx) + 1)
        else:
            print(0)
    else:
        
        xxx = (p_zero + pow(2, (N - (i + 1)), cnt1 + 1)) % (cnt1 + 1)
        xxx += cnt1 + 1 if xxx < 0 else 0
        print(f1(xxx) + 1)

Solution (Python):


import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    N = int(input())
    S = input()
    cnt0 = S.count("1")

    if cnt0 == 0:
        print(*[1]*N, sep="\n")
        return

    X = int(S, 2)

    def f2():
        cache = [-1] * max(9, cnt0+1)
        cache[0] = 0
        for i in range(3): cache[1<<i] = 1
        def f2(x):
            if cache[x] != -1:
                
                return cache[x]

            y = bin(x).count("1")
            z = 1 + f2(x % y)
            cache[x] = z

            return z
        f2.cache = cache
        return f2
    f2 = f2()

    dc = {}
    for k, v in (("0", 1), ("1", -1)):
        x = cnt0 + v
        y = X % x if x else 0
        dc[k] = (x, v, y, [1, N-1])

    ans = [0] * N
    for i in reversed(range(N)):
        si = S[i]
        cnt, v, n, m1 = dc[si]

        if cnt == 0:
            ans[i] = 0
            continue

        ni = N - i - 1
        m2 = (m1[0]<<(m1[1]-i)) % cnt
        n = (n + v*m2) % cnt
        m1[0] = m2; m1[1] = i

        ans[i] = 1 + f2(n)

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


if __name__ == "__main__":
    resolve()

Solution (Python):
def mpow(a,b,m):
    ans=1
    while b >0 :
        if b&1:
            ans = (ans*a)%m
        a=(a*a)%m
        b=b>>1

    return ans

def calcmod(X,m,N):
    mod=0
    X=X[::-1]
    
    for i in range(N):
        if X[i] == '1':
        
            mod += mpow(2,i,m)
            mod%=m
    return mod

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


def findsteps(mm):
    cnt=0
    while mm !=0:
        cnt+=1
        mm=mm%popcount(mm)
    return cnt
N=int(input())
x=input()
X=int(x,2)


m=popcount(X)
m1=m+1
m2=m-1
firstmod=calcmod(x,m1,N)
if m2 !=0:
    secondmod=calcmod(x,m2,N)
fans=[0 for i in range(N)]
k=0
for i in range(N-1,-1,-1):
    if X & (1<<i) >0:
        
        
        if m2 == 0:
            ans=0
        else:
            mm=secondmod - mpow(2,i,m2)
            if mm < 0:
                mm+=m2
            mm=mm%m2
            ans=1+findsteps(mm)
    else:
        mm = firstmod + mpow(2,i,m1)
        mm=mm%m1
        ans=1+findsteps(mm)
    fans[k] = ans
    k+=1
        
for i in fans:
    print(i)

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




original_pop_count = x.count('1')
one_pop_count = original_pop_count - 1
zero_pop_count = original_pop_count + 1

one_mod = 0
zero_mod = 0
for b in x:
    
    if one_pop_count != 0:
        one_mod = (one_mod * 2 + int(b)) % one_pop_count
    zero_mod = (zero_mod * 2 + int(b)) % zero_pop_count


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


one_pow2 = [1] * 220000
zero_pow2 = [1] * 220000
for i in range(1, 220000):
    if one_pop_count != 0:
        one_pow2[i] = one_pow2[i-1] * 2 % one_pop_count
    zero_pow2[i] = zero_pow2[i-1] * 2 % zero_pop_count


for i in range(n-1, -1, -1):
    if x[n-1-i] == '1':
        if one_pop_count != 0:
            nxt = one_mod
            nxt -= one_pow2[i]
            nxt %= one_pop_count
            print(f[nxt] + 1)
        else:
            print(0)
    if x[n-1-i] == '0':
        nxt = zero_mod
        nxt += zero_pow2[i]
        nxt %= zero_pop_count
        print(f[nxt] + 1)

Solution (Python):
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
fact = math.factorial
sys.setrecursionlimit(10**9)
INF = 10**9
mod = 10**9+7

N = i()
X = s()[::-1]
num1 = 1
num2 = 1
num3 = 0
num4 = 0
cnt = X.count('1')
cnt1 = cnt+1
cnt2 = cnt-1
nums1 = []
nums2 = []
ans = [1]*N

for i in range(N):
    if X[i] == '0':
        nums1.append(num1)
    else:
        num3 += num1
        num4 += num2
        nums1.append(num2)
    if cnt1 != 0:
        num1 = (num1*2)%cnt1
    if cnt2 != 0:
        num2 = (num2*2)%cnt2

for i in range(N):
    if X[i] == '0':
        if cnt1 != 0: 
            nums2.append((num3+nums1[i])%cnt1)
        else:
            nums2.append(0)
            ans[i] = 0
    else:
        if cnt2 != 0:    
            nums2.append((num4-nums1[i])%cnt2)
        else:
            nums2.append(0)
            ans[i] = 0
nums2.reverse()
ans.reverse()

def p(n):
    if n == 0:
        return
    ans[i] += 1
    c = n%(bin(n).count('1'))
    p(c)

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

Solution (Python):
def input_int():
    return map(int, input().split())

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

N=one_int()
S=one_str()

bit_count = S.count("1")
S_num = int(S,2)
S_min = S_num % (bit_count-1) if bit_count-1!=0 else 0
S_plu = S_num % (bit_count+1)













def mods(temp, count):
    count+=1
    if temp!=0:



        


        count = mods(temp%bin(temp).count("1") , count)

    return count

for i in range(N):
    if S[i]=="0":
        part = pow(2, (N-i-1), bit_count+1)
        num = (S_plu + part ) % (bit_count+1)
        print(mods(num, 0))
    else:
        if S_num == 2**(N-i-1):
            print(0)
            continue
        part = pow(2, (N-i-1), bit_count-1)
        num = (S_min - part)%(bit_count-1)
        print(mods(num, 0))

Solution (Python):
n = int(input())
X = input()
x = int(X,2)
bitx = bin(x).count('1')
 
ans = [0]*(bitx+2)
for i in range(1,bitx+2):
    ans[i] = 1 + ans[i%bin(i).count('1')]

l = []
bitp = bitx + 1
bitm = bitx - 1
xmp = 0
xmm = 0


if bitx != 1:
    for i in range(n):
        if X[i] == '1':
            xmp += pow(2, n-(i+1), bitp)
            xmm += pow(2, n-(i+1), bitm)
    for i in range(n):
        if X[i] == '1':
            xm = (xmm - pow(2,n-i-1,bitm)) % bitm
            l.append(str(1+ans[xm]))
        else:
            xm = (xmp + pow(2,n-i-1,bitp))%bitp
            l.append(str(1+ans[xm]))
 
else:
    for i in range(n):
        if X[i] == '1':
            xmp += pow(2, n-(i+1), bitp)
    for i in range(n):
        if X[i] == '1':
            l.append(str(0))
        else:
            xm = (xmp + pow(2,n-i-1,bitp))%bitp
            l.append(str(1+ans[xm]))
 
print('\n'.join(l))

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

pops = bin(x).count("1")
x_pop_p = x%(pops + 1)
try:
    x_pop_m = x%(pops - 1)
except:
    x_pop_m = 0
for i in range(0,n):
    if x_s[i] == '1':
        if pops > 1:
            tmp = (x_pop_m - pow(2,n-1-i,(pops - 1)))%(pops - 1)
        else:
            print(0)
            continue
    else:
        tmp = (x_pop_p + pow(2,n-1-i,(pops + 1))) % (pops + 1)
    cnt = 1
    while tmp:
        tmp %= bin(tmp).count("1")
        cnt += 1
    print(cnt)

Solution (Python):
n=int(input())
x=input()
cntm=0
cntp=0
fn=0
xi=[0]*n
ans=[0]*n
for i in range(n):
    if x[i]=="1":
        fn+=1
for i in reversed(range(n)):
    if x[i]=="1":
        cntp+=pow(2,n-i-1,fn+1)
        cntp%=fn+1
        if fn>1:
            cntm+=pow(2,n-i-1,fn-1)
            cntm%=fn-1
for i in reversed(range(n)):
    if x[i]=="1":
        if fn>1:
            xi[i]=(cntm-pow(2,n-i-1,fn-1))%(fn-1)
            ans[i]+=1
    else:
        xi[i]=(cntp+pow(2,n-i-1,fn+1))%(fn+1)
        ans[i]+=1

for i in range(n):
    num=xi[i]
    while num>0:
        cnt=0
        for j in range(31):
            if (num>>j)&1:
                cnt+=1
        num%=cnt
        ans[i]+=1
    print(ans[i])

Solution (Python):
n = int(input())
x = input()
original_pop_count = x.count('1')
one_pop_count = original_pop_count-1
zero_pop_count = original_pop_count+1

one_mod = 0
zero_mod= 0
for b in x:
    if one_pop_count!=0:
        one_mod=(one_mod*2+int(b))%one_pop_count
    zero_mod=(zero_mod*2+int(b))%zero_pop_count

f = [0]*220000
pop_count = [0]*220000
for i in range(1,220000):
    pop_count[i]= pop_count[i//2] + i%2
    f[i] = f[i%pop_count[i]]+1
one_pow2 = [1]*220000
zero_pow2 = [1]*220000
for i in range(1,220000):
    if one_pop_count!=0:
        one_pow2[i] = one_pow2[i-1]*2%one_pop_count
    zero_pow2[i] = zero_pow2[i-1]*2%zero_pop_count


for i in range(n-1,-1,-1):
    if x[n-1-i]=='1':
        if one_pop_count!=0:
            nxt = one_mod
            nxt-=one_pow2[i]
            nxt%=one_pop_count
            print(f[nxt]+1)
        else:
            print(0)
    if x[n-1-i]=='0':
        nxt = zero_mod
        nxt+=zero_pow2[i]
        nxt%=zero_pop_count
        print(f[nxt]+1)

Solution (Python):
import sys

DEBUG=False
if DEBUG:
    f=open("202007_2nd/D_input.txt")
else:
    f=sys.stdin

def cnt_func(num):
    cnt=0
    while num:
        num%=bin(num).count("1")
        cnt+=1
    return cnt+1
n=int(f.readline().strip())
s=f.readline().strip()
input_val=int(s,2)
input_one_count=s.count("1")

zero_first=input_val%(input_one_count+1)
one_first=input_val%(input_one_count-1) if input_one_count>1 else 0
ans=0
for idx,emt in enumerate(s):
    p=n-idx-1
    if emt=="0": 
        ans=cnt_func((zero_first+(pow(2,p,input_one_count+1)))%(input_one_count+1))
    else: 
        if input_one_count>1:
            ans=cnt_func((one_first-(pow(2,p,input_one_count-1)))%(input_one_count-1))
        else:
            ans=0
    print(ans)
f.close()

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
N = int(input())
X = input()
if X == '0':
    for _ in range(N):
        print(1)
        exit()

mem = [None] * (200005)
mem[0] = 0
def f(n):
    if mem[n] is not None: return mem[n]
    c = bin(n).count('1')
    r = 1 + f(n%c)
    mem[n] = r
    return r

for i in range(200005):
    f(i)

cnt = X.count('1')
a,b = cnt+1, cnt-1

ans = [None] * N

n = 0
for c in X:
    n *= 2
    n += int(c)
    n %= a
for i,c in reversed(list(enumerate(X))):
    if c=='1': continue
    ans[i] = mem[(n+pow(2,N-i-1,a))%a] + 1

if b:
    n = 0
    for c in X:
        n *= 2
        n += int(c)
        n %= b
    for i,c in reversed(list(enumerate(X))):
        if c=='0': continue
        ans[i] = mem[(n-pow(2,N-i-1,b))%b] + 1
else:
    for i in range(N):
        if ans[i] is None:
            ans[i] = 0

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

Solution (Python):
n = int(input())
x = input()
count_1 = x.count('1')
value = [0, 0]
x_int = int(x, 2)
value[0] = x_int % (count_1 - 1) if count_1 > 1 else 0
value[1] = x_int % (count_1 + 1)
for i in range(n):
    if x[i] == '0':
        tmp = (pow(2, n - i - 1, count_1 + 1) + value[1]) % (count_1 + 1)
    else:
        if count_1 == 1:
            print(0)
            continue
        tmp = (-pow(2, n - i - 1, count_1 - 1) + value[0]) % (count_1 - 1)
    ans = 1
    while tmp > 0:
        tmp = tmp % (bin(tmp).count('1'))
        ans += 1
    print(ans)

Solution (Python):
N = int(input())
X = input()   
              
x_val = int(X, 2)
pc_x = X.count('1')
              
x_mod_pc_x_plus_1 = x_val % (pc_x + 1)
x_mod_pc_x_minus_1 = x_val % max(pc_x - 1, 1)
              
for i in range(N):
    if X[i] == '1':
        pc = pc_x - 1
        if pc == 0:
            print(0)
            continue
        val = (x_mod_pc_x_minus_1 - pow(2, N-i-1, pc)) % pc
    else:     
        pc = pc_x + 1
        val = (x_mod_pc_x_plus_1 + pow(2, N-i-1, pc)) % pc
    ans = 1   
    while val > 0:
        val %= bin(val).count('1')
        ans += 1
    print(ans)

Solution (Python):


table = [0 for i in range(2*10**5+5)]
for i in range(2*10**5+5):
    table[i] = "{:0b}".format(i).count("1")


def main():
    N = int(input())
    X = input()
    t = X.count("1")
    x1, x2 = int(X, 2) % (t+1), int(X, 2) % (t-1) if t != 1 else 0
    for i in range(N):
        ans = 1
        x = 0
        if X[i] == "0":
            
            p = pow(2, N-i-1, t+1)
            x = x1 + p
            x %= t+1
        elif t != 1:
            p = pow(2, N-i-1, t-1)
            x = x2 - p
            x %= (t-1)
        else:
            ans = 0
        while x > 0:
            x %= table[x]
            ans += 1
        print(ans)


if __name__ == '__main__':
    main()

Solution (Python):


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

original_pop_count = x.count("1")
one_pop_count = original_pop_count - 1
zero_pop_count = original_pop_count + 1

one_mod = 0
zero_mod = 0
for b in x:
  if one_pop_count != 0:
    one_mod = (one_mod * 2 + int(b)) % one_pop_count
  zero_mod = (zero_mod * 2 + int(b)) % zero_pop_count


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


one_pow2 = [1] * 220000
zero_pow2 = [1] * 220000
for i in range(1, 220000):
  if one_pop_count != 0:
    one_pow2[i] = one_pow2[i-1] * 2 % one_pop_count
  zero_pow2[i] = zero_pow2[i-1] * 2 % zero_pop_count

for i in range(n-1, -1, -1):
  if x[n-1-i] == "1":
    if one_pop_count != 0:
      nxt = one_mod
      nxt -= one_pow2[i]
      nxt %= one_pop_count
      print(f[nxt] + 1)
    else:
      print(0)
  if x[n-1-i] == "0":
    nxt = zero_mod
    nxt += zero_pow2[i]
    nxt %= zero_pop_count
    print(f[nxt] + 1)

Solution (Python):
import sys

DEBUG=False
if DEBUG:
    f=open("202007_2nd/D_input.txt")
else:
    f=sys.stdin

def cnt_func(num):
    cnt=0
    while num:
        num%=bin(num).count("1")
        cnt+=1
    return cnt+1
n=int(f.readline().strip())
s=f.readline().strip()
input_val=int(s,2)
input_one_count=s.count("1")

zero_first=input_val%(input_one_count+1)
one_first=input_val%(input_one_count-1) if input_one_count>1 else 0
ans=0
for idx,emt in enumerate(s):
    p=n-idx-1
    if emt=="0": 
        ans=cnt_func((zero_first+(pow(2,p,input_one_count+1)))%(input_one_count+1))
    else: 
        if input_one_count>1:
            ans=cnt_func((one_first-(pow(2,p,input_one_count-1)))%(input_one_count-1))
        else:
            ans=0
    print(ans)
f.close()

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


def main():
    N = int(input())
    X = input()

    X_int = int(X, 2)

    pcount_X = popcount(X_int)

    pcount_X_pls1 = pcount_X + 1
    pcount_X_mns1 = pcount_X - 1
    
    X_mod_pcount_X_pls1 = X_int % pcount_X_pls1
    if pcount_X_mns1 != 0:
        X_mod_pcount_X_mns1 = X_int % pcount_X_mns1

    for i,bit in enumerate(X):
        bit = int(bit)
        if bit == 0:
            n = (X_mod_pcount_X_pls1 + pow(2, N-i-1, pcount_X_pls1)) % pcount_X_pls1
        else:
            if pcount_X_mns1 == 0:
                print(0)
                continue
            n = (X_mod_pcount_X_mns1 - pow(2, N-i-1, pcount_X_mns1)) % pcount_X_mns1

        ans = 1
        while n > 0:
            ans += 1
            n %= popcount(n)
        print(ans)
        
main()

Solution (Python):
n = int(input())
s = input()
x = int(s, 2)
pcx = s.count("1")
pc1 = x % (pcx - 1) if pcx > 1 else 0
pc2 = x % (pcx + 1)

def f(j):
    cnt = 0
    while j:
        j %= bin(j).count("1")
        cnt += 1
    return cnt

for i, y in enumerate(s):
    k = n - 1 - i
    if y == "0":
        print(f((pc2 + pow(2, k, pcx + 1)) % (pcx + 1)) + 1)
    elif pcx > 1:
        print(f((pc1 - pow(2, k, pcx - 1)) % (pcx - 1)) + 1)
    else:
        print(0)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n):
  res = [None] * n
  for i in range(n):
    res[i] = II()
  return res
def LIR(n):
  res = [None] * n
  for i in range(n):
    res[i] = LI()
  return res
def FR(n):
  res = [None] * n
  for i in range(n):
    res[i] = IF()
  return res
def LIR(n):
  res = [None] * n
  for i in range(n):
    res[i] = IF()
  return res
def LIR_(n):
  res = [None] * n
  for i in range(n):
    res[i] = LI_()
  return res
def SR(n):
  res = [None] * n
  for i in range(n):
    res[i] = S()
  return res
def LSR(n):
  res = [None] * n
  for i in range(n):
    res[i] = LS()
  return res
mod = 1000000007
inf = float('INF')


def solve():
  def f(n, c):
    tmp = n % c
    t = tmp
    b = 0
    while tmp:
      if tmp & 1:
        b += 1
      tmp //= 2
    if t:
      return f(t, b) + 1
    else:
      return 1
  n = II()
  a = S()
  b = 0
  for ai in a:
    if ai == "1":
      b += 1
  a = a[::-1]
  bp = 0
  bm = 0
  if b != 1:
    for i, ai in enumerate(a):
      if ai == "1":
        bp += pow(2, i, b + 1)
        bm += pow(2, i, b - 1)
        bp %= b + 1
        bm %= b - 1
    ans = []
    for i, ai in enumerate(a):
      if ai == "1":
        tmpbm = bm - pow(2, i, b - 1)
        tmpbm %= b - 1
        ans.append(f(tmpbm, b - 1))
      else:
        tmpbp = bp + pow(2, i, b + 1)
        tmpbp %= b + 1
        ans.append(f(tmpbp, b + 1))
    for ai in ans[::-1]:
      print(ai)
    return
  else:
    for i, ai in enumerate(a):
      if ai == "1":
        bp += pow(2, i, b + 1)
        bp %= b + 1
    ans = []
    for i, ai in enumerate(a):
      if ai == "1":
        ans.append(0)
      else:
        tmpbp = bp + pow(2, i, b + 1)
        tmpbp %= b + 1
        ans.append(f(tmpbp, b + 1))
    for ai in ans[::-1]:
      print(ai)
    return



if __name__ == '__main__':
  solve()

Solution (Python):
N = int(input())
X = str(input())
count = X.count("1")
num, nump, numm = 0, 0, 0
now, nowp, nowm = 1, 1, 1

if count == 0:
  for i in range(N):
    print(1)
    quit()
elif count == 1:
  if X[-1] == "1":
    for i in range(N):
      if i != N - 1:
        print(2)
      else:
        print(0)
  else:
    for i in range(N):
      if i!= N - 1:
        if X[i] == "1":
          print(0)
        else:
          print(1)
      else:
        print(2)
  quit()
  

xx = [0] * N
x_plus = [0] * N
x_minus = [0] * N
for i in range(1, N + 1):
  if i != 1:
    now *= 2
    nowp *= 2
    
    now %= count
    nowp %= (count + 1)
    

    nowm *= 2
    nowm %= (count - 1)
  
  else:
    now %= count
    nowp %= (count + 1)
    nowm %= (count - 1) 
  xx[i - 1] = now
  x_plus[i - 1] = nowp
  x_minus[i - 1] = nowm
  if X[-i] == "1":
    num += now
    num %= count
    nump += nowp
    nump %= count + 1
    numm += nowm
    numm %= count - 1
    


nextn = [0] * N

for i in range(N):
    if X[i] == "0":
      a = nump + x_plus[N - 1 - i]
      b = count + 1
      
      nextn[i] = a % b
    else:
      
      
      
        a = numm - x_minus[N - 1 - i]
        b = count - 1
        nextn[i] = a % b
        

for i in range(N):
  if nextn[i] == 0:
    print("1")
  else:
    nownow = nextn[i]
    ans = 1
    while nownow != 0:
      alpha = bin(nownow)[2:]
      beta = str(alpha).count("1")
      nownow %= beta
      ans += 1
    print(ans)

Solution (Python):


import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from functools import lru_cache


@lru_cache(maxsize=2*10**5)
def f2(x):
    if x == 0: return 0
    y = bin(x).count("1")
    return 1 + f2(x % y)

def resolve():
    N = int(input())
    S = input()
    cnt0 = S.count("1")

    if cnt0 == 0:
        print(*[1]*N, sep="\n")
        return

    X = int(S, 2)

    dc = {}
    for k, v in (("0", 1), ("1", -1)):
        x = cnt0 + v
        y = X % x if x else 0
        dc[k] = (x, v, y, [1, N-1])

    ans = [0] * N
    for i in reversed(range(N)):
        si = S[i]
        cnt, v, n, m1 = dc[si]

        if cnt == 0:
            ans[i] = 0
            continue

        ni = N - i - 1
        m2 = (m1[0]<<(m1[1]-i)) % cnt
        n = (n + v*m2) % cnt
        m1[0] = m2; m1[1] = i

        ans[i] = 1 + f2(n)

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


if __name__ == "__main__":
    resolve()

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

def f(n):
    cnt = 0
    while n>0:
        n = n%popcnt(n)
        cnt += 1
    return cnt

def solve(X):
    Y = int(X, 2)
    c = X.count("1")
    m, p = c-1, c+1
    Ym, Yp = Y%m if m else -1, Y%p
    for i in range(N):
        if X[i] == "1":
            Y = (Ym - pow(2,N-i-1,m))%m if Ym!=-1 else -1
        else:
            Y = (Yp + pow(2,N-i-1,p))%p
        print(f(Y) + 1 if Y!=-1 else 0)

N = int(input())
solve(input())

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)