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:
N = int(input())
X = input()
p0 = X.count('1')
p1, p2 = p0-1, p0+1
mem = {0:0}
def f(n):
    if n in mem:
        return mem[n]
    else:
        p = bin(n).count('1')
        ret = f(n % p) + 1
        mem[n] = ret
        return ret
r1 = r2 = 0
k1 = k2 = 1
for i in range(N):
    if X[-i-1] == '1':
        r1 = (r1+k1) % p1
        r2 = (r2+k2) % p2
    k1 = k1 * 2 % p1
    k2 = k2 * 2 % p2

ans = [None]*N
k1 = k2 = 1
for i in range(N):
    if X[-i-1] == '0':
        r = (r2 + k2) % p2
    else:
        r = (r1 - k1) % p1
    ans[-i-1] = f(r) + 1
    k1 = k1 * 2 % p1
    k2 = k2 * 2 % p2
for i in range(N):
    print(ans[i])

Submission status: Runtime Error

Solution code:
LIM=200002
L=[0]*LIM

def bin_sum(Y):
    S=bin(Y)[2:]
    count=0
    for i in range(len(S)):
        count+=int(S[i])
    return count

def bin_sum2(Y):
    count=0
    for i in range(len(Y)):
        count+=int(Y[i])
    return count

for i in range(1,LIM):
    L[i]+=bin_sum(i)

def pop_num(N,b,L):
  	if N==0:
      return 0
    count=1
    N=N%b
    while N!=0:
        b=L[N]
        N=N%b
        count+=1
    return count
X=int(input())
Y=input()
d=bin_sum2(Y)+1
c=bin_sum2(Y)-1
for i in range(X):
    Y_i=Y[:i]+str(abs(int(Y[i])-1))+Y[i+1:]
    if Y_i[i]=="1":
        b=d
    else:
        b=c
    print(pop_num(int(Y_i,2),b,L))

Submission status: Runtime Error

Solution code:
import sys
import math
sys.setrecursionlimit(10000)

import heapq

def input():
    return sys.stdin.readline().rstrip()


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 = list(map(int, input()))

Xp = sum(X)
# print(Xp)
a = 0
b = 0
# c = 0
for i, x in enumerate(X):
    i_reverse = N-i-1
    a = (a + x * (1<<i_reverse)) % (Xp-1)
    b = (b + x * (1<<i_reverse)) % (Xp+1)
    # c = (c + x * (1<<i_reverse))
    # print(bin(c))

# print(a, b)

for i in range(N):
    i_reverse = N-i-1
    m = ([a, b][X[i]==0] + [-1, 1][X[i]==0] * (1<<i_reverse)) % [Xp-1, Xp+1][X[i]==0]
    # print(i, ([a, b][X[i]==0], [-1, 1][X[i]==0]*(1<<i_reverse)), [Xp-1, Xp+1][X[i]==0], X[i]==0)
    # print(m)
    count = 1
    while m > 0:
        p = sum([int(c) for c in str(bin(m)[2:])])
        m = m % p
        count += 1
    print(count)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce

# 各クエリO(1)
# 求めたいのは0になるまでの回数
# 事前に1 - 2*10**5まで、になった回数を記録しておくとか？ (小さい方の数は必ずわかっている) (あまりがbit超で10**5を超えないのはわかっている)

# これがクリアされても 2**(2*10**5)の数字であまりが取れない問題がある
# 一回割ってしまえばこっちのもんよ

N = a_int()
X = read()[:-1]
px0 = X.count('1')
# 上から、px0-1, px0, px0+1で割ったもの
x0n = 0
x0 = 0
x0p = 0
for i, bit in enu(reversed(X)):
    if bit == '1':
        x0n += pow(2, i, px0 - 1)
        x0n %= px0 - 1
        x0 += pow(2, i, px0)
        x0 %= px0
        x0p += pow(2, i, px0 + 1)
        x0p %= px0 + 1


x0 = [x0n, x0, x0p]  # px0-1, px0, px0+1で割ったもの

first_mod = []  # 後ろから順番に1回だけ操作を行ったときの数字(Xi % popcount(Xi))
for i, bit in enumerate(reversed(X)):
    if bit == '0':
        # 1に反転する
        first_mod.append((x0[2] + pow(2, i, px0 + 1)) % (px0 + 1))
    elif bit == '1':
        first_mod.append((x0[0] - pow(2, i, px0 - 1)) % (px0 - 1))


# print(first_mod[::-1], sep='\n')  # これが違うぞーなんでだ
# これは必ずpx0+-1よりも小さいので、事前に対応表を作っておけばすぐに求められる(それとも求めなくてもいいか？)(logがつくからしなくても良さそう)

ans = []
for x in reversed(first_mod):
    cnt = 1  # すでに一回操作しているので
    while x != 0:
        x = x % bin(x).count('1')
        cnt += 1
    ans.append(cnt)


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

Submission status: Runtime Error

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

def popcount(n):
    bin_n = bin(n)[2:]
    count = 0
    for i in bin_n:
        count += int(i)
    return count

cnt = popcount(int(''.join(x), base=2))

dic = {}
for i in range(n):
    temp = x[:]
    if temp[i] == '0':
        temp[i] = '1'
        cnt_temp = cnt + 1
    else:
        temp[i] = '0'
        cnt_temp = cnt - 1
    temp = ''.join(temp)
    num = int(temp, base=2)
    num = num % cnt_temp
    lst = [num]
    ans = 1
    while num != 0:
        if num in dic:
            ans += dic[num]
            for i in range(len(lst)):
                dic[lst.pop()] = dic[num] + i
            break
        ans += 1
        num = num%popcount(num)
        lst.append(num)
    for i in range(len(lst)):
        dic[lst.pop()] = i
    print(ans)

Submission status: Runtime Error

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

for i in range(N):
    ans=0
    if Xdef[i]=='0':
        X=int(Xdef,2)+2**(N-i-1)
    else:
        X=int(Xdef,2)-2**(N-i-1)
    #print(X)
    while True:
        X=X%int(format(X,'b').count('1'))
        ans+=1
        if X==0:
            break
    print(ans)

Submission status: Runtime Error

Solution code:

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

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

for i in range(n-1,-1,-1):
    xi=x^(1<<i)
#    print(xi,popcount(xi),xi%popcount(xi))
    icnt=0
    while xi>0:
        icnt+=1
        xi=xi%popcount(xi)
    print(icnt)

Submission status: Runtime Error

Solution code:
def popcntdiv(n):
  return int(n,2) % n.count("1")

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


for i in range(n):
  ans = 0
  time = 0
  k = list(x)
  k[i] = str(abs(int(k[i])-1))
  k = "".join(k)  
  
  while k != "0":
    k = str(format(popcntdiv(k),"b"))
    ans += 1 
  print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
X=0
for i in range(n):
    X+=int(x[n-1-i])*(2**i)

lis=[0,1]

for i in range(2,n+1):
    ni=i
    cnti=0
    while ni!=0:
        if ni%2==1:
            cnti+=1
        ni=ni//2
    lis.append(lis[i%cnti]+1)

cnt=0
for i in range(len(x)):
    if x[i]=="1":
        cnt+=1

for i in range(n):
    Xi=X
    ci=cnt
    if x[i]=="0":
        Xi+=2**(n-1-i)
        ci+=1
    else:
        Xi-=2**(n-1-i)
        ci-=1
    print(lis[Xi%ci]+1)

Submission status: Runtime Error

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

for i in range(n):
  xi = x[0:i] + '1' + x[i+1:]
  if x == xi:
    xi = x[0:i] + '0' + x[i+1:]
  
  def popcount(m):
    return m.count('1')

  def func(o):
    p = popcount(bin(o))
    if o % p == 0:
      return 1
    else:
      return func(o % p) + 1
    
  print(func(int('0b' + xi, 2)))

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
value = []
for i in range(2 * (10 ** 5) + 1):
    ans = 0
    while i > 0:
        i = i % bin(i).count('1')
        ans += 1
    value.append(ans)

for i in range(n):
    t = x[:i] + ('0' if x[i] == '1' else '1') + x[i + 1:]
    ans = 1
    t = (int(t, 2) % (t.count('1')))
    print(ans + value[t])

Submission status: Runtime Error

Solution code:
N = int(input())
a = input()
def bit2(inp):
    A = len(inp)
    ans = 0
    for i in range(A):
        if inp[A-1-i] == "1":
            ans += 2 ** i
    return ans

def bitReverse(bit,i):
    k = "1"
    if bit[i] == "1":
        k = "0"
    return bit[:i] + k + bit[i+1:]
def bitCount(bit):
    count = 0
    for i in bit:
        if i == "1":
            count += 1
    return count
def toBit(inp,keta):
    ans = ""
    for i in range(keta-1,-1,-1):
        if 2 ** i <= inp:
            inp -= 2 ** i
            ans = ans + "1"
        else:
            ans = ans + "0"
    return ans

def answer(bit,count):
    point = bit2(bit)
    c = bitCount(bit)
    if point%c == 0:
        return count+1
    return answer(toBit(point%c,len(bit)),count+1)
    
length = len(a)
ans = [0]* 20
for i in range(1,20):
    ans[i] = answer(toBit(i,20),0)
for i in range(length):
    k = bitReverse(a,i)
    point = bit2(k)
    c = bitCount(k)
    print(ans[point%c]+1)

Submission status: Runtime Error

Solution code:
def solve():
  def popcount(x):
    S = format(x,'b')
    cnt = 0
    for s in S:
      if s=='1':
        cnt+=1
    return cnt
  N = int(input())
  X = input()
  num = 0
  pcnt = 0
  for i, x in enumerate(X):
    if x=='1':
      pcnt += 1
      num += 2**(N-i-1)
  a = num//pcnt
  b = num%pcnt
  for i, x in enumerate(X):
    ans = 1
    if x=='1':
      n1 = (a+b-2**(N-i-1))%(pcnt-1)
    else:
      n1 = (b-a+2**(N-i-1))%(pcnt+1)
    while n1 >5:
      pc = popcount(n1)
      n1 = n1%pc
      ans +=1
    if n1==0:
      print(ans)
    elif n1==1:
      print(ans+1)
    elif n1==2:
      print(ans+1)
    elif n1==3:
      print(ans+2)
    elif n1==4:
      print(ans+1)
    elif n1==5:
      print(ans+2)
solve()

Submission status: Runtime Error

Solution code:
import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7

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

    popdic = {}
    xx = int(X, 2)

    def popcount(n):
        tmp = n
        n = bin(n)
        return tmp % n.count("1")

    for i in range(1, N+1):
        x = xx
        tmp = x
        if X[i-1] == "1":
            x -= 2**(N-i)
        else:
            x += 2**(N-i)
        count = 0
        while(x!=0):
            tmpdic = {}
            if x not in popdic:
                tmpdic[x] = count
                count += 1
                x = popcount(x)
            else:
                count += popdic[x]
                break
        popdic[tmp] = count
        for k, v in tmpdic.items():
            popdic[k] = count - v
        print(count)



if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
# print (int(x,2))
a = x.count('1')
# print (a)


for i in range(n):
  if x[i] == '0':
    b = '1'
    cnt = a + 1
  else:
    b = '0'
    cnt = a - 1
  d = x[:i] + b + x[i+1:]
  # print (d, int(d,2))
  v = int(d,2)
  out = 0
  # while v != 0:
  v %= cnt
  cnt = bin(v).count('1')
  if cnt == 0:
    out = 1
  elif cnt < 3:
    out = 2
  else:
    out = 3
  print (out)

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
def funk(x, temp_count):
    if x in log_dict:
        ans = log_dict[x]
        return ans
    x = x % temp_count
    if x == 0:
        log_dict[x] = 1
        return 1
    temp_count = bin(x).count("1")
    ans = funk(x, temp_count)
    log_dict[x] = ans
    ans += 1
    return ans
n = int(input())
bit = input()
count = bit.count("1")
log_dict = {}
log_dict[1] = 1
log_dict[2] = 1
for i in range(n):
    temp_count = count
    if bit[i] == "1":
        temp_count -= 1
        x_bit = bit[:i] + "0" + bit[i+1:]
    else:
        temp_count += 1
        x_bit = bit[:i] + "1" + bit[i+1:]
    x = int(x_bit, 2)
    ans = funk(x, temp_count)
    print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
def pc(a, cnt):
    if int(a, 2)%a.count("1") == 0:
        return cnt + 1
    else:
        a = bin(int(a, 2)%a.count("1"))
        return pc(a[2:], cnt+1)

for i in range(n):
    chk = x[:i] + str(1^int(x[i])) + x[i+1:]
    print(pc(chk, 0))

Submission status: Runtime Error

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

import copy

V = [1]*200000
for i in range (2, 200001):
    a = i
    b = str(bin(i))
    c = b.count('1')
    d = a%c
    if d ==0:
        V[i-1] = 1
    else:
        V[i-1] = V[d-1]+1

A = []
for i in range (0, len(X)):
    A.append(X[i])

for i in range (0, len(X)):
    D = copy.deepcopy(A)
    D[i] = 1-int(D[i])
    L = str()
    for i in range (0, len(D)):
        L = L+str(D[i])
    K= int(L, base = 2)
    K = int(K)
    Counter = L.count('1')
    if K%Counter == 0:
        print(1)
    else:
        print(V[K%Counter-1]+1)

Submission status: Runtime Error

Solution code:
from collections import Counter
N=int(input())
X=input()
value = int(X,2)
#print(value)
TFlist =[]
for i in range(N):
  if X[i] == '0':
  	TFlist.append(False)
  else:
    TFlist.append(True)
#print(TFlist)
p = sum(TFlist)


def count_ones_by_bin(num):
    bin_num = bin(num)[2:]
    count = 0
    for i in bin_num:
            count += int(i)
    return count
  
def popcount(n):
 # print("popcount",n)
  return (n  % count_ones_by_bin(n))

for i in range(N):
#  print("N", N)
  cnt = 0
  if TFlist[i]: tmp = (value % (p-1) - (pow(2,(N-i-1), (p-1)))) % (p-1)
  else: tmp = (value % (p+1) + ( pow(2,(N-i-1), (p+1) ) ) ) % (p+1)
 # print(tmp)
  cnt += 1
  while tmp != 0:
    cnt+= 1
    tmp = popcount(tmp)
  print(cnt)

Submission status: Runtime Error

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

k = [0,1,1,2,1,2,1,2,1,2,1,2,1,2,2,3,1,2,1] #18まで
one = [0]*N

c = 0
for i in range(N):
    if X[i] == "1":
        c += 1
for i in range(N):
    if X[i] == "1":
        one[i] = c-1
    else:
        one[i] = c+1
#print(one)

b1 = bin_num = int(X, 2)

for i in range(N):
    if X[i] == "0":
        B1 = b1 + 2**(N-1-i)
    else:
        B1 = b1 - 2**(N-1-i)
    #print(B1)
    B2 = B1%one[i]
    x = format(B2, 'b')
    #print(x)
    S = len(str(x))

    c2 = 0
    for j in range(S):
        if x[j] == "1":
            c2 += 1

    if c2 == 0:
        print(1)
    else:
        print(2+k[B2%c2])

Submission status: Runtime Error

Solution code:
a = input()
N = input()
for i in range(len(N)):
    n = list(N)
    if N[i] =="0":
        n[i] = "1"
    else:
        n[i] = "0"
    n = int("".join(n),2)        
    s = 0
    while True:
        n = n % sum(list(map(int,bin(n)[2:])))
        s = s + 1
        if n > 0:
            continue
        break
    print(s)

Submission status: Runtime Error

Solution code:
import math
#N=int(input())
#a=list(map(int,input().split()))

#for i in range(10**4):
#    for j in range(10**4):
#        for i in range(10**4):
#            if i**2+j**2+k**2+i*j+j*k+k*i==N:
#                ans+=1
#            if i**2+j**2+k**2+i*j+j*k+k*i>=N:
#                break
#print(ans)

N=int(input())
Xdef=input()

for i in range(N):
    ans=0
    if Xdef[i]=='0':
        X=int(Xdef,2)+2**(N-i-1)
    else:
        X=int(Xdef,2)-2**(N-i-1)
    #print(X)
    while True:
        X=X%int(format(X,'b').count('1'))
        ans+=1
        if X==0:
            break
    print(ans)

Submission status: Runtime Error

Solution code:
import copy
N = int(input())
a = str(input())
c = list(a)

for i in range(len(c)):
  x = copy.copy(c)
  if x[i] == "0":
    x[i] = "1"
  elif x[i] == "1":
    x[i] = "0"
  val = int("".join(x),2)
  #print(val)
  d = x.count("1")
  cns = 1
  while val % d != 0:
    #print(val,d)
    val %= d
    d = list(str(bin(val))).count("1")
    #print(d)
    cns += 1
  print(cns)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)
n = int(input())
X = input()
nx = int(X, 2)
dp = [-1] * (10**6+1)
def f(n):
    if n < 10**6 and dp[n] > 0:
        return dp[n]
    pc = bin(n).count('1')
    nn = n%pc
    if nn == 0:
        return 1

    d = f(nn) + 1
    if n < 10**6:
        dp[n] = d
    return d

for i in range(n-1, -1, -1):
    # ibit目を反転させる # つまりi**2を引く
    tmp = pow(2, i)

    if (nx>>i)&1:
        nx -= tmp
        print(f(nx))
        nx += tmp
    else:
        nx += tmp
        print(f(nx))
        nx -= tmp

Submission status: Runtime Error

Solution code:
N = int(input())
X = str(input())
n = sum(list(map(int, X)))
for i in range(N):
  Y = ''
  m = n
  if X[i] == '0':
    Y = X[:i] + '1' + X[i+1:]
    m += 1
  else:
    Y = X[:i] + '0' + X[i+1:]
    m -= 1
  Z = int(Y, 2)
  Z = Z % m
  ans = 1
  while Z != 0:
    m = sum(list(map(int, format(Z, 'b'))))
    Z %= m
    ans += 1
  print(ans)

Submission status: Runtime Error

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

popcount = [0] * 20
count = [0] * 20
for i in range(1,20):
    a = bin(i)[2:]
    cnt = a.count('1')
    popcount[i] = i % cnt

for i in range(1,20):
    cnt = 1
    nex = popcount[i]
    while nex != 0:
        nex = popcount[nex]
        cnt += 1
    count[i] = cnt

for i in range(N):
    x = X.copy()
    x[i] = '1' if x[i] == '0' else '0'
    x = ''.join(x)
    num = x.count('1')
    pop = int(x,2) % num
    ans = count[pop] + 1
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def s(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
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)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 1
ans = 0
inf = float("inf")

n = k()
x = s()
po = int(x,2)
cnt = x.count("1")
for i in range(n):
    ans = 0
    count = 0
    a = 2**(n-i-1)
    if x[i] == "0":
        ans = po+a
        count = cnt+1
    else:
        ans = po-a
        count = cnt-1
    if ans % count == 0:
        print(1)
    elif ans % count == 1 or (ans%count) % 2 == 0:
        print(2)
    else:
        print(3)

Submission status: Runtime Error

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

from collections import Counter
import sys

up = [0]*n
do = [0]*n

b = Counter(x)

if b["1"] >= 2:
    pr = b["1"]
    a = 1
    for i in range(n):
        up[n-1-i] = a
        a = a*2 % (pr+1)
    
    a = 1
    for i in range(n):
        do[n-1-i] = a
        a = a*2 % (pr-1)
        
    upsum,dosum = 0,0
    for i in range(n):
        upsum = (upsum + (int(x[i]) * up[i])) % (pr+1)
        dosum = (dosum + (int(x[i]) * do[i])) % (pr-1)
        
    pop = [0] * (n+1)
    for i in range(1,n+1):
        xx = bin(i)[2:]
        c = Counter(xx)
        pop[i] = i % c["1"]
        
    for i in range(n):
        if x[i] == "0":
            ss = (upsum + up[i]) % (pr+1)
            
            aa = 0
            for j in range(30):
                if ss == 0:
                    break
                else:
                    ss = pop[ss]
                    aa += 1
                    
            print(aa+1)
            
        elif x[i] == "1":
            ss = (dosum + (pr-1) - do[i]) % (pr-1)
            
            aa = 0
            for j in range(30):
                if ss == 0:
                    break
                else:
                    ss = pop[ss]
                    aa += 1
                    
            print(aa+1)
            
else:
    pr = b["1"]
    a = 1
    for i in range(n):
        up[n-1-i] = a
        a = a*2 % (pr+1)

    upsum = 0
    for i in range(n):
        upsum = (upsum + (int(x[i]) * up[i])) % (pr+1)

    pop = [0] * (n+1)
    for i in range(1,n+1):
        xx = bin(i)[2:]
        c = Counter(xx)
        pop[i] = i % c["1"]
                
    ss = (upsum + up[j]) % (pr+1)
            
    for j in range(n):
        if x[j] == "1":
            print(0)
        else:
            
            
            aa = 0
            for k in range(30):
                if ss == 0:
                    break
                else:
                    ss = pop[ss]
                    aa += 1
                    
            print(aa+1)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
import numpy as np
import math
sys.setrecursionlimit(10**6)
def S(): return sys.stdin.readline().rstrip()
def SL(): return map(str,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def IL(): return map(int,sys.stdin.readline().rstrip().split())

def popcount(val):
    return bin(val).count('1')

def Main():
    n = I()
    x = S()

    for rep in range(n):
        tmp = '1' if x[rep]=='0' else '0'
        bit = x[:rep] + tmp + x[rep+1:]
        itg = int(bit,2)

        c = 0
        while True:
            itg %= popcount(itg)
            c += 1
            if itg==0:
                break
        
        print(c)
    return

if __name__=='__main__':
    Main()

Submission status: Runtime Error

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

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
    #print(X)
    v = int('0b'+X, 0)
    new = v % pop
    #print(new)
    if new == 0:
        print('1')
        continue
    counter = 1
    while True:
        counter += 1
        new = new % popcount(str(bin(new)))
        if new == 0:
            print(counter)
            break

Submission status: Runtime Error

Solution code:
import numpy as np
import math
import scipy as sp
import queue
import collections

MOD = 10 ** 9 + 7
INF = 10 ** 9

def main(kwargs):
    n = kwargs["n"]
    x = kwargs["x"]
    F = [0 for i in range(int("1" * n, 2))]

    def f(x):
        if F[x - 1] != 0:
            return F[x - 1]
        else:
            new_x = x % popcount(x)

            if new_x == 0:
                return 1
            else:
                F[x - 1] = f(new_x) + 1
                return F[x - 1]

    for i in range(int("1" * n, 2)):
        F[i] = f(i + 1)

    X = [x for i in range(n)]

    for i in range(1, n):
        if X[i] == "0":
            X[i] = "{}1{}".format(X[i][:i], X[i][i + 1:])
        else:
            X[i] = "{}0{}".format(X[i][:i], X[i][i + 1:])

    res = [F[int(x, 2) - 1]for x in X]
    res = "\n".join(res)
    return res

def popcount(x):
    s = bin(x)
    return s.count("1")

if __name__ == "__main__":
    kwargs = {}

    cin = input().split()
    kwargs["n"] = [int(i) for i in cin][0]
    cin = input().split()
    kwargs["x"] = cin[0]

    cout = main(kwargs)
    print(cout)

Submission status: Runtime Error

Solution code:
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#int outn=int(input())
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")
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((x10+pow(2,n-i,pc-1))%(pc-1))
la=[float("inf")]*n
for i in range(1,n+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
for a in ans:
  if a==0:
    print(1)
  else:
    print(1+la[a-1])

Submission status: Runtime Error

Solution code:
N=int(input())
X=input()
X10=int(X,2)
one=X.count('1')
a=X10%(one-1)
b=X10%(one+1)
c=one-1
d=one+1
def popcount(n):
  c=format(n,'b').count('1')
  if c==0:
    print(n)
  return n%c
def f(n):
  count=0
  while n>0:
    n=popcount(n)
    count+=1
  return count

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

Solution code:
from functools import lru_cache


def popcnt(n):
    c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c >> 8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c >> 16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c >> 32) & 0x00000000ffffffff)
    return c


@lru_cache(maxsize=None)
def rec(n):
    if n == 0:
        return 0
    else:
        return rec(n % popcnt(n)) + 1


n = int(input())
arr = input()

li = []

for i in range(n):
    tmp = arr[:i] + str(1 ^ int(arr[i])) + arr[i + 1:]
    li.append(int(tmp, 2))

for x in li:
    print(rec(x))

Submission status: Runtime Error

Solution code:
def popcnt3(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

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

for i in range(N):
    x = X.copy()
    cnt = 0
    x[i] = str(int(x[i])^1)
    n = int("".join(x), 2)

    while n>0:
        n = n%popcnt3(n)
        cnt += 1
    print(cnt)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;


#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define PSET(x,y) fixed<<setprecision(y)<<x
#define pb push_back
#define pii pair<int,int>
#define pf push_front
#define mp make_pair
#define vi vector<int>
#define vip vector<pair<int,int> >
#define ff first
#define ss second
#define int long long
//#define mod 1000000007
#define BIG 998244353
#define s(t) scanf("%lld",&t)
#define p(t) printf("%lld\n",t)
#define mii map<int,int>
#define MSET(table,i) memset(table, i, sizeof(table))
#define endl '\n'
#define tc int t;cin>>t;while(t--)
#define pi  3.1415926358
#define bits(x) __builtin_popcount(x)
#define minimum(a,n) min_element(a,a+n)-a
#define maximum(a,n) max_element(a,a+n)-a
#define pqbig priority_queue<int>
#define pqsmall priority_queue<pii,vector<pii>,greater<pii> >
#define all(v) v.begin(),v.end()
#define sitr set<int>:: iterator
#define spitr set<pii>:: iterator
#define mitr map<int,int>:: iterator

int toint(const string &s) {stringstream ss; ss << s; int x; ss >> x; return x;}
string tostring ( int number ) {stringstream ss; ss << number; return ss.str();}


typedef tree<pair<pii, pair<int, pii> >, null_type, less<pair<pii, pair<int, pii> > >, rb_tree_tag,
        tree_order_statistics_node_update>
        new_data_set;


#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl

int power(int n, int p, int mod)
{
	if (p == 0)
		return 1;
	int x = power(n, p / 2, mod);
	x *= x, x %= mod;
	if (p & 1)
		x *= n, x %= mod;
	return x;
}

int solve(string &s, int mod)
{
	if (mod == 0)
		return -1;
	if (mod == 1)
		return 0;

	int ans = 0;
	for (int i = 0; i < s.size(); i++)
	{
		if(s[i]=='0')
			continue;
		int id = s.size() - 1 - i;
		ans += power(2, id, mod);
		ans %= mod;
		//trace2(ans,mod);
	}
	return ans;
}

int32_t main()
{
	fast;
	int n; cin >> n;
	string s; cin >> s;
	int cnt = count(all(s), '1');

	int rem_pos = solve(s, cnt + 1);
	int rem_neg = solve(s, cnt - 1);

	//trace2(rem_pos,rem_neg);

	for (int i = 0; i < n; i++)
	{
		if (s[i] == '1')
		{
			if (cnt == 1)
				cout << 0 << endl;
			else
			{
				int start = rem_neg-power(2,n-1-i,cnt-1);
				start+=(cnt-1),start%=(cnt-1);
				//trace1(start);
				int ans = 1;
				while (start)
				{
					ans++;
					start %= bits(start);
				}
				cout << ans << endl;
			}
		}
		else
		{
			int start = rem_pos+power(2,n-1-i,cnt+1);
			start%=(cnt+1);
			//trace1(start);
			int ans = 1;
			while (start)
			{
				ans++;
				start %= bits(start);
			}
			cout << ans << endl;
		}
	}
}