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()
pc = 0
for i in range(len(x)):
    if x[i]=='1':
        pc += 1
def popcount(s):
    c = 0
    for i in range(len(s)):
        if s[i]=='1':
            c += 1
    return c
d = dict()
d[1] = 1
d[0] = 0
for i in range(2, 10000):
    while True:
        v = i % popcount(str(bin(i)))
        if v in d:
            d[i] = d[v] + 1
            break
        
for i in range(len(x)):
    X = x[0:i] + ('0' if x[i]=='1' else '1') + x[i+1:len(x)]
    if x[i]=='1':
        pop = pc-1
    else:
        pop = pc+1
    v = int('0b'+X, 0)
    if pop==0:
        print('0')
        continue
    new = v % pop
    if new == 0:
        print('1')
        continue
    counter = 1
    while True:
        if new in d:
            print(d[new] + 1)
            break
        counter += 1
        oldnew = new
        new = new % popcount(str(bin(new)))
        if new in d:
            print(counter + d[new])
            break
        if new == 0:
            print(counter)
            break

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n = int(input())
x = input()
# compute initial hamming
d = defaultdict()
d[0] = 0

def ham(n):
    c = 0
    while n:
        c += 1
        n &= n - 1
    return c

initial_ham = 0
for i in x:
    if i == '1':
        initial_ham += 1
# also compute initial evaluation
# work out the value up to initial_ham + 1

for i in range(initial_ham + 2):
    counter = 0
    fix_i = i
    while i != 0:
        cur_weight = ham(i)
        i %= cur_weight
        counter += 1
    d[fix_i] = counter

initial_val = int(x, 2)
tmp = 1<<n
for i in range(n):
    tmp //= 2
    if x[i] == '0':
        cur_val = initial_val + tmp
        cur_ham = initial_ham + 1
    else:
        cur_val = initial_val - tmp
        cur_ham = initial_ham - 1
    
    # the modulo is always initial_ham +- 1
    cur_cur_val = cur_val
    cur_list = [cur_val]
    while cur_val not in d:
        cur_val %= cur_ham
        cur_ham = ham(cur_val)
        cur_list.append(cur_val)
    # now i need to process the list
    # now cur_val is in d
    m = len(cur_list)
    m -= 1
    counter = 1
    for i in range(m-1,-1,-1):
        d[cur_list[i]] = d[cur_val] + counter
        counter += 1
    print(d[cur_list[0]])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

def hanten(num):
  if(N==1):
    if(X=="0"):
      return '1'
    else:
      return '0'
  else:
    if(num==0):
      if(X[num]=="0"):
        s = '1' + X[i+1:]
      else:
        s = '0' + X[i+1:]
      return s

    elif(num==N-1):
      if(X[num]=="0"):
        s = X[:num] + '1'
      else:
        s = X[:num] + '0'
      return s
    else:
      if(X[num]=="0"):
        s = X[:num] + '1' + X[num+1:]
      else:
        s = X[:num] + '0' + X[num+1:]
      return s

def scount(num2):
  counter=Counter(num2)
  return counter["1"]

def popcount(num3,cnt):
  s=int(num3,2)%cnt
  return bin(s)

for i in range(0,N):
  res=0
  number=X
  number=hanten(i)
  while(int(number,2)!=0):
    r1=scount(number)
    r2=popcount(number,r1)
    number=r2
    res+=1
  print(res)

Submission status: Time Limit Exceeded

Solution code:
import copy
N = int(input())
X = int(input(),2)

'''
def f(num):
    ii = 0
    while num!=0:
        num = num % str(bin(num)).count('1')
        ii+=1
    return ii
'''

for i in range(N-1,-1,-1):
    X4 = X^(1<<i)
    ii = 0
    while X4!=0:
        X4 = X4 % str(bin(X4)).count('1')
        ii+=1
    print(ii)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=input()
X=int(S,2)

#Sのビット数
bitcount=0
for i in range(N):
  if S[i]=='1':
    bitcount+=1
bp=bitcount+1
bm=bitcount-1
    

fXp=X%bp
if bm!=0:
  fXm=X%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)]  
ls2=[0 for i in range(bitcount+2)]
for i in range(1,bitcount+2):
  ls[i]=f(i)
  ls2[i]=ls2[ls[i]]+1

for i in range(N):
  if S[i]=='0':
    print(ls2[(fXp+2**(N-1-i))%bp]+1)
  else:
    if bm==0:
      print(0)
    else:
      print(ls2[(fXm-2**(N-1-i))%bm]+1)
  
      #print(ls2[(fXm-ls_bitm[N-1-i])%bm]+1)