Problem:


Score : 400 points

Problem Statement

Let \mathrm{popcount}(n) be the number of 1s 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



Sample input:
3
011


Sample output:
2
1
1

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n = int(input())
x = input()
c = x.count("1")
m = 0
m2 = 0
for i in range(n):
    if x[i] == "1":
        m += pow(2, (n - i - 1), c + 1)
        m %= c + 1
m2 = 0
if c!=1:
    for i in range(n):
        if x[i] == "1":
            m2 += pow(2, (n - i - 1), c - 1)
            m2 %= c - 1

for i in range(n):
    if x[i] == "1":
        if c != 1:
            t = m2 - pow(2, (n - i - 1), c - 1)
            t %= c - 1
            count = 1
        else:
            t = 0
            count = 0
    else:
        t = m + pow(2, (n - i - 1), c + 1)
        t %= c + 1
        count = 1
    while t > 0:
        t %= bin(t).count("1")
        count += 1
    print(count)

Submission status: Accepted

Solution code:
from functools import lru_cache

N = int(input())
X = input()
x = int(X, 2)
y = X.count('1')
if y == 1:
    x2 = 0
else:
    x2 = x % (y-1)
x1 = x % (y+1)

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

d = [0] * (2*10**5+5)
for i in range(2*10**5+5):
    d[i] = f(i)

for i in range(N):
    if x >>(N - i - 1) & 1:
        # print(f(x-pow(2, N-i-1)))
        if y - 1 == 0:
            print(0)
        else:
            print(d[(x2 - pow(2, N - i - 1, y-1)) % (y-1)] + 1)
    else:
        # print(f(x+pow(2, N-i-1)))
        print(d[(x1 + pow(2, N - i - 1, y+1)) % (y+1)] + 1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

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

lst = [-1] * (4 * N + 10)
lst[0] = 0
lst[1] = 1

def calc(x):
    if lst[x] != -1:
        return lst[x]
    count = 0
    y = x
    while y:
        if y % 2 == 1:
            count += 1
        y //= 2
    lst[x] = calc(x % count) + 1
    return lst[x]



count = X.count('1') #1の数

count1 = count - 1
count2 = count + 1

# print (count)
total1 = 0
total2 = 0

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

        total2 += pow(2, i, count2)
        total2 %= (count2)
# print ('total', total)

for i in range(N):
    if X[i] == '1':
        if count1 == 0:
            print (0)
            continue
        tmp_total = (total1 - pow(2, N - 1 - i, count1)) % count1
        amari = tmp_total % count1
        ans = calc(amari) + 1
        print (ans)
    else: # 0の時
        tmp_total = (total2 + pow(2, N - 1 - i, count2)) % count2
        amari = tmp_total % (count2)
        ans = calc(amari) + 1
        print (ans)

Submission status: Accepted

Solution code:

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
    # print(lut)
    # print(format(X, 'b'))
    
    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
            # m = (mm - mask) % dm
        else:
            # m = (mp + mask) % dp
            m = (mp + pow(2, N-i-1, dp)) % dp
            _ans = lut[m] + 1
        ans.append(_ans)
    print(*ans, sep='\n')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def f(n):
    if n in memo:
        return memo[n]
    c=list(str(bin(n)))[2:].count('1')
    r=n%c
    if r>0:
        memo[n]=f(r)+1
    else:
        memo[n]=1
    return memo[n]

memo={0:0}
N=int(input())
X=list(input())
XC=X.count('1')
XN=int('0b'+''.join(X),2)
for i in range(N):
    if X[i]=='1':
        if XC==1:
            print(0)
            continue
        tx=(XN%(XC-1)-pow(2,N-i-1,XC-1))
        if tx<0:
            tx+=XC-1
        tx%=XC-1
    else:
        tx=(XN%(XC+1)+pow(2,N-i-1,XC+1))%(XC+1)
    print(f(tx)+1)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    *X, = map(int, input())

    memo = [-1] * 21

    def f(x):
        ret = 0
        while x > 0:
            x = x % bin(x)[2:].count('1')
            ret += 1
        return ret

    for x in range(21):
        memo[x] = f(x)

    cnt = X.count(1)

    if cnt == 1:
        ans = []
        i = 0
        for d in reversed(X):
            if d:
                ans.append(0)
                continue
            if i == 0 or X[-1]:
                ans.append(2)
            else:
                ans.append(1)
            i += 1
            
        ans.reverse()

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

    pow2_0_1 = [1]
    pow2_1_0 = [1]

    t_0_1 = 1
    t_1_0 = 1
    for i in range(N):
        t_0_1 = t_0_1 * 2 % (cnt + 1)
        pow2_0_1.append(t_0_1)

        t_1_0 = t_1_0 * 2 % (cnt - 1)
        pow2_1_0.append(t_1_0)

    chg_0_1 = 0
    chg_1_0 = 0
    i = 0
    for d in reversed(X):
        if d:
            chg_0_1 = (chg_0_1 + pow2_0_1[i]) % (cnt + 1)
            chg_1_0 = (chg_1_0 + pow2_1_0[i]) % (cnt - 1)
        i += 1

    ans = []
    i = 0
    for d in reversed(X):
        if d:
            t = (chg_1_0 - pow2_1_0[i]) % (cnt - 1)
        else:
            t = (chg_0_1 + pow2_0_1[i]) % (cnt + 1)
        i += 1

        add_v = 1
        while t > 20 or memo[t] == -1:
            t = t % bin(t)[2:].count('1')
            add_v += 1
        ans.append(memo[t] + add_v)

    ans.reverse()

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


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
#
# sys.setrecursionlimit(10 ** 7)
#
# (int(x)-1 for x in input().split())
# rstrip()
#
# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok

Submission status: Accepted

Solution code:
N = int(input())
X = input()
cnt = X.count('1')
Y, Z = 0, 0
for i in range(N):
    if cnt > 1:
        Y = (Y + int(X[i])*pow(2, N-i-1, cnt-1))%(cnt-1)
    Z = (Z + int(X[i])*pow(2, N-i-1, cnt+1))%(cnt+1)

def popcount(n):
    c = bin(n).count('1')
    return c

for i in range(N):
    if X[i] == '1':
        pc = cnt - 1
        if pc <= 0:
            print(0)
            continue
        else:
            Y_i = (Y - pow(2, N-i-1, cnt-1))%(cnt-1)
            ans = 1
            while Y_i > 0:
                Y_i = Y_i % popcount(Y_i)
                ans += 1
            print(ans)
    else:
        Z_i = (Z + pow(2, N-i-1, cnt+1))%(cnt+1)
        ans = 1
        while Z_i > 0:
            Z_i = Z_i % popcount(Z_i)
            ans += 1
        print(ans)

Submission status: Accepted

Solution code:
n = int(input())
x = int(input(),2)
# b = int(2**(n-1))
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)
# print(x,pc,mp,mm)
for i in range(n):
    if d[-i-1]==0:
        m = 1
        temp = (mp+pow(2,n-i-1,pc+1)) % (pc+1)
        ans = 1
    else:
        if mm == -1:
            temp = 0
            ans = 0
        else:    
            m = -1
            temp = (mm-pow(2,n-i-1,pc-1)) % (pc-1)
            ans = 1
    # temppc = pc+m
    # temp = x^b
    # ans = 1
    # print(temp)
    # print(temp,mm,pc,pow(2,n-i,pc+1),(mm-pow(2,n-i-1,pc+1)) % (pc-1))
    while temp:
        
        c = temp
        temppc = 0
        while c:
            if c&1 == 1:
                temppc += 1
            c=c>>1
        # print(temp)
        # print(i,temp,ans,temppc)
        # print(temp)
        # s = str(bin(temp))
        # print(temp,popcount(temp))
        if temppc == 0:
            break
        temp = temp % temppc
        ans += 1
        # c = temp
        # temppc = 0
        # while c:
        #     if c&1 == 1:
        #         temppc += 1
        #     c=c>>1
        # print(temp,s)
        # break
    # b=b>>1
    print(ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    x = input()
    x = '0b'+x

    x = int(x,0)
    m = bin(x).count('1')

    if m > 1:
        a = x%(m-1)
    b = x%(m+1)
    tmp_a = 1
    tmp_b = 1
    xx = []

    for i in range(n):
        if (x >> i) &1:
            if m == 1:
                xx.append(0)
                continue
            else:
                y = (a - tmp_a)%(m-1)
        else:
            y = (b + tmp_b)%(m+1)
        tmp_a *= 2
        if m > 1:
            tmp_a %= (m-1)
        tmp_b *= 2
        tmp_b %= (m+1)

        cnt = 1
        while y != 0:
            cnt += 1
            y = solve(y)
        xx.append(cnt)
    
    # print(xx)
    for i in range(n-1,-1,-1):
        print(xx[i])

def solve(n):
    m = bin(n).count('1')
    return n%m

main()

Submission status: Accepted

Solution code:
N=int(input())
X=input()
X10=int(X,2)
one=X.count('1')
def popcount(n):
  c=format(n,'b').count('1')
  if c!=0:
    return n%c
  else:
    return 0
def f(n):
  count=0
  while n>0:
    n=popcount(n)
    count+=1
  return count
if one==1:
  e=X10%2
  for i in range(N):
    if X[i]=='0':
      Y=e+pow(2,N-i-1,2)
      print(f(Y)+1)
     
    elif X[i]=='1':
      print(0)
if one==0:
  for i in range(N):
    print(1)
if one>1:
  a=X10%(one-1)
  b=X10%(one+1)
  c=one-1
  d=one+1
  for i in range(N):
    if X[i]=='1':
      Y=(a-pow(2,N-i-1,c))%c
      print(f(Y)+1)
    if X[i]=='0':
      Y=(b+pow(2,N-i-1,d))%d
      print(f(Y)+1)

Submission status: Accepted

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in R(V)]
    FromStdin=True if ls==None else False
    for i in R(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

ans=0

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

def f_init(x):
    rt=[0]*3
    p=x.count('1')
    N=len(x)
    for i in range(N):
        if x[i]=='1':
            for j in [-1,0,1]:
                rt[j]+=b[j][N-1-i]
                rt[j]%=p+j
#    show('init',x,rt,1+a[rt[0]])
    ans=[0]*3
    for j in [-1,0,1]:
        ans[j]=1+f(rt[j])
    return rt,ans
    


n=I()
s=S_()

N=2*10**5+10
a=[0]*(N+1)
p=s.count('1')


if p>1:
            
    for i in rep(N):
        a[i]=f(i)
    
    t=1
    t_p=1
    t_m=1
    p_p=p+1
    p_m=p-1
    
    f_x=0
    f_p=0
    f_m=0
    for i in rep(n)[::-1]:
        if s[i]=='1':
            f_x+=t%p
            f_p+=t_p%p_p
            f_m+=t_m%p_m
        t*=2
        t_p*=2
        t_m*=2
        t%=p
        t_p%=p_p
        t_m%=p_m
    
    t_p=1
    t_m=1
    ans=[]
    for i in rep(n)[::-1]:
        if s[i]=='1':
            nx=f_m-t_m%p_m
            nx%=p_m
        if s[i]=='0':
            nx=f_p+t_p%p_p
            nx%=p_p
        ans+=a[nx]+1,
    
        t*=2
        t_p*=2
        t_m*=2
        t%=p
        t_p%=p_p
        t_m%=p_m
    
    
    for i in ans[::-1]:
        print(i)

elif p==1:
       
    for i in rep(N):
        a[i]=f(i)
    
    t=1
    t_p=1
    t_m=1
    p_p=p+1
    p_m=p-1
    
    f_x=0
    f_p=0
    f_m=0
    for i in rep(n)[::-1]:
        if s[i]=='1':
            f_x+=t%p
            f_p+=t_p%p_p
            #f_m+=t_m%p_m
        t*=2
        t_p*=2
        t_m*=2
        t%=p
        t_p%=p_p
        #t_m%=p_m
    
    t_p=1
    t_m=1
    ans=[]
    for i in rep(n)[::-1]:
        if s[i]=='1':
            ans+=0,
        if s[i]=='0':
            nx=f_p+t_p%p_p
            nx%=p_p
            ans+=a[nx]+1,
    
        t*=2
        t_p*=2
        t_m*=2
        t%=p
        t_p%=p_p
        #t_m%=p_m
    
    
    for i in ans[::-1]:
        print(i)

elif p==0:
       
    for i in rep(N):
        a[i]=f(i)
    
    t=1
    t_p=1
    t_m=1
    p_p=p+1
    p_m=p-1
    
    f_x=0
    f_p=0
    f_m=0
    for i in rep(n)[::-1]:
        if s[i]=='1':
            f_x+=t%p
            f_p+=t_p%p_p
            #f_m+=t_m%p_m
        t*=2
        t_p*=2
        t_m*=2
        #t%=p
        t_p%=p_p
        #t_m%=p_m
    
    t_p=1
    t_m=1
    ans=[]
    for i in rep(n)[::-1]:
        if s[i]=='1':
            ans+=0,
        if s[i]=='0':
            nx=f_p+t_p%p_p
            nx%=p_p
            ans+=a[nx]+1,
    
        t*=2
        t_p*=2
        t_m*=2
#        t%=p
        t_p%=p_p
        #t_m%=p_m
    
    
    for i in ans[::-1]:
        print(i)

Submission status: Accepted

Solution code:
def bc(x):
    return bin(x).count("1")

def f(n):
    res = 0
    for i in range(n):
        if n == 0:
            return res
        else:
            res += 1
            n = n % bc(n)
    return res

N,X = open(0).read().split()
N = int(N)
pc = X.count('1')
na = 0
nb = 0
if N == 1:
    if X == '1':
        print(0)
    else:
        print(1)
else:
    if pc == 0:
        for i in range(N):
            print(1)
    elif pc == N:
        for i in range(1,N+1):
            na = (na+pow(2,N-i,N-1)) % (N-1)
        for i in range(1,N+1):
            temp = na
            temp = (temp-pow(2,N-i,N-1)) % (N-1)
            print(f(temp)+1)
    elif pc == 1:
        ind = X.index('1')
        na = pow(2,N-ind-1,2)
        for i in range(1,N+1):
            if i != ind + 1:
                temp = na
                temp = (temp+pow(2,N-i,2)) % 2
                print(f(temp)+1)
            else:
                print(0)
    else:
        for i in range(1,N+1):
            if X[i-1] == '1':
                na = (na+pow(2,N-i,pc-1)) % (pc-1)
        for i in range(1,N+1):
            if X[i-1] == '1':
                nb = (nb+pow(2,N-i,pc+1)) % (pc+1)
        for i in range(1,N+1):
            if X[i-1] == '1':
                temp = na
                temp = (temp-pow(2,N-i,pc-1)) % (pc-1)
                print(f(temp)+1)
            else:
                temp = nb
                temp = (temp+pow(2,N-i,pc+1)) % (pc+1)
                print(f(temp)+1)

Submission status: Accepted

Solution code:
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)

mod = 1000000007
inf = int(1e18)

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft


memo = {}

def countbit(x):
    i = 0
    cnt = 0
    while x >= 1<<i:
        if x & (1<<i):
            cnt += 1
        i += 1
    return cnt


def count(x):
    # if c == 0:
    #     return 0
    # s = 1
    # x = x % c
    s = 0
    while x != 0:
        s += 1
        x = x % countbit(x)
    return s

def main():
    n = int(input())
    xs = list(input())
    c = len([i for i in xs if i == '1'])
    dp = {}
    dps = {}
    for i in range(-1, 2):
        cc = c + i
        if cc == 0:
            continue
        dp[cc] = [-1] * n
        base = 1 % cc
        dpstmp = 0
        for i in range(n):
            dp[cc][i] = base
            if xs[-i-1] == '1':
                dpstmp += base
            base = base * 2 % cc
        dps[cc] = dpstmp % cc

    for i in range(n):
        cc = c
        if xs[i] == '1':
            cc -= 1
        else:
            cc += 1
        if cc == 0:
            print(0)
            continue
        res = dps[cc]
        if xs[i] == '1':
            res = (res - dp[cc][-i-1]) % cc
        else:
            res = (res + dp[cc][-i-1]) % cc
        s = count(res) + 1
        print(s)


main()

Submission status: Accepted

Solution code:
n = int(input())
x = str(input())
kosu1 = 0
kazu = 0
for i in range(n):
    kazu += 2 ** (n - i - 1) * int(x[i])
    if x[i] == '1':
        kosu1 += 1
if kosu1 ==1:
    kazup = kazu % (kosu1 + 1)
    magic17 = [0, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 2, 3, 1, 2]
    box = [0] * (kosu1 + 1)

    amarip = [1] * n
    amarim = [1] * n
    for i in range(1, n):
        amarip[i] = (amarip[i - 1] * 2) % (kosu1 + 1)
    for i in range(n):
        if x[i] == '1':
            print(0)
        else:
            a = (kazup + amarip[n - 1 - i]) % (kosu1 + 1)

            if a <= 18:
                print(magic17[a] + 1)
            else:
                num = 0
                for i in range(len(str(bin(a)))-2):
                    if str(bin(a))[-1 - i] == '1':

                        num += 1
                print(magic17[a % num] + 2)
else:
    kazup = kazu % (kosu1 + 1)
    kazum = kazu % (kosu1 - 1)
    magic17 = [0,1,1,2,1,2,1,2,1,2,1,2,1,2,2,3,1,2,1]
    box = [0] * (kosu1 +1)

    amarip = [1] * n
    amarim = [1] * n
    for i in range(1,n):
        amarip[i] = (amarip[i - 1]*2) % (kosu1 + 1)
        amarim[i] = (amarim[i - 1]*2) % (kosu1 - 1)
    for i in range(n):
        if x[i] == '1':
            a = (kazum - amarim[n-1-i]) % (kosu1 - 1)

            if a <= 18:
                print(magic17[a]+1)
            else:
                num = 0

                for i in range(len(str(bin(a)))-2):
                    if str(bin(a))[-1-i] == '1':

                        num += 1
                print(magic17[a % num] + 2)
        else:
            a = (kazup + amarip[n - 1 - i]) % (kosu1 + 1)
            if a <= 18:
                print(magic17[a] + 1)
            else:
                num = 0
                for i in range(len(str(bin(a)))-2):
                    if str(bin(a))[-1 - i] == '1':

                        num += 1
                print(magic17[a % num] + 2)

Submission status: Accepted

Solution code:
FAST_IO = 1
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()

    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())
rrmm = lambda n: [rrm() for _ in xrange(n)]
N = rri()

num = list(rr())
count = num.count('1')
pwrTwo_plus = [0] * N 
pwrTwo_plus[0] = 1 % (count+1)
if count>1:
    pwrTwo_minus = [0] * N 
    pwrTwo_minus[0] = 1 % (count-1)  
for i in range(1, N):  
    pwrTwo_plus[i] = pwrTwo_plus[i - 1] * (2 % count)  
    pwrTwo_plus[i] %= count+1
    if count>1:
        pwrTwo_minus[i] = pwrTwo_minus[i - 1] * (2 % count)  
        pwrTwo_minus[i] %= count-1

def getMod(_str, n, k, plus) :  
    
    # To store the result  
    res = 0
    i = 0
    j = n - 1
    while (i < n) :  
  
        # If current bit is 1  
        if (_str[j] == '1') :  
  
            # Add the current power of 2  
            if plus:
                res += (pwrTwo_plus[i] )  
                res %= k  
            else:
                res += (pwrTwo_minus[i] )  
                res %= k  
              
        i += 1
        j -= 1
  
    return res  
dic = {}
def f(x):
    if x in dic:
        return dic[x]
    if x== 0:
        return 0
    tmp = x% bin(x).count('1')
    dic[x] = f(tmp)+1
    return dic[x]
    

ans_1 = getMod(num, N, count+1, True)
if count>1:
    ans_2 = getMod(num, N, count-1, False)
for i in range(N):
    if num[i] =='0':
        cur_count = count+1
    else:
        cur_count =count-1
    if cur_count ==0:
        print(0)
    else:
        if num[i] =='0':
            cur_num = ans_1
            cur_num += pwrTwo_plus[N-1-i]
            cur_num %= cur_count
            print(f(cur_num)+1)
        else:
            cur_num = ans_2
            cur_num -=pwrTwo_minus[N-1-i] 
            cur_num %= cur_count
            print(f(cur_num)+1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)

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)

Submission status: Accepted

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

D={}
for i in range(1,N+1):
    Nun=i+0
    cnt=0
    while Nun!=0:
        if Nun in D:
            cnt+=D[Nun]
            Nun=0
        S=str(bin(Nun))
        One=S.count("1")
        if One==0:
            break
        else:
            Nun=Nun%One
            cnt+=1
    D[i]=cnt
D[0]=0
#print(D)

One=X.count("1")
#print(One)

if One==0:
    for i in range(N):
        print(1)
elif One==1:
    for i in range(N-1):
        if X[i]=="1":
            print(0)
        else:
            print(1)
    if X[-1]=="0":
        print(2)
    else:
        print(0)
else:
    Num10=0
    for i in range(N):
        if X[i]=="1":
            Num10+=pow(2,N-1-i,One-1)
    Num10%=(One-1)
    #print(Num10,Num10)
    Num01=0
    for i in range(N):
        if X[i]=="1":
            Num01+=pow(2,N-1-i,One+1)
    Num01%=(One+1)
    #print(Num01)
    for i in range(N):
        if X[i]=="1":
            A=Num10-pow(2,N-1-i,One-1)
            #print(A)
            if A==0:
                print(1)
            elif A%(One-1)==0:
                print(1)
            else:
                A%=(One-1)
                print(1+D[A])
            #print(A)
        else:
            A=Num01+pow(2,N-1-i,One+1)
            if A%(One+1)==0:
                print(1)
            else:
                A%=(One+1)
                print(D[A]+1)

Submission status: Accepted

Solution code:
CH = [0,1,1,2,1,2,1,2,1,2,1,2,1,2,2,3,1,2,1,2,1]
N = int(input())
X = input()
s = 0
a = 1
A = []
B = []
for x in X:
    if x == "1":
        s += 1
for i in range(N):
    A.append(a)
    a = a*2 %(s+1)
a = 1
num = int(X,2)
num1 = num%(s+1)
if s > 1:
    num2 = num%(s-1)
    for i in range(N):
        B.append(a)
        a = a*2 %(s-1)
for i in range(N):
    if int(X[i])==1:
        p = s-1
        if p == 0:
            print(0)
            continue
        x = (num2-B[N-1-i])%p
        if x > 20:
            y = x%sum(map(int,list(bin(x))[2:]))
            print(2+CH[y])
        else:
            print(1+CH[x])
    else:
        p = s+1
        x = (num1+A[N-1-i])%p
        if x > 20:
            y = x%sum(map(int,list(bin(x))[2:]))
            print(2+CH[y])
        else:
            print(1+CH[x])

Submission status: Accepted

Solution code:
import sys
from collections import Counter
N = int(input())
X = list(input())
revX = reversed(X)
count01 = Counter(X)
if count01['1'] == 0:
    for i in range(N):
        print(1)
    sys.exit()
m1 = count01['1']-1
p1 = count01['1']+1
powrem = []
m1rem = 0
p1rem = 0
basem1 = 1
basep1 = 1
if m1 == 0:
    for i, xi in enumerate(revX):
    # print(basep1)
        if xi == '0':
            powrem += [basep1 % p1]
        else:
            powrem += [0]
            p1rem = (p1rem + basep1) % p1
        basep1 = (basep1 * 2) % p1
    revpowrem = reversed(powrem)
    # print(list(revpowrem))
    for xi, rem in zip(X, revpowrem):
        c = 1
        if xi == '0':
            r = (p1rem+rem)%p1
        else:
            print(0)
            continue
        # print(r, xi, rem)
        while r != 0:
            p = bin(r).count('1')
            r = r % p
            c += 1
        print(c)
    sys.exit()

for i, xi in enumerate(revX):
    # print(basep1)
    if xi == '0':
        powrem += [basep1 % p1]
    else:
        powrem += [basem1 % m1]
        m1rem = (m1rem + basem1) % m1
        p1rem = (p1rem + basep1) % p1
    basem1 = (basem1 * 2) % m1
    basep1 = (basep1 * 2) % p1
revpowrem = reversed(powrem)
# print(list(revpowrem))
for xi, rem in zip(X, revpowrem):
    c = 1
    if xi == '0':
        r = (p1rem+rem)%p1
    else:
        r = (m1rem-rem)%m1
    # print(r, xi, rem)
    while r != 0:
        p = bin(r).count('1')
        r = r % p
        c += 1
    print(c)

Submission status: Accepted

Solution code:
import sys
import numpy as np
import numba
from numba import njit
i8 = numba.int64

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

@njit((), cache=True)
def compute_small_f():
    popcount = np.empty(1 << 18, np.int64)
    popcount[0] = 0
    for n in range(18):
        popcount[1 << n:1 << n + 1] = popcount[:1 << n] + 1
    f = np.empty(1 << 18, np.int64)
    f[0] = 0
    for n in range(1, 1 << 18):
        f[n] = 1 + f[n % popcount[n]]
    return f

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

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

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

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

Submission status: Accepted

Solution code:
import sys


def _s(): return sys.stdin.readline().strip()


def _i(): return int(sys.stdin.readline().strip())


def main():
    n = _i()
    s = _s()
    m = s.count("1")
    arr = list(range(max(1, m-1), m+2))
    d1 = {}
    for ai in arr:
        d1[ai] = [1 % ai]
        for i in range(n-1):
            d1[ai].append((2*d1[ai][-1]) % ai)

    d2 = {ai: 0 for ai in arr}
    for ai in arr:
        for i, c in enumerate(reversed(s)):
            if c == "1":
                d2[ai] = (d2[ai] + d1[ai][i]) % ai

    lst = [0] * (n+1)
    for i in range(1, n+1):
        t = i % bin(i)[2:].count("1")
        lst[i] = 1 + lst[t]

    i = n
    for c in s:
        i -= 1
        if c == "1":
            m1 = m - 1
            if m1 == 0:
                print(0)
                continue
            else:
                t = (d2[m1] - d1[m1][i]) % m1
        else:
            m1 = m + 1
            t = (d2[m1] + d1[m1][i]) % m1
        print(lst[t] + 1)


if __name__ == "__main__":
    main()