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: Runtime Error

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[4]:


import copy


# In[41]:


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


# In[46]:


def func(N,X):
    for i in range(N):
        ans = 1
        xi = copy.deepcopy(X)
        xi[i] = str(1-int(X[i]))
        popcount = xi.count("1")
        num = int("".join(xi),2)
        while num%popcount != 0:
            num = num%popcount
            popcount = format(num,"b").count("1")
            ans += 1
        print(ans)


# In[47]:


func(N,X)


# In[ ]:

Submission status: Runtime Error

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

def toggle_nth_bit(num: int, n: int):
    return num ^ (1 << n-1)

def popcount(num: int, cnt: int):
    val = 0
    while True:
        val += 1
        num = num % cnt
        cnt = str(bin(num)).count('1')
        if num == 0:
            return val

for i in range(N):
    reverse_bitX = toggle_nth_bit(int(X, 2), len(X)-i)
    print(popcount(reverse_bitX, str(bin(reverse_bitX)).count('1')))

Submission status: Runtime Error

Solution code:
import copy
N = int(input())
X = list(map(int,input()))
for i in range(N):
    temp = copy.copy(X)
    if(temp[i] == 0):
        temp[i] =  1
    else:
        temp[i] =  0
    stri = ''.join(map(str, temp))
    num = int(stri, 2)
    count_1 = bin(num).count('1')

    # print(num,count_1)
    for i in range(1000000):
        surplus = num%count_1
        if(surplus == 0):
            break
        num = surplus
        count_1 = bin(num).count('1')
    print(i+1)

Submission status: Runtime Error

Solution code:

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

# def main():
n_ansl = [0]*(n)
for i in range(1,n):
# for i in range(1,20):
    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


one_cnt = x.count('1')

if one_cnt == 0:
    for _ in range(n):
        print(1)

c2bl = [1]*n
c2blp = [1]*n
c2blm = [1]*n

curr_2b = 1
curr_2b_p = 1
curr_2b_m = 1
curr_sum = 0
curr_sum_p1 = 0
curr_sum_m1 = 0
for i in range(n-1, -1, -1):
    c2bl[i] = curr_2b
    c2blp[i] = curr_2b_p
    c2blm[i] = curr_2b_m
    if x[i] == '1':
        curr_sum += curr_2b
        curr_sum_p1 += curr_2b_p
        curr_sum_m1 += curr_2b_m
        curr_sum%=one_cnt
        curr_sum_p1%=(one_cnt+1)
        if one_cnt > 1:
            curr_sum_m1%=(one_cnt-1)
    curr_2b*=2
    curr_2b_p*=2
    curr_2b_m*=2
    curr_2b%=one_cnt
    curr_2b_p%=(one_cnt+1)
    if one_cnt > 1:
        curr_2b_m%=(one_cnt-1)



    
curr_2b = 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
        diff = (-1)*c2blm[i]
        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
        diff = c2blp[i]
        ans = (curr_sum_p1 + diff)%(one_cnt+1)
        ansl[i] = (n_ansl[ans]+1)
    # curr_2b *= 2
    # curr_2b*=2
    # curr_2b_p*=2
    # curr_2b_m*=2
    # curr_2b%=one_cnt
    # curr_2b_p%=(one_cnt+1)
    # if one_cnt > 1:
    #     curr_2b_m%=(one_cnt-1)


# print(ansl)
for a in ansl:
    print(a)

# if __name__ == "__main__":
#     main()

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
x_bin = int(x,2)
list_f = [0 for i in range(10**6+1)]
for i in range(1,10**6+1):
  bi = bin(i).count("1")
  if i%bi==0:
    list_f[i] =1
  else:
    amari = i%bi
    list_f[i] = 1+ list_f[amari]
#print(list_f[:20])
for i in range(0,n):
  if x[i]=="0":
    t = x_bin+ 2**(n-1-i)
    t_bin=bin(t).count("1")
    t_amari = t%t_bin
    if t_amari==0:
      print(1)
    else:
      print(list_f[t_amari]+1)
 
  else:
    t = x_bin - 2**(n-1-i)
    t_bin=bin(t).count("1")
    t_amari = t%t_bin
#    print(1,t_amari)
    if t_amari==0:
      print(1)
    else:
      print(list_f[t_amari]+1)

Submission status: Runtime Error

Solution code:
def count_(n):
    count = 0
    while n != 0:
        rem = n % 2
        n = n // 2
        if rem == 1:
            count += 1
    return count

n = int(input())
binary = input()
count_1 = 0
value = 0
j = 0
for i in range(n-1, -1, -1):
    if binary[i] == '1':
        count_1 += 1
        value = value + 2**j
    j += 1

for i in range(n):
    new_value = value
    new_count_1 = count_1
    final_count = 1
    if binary[i] == '0':
        new_value = new_value + (2**(n-i-1))
        new_count_1 += 1

    else:
        new_value = new_value - (2**(n-i-1))
        new_count_1 -= 1
    
    rem = new_value%new_count_1
    while rem > 0:
        x = count_(rem)
        rem = rem % x
        final_count += 1

    print(final_count)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)
from functools import lru_cache

def input():
    return sys.stdin.readline().rstrip()
@lru_cache(maxsize =None)
def tc(n):
     y =n
     count =0
     while y:
         if y%2==1:
             count +=1
         y=y//2
     ans =n % count
     if ans ==0:
         return 1
     else:
         return tc(ans) +1



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

    for i in range(N-1, -1, -1):
        t = 2 ** i ^ X
        print(tc(t))









if __name__ == "__main__":
    main()

Submission status: Runtime Error

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


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


# dp = [0] * 1000000
for i in range(n - 1, -1, -1):
    num = (2 ** i) ^ x
    ans = 0
    #   bit_count_init = popcount(num)
    #    if dp[bit_count_init] != 0:
    #        print(dp[bit_count_init])
    #        continue
    while True:
        bit_count = bc(num)
        num %= bit_count
        #        if dp[num] != 0:
        #            print(a)
        ans += 1
        if num == 0:
            print(ans)
            #            dp[bit_count_init] = ans
            break

Submission status: Runtime Error

Solution code:
# [] = list(map(int, input().split()))
# = map(int, input().split())

import copy


def countSetBits(setBitsN):
    count = 0
    while (setBitsN):
        count += setBitsN & 1
        setBitsN >>= 1
    return count


def popcount(popN):
    return popN % countSetBits(popN)


n = int(input())
x = list(map(int, list(input())))
for i in range(n):
    xc = copy.copy(x)
    if xc[i] == 1:
        xc[i] = 0
    else:
        xc[i] = 1
    D = 0
    for j in range(n):
        D += xc[-1 - j] * 2 ** j
    timeCount = 0
    while True:
        D = popcount(D)
        timeCount += 1
        if D == 0:
            break
    print(timeCount)

Submission status: Runtime Error

Solution code:
def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f

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

for i in range(N):
  if X[i] == 0:
    X[i] = 1
  else:
    X[i] = 0
  print(popcount(int(bin(X))))
  if X[i] == 0:
    X[i] = 1
  else:
    X[i] = 0

Submission status: Runtime Error

Solution code:
from collections import defaultdict
def main():
    def f(n):
        if n == 0:
            return 0
        if d[n] != 0:
            return d[n]
        d[n] = f(n % sum(list(map(int, bin(n)[2:])))) + 1


    n = int(input())
    X = list(input())
    rev = lambda x: '1' if x == '0' else '0'
    d = defaultdict(int)
    d[0] = 0
    for i in range(1, n):
        f(i)
    X[0] = rev(X[0])
    print(d[int(''.join(X), 2) % sum(list(map(int, X)))] + 1)
    for i in range(n - 1):
        X[i] = rev(X[i])
        X[i + 1] = rev(X[i + 1])
        print(d[int(''.join(X), 2) % sum(list(map(int, X)))] + 1)




if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

def n2(N):
  res = ''
  n=N
  while n>0:
    if n%2==0:
      res = '0' + res
    else:
      res = '1' + res
    n = n//2
  return res

def p(N):
  n=sum(int(x) for x in list(n2(N)))
  return n

N=int(input().rstrip('\n'))
X=[int(x) for x in list(input().rstrip('\n'))]
xm=sum((2**(N-y-1))*z for y,z in zip(range(N),X))
for i in range(N):
  if X[i]==0:
    xn=xm+2**(N-i-1)
  else:
    xn=xm-2**(N-1-i)
  res = 0
  while 5572>573:
    xn=xn%p(xn)
    res += 1
    if xn==0:
      break
  print(res)

Submission status: Runtime Error

Solution code:
def myf(s):
    for i in range(1, 7):
        popcount = s.count('1')
        s = bin(int(s, 0) % popcount)
        if int(s, 0) == 0:
            break
    return i

n = int(input())
x = '0b' + input()
lst = ['1', '0']
for i in range(n):
  z = x[:i + 2] + lst[int(x[i + 2])] + x[i + 3:]
  print(myf(z))

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
COUNT = x.count('1')
mod1 = COUNT - 1
mod2 = COUNT + 1

# その桁に1が立っていた時の余り
mod = [[0, 0] for _ in range(n+1)]
mult = 1
mod[0][0] = 1 % mod1
mod[0][1] = 1 % mod2
for i in range(1, n+1):
    mod[i][0] = (mod[i-1][0] * (2 % mod1)) % mod1
    mod[i][1] = (mod[i-1][1] * (2 % mod2)) % mod2

all_mod1 = 0
all_mod2 = 0
for i in range(n):
    if x[i] == '1':
        all_mod1 = (all_mod1 + mod[n-1-i][0])
        all_mod2 = (all_mod2 + mod[n-1-i][1])
all_mod1 %= mod1
all_mod2 %= mod2

def popcount(idx):
    idx -= 1
    ret = 0
    if x[idx] == '1':
        ret = (all_mod1 - mod[n-1-idx][0]) % mod1
    else:
        ret = (all_mod2 + mod[n-1-idx][1]) % mod2
    return ret

bit_cnt_table = [0 for _ in range(n+1)]
bit_cnt_table[1] = 1
base = 0
i = 2
while i <= n:
    if i % (2 ** base) == 0:
        base += 1
    bit_cnt_table[i] = 1 + bit_cnt_table[i - 2**(base)]
    i += 1

def func(num):
    if bit_cnt_table[num] == 0:
        return 0
    return num % bit_cnt_table[num]

f = [-1 for _ in range(n+1)]
f[0] = 0
f[1] = 1
for i in range(2, n+1):
    tmp = func(i)
    f[i] = 1 + f[tmp]
# print("all_mod", all_mod1, all_mod2)
ans = []
for i in range(1, n+1):
    p = popcount(i)
    ans_i = 1 + f[p]
    # print(i, p, ans_i)
    ans.append(str(ans_i))
print("\n".join(ans))
# print(f)
# print(bit_cnt_table)

Submission status: Runtime Error

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

def ppc(k): #k:2進数 bin
  cnt1 = sum( list(k) )
  k_10 = int(k, 2) #１０進数
  return format( k_10 % cnt1, 'b') #2adic

for i in range(n):
  ly = list(x)
  if ly[i] == '0':
    ly[i] = '1'
    y = ''.join(ly)
  else:
    ly[i] = '0'
    y = ''.join(ly)
  cnt = 0
  
  while True:
    if y == '0':
      break
    y = ppc(y)
    cnt += 1
  print(cnt)

Submission status: Runtime Error

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

def input():
    return sys.stdin.readline().rstrip()
@lru_cache(maxsize =None)
def tc(n):
     y =n
     count =0
     while y:
         if y%2==1:
             count +=1
         y=y//2
     ans =n % count
     if ans ==0:
         return 1
     else:
         return tc(ans) +1



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

    for i in range(N-1, -1, -1):
        t = 2 ** i ^ X
        print(tc(t))









if __name__ == "__main__":
    main()