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: Time Limit Exceeded

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

num_of_1 = x.count("1")

first = int(x, 2)

for i in range(n):
    temp_num_of_1 = num_of_1 + 1 if x[i] == "0" else num_of_1 - 1

    ans = 0

    if temp_num_of_1 > 0:
        a = first + 2 ** (n - i - 1) if x[i] == "0" else first - 2 ** (n - i - 1)

        a = a % temp_num_of_1

        temp = bin(a)[2:]

        ans += 1
    
        while temp.count("1") != 0:
            a = int(temp, 2)

            a = a % temp.count("1")

            temp = bin(a)[2:]

            ans += 1

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np 
#popcount=[0]*n
"""eight_1=[0,1,1,2,1,2,2,3]
eight_2=[0]*64
for i in range(8):
  for j in range(8):
    eight_2[i*8+j]=eight_1[i]+eight_1[j]
#eight_01=0
#eight_02=0
#eight_03=0
#print(eight_2)
for k in range(n):
  if eight_01==64:
    eight_02+=1
    eight_01=0
    if eight_02==64:
      eight_03+=1
      eight_02=0
  popcount[k]=eight_2[eight_01]+eight_2[eight_02]+eight_2[eight_03]
  eight_01+=1
f=[0]*n
"""
def popcount(n):
    return bin(n).count("1")

def f(n):
  if n==1:
    return 1
  if n==0:
    return 0
  #s=bin(n)[1:]
  r=n%popcount(n)
  return (f(r)+1)
  
  
n=int(input())
x=input()
#x=np.array([y for y in x])
x_num=int(x,2)
#x_len=n
n+=1
#n_2=2**n
n+=-1
for m in range(n):
  #print(2**(n-m-1))
  if x[m]=="1":
    r=x_num-2**(n-m-1)
    #print("PLUS")
  else:
    r=x_num+2**(n-m-1)
  #print(r)
  
  print(f(r))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

from collections import defaultdict
d = defaultdict(lambda: -1)

Xmemo = defaultdict(lambda: -1)
Xmemo[0]=0

def dfs(X):
    if Xmemo[X]==-1:
        if d[X]==-1:
            popcount = bin(X).count("1")
            d[X]=popcount
        else:
            popcount = d[X]

        if popcount == 1:
            Xmemo[X]=1
            return 1

        Xmemo[X] = dfs(X%popcount)+1

    return Xmemo[X]

ans = [0]*n

Xpopcount = bin(X).count("1")

for i in reversed(range(n)):
    neX = X^(1<<i)

    if X & (1 << i):
        d[neX] = Xpopcount-1
    else:
        d[neX] = Xpopcount+1
    print(dfs(neX))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = input()
m = int(x, 2)
def pop(i):
  b = format(i, "b")
  return b.count("1")
for i in range(n):
  y = m ^ (1<<(n-1-i))
  count = 0
  while y > 0:
    y = y % pop(y)
    count += 1
  print(count)

Submission status: Time Limit Exceeded

Solution code:
# import sys
# input = sys.stdin.readline

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

n = int(input())
x = list(input())
xc = x.count("1")
xu = []
xd = []
if xc == 0:
    for i in range(n):
        print(1)
        exit()
t = 1
for i in range(n):
    mod = xc+1
    xu.append(t%mod)
    t *= 2
t = 1
flag = False
for i in range(n):
    mod = xc-1
    if mod == 0:
        xd.append(0)
        flag = True
    else:
        xd.append(t%mod)
        t *= 2
xu.reverse()
xd.reverse()
s_xu = 0
s_xd = 0
for i in range(n):
    if x[i] == "1":
        s_xu += xu[i]
        s_xd += xd[i]

# print(xu)
# print(xd)

for i in range(n):
    cnt = 1
    if x[i] == "0":
        tar = (s_xu+xu[i])%(xc+1)
        #print(tar)
        while tar != 0:
            b_tar = list(bin(tar)[2:])
            tar %= b_tar.count("1")
            cnt += 1
        print(cnt)
    else:
        if flag:
            print(0)
        elif s_xd-xd[i] == 0:
            print(1)
        else:
            tar = (s_xd-xd[i])%(xc-1)
            #print(tar)
            while tar != 0:
                b_tar = list(bin(tar)[2:])
                tar %= b_tar.count("1")
                cnt += 1
            print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def count1(n):
    nx=bin(n)
    return nx.count('1')

N=int(input())
X=input()
for i in range(N):
    Ni2=X
    if X[i]=='0':
        Ni2=X[:i]+'1'+X[(i+1):] #文字列は変更できない
    else:
        Ni2=X[:i]+'0'+X[(i+1):]
    Ni=int(Ni2,2)
    ans=0
    #print(Ni)
    while Ni!=0:
        Ni=Ni%count1(Ni)
        ans+=1
    print(ans)

Submission status: Time Limit Exceeded

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

N,X = open(0).read().split()
N = int(N)
X = int(X, 2)
cache = {}

for i in range(0, N):
    x = X ^ (1 << (N - 1 - i))
    nums = []
    ans = 0
    while x != 0:
        if x in cache:
            ans += cache[x]
            break
        y = popcount(x)
        nums.append(x)
        x = x % y
        ans += 1
    for j, n in enumerate(nums):
        cache[n] = ans - j
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = input()
init = X.count('1')
X = int(X, 2)

mask = 0b1 << (N-1)
ans = 0

for i in range(N):
    ans = 0
    flg = 0
    a = X ^ mask
    if a - X > 0:
        tmp = init + 1
    else:
        tmp = init - 1
    while a != 0:
        ans += 1
        if flg == 0:
            num = tmp
            flg = 1
        else:
            num = str(bin(a)).count('1')
        a = a % num
    mask = mask >> 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
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
for n, i in enumerate(X):
    ans = 1
    tmp = bin_X ^ pow(2, N - n - 1)
    if tmp == 0:
        print(0)
        continue
    if i == '1':
        tmp %= cnt - 1
    else:
        tmp %= cnt + 1
    while tmp != 0:
        tmp = pop_counter(tmp)
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = input()
x = int(X, 2)
cnt = X.count("1")
tmp = cnt
ans = 0
for i in reversed(range(N)):
    ans = 0
    if X[N-i-1]=="1":
        tmp -= 1
    if X[N-i-1]=="0":
        tmp += 1
    target = x^(1<<i)
    while target>0:
        target = target%tmp
        tmp = bin(target).count("1")
        ans += 1
    print(ans)
    tmp = cnt

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

def binToInt(X):
    ret = 0
    for s in X:
        ret <<= 1
        if s == '1':
            ret += 1
    return ret

def cnt(n):
    ret = 0
    while n > 0:
        n, r = divmod(n, 2)
        ret += r
    return ret

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

N = int(input())
X = binToInt(input().rstrip())

for i in range(N)[::-1]:
    print(f(X ^ (1 << i)))

Submission status: Time Limit Exceeded

Solution code:


n=int(input())

ans=[0]*n
for i in range(n):
    x=i
    cnt=0
    while x>0:
        cnt+=1
        r = 0
        for j in range(19):
            if (x>>j)&1:
                r+=1
            if x>>j==0:
                break
        x=x%r
    ans[i]=cnt

s=input()
l=[0]*(n+1)
rem=[0]*30
num=0
temp=0
k=1
for i in reversed(range(0,n)):
    if int(s[i]):
        num+=k
        temp+=1
    k<<=1
k=1
for i in reversed(range(1,n+1)):
    num1=num^k
    if num1:
        l[i]+=1
        num1%=temp+(1 if num1>num else -1)
    l[i]+=ans[num1]
    k<<=1
for i in range(1,n+1):
    print(l[i])