Problem:
 Score : 400 points    Problem Statement Let \mathrm{popcount}(n) be the number of 1 s in the binary representation of n .
For example, \mathrm{popcount}(3) = 2 , \mathrm{popcount}(7) = 3 , and \mathrm{popcount}(0) = 0 .  Let f(n) be the number of times the following operation will be done when we repeat it until n becomes 0 : "replace n with the remainder when n is divided by \mathrm{popcount}(n) ." (It can be proved that, under the constraints of this problem, n always becomes 0 after a finite number of operations.)  For example, when n=7 , it becomes 0 after two operations, as follows:   \mathrm{popcount}(7)=3 , so we divide 7 by 3 and replace it with the remainder, 1 .  \mathrm{popcount}(1)=1 , so we divide 1 by 1 and replace it with the remainder, 0 .   You are given an integer X with N digits in binary.
For each integer i such that 1 \leq i \leq N , let X_i be what X becomes when the i -th bit from the top is inverted.
Find f(X_1), f(X_2), \ldots, f(X_N) .      Constraints  1 \leq N \leq 2 \times 10^5  X is an integer with N digits in binary, possibly with leading zeros.         Input Input is given from Standard Input in the following format:  N  X       Output Print N lines. The i -th line should contain the value f(X_i) .        Sample Input 1 3
011      Sample Output 1 2
1
1   X_1 = 7 , which will change as follows: 7 \rightarrow 1 \rightarrow 0 . Thus, f(7) = 2 .  X_2 = 1 , which will change as follows: 1 \rightarrow 0 . Thus, f(1) = 1 .  X_3 = 2 , which will change as follows: 2 \rightarrow 0 . Thus, f(2) = 1 .        Sample Input 2 23
00110111001011011001110      Sample Output 2 2
1
2
2
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
3

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque, defaultdict


from collections import Counter

from itertools import accumulate,combinations,permutations,product

from heapq import heapify,heappop,heappush


from functools import reduce,lru_cache

from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    

    N = int(input())
    s = input()
    
    
    
    
    def bin(x): return format(x, 'b')
    def bitcount(x): return bin(x).count("1")
    
    @lru_cache(None)
    def r(n):
        if n==0:
            return 0
        bc=bitcount(n)
        return r(n%bc)+1

    mod=s.count("1")
    c1=0
    c2=0
    cur1=1%(mod+1)
    
    if mod>1:
        cur2=1%(mod-1)
        for i in range(N):
            if s[-1-i]=="1":
                c1+=cur1
                c1%=(mod+1)
                c2+=cur2
                c2%=(mod-1)

            cur1=cur1*2%(mod+1)
            cur2=cur2*2%(mod-1)
    else:
        for i in range(N):
            if s[-1-i]=="1":
                c1+=cur1
                c1%=(mod+1)
            cur1=cur1*2%(mod+1)



    for i in range(N):
        if s[i]=="1":
            f=-1
            cmod=mod-1
        else:
            f=1
            cmod=mod+1

        if cmod==0:
            print(0)
            continue
        
        if f==1:
            n=c1+pow(2,N-1-i,cmod)
            n%=cmod
        else:
            n=c2-pow(2,N-1-i,cmod)
            n%=cmod

        print(1+r(n))
    





if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
X = input()
bin_X = int(X, 2)
cnt = 0
for i in X:
    if i == '1':
        cnt += 1


def bit_count(bits):
    cnt = 0
    while bits:
        bits = bits & (bits - 1)
        bits >> 1
        cnt += 1
    return cnt


def pop_counter(n):
    return n % bit_count(n)


ans = 0
xp = bin_X % (cnt + 1)
if cnt != 1:
    xm = bin_X % (cnt - 1)
else:
    xm = 0
for n, i in enumerate(X):
    if i == '0':
        tmp = xp + pow(2, N - n - 1, cnt + 1)
        tmp %= cnt + 1
    elif cnt != 1:
        tmp = xm - pow(2,N-n-1,cnt-1)
        tmp %= cnt -1
    else:
        print(0)
        continue
    ans = 1
    while tmp != 0:
        tmp = pop_counter(tmp)
        ans += 1
    print(ans)

Solution (Python):
import sys
INF = 1 << 60
MOD = 10**9 + 7 
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    dp = [INF] * (200005)
    dp[0] = 0
    for i in range(1, 200005):
        dp[i] = 1 + dp[i % bin(i).count('1')]

    n = int(input())
    X = input()
    p = X.count('1')

    if p == 0:
        ans = [1] * n
        print(*ans, sep = '\n')
        return

    if p == 1:
        idx = X.index('1')
        if idx < n - 1:
            ans = [1] * n
            ans[idx] = 0
            ans[n - 1] = 2
        else:
            ans = [2] * n
            ans[idx] = 0
        print(*ans, sep = '\n')
        return

    minus1, plus1 = 0, 0
    for c in X:
        minus1 = (minus1 * 2 + int(c)) % (p - 1)
        plus1 = (plus1 * 2 + int(c)) % (p + 1)

    ans = [None] * n
    for i, c in enumerate(X):
        if c == '0':
            ans[i] = 1 + dp[(plus1 + pow(2, n - 1 - i, p + 1)) % (p + 1)]
        else:
            ans[i] = 1 + dp[(minus1 - pow(2, n - 1 - i, p - 1)) % (p - 1)]
    print(*ans, sep = '\n')
resolve()

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

memo = [-1] * (n+10)
def calc(x):
    if(memo[x] != -1):
        return memo[x]
    if(x==0):
        return 0
    cnt = 0
    x2 = x
    while(x2 > 0):
        cnt += (x2&1)
        x2 //= 2
    next = x%cnt
    memo[x] = 1 + calc(next)
    return memo[x]

cnt0 = x.count('1')
if(cnt0 == 0):
    ans = [1] * n
    print('\n'.join(map(str,ans)))
    exit()
if(cnt0==1):
    ans = [0] * n
    for i in range(n):
        ans1 = 1 + ( x[-1] == '1')
        if(x[i]=='0'):
            if(i==n-1):
                ans[i] = 2
            else:
                ans[i] = ans1
        else:
            ans[i] = 0
    print('\n'.join(map(str,ans)))
    exit()

rem_p = [0] * n
rem_m = [0] * n
rem_p[0] = 1
rem_m[0] = 1%(cnt0-1)

for i in range(1,n):
    rem_p[i] = (2*rem_p[i-1])%(cnt0+1)
    rem_m[i] = (2*rem_m[i-1])%(cnt0-1)

x_p = 0
x_m = 0
for i in range(n):
    if(x[n-1-i] == '1'):
        x_p += rem_p[i]
        x_m += rem_m[i]
x_p %= (cnt0+1)
x_m %= (cnt0-1)

ans = [0] * n
for i in range(n):
    if(x[i]=='1'):
        first = (x_m - rem_m[n-1-i])%(cnt0-1)
        ans[i] = calc(first) + 1
    else:
        first = (x_p + rem_p[n-1-i])%(cnt0+1)
        ans[i] = calc(first) + 1

print('\n'.join(map(str,ans)))

Solution (Python):




import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
n=I()
lis=list(SI())
orig=0
for i in range(n):
    if lis[i]=="0":
        lis[i]=0
    else:
        lis[i]=1
orcount=sum(lis)
m1=0
m3=0
if orcount==1:
    for i in range(n):
        if lis[i]==1:
            m3=(m3+pow(2,n-i-1,orcount+1))
elif orcount>1:
    for i in range(n):
        if lis[i]==1:
            m1=(m1+pow(2,n-i-1,orcount-1))
            m3=(m3+pow(2,n-i-1,orcount+1))
        
        
m1=m1
m3=m3



dp=[0 for i in range(n+1)]
dp[1]=1
for i in range(1,n):
    
    count=0
    j=0
    while pow(2,j)<=i+1:
        if ((i+1)>>j) %2==1:
            count+=1
        j+=1
    z=1
    dp[i+1]=z+dp[(i+1)%count]

for i in range(n):
    if lis[i]==0:
        
        pr=orcount+1
        num=m3+pow(2,n-i-1,pr)
    else:
        
        pr=orcount-1
        if pr!=0:
            num=m1-pow(2,n-i-1,pr)
    
    if pr==0:
        print(0)
    else:
        print(1+dp[num%pr])

Solution (Python):
def f(n):
  c=0
  while n>0:
    n%=format(n, 'b').count('1')
    c+=1
  return c

N=int(input())
X=input()
nums=[0]+[f(i) for i in range(1, N+1)]

a=0
b=0
for i in range(N):
  if X[i]=='0':
    a+=1
  else:
    b+=1

s=0
t=0
if b>1:
  for i in range(N):
    s=(s+int(X[i])*pow(2, N-1-i, b+1))%(b+1)
    t=(t+int(X[i])*pow(2, N-1-i, b-1))%(b-1)
else:
  for i in range(N):
    s=(s+int(X[i])*pow(2, N-1-i, b+1))%(b+1)
    
if b==1:
  for i in range(N):
    if X[i]=='0':
      tmp=(s+pow(2, N-1-i, b+1))%(b+1)
      print(nums[tmp]+1)
    else:
      print(0)
  exit()

for i in range(N):
  if X[i]=='0':
    tmp=(s+pow(2, N-1-i, b+1))%(b+1)
    print(nums[tmp]+1)
  else:
    tmp=(t-pow(2, N-1-i, b-1))%(b-1)
    print(nums[tmp]+1)

Solution (Python):
def main():
    N = int(input())
    X = input()
    MOD = sum(map(lambda x: x == '1',X))
    lowNumber = []
    for i in range(MOD + 1):
        anscur = i
        cnt = 1
        while anscur != 0:
            oneCount = bin(anscur).count('1')
            anscur %= oneCount
            cnt += 1
        lowNumber.append(cnt)
    if MOD == 0:
        print("1" + "\n1" * (N-1))
        return 0
    if MOD == 1 and X[-1] == '1':
        print("2\n" * (N-1) + "0")
        return 0
    if MOD == 1 and X[-1] == '0':
        ans = ''
        for i in range(N):
            if X[i] == '1':
                ans += '0'
            elif i != N-1:
                ans += '1'
            else:
                ans += '2'
            if i != N-1:
                ans += '\n'
        print(ans)
        return 0
    MODP1 = MOD + 1
    MODM1 = MOD - 1
    POWEROFTWOP1 = [0] * 200001
    POWEROFTWOM1 = [0] * 200001
    POWEROFTWOP1[0] = 1
    POWEROFTWOM1[0] = 1
    for i in range(1,N):
        POWEROFTWOP1[i] = (POWEROFTWOP1[i-1] * 2) % MODP1
        POWEROFTWOM1[i] = (POWEROFTWOM1[i-1] * 2) % MODM1
    xMODP1 = 0
    xMODM1 = 0
    for i in range(N):
        if X[i] == '1':
            xMODP1 += POWEROFTWOP1[N - i - 1]
            xMODP1 %= MODP1
            xMODM1 += POWEROFTWOM1[N - i - 1]
            xMODM1 %= MODM1
    ans = ""
    for i in range(N):
        if X[i] == '0':
            anscur = xMODP1
            anscur += POWEROFTWOP1[N - i - 1]
            anscur %= MODP1
        if X[i] == '1':
            anscur = xMODM1
            anscur -= POWEROFTWOM1[N - i - 1]
            anscur %= MODM1
        ans += str(lowNumber[anscur])
        if i != N-1:
            ans += '\n'
    print(ans)
                    
main()

Solution (Python):
n = int(input())
x = input()
k = x.count("1")
s = int(x, 2)

def ev(n):
	cnt = 0
	while n != 0:
		m = bin(n).count("1")
		n = n % m
		cnt += 1
	return cnt

if k != 1:
	k1 = s%(k-1)
	k2 = s%(k+1)
	for i in range(n):
		if x[i] == "0":
			print(ev((k2+pow(2, n-i-1, k+1)) % (k+1))+1)
		else:
			print(ev((k1-pow(2, n-i-1, k-1)) % (k-1))+1)
else:
	k2 = s%(k+1)
	for i in range(n):
		if x[i] == "0":
			print(ev((k2+pow(2, n-i-1, k+1)) % (k+1))+1)
		else:
			print(0)

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

def f(x):
    cnt=0
    while(x>0):
        x%=popcount(x)
        cnt+=1
    return cnt

n=int(input())
s=input()
d=s.count("1")
if d==0:
    for i in range(n):
        print(1)
elif d==1:
    if s[-1]=="1":
        for i in range(n-1):
            print(2)
        else:
            print(0)
    else:
        for i in range(n-1):
            if s[i]=="1":
                print(0)
            else:
                print(1)
        print(2)
else:
    ints=int(s,2)
    m=ints%(d-1)
    M=ints%(d+1)
    s=s[::-1]
    toaddm=-1
    toaddM=1
    res=[None for i in range(n)]
    for i in range(n):
        if s[i]=="1":
            res[i]=f((m+toaddm)%(d-1))+1
        else:
            res[i]=f((M+toaddM)%(d+1))+1
        toaddm*=2
        toaddm%=d-1
        toaddM*=2
        toaddM%=d+1
    for i in res[::-1]:
        print(i)

Solution (Python):
n = int(input())
x = input()
ans = [0]*(n+1)

for i in range(1,n+1):
    s = format(i, 'b')
    c = s.count('1')
    a = i%c
    ans[i] += 1
    ans[i] += ans[a] 

one_cnt = x.count('1')
numx = int(x,2)

for i in range(n):
    temp = one_cnt
    if x[i]=='0':
        temp += 1
        num = numx%temp + pow(2,n-1-i,temp)
    else:
        if temp>1:
            temp -= 1
            num = numx%temp - pow(2,n-1-i,temp)
        else:
            print(0)
            continue
    print(ans[num%temp]+1)

Solution (Python):


n = int(input())
X = input()
c = 0
cnt = 0
for i,x in enumerate(X):
    c += (1<<(n-i-1))*int(x)
    cnt += int(x)

amari_cnt_p = c % (cnt+1)
if cnt != 1:
    amari_cnt_m = c % (cnt-1)

dp = []
for d in range(n):
    if X[d] == "0":
        amari = (amari_cnt_p + pow(2,n-d-1,cnt+1))%(cnt+1)
    else:
        if cnt != 1:
            amari = (amari_cnt_m - pow(2,n-d-1,cnt-1))%(cnt-1)
        else:
            amari = -1
    dp.append(amari)

memo = [-1]*(2*10**5+10)
memo[0] = 1
def calc(n):
    if n == -1:
        return 0
    if n == 0:
        return 1
    if memo[n] != -1:
        return memo[n]
    cnt = 1
    while n > 0:
        c = bin(n).count("1")
        n %= c
        cnt += 1
    memo[n] = cnt
    return cnt

for d in dp:
    ans = calc(d)
    print(ans)

Solution (Python):
def main():
    n_ansl = [0]*(2*(10**5))
    for i in range(1,2*(10**5)):
    
        cnt = 0
        one_cnt = bin(i).count("1")
        rem = i
        while rem != 0:
            one_cnt = bin(rem).count("1")
            rem = rem%one_cnt   
            cnt += 1
        n_ansl[i] = cnt
 
    n = int(input())
    x = list(input())
    one_cnt = x.count('1')

    if one_cnt == 0:
        for i in range(n):
            print(1)
        exit()
    
    curr_2b_p = 1
    curr_2b_m = 1
    curr_sum_p1 = 0
    curr_sum_m1 = 0
    for i in range(n-1, -1, -1):
        if x[i] == '1':
            curr_sum_p1 += curr_2b_p
            curr_sum_m1 += curr_2b_m
            curr_sum_p1%=(one_cnt+1)
            if one_cnt > 1:
                curr_sum_m1%=(one_cnt-1)
        curr_2b_p*=2
        curr_2b_p%=(one_cnt+1)
        if one_cnt > 1:
            curr_2b_m*=2
            curr_2b_m%=(one_cnt-1)
 
        
 
    curr_2b_p = 1
    curr_2b_m = 1
    ansl = [0]*(n)
    for i in range(n-1, -1, -1):
        if x[i] == '1':
            diff = (-1)*curr_2b_m
            if one_cnt > 1:
                ans = (curr_sum_m1 + diff)%(one_cnt-1)
                ansl[i] = n_ansl[ans]+1
            else:
                ansl[i] = 0
        else:
            diff = curr_2b_p
            ans = (curr_sum_p1 + diff)%(one_cnt+1)
            ansl[i] = (n_ansl[ans]+1)
        curr_2b_p*=2
        curr_2b_p%=(one_cnt+1)
        if one_cnt > 1:
            curr_2b_m*=2
            curr_2b_m%=(one_cnt-1)
 
 
    
    for a in ansl:
        print(a)
 
if __name__ == "__main__":
    main()

Solution (Python):
def main():
    n_ansl = [0]*(2*(10**5))
    for i in range(1,2*(10**5)):
    
        cnt = 0
        one_cnt = bin(i).count("1")
        rem = i
        while rem != 0:
            one_cnt = bin(rem).count("1")
            rem = rem%one_cnt   
            cnt += 1
        n_ansl[i] = cnt
 
    n = int(input())
    x = list(input())
    one_cnt = x.count('1')

    if one_cnt == 0:
        for i in range(n):
            print(1)
        exit()
    
    curr_2b_p = 1
    curr_2b_m = 1
    curr_sum_p1 = 0
    curr_sum_m1 = 0
    for i in range(n-1, -1, -1):
        if x[i] == '1':
            curr_sum_p1 += curr_2b_p
            curr_sum_m1 += curr_2b_m
            curr_sum_p1%=(one_cnt+1)
            if one_cnt > 1:
                curr_sum_m1%=(one_cnt-1)
        curr_2b_p*=2
        curr_2b_p%=(one_cnt+1)
        if one_cnt > 1:
            curr_2b_m*=2
            curr_2b_m%=(one_cnt-1)
 
        
 
    curr_2b_p = 1
    curr_2b_m = 1
    ansl = [0]*(n)
    for i in range(n-1, -1, -1):
        if x[i] == '1':
            diff = (-1)*curr_2b_m
            if one_cnt > 1:
                ans = (curr_sum_m1 + diff)%(one_cnt-1)
                ansl[i] = n_ansl[ans]+1
            else:
                ansl[i] = 0
        else:
            diff = curr_2b_p
            ans = (curr_sum_p1 + diff)%(one_cnt+1)
            ansl[i] = (n_ansl[ans]+1)
        curr_2b_p*=2
        curr_2b_m*=2
        curr_2b_p%=(one_cnt+1)
        if one_cnt > 1:
            curr_2b_m%=(one_cnt-1)
 
 
    
    for a in ansl:
        print(a)
 
if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
x = input()
pop = x.count("1")
lst1 = [1]
for i in range(n-1):
    lst1.append(lst1[-1] * 2 % (pop + 1))
lst1.reverse()
num1 = 0
for i in range(n):
    if x[i] == "1":
        num1 += lst1[i]
        num1 %= (pop + 1)
if pop == 1 or pop == 2:
    lst2 = [0] * n
else:
    lst2 = [1]
    for i in range(n-1):
        lst2.append(lst2[-1] * 2 % (pop - 1))
    lst2.reverse()
    num2 = 0
    for i in range(n):
        if x[i] == "1":
            num2 += lst2[i]
            num2 %= (pop - 1)
x2 = int(x, 2)
for i in range(n):
    if x[i] == "1":
        if pop == 1:
            print(0)
            continue
        elif pop == 2:
            print(1)
            continue
        else:
            num = num2 - lst2[i]
            num %= (pop - 1)
    else:
        num = num1 + lst1[i]
        num %= (pop + 1)
    count = 1
    while num:
        num %= bin(num).count("1")
        count += 1
    print(count)

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 = 0
for i in range(N):
    if X[i] == '1':
        cnt += 1
cnt1 = cnt+1
cnt2 = cnt-1
nums = []
ans = []
tans = [1]*N
for i in range(N):
    if X[i] == '0':
        nums.append(num1)
    else:
        num3 += num1
        num4 += num2
        nums.append(num2)
    if cnt1 != 0:
        num1 = (num1*2)%cnt1
    if cnt2 != 0:
        num2 = (num2*2)%cnt2
if cnt1 != 0:
    num3 %= cnt1
if cnt2 != 0:
    num4 %= cnt2
for i in range(N):
    if X[i] == '0':
        if cnt1 != 0: 
            ans.append((num3+nums[i])%cnt1)
        else:
            ans.append(0)
            tans[i] = 0
    else:
        if cnt2 != 0:    
            ans.append((num4-nums[i])%cnt2)
        else:
            ans.append(0)
            tans[i] = 0
ans.reverse()
tans.reverse()
def f(n):
    if n == 0:
        return
    tans[i] += 1
    c = n%(list(bin(n)[2:]).count('1'))
    f(c)
for i in range(N):
    f(ans[i])
for i in range(N):
    print(tans[i])

Solution (Python):
def Base_n_to_10(X,n):
    out = 0
    for i in range(1,len(str(X))+1):
        out += int(X[-i])*(n**(i-1))
    return out
def Base_10_to_n(X, n):
    if (int(X/n)):
        return Base_10_to_n(int(X/n), n)+str(X%n)
    return str(X%n)
n=int(input())
x=input()
ans=[]
pc=x.count("1")
la=[float("inf")]*pc
for i in range(1,pc+1):
    i10=str(Base_10_to_n(i, 2)).count("1")
    if i%i10==0:
      la[i-1]=1
    else:
      la[i-1]=la[(i%i10)-1]+1
if pc!=1:
  x10=Base_n_to_10(x,2)
  a=x10%(pc+1)
  b=x10%(pc-1)
  for i in range(1,n+1):
    if x[i-1]=="0":
      ans.append((a+pow(2,n-i,pc+1))%(pc+1))
    else:
      ans.append((b-pow(2,n-i,pc-1))%(pc-1))
  for a in ans:
    if a==0:
      print(1)
    else:
      print(1+la[a-1])
else:
  x10=Base_n_to_10(x,2)
  for i in range(1,n+1):
    if x[i-1]=="0":
      ans.append((x10+pow(2,n-i,pc+1))%(pc+1))
    else:
      ans.append("n")
  for a in ans:
    if a==0:
      print(1)
    elif a=="n":
      print(0)
    else:
      print(1+la[a-1])

Solution (Python):
def main():
    n_ansl = [0]*(2*(10**5))
    for i in range(1,2*(10**5)):
    
        cnt = 0
        one_cnt = bin(i).count("1")
        rem = i
        while rem != 0:
            one_cnt = bin(rem).count("1")
            rem = rem%one_cnt   
            cnt += 1
        n_ansl[i] = cnt
 
    n = int(input())
    x = list(input())
    one_cnt = x.count('1')

    if one_cnt == 0:
        for i in range(n):
            print(1)
        exit()
    
    x = x[::-1]

    curr_sum_p1 = 0
    curr_sum_m1 = 0
    dummy = 1
    for i, xi in enumerate(x):
        if xi == '1':
            curr_sum_p1 += pow(2,i,one_cnt+1)
            curr_sum_p1%=(one_cnt+1)
            if one_cnt > 1:
                curr_sum_m1 += pow(2,i,one_cnt-1)
                curr_sum_m1%=(one_cnt-1)
        dummy *= 2
        dummy %= (one_cnt+1)
        
    ansl = [0]*(n)
    for i, xi in enumerate(x):
        if xi == '1':
            if one_cnt > 1:
                diff = (-1)*pow(2,i,one_cnt-1)
                ans = (curr_sum_m1 + diff)%(one_cnt-1)
                ansl[i] = n_ansl[ans]+1
            else:
                ansl[i] = 0
        else:
            diff = pow(2,i,one_cnt+1)
            ans = (curr_sum_p1 + diff)%(one_cnt+1)
            ansl[i] = (n_ansl[ans]+1)
 
 
    
    for a in ansl[::-1]:
        print(a)
 
if __name__ == "__main__":
    main()

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

def main():
    n = int(input())
    x = input()

    c1 = x.count('1')
    cc2 = int('0b' + x, 0) % (c1 + 1)

    if c1 == 1:
        for i in range(n):
            if x[i] == '1':
                print(0)
            else:
                print(f((pow(2, n-i-1, c1+1) + cc2) % (c1 + 1)) + 1)
        exit()

    cc1 = int('0b' + x, 0) % (c1 - 1)

    for i in range(n):
        if x[i] == '1':
            print(f((-pow(2, n-i-1, c1-1) + cc1) % (c1 - 1)) + 1)
        else:
            print(f((pow(2, n-i-1, c1+1) + cc2) % (c1 + 1)) + 1)

main()

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

def popcnt(x):
    n=x
    res=0
    while n>0:
        res+=n%2
        n//=2
    return res

table=[0,1]+[-1 for i in range(219998)]
for i in range(2,220000):
    table[i]=table[i%popcnt(i)]+1

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

plus=0  
minus=0

for i in range(N):
    plus+=int(X[i])*pow(2,N-1-i,max(1,moto-1))
    minus+=int(X[i])*pow(2,N-1-i,moto+1)
    plus%=(max(1,moto-1))
    minus%=(moto+1)

for i in range(N):
    ans=0
    if X[i]=='1':
        ans=plus
        ans-=pow(2,N-1-i,max(1,moto-1))
        ans%=(max(1,moto-1))
        if moto==1:
            ans=-1
    else:
        ans=minus
        ans+=pow(2,N-1-i,moto+1)
        ans%=(moto+1)
    if ans==-1:
        print(0)
    else:
        print(table[ans]+1)

Solution (Python):
n = int(input())
x = input()
k = x.count("1")
cnt = 0
s = int(x, 2)
if k >= 2:
	k1 = s % (k-1)
k2 = s % (k+1)
while s != 0:
	targ = bin(s).count("1")
	s = s % targ
	cnt += 1

def ev(n):
	cnt = 0
	while n != 0:
		m = bin(n).count("1")
		n = n % m
		cnt += 1
	return cnt

if k != 1:
	for i in range(n):
		if x[i] == "0":
			targ = k+1
			print(ev((k2+pow(2, n-i-1, targ)) % targ)+1)
		else:
			targ = k-1
			print(ev((k1-pow(2, n-i-1, targ)) % targ)+1)
else:
	for i in range(n):
		if x[i] == "0":
			targ = k+1
			print(ev((k2+pow(2, n-i-1, targ)) % targ)+1)
		else:
			targ = k-1
			print(0)

Solution (Python):
def main():
    n_ansl = [0]*(2*(10**5))
    for i in range(1,2*(10**5)):
    
        cnt = 0
        one_cnt = bin(i).count("1")
        rem = i
        while rem != 0:
            one_cnt = bin(rem).count("1")
            rem = rem%one_cnt   
            cnt += 1
        n_ansl[i] = cnt
 
    n = int(input())
    x = list(input())
    one_cnt = x.count('1')

    if one_cnt == 0:
        for i in range(n):
            print(1)
        exit()
    
    x = x[::-1]

    curr_sum_p1 = 0
    curr_sum_m1 = 0
    for i, xi in enumerate(x):
        if xi == '1':
            curr_sum_p1 += pow(2,i,one_cnt+1)
            curr_sum_p1%=(one_cnt+1)
            if one_cnt > 1:
                curr_sum_m1 += pow(2,i,one_cnt-1)
                curr_sum_m1%=(one_cnt-1)
 
        
    ansl = [0]*(n)
    for i, xi in enumerate(x):
        if xi == '1':
            if one_cnt > 1:
                diff = (-1)*pow(2,i,one_cnt-1)
                ans = (curr_sum_m1 + diff)%(one_cnt-1)
                ansl[i] = n_ansl[ans]+1
            else:
                ansl[i] = 0
        else:
            diff = pow(2,i,one_cnt+1)
            ans = (curr_sum_p1 + diff)%(one_cnt+1)
            ansl[i] = (n_ansl[ans]+1)
 
 
    
    for a in ansl[::-1]:
        print(a)
 
if __name__ == "__main__":
    main()

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

def main():
    N = int(input())
    Xs = input()
    X = int(Xs, 2)
    d = popcnt(X)

    lut = [0] * N
    for i in range(1, N):
        Xi = i % popcnt(i)
        lut[i] = lut[Xi] + 1

    dp = d+1
    dm = d-1
    mp = X % dp
    mm = X % dm if dm else 0
    
    
    
    ans = []
    for i in range(N):
        mask = 1 << (N-i-1)
        Xi = X ^ mask
        _ans = 0
        if Xs[i] == '1':
            if dm:
                m = (mm - pow(2, N-i-1, dm)) % dm
                _ans = lut[m] + 1
            
        else:
            
            m = (mp + pow(2, N-i-1, dp)) % dp
            _ans = lut[m] + 1
        ans.append(_ans)
    print(*ans, sep='\n')

if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
x = int(input(),2)
pc = 0
d = []
c = x
for i in range(n):
    d.append(c&1)
    if c&1 == 1:
        pc += 1
    c=c>>1
mp = x%(pc+1)
if pc == 1:
    mm = -1
else:
    mm = x%(pc-1)
for i in range(n):
    if d[-i-1]==0:
        temp = (mp+pow(2,n-i-1,pc+1)) % (pc+1)
        ans = 1
    else:
        if mm == -1:
            temp = 0
            ans = 0
        else:    
            temp = (mm-pow(2,n-i-1,pc-1)) % (pc-1)
            ans = 1
    while temp:
        c = temp
        temppc = 0
        while c:
            if c&1 == 1:
                temppc += 1
            c=c>>1
        if temppc == 0:
            break
        temp = temp % temppc
        ans += 1
    print(ans)

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


bitcount=0
for i in range(N):
  if S[i]=='1':
    bitcount+=1
bp=bitcount+1
bm=bitcount-1

lsp=[1 for i in range(N)]
for i in range(1,N):
  lsp[i]=(lsp[i-1]*2)%bp
lsp.reverse()
fXp=0
for i in range(N):
  if S[i]=='1':
    fXp=(fXp+lsp[i])%bp
    
if bm!=0:
  lsm=[1 for i in range(N)]
  for i in range(1,N):
    lsm[i]=(lsm[i-1]*2)%bm
  lsm.reverse()
  fXm=0
  for i in range(N):
    if S[i]=='1':
      fXm=(fXm+lsm[i])%bm


def f(n):
  c=0
  x=1
  while x<=n:
    if n&x>0:
      c+=1
    x*=2
  return n%c

ls=[0 for i in range(bitcount+2)]  
for i in range(1,bitcount+2):
  ls[i]=ls[f(i)]+1

for i in range(N):
  if S[i]=='0':
    print(ls[(fXp+lsp[i])%bp]+1)
  else:
    if bm==0:
      print(0)
    else:
      print(ls[(fXm-lsm[i])%bm]+1)

Solution (Python):
def main(N, X):
    lst = list(map(int, list(X)))
    num = lst.count(1)  

    def func(x):    
        lst = list(bin(x)[2:])
        amari =  x % lst.count('1')
        return amari

    d = {}
    for i in range(1, N):
        d[i] = func(i)


    
    plus = []   
    minus = []  

    p = 1
    m = 1
    for n in range(N):
        p %= (num + 1)
        plus.append(p)
        p *= 2
        if num - 1 > 0:
            m %= (num - 1)
            minus.append(m)
            m *= 2

    o = int(X, 2)   
    amari_plus = o % (num + 1)
    if num - 1 > 0:
        amari_minus = o % (num - 1)

    for i in range(N):
        if lst[i] == 0:
            amari = (amari_plus + plus[- i - 1]) % (num + 1)
        elif num - 1 <= 0:
            print(0)
            continue
        else:
            amari = (amari_minus + (num - 1) - minus[- i - 1]) % (num - 1)
        ans = 1
        while amari != 0:
            amari = d[amari]
            ans += 1
        print(ans)

if __name__ == '__main__':
    N = int(input())
    X = input()
    main(N, X)

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

    c1 = x.count('1')
    if c1 > 1:
        cc1 = int('0b' + x, 0) % (c1 - 1)
    cc2 = int('0b' + x, 0) % (c1 + 1)

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

    if c1 == 1:
        for i in range(n):
            if x[i] == '1':
                print(0)
            else:
                print(f((pow(2, n-i-1, c1+1) + cc2) % (c1 + 1)) + 1)
        exit()

    for i in range(n):
        if x[i] == '1':
            print(f((-pow(2, n-i-1, c1-1) + cc1) % (c1 - 1)) + 1)
        else:
            print(f((pow(2, n-i-1, c1+1) + cc2) % (c1 + 1)) + 1)

main()

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



s = input()
x = int(s, base=2)
popcount = s.count('1')
y_zero = x % (popcount + 1)
if popcount > 1:
    y_one = x % (popcount - 1)
dp = [-1] * n
dp[0] = 0
 
 
def calc(y):
    if dp[y] != -1:
        return dp[y]
    dp[y] = 1 + calc(y % bin(y).count('1'))
    return dp[y]
 
 
ans = [0] * n
rem_zero = 1
if popcount > 1:
    rem_one = popcount - 2
for i in range(n):
    if s[n - 1 - i] == '0':
        ans[n - 1 - i] = 1 + calc((y_zero + rem_zero) % (popcount + 1))
    elif popcount > 1:
        ans[n - 1 - i] = 1 + calc((y_one + rem_one) % (popcount - 1))
    else:
        ans[n - 1 - i] = 0
    rem_zero = rem_zero * 2 % (popcount + 1)
    if popcount > 1:
        rem_one = rem_one * 2 % (popcount - 1)
for i in range(n):
    print(ans[i])

Solution (Python):
import sys

import math
import collections

import bisect
import itertools
import fractions

import copy

import decimal

import queue



sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))



eps = 10 ** (-9)


def main():
    def popcounter(n):
        cnt = 0
        if n == 0:
            return 0
        for _ in range(INF):
            tmp = bin(n).count("1")
            n = n % tmp
            cnt += 1
            if n == 0:
                return cnt

    n = ni()
    x = sys.stdin.readline()
    x_1 = x.count("1")

    num = int(x, 2)
    num1 = num % (x_1 - 1) if x_1 - 1 > 0 else 0
    num0 = num % (x_1 + 1)

    ans = []
    for i in range(n):
        if x[n - 1 - i] == "1":
            if x_1 - 1 < 1:
                ans.append(0)
                continue
            else:
                tmp_n = (num1 - pow(2, i, x_1 - 1)) % (x_1 - 1)
        else:
            tmp_n = (num0 + pow(2, i, x_1 + 1)) % (x_1 + 1)
        ans.append(popcounter(tmp_n) + 1)

    l = len(ans)
    for i in range(l - 1, -1, -1):
        print(ans[i])


if __name__ == '__main__':
    main()