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

def popcount(nn):
    bin_n = bin(nn)[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
        popcnt = popcount(num)
        num %= popcnt
        lst.append(num)
    for i in range(len(lst)):
        dic[lst.pop()] = i
    print(ans)

Submission status: Runtime Error

Solution code:
def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x = x + (x >> 8) 
    x = x + (x >> 16) 
    x = x + (x >> 32) 
    return x & 0x0000007f
  
def func(n, c):
  next = n%popcount(n)
  c+=1
  if ans[next]!=-1:
    return ans[next]+c
  if next == 0:
    return c
  else:
    return func(next, c)

def solve(n, c):
  next = n%popcount(n)
  c+=1
  if next <= maint and ans[next]!=-1:
    return ans[next]+c
  if next == 0:
    return c
  else:
    return func(next, c)
  
ma = "1"*26
maint = int(ma, 2)+1
n=int(input())
x=input()
ans = [-1]*maint
ans[0]=0
for i in range(1, maint):
  ans[i] = func(i, 0)

for i in range(n):
  temp=list(x)
  if x[i]=="0":
    temp[i]="1"
  else:
    temp[i]="0"
  itemp = int("".join(temp), 2)
  #print(itemp)
  if itemp<=maint:
    print(ans[itemp])
  else:
    print(solve(itemp, 0))

Submission status: Runtime Error

Solution code:
n = int(input())
x = [int(x) for x in list(input())]

x_cnt = 0
for i, y in enumerate(x):
    if y == 1:
        x_cnt += 1

aa = x_cnt + 1
bb = x_cnt - 1

a = [1 % aa]
b = [1 % bb]

for _ in range(n-1):
    a.append(a[-1]*2 % aa)
    b.append(b[-1]*2 % bb)

a = a[::-1]
b = b[::-1]

x_ps = 0
x_ng = 0
for i, val in enumerate(x):
    if val == 1:
        x_ps += a[i]
        x_ng += b[i]

for i in range(n):
    ans = 0
    if x[i] == 0:
        cnt = x_cnt + 1
        val = (x_ps + a[i]) % cnt
    else:
        cnt = x_cnt - 1
        if cnt == 0:
            print(ans)
            continue
        val = (x_ng - b[i]) % cnt
    ans += 1

    tmp = val
    cnt = 0
    while tmp > 0:
        if tmp & 1:
            cnt += 1
            tmp = (tmp-1) // 2
        else:
            tmp = tmp // 2
    if cnt == 0:
        print(ans)
        continue

    while val > 0:
        ans += 1
        val = val % cnt
        tmp = val % cnt
        cnt = 0
        while tmp > 0:
            if tmp & 1:
                cnt += 1
                tmp = (tmp-1) // 2
            else:
                tmp = tmp // 2
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n = int(readline())
lst1 = list(readline().rstrip().decode('utf-8'))


res = lst1.copy()
res = "".join(res)
ct = res.count("1")
res = int(res,2)

amari_of_m = res%(ct-1)
amari_of_p = res%(ct+1)

def pow(n,p,mod): #繰り返し二乗法(nのp乗)
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod

def func(res):
    ans = 1
    while True:
        ct = 0
        for i in range(len(bin(res))):
            if res>>i&1:
                ct += 1
        if res%ct == 0:
            print(ans+1)
            return
        else:
            res %= ct
            ans += 1

for i in range(n):
    #resres = (1<<(n-i-1)) if lst1[i] == "1" else (1<<(n-i-1))
    resres = pow(2,n-i-1,ct-1) if lst1[i] == "1" else pow(2,n-i-1,ct+1)
    if lst1[i] == "1":
        resres -= amari_of_m
        resres %= ct-1
    else:
        resres += amari_of_p
        resres %= ct+1
    if not resres:
        print(1)
    else:
        func(resres)

Submission status: Runtime Error

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

def solve(k, cnt, Ans):
    S = str(bin(k)).count("1") 
    L = k % S
    if L < len(Ans)-1:
        return Ans[L]
    elif L == 0:
        return 1
    cnt += solve(L,cnt)
    return cnt 

N = int(input())
P = input()
I = P.count("1")
Df = int(P,2)
Ans = [1]

for i in range(1, I+1):
    cnt = 1
    Ans.append(solve(i, cnt, Ans)+1)
#print(Ans)

for i in range(N-1):
    if P[i] == "1":
        tmp = Df - 2**(N-i-1)
        cur = I-1
    else:
        tmp = Df + 2**(N-i-1)
        cur = I + 1 
    print(Ans[tmp%cur])
    #print(solve(tmp,cnt))

if P[N-1] == "1":
    tmp = Df - 1
else:
    tmp = Df + 1
cur = str(bin(tmp)).count("1")
print(Ans[tmp%cur])
#print(solve(N,cnt))

Submission status: Runtime Error

Solution code:

n = int(input())
s=input()
p=0
c=0
for i in range(n):
    if s[i]=='1':
        p+=2**(n-i-1)
        c+=1
for i in range(n):
    k=p
    z=c
    if s[i]=='0':
        k+=2**(n-i-1)
        z+=1
    else:
        k-=2**(n-i-1)
        z-=1
    if z==1:
        print(1)
    elif (k&1)==(z&1):
        if k%z==0:
            print(1)
        else:
            print(2)
    else:
        print(3)

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 = list(input())
count = 0
for i in x:
    if i == "1": count += 1
    
output = []
for n in range(N):
    cnt = 1
    tmp_count = count
    y = x.copy()
    if y[n] == "1":
        y[n] = "0"
        tmp_count -= 1
    else:
        y[n] = "1"
        tmp_count += 1

    s = "".join(y)
    v = int(s, 2) % tmp_count
    tmp_count = popcount(v)

    while (v > 0):
        v %= tmp_count
        tmp_count = popcount(v)
        cnt += 1

    output.append(cnt)

print(*output, sep="\n")

Submission status: Runtime Error

Solution code:
N=int(input())
X=[x for x in input()]
ONE=X.count('1')

ans=0
L=[0,1,1,2,1,2,1,2,1,1,1,2,1,2,2]

def func(n,popcount):
  index=n%popcount
  print(L[index]+1)
  

for i in range(N):
  if X[i]=='0':
    temp=int(''.join(X),2)+2**(N-1-i)
    func(temp,ONE+1)
  else:
    temp=int(''.join(X),2)-2**(N-1-i)
    func(temp,ONE-1)

Submission status: Runtime Error

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

xlist = [0] *n
ans =  [0] *n

def count(num):
    num = (num & 0x55555555) + (num >> 1 & 0x55555555)
    num = (num & 0x33333333) + (num >> 2 & 0x33333333)
    num = (num & 0x0F0F0F0F) + (num >> 4 & 0x0F0F0F0F)
    num = (num & 0x00FF00FF) + (num >> 8 & 0x00FF00FF)
    num = (num & 0x0000FFFF) + (num >>16 & 0x0000FFFF)
    return num



for i in range(n):
    xs = x
    if x[i] == '0':
        xs=x[:i]+'1'+x[i+1:]
    else:
        xs=x[:i]+'0'+x[i+1:]
    xlist[i]=xs

i=0


for xi in xlist:
    x = int(xi,2)
    a=0
    while not x ==0:
        x = x%count(x)
        a +=1
    ans[i]=a
    i+=1

for a in ans:
    print(a)

Submission status: Runtime Error

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


def calc(i, count):
    r = i % bin(i).count("1")
    if r != 0:
        return calc(r, count + 1)
    else:
        return count + 1


for i in range(1, N + 1):
    a = int(X, 2) ^ int((bin(1 << ((N - 1) - (i - 1)))), 2)
    b = calc(a, 0)
    print(b)

Submission status: Runtime Error

Solution code:
N = int(input())
S = list(map(int,list(input())))
S.reverse()
r = [0 for _ in range(10 ** 5 + 100)]
p0 = [0 for _ in range(N + 100)]
q0 = 0
p1 = [0 for _ in range(N + 100)]
q1 = 0
q = S.count(1)
p0[0] = 1
p1[0] = 1
for i in range(N):
    p0[i + 1] = (p0[i] * 2) % (q + 1)
    if S[i] == 1:
        q0 += p0[i]
        q0 %= q + 1

for i in range(N):
    p1[i + 1] = (p1[i] * 2) % (q - 1)
    if S[i] == 1:
        q1 += p1[i]
        q1 %= q - 1

r[0] = 0
for i in range(1,10 ** 5+10):
    qx = 0
    for i2 in range(20):
        if i >> i2 & 1:
            qx += 1
    r[i] = r[i % qx] + 1
for i in range(N):
    if S[N - i - 1] == 0:
        print(r[(q0 + p0[N-i-1]) % (q + 1)] + 1)
    else:
        print(r[(q1 - p1[N-i-1]) % (q - 1)] + 1)

Submission status: Runtime Error

Solution code:
def mpower(a, b, n):
    if b == 0:
        return 1
    if b == 1:
        return a % n
    a1 = a
    k = 1
    while a1 < n and k < b:
        a1 = a1 * a
        k = k + 1

    a1 = a1 % n
    b1 = b // k
    a2 = a
    b2 = b % k
    return (mpower(a1, b1, n)*mpower(a2, b2, n)) % n


def main():
    n = int(input())
    x = input()
    k = int(x, 2)
    p = x.count("1")
    kp0 = k % (p - 1)
    kp1 = k % (p + 1)
    f = [0] * (n + 1)
    for i in range(1, n + 1):
        f[i] = f[i % bin(i).count("1")] + 1
    for i in range(n):
        if x[i] == "1":
            pi = p - 1
            if pi == 0:
                print(0)
                continue
            print(f[(kp0 - mpower(2, n - i - 1, pi)) % pi] + 1)
        else:
            pi = p + 1
            print(f[(kp1 + mpower(2, n - i - 1, pi)) % pi] + 1)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

def popcount(s):
  return s.count('1')

def f(s):
  sub = int(s, 2) % popcount(s)
  if sub:
    return 1 + f('{:b}'.format(sub))
  else:
    return 1

for n in range(N-1, -1, -1):
  print(f('{:b}'.format(int(X, 2) ^ 2**n)))

Submission status: Runtime Error

Solution code:
n = int(input())
s = input()
num=int(s,2)

for i in range(n):
    if s[i]=='1':
        a=num-(2**(n-i-1))
    else:
        a=num+(2**(n-i-1))
    counter=0
    while True:
        sa=format(a, 'b')
        warukazu=sa.count('1')
        a=a%warukazu
        counter+=1
        if a==0:
            print(counter)
            break

Submission status: Runtime Error

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

n = int(input())
x = input()
px = x.count("1")
a = px + 1
b = px - 1
tmpa = 0
tmpb = 0

A = [False] * n
for i in range(n):
    if x[i] == "1":
        tmpa += pow(2, n - i - 1, a)
        tmpa %= a
        tmpb += pow(2, n - i - 1, b)
        tmpb %= b

for i in range(1, n + 1):
    count = 1
    if x[i - 1] == "1":  # x[i] == "1" -> "0"
        y = tmpb - pow(2, n - i, b)
        y %= b
    else:  # x[i] == "0" -> "1"
        y = tmpa + pow(2, n - i, a)
        y %= a
    while y:
        y %= popcount(y)
        count += 1
    print(count)

Submission status: Runtime Error

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

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

p = [-1 for _ in range(2*(10**5)+10)]
cnt = x.count('1')

def calc(a):
  #print('a=',a)
  if p[a] != -1:
    return p[a]
  else:
    if a == 0:
      ret = 0
    else:
      b = bin(a).count('1')
      ret = 1+calc(a%b)
    p[a] = ret
    return ret

x0 = int(x,2)%(cnt-1)
x1 = int(x,2)%(cnt+1)
xx0 = [1]
for i in range(n+1):
  xx0.append((xx0[-1]*2)%(cnt-1))
xx1 = [1]
for i in range(n+1):
  xx1.append((xx1[-1]*2)%(cnt+1))
  
for i in range(n):
  y = list(x)
  if y[i] == '0':
    xx = xx1[n-i-1]
    print(calc((x1+xx)%(cnt+1))+1)
  else:
    xx = xx0[n-i-1]
    print(calc((x0-xx)%(cnt-1))+1)

Submission status: Runtime Error

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

def power(x, n):
    if n == 0: return 1
    value = power(x, int(n / 2))
    value *= value
    if n % 2 == 1: value *= x
    return value

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

counter = sum(list(map(int, x)))
number = sum([power(2, n-i-1) for i in range(n) if x[i] == '1'])

def f(num, cnt):
    if num == 0:
        return cnt
    popcount = sum(list(map(int, format(num, 'b'))))
    return f(num % popcount, cnt+1)

for i in range(n):
    if x[i] == '0':
        m = number + power(2, n-i-1)
        print(f(m % (counter+1), 1))
    if x[i] == '1':
        m = number - power(2, n-i-1)
        print(f(m % (counter-1), 1))

Submission status: Runtime Error

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


# cache = {}
import functools


def main():
    n = int(input().strip())
    x_str = input().strip()
    x = int(x_str, 2)

    for i in range(n, 0, -1):
        cur_bit = 1 << (i - 1)
        xi = x ^ cur_bit

        print(fc(xi))


@functools.lru_cache(maxsize=None)
def fc(n):
    n_bin = bin(n)
    c = len(n_bin[2:].replace('0', ''))
    if n % c == 0:
        return 1
    else:
        return fc(n % c) + 1


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

for i in range(N):
    res = 1
    tmp = int(X, 2) ^ (1<<(N-i-1))
    
    while tmp % len(format(tmp, 'b').replace('0','')) != 0:
        tmp = tmp % len(format(tmp, 'b').replace('0',''))
        res += 1
    print(res)

Submission status: Runtime Error

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

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

def pc(n: int):
    return bin(n).count('1')

for i in range(N-1,-1,-1):
    x = toggle_nth_bit(X,i)
    ans = 0
    while True:
        x = x % pc(x)
        ans += 1
        if x == 0:
            break
    print(ans)

Submission status: Runtime Error

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

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

N = INT()
S = list(map(int, input()))[::-1]
pcnt1 = S.count(1) - 1
pcnt2 = S.count(1) + 1
base1 = base2 = 0
for i in range(N):
    if S[i]:
        base1 += pow(2, i, pcnt1)
        base2 += pow(2, i, pcnt2)

ans = [0] * N
for i in range(N):
    if S[i]:
        cur = (base1 - pow(2, i, pcnt1)) % pcnt1
    else:
        cur = (base2 + pow(2, i, pcnt2)) % pcnt2
    cnt = 1
    while cur:
        cur %= popcount(cur)
        cnt += 1
    ans[i] = cnt
for a in ans[::-1]:
    print(a)

Submission status: Runtime Error

Solution code:
import sys

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

if n==1:
    if x=="0":
        print(1)
    else:
        print(0)
    sys.exit()


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

cpls=cnt+1
cmns=cnt-1

cplis=[1]
if cpls!=0:
    for i in range(n):
        cplis.append((cplis[i]*2)%cpls)
cmlis=[1]
if cmns!=0:
    for i in range(n):
        cmlis.append((cmlis[i]*2)%cmns)

cpsum=0
cmsum=0
for i in range(n):
    if x[i]=="1":
        cpsum=(cpsum+cplis[n-1-i])%cpls
        cmsum=(cmsum+cmlis[n-1-i])%cmns

for i in range(n):
    if x[i]=="0":
        Xi=(cpsum+cplis[n-1-i])%cpls
        print(lis[Xi]+1)
    else:
        if cmns==0:
            print(0)
        else:
            Xi=(cmsum-cmlis[n-1-i])%cmns
            print(lis[Xi]+1)

Submission status: Runtime Error

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

def popcount(n): 
    count = 0
    while (n): 
        count += n & 1
        n >>= 1
    return count 

def f(x):
	if x == 0:
		return 0
	else:
		return 1 + f(x % popcount(x))

totalpopcount = popcount(x)
for i in range(1, n + 1):
	one_shifted = (1 << n - i)
	if x & one_shifted:
		print(f((x ^ one_shifted) % (totalpopcount - 1)) + 1)
	else:
		print(f((x ^ one_shifted) % (totalpopcount + 1)) + 1)

Submission status: Runtime Error

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

two_times = [1, 2, 4, 6, 8, 10, 12, 16]
three_times = [3, 5, 7, 9, 11, 13, 14, 17]

for i in range(n):
    tmp = list(x)
    if tmp[i] == "0":
        tmp[i] = "1"
    else:
        tmp[i] = "0"
    cnt = tmp.count("1")
    num = int("".join(tmp), 2)
    if num % cnt in two_times:
        print(2)
    elif num % cnt in three_times:
        print(3)
    elif num % cnt == 0:
        print(1)
    else:
        print(4)

Submission status: Runtime Error

Solution code:
ma = lambda :map(int,input().split())
ni = lambda:int(input())
import collections
import math
import itertools
gcd = math.gcd
n = ni()
x = input()
xr = x[::-1]
px = x.count("1")
def solve(t):
    ret = 1 #最初の一回
    while t>0:
        p = bin(t).count("1")
        t %=p
        ret +=1
    return ret
x_tp = 0
x_tm = 0

for i in range(n):
    x_tp = (x_tp + int(xr[i])*pow(2,i,px+1) ) %(px+1) ## 0->1
if px>1:
    for i in range(n):
        x_tm = (x_tm + int(xr[i])*pow(2,i,px-1) ) %(px-1) # 1->0
ans = []

for i in range(n):
    if xr[i] =="0":
        x_tmp = (x_tp + pow(2,i,px+1) ) %(px+1)
    else:#1->0
        x_tmp = (x_tm - pow(2,i,px-1)) %(px-1)
    t = solve(x_tmp)
    ans.append(t)
for i in range(n-1,-1,-1):
    print(ans[i])

Submission status: Runtime Error

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

memo = {}

if N == 1:
    print(1)
    exit()


def count_one(num):
    if num in memo:
        return memo[num]
    else:
        v = bin(num)[2:].count('1')
        memo[num] = v
        return v


one_count = 0
for x in X:
    if x == '1':
        one_count += 1

for i in range(N):
    #print(' i : ' + str(i))
    ans = 0
    tmp = one_count
    if X[i] == '1':
        X[i] = '0'
        tmp -= 1
    else:
        X[i] = '1'
        tmp += 1
    base_10 = int(''.join(X), 2)
    while True:
        base_10 %= tmp
        ans += 1
        if base_10 == 0:
            print(ans)
            if X[i] == '1':
                X[i] = '0'
            else:
                X[i] = '1'
            break
        tmp = count_one(base_10)
        # print(tmp)

Submission status: Runtime Error

Solution code:
n = int(input())
x = int(input(),2)
zuru = [0, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 2, 3, 1, 2, 1, 2, 1, 1, 2, 3, 1, 2, 2, 3, 2, 2, 2, 2, 1, 2, 1, 2, 1, 2, 2, 3, 1, 2, 1, 3, 2, 2, 2, 2, 1, 2, 2, 3, 2, 2, 2, 1, 2, 2, 2, 2, 1, 2, 2, 3, 1, 2, 1, 2, 1, 1, 2, 3, 1, 2, 2, 3, 2, 2, 2, 2, 1, 1, 2, 3, 1, 2, 2, 2, 2, 2, 2, 2, 1, 3, 2, 3, 1, 2, 2, 3, 2, 2, 2, 3, 2, 2, 2, 2, 1, 2, 1, 3, 2, 2, 2, 1, 1, 2, 3, 3, 1, 2, 2, 3, 2, 3, 1, 2, 1]

_max = pow(2, n-1)
while 1:
  n = x ^ _max
  count = 0
  while n != 0:
    if 0 <= n <=1024:
      count += zuru[n]
      break
    n = n % bin(n).count("1")
    count += 1
  print(count)
  n = x ^ _max
  _max = _max // 2
  if _max == 0:
    break

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
n = int(input())
x = input()
c = x.count("1")
m = 0
for i in range(n):
    if x[i] == "1":
        m += pow(2, (n - i - 1), c + 1)
m %= c + 1
m2 = 0
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":
        t = m2 - pow(2, (n - i - 1), c - 1)
        t %= c - 1
    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: Runtime Error

Solution code:
"""
    こんにちは。これはクシャルです
    
    Author : thekushalghosh (クシャル)
    Team   : CodeDiggers
 
    I prefer Python language over the C++ language :p :D
        
    Visit my website : thekushalghosh.github.io
"""
import sys,math,cmath,time,itertools
start_time = time.time()
##########################################################################
################# ---- THE ACTUAL CODE STARTS BELOW ---- #################
a = [0] * (100000 + 1)
for i in range(1,100000 + 1):
    q = bin(i).replace("0b","")
    a[i] = a[i % q.count("1")] + 1
    
def solve():
    global a
    n = inp()
    s = insr()
    w = s.count("1")
    qw = int(s,2)
    for i in range(n):
        if s[i] == "0":
            qw = qw + (2 ** (n - i - 1))
            w = w + 1
        else:
            qw = qw - (2 ** (n - i - 1))
            w = w - 1
        if w == 0:
            print(0)
        else:
            print(a[qw % w] + 1)
        if s[i] == "0":
            qw = qw - (2 ** (n - i - 1))
            w = w - 1
        else:
            qw = qw + (2 ** (n - i - 1))
            w = w + 1
    
################## ---- THE ACTUAL CODE ENDS ABOVE ---- ##################
##########################################################################
 
def main():
    global tt
    if not ONLINE_JUDGE:
        sys.stdin = open("input.txt","r")
        sys.stdout = open("output.txt","w")
    t = 1
    for tt in range(t):
        solve()
    if not ONLINE_JUDGE:
        print("Time Elapsed :",time.time() - start_time,"seconds")
        sys.stdout.close()
    
#---------------------- USER DEFINED INPUT FUNCTIONS ----------------------#
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    return(input().strip())
def invr():
    return(map(int,input().split()))
 
#------------------ USER DEFINED PROGRAMMING FUNCTIONS ------------------#
def counter(a):
    q = [0] * max(a)
    for i in range(len(a)):
        q[a[i] - 1] = q[a[i] - 1] + 1
    return(q)

def counter_elements(a):
    q = dict()
    for i in range(len(a)):
        if a[i] not in q:
            q[a[i]] = 0
        q[a[i]] = q[a[i]] + 1
    return(q)

def string_counter(a):
    q = [0] * 26
    for i in range(len(a)):
        q[ord(a[i]) - 97] = q[ord(a[i]) - 97],1
    return(q)
 
def factors(n):
    q = []
    for i in range(1,int(n ** 0.5) + 1):
        if n % i == 0: q.append(i); q.append(n // i)
    return(list(sorted(list(set(q)))))
 
def prime_factors(n):
    q = []
    while n % 2 == 0: q.append(2); n = n // 2
    for i in range(3,int(n ** 0.5) + 1,2):
        while n % i == 0: q.append(i); n = n // i
    if n > 2: q.append(n)
    return(list(sorted(q)))

def transpose(a):
    n,m = len(a),len(a[0])
    b = [[0] * n for i in range(m)]
    for i in range(m): 
        for j in range(n): 
            b[i][j] = a[j][i]
    return(b)

#-----------------------------------------------------------------------#
        
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
    input = sys.stdin.readline
    
main()

Submission status: Runtime Error

Solution code:
n = int(input())
x = list(input())
cnt = x.count("1")

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):
    y = x[:]
    if x[i] == "1":
        y[i] = "0"
        z = "".join(y)
        z = int(z, 2)
        z %= (cnt - 1)
        if z == 0:
            print(1)
        else:
            ans = 1
            while z > 0:
                z %= popcount(z)
                ans += 1
            print(ans)
    else:
        y[i] = "1"
        z = "".join(y)
        z = int(z, 2)
        z %= (cnt + 1)
        if z == 0:
            print(1)
        else:
            ans = 1
            while z > 0:
                z %= popcount(z)
                ans += 1
            print(ans)

Submission status: Runtime Error

Solution code:
def popcount(a):
    s = str(bin(a))
    return s.count('1')

def func(a):
    cnt=0
    while True:
        a = a % popcount(a)
        cnt+=1
        if a==0:
            break
    return cnt

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

answermap={}

for i in range(n):
    x2 = list(x)
    if x[i] =='0':
        x2[i] = '1'
    else:
        x2[i] = '0'
    x3 = int("".join(x2),2)
    if x3 in answermap.keys():
        print(answermap[x3])
    else:
        ans = func(x3)
        answermap[x3] = ans
        print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
S = list(map(int,list(input())))
S.reverse()
r = [0 for _ in range(10 ** 5 + 1)]
p0 = [0 for _ in range(N + 1)]
q0 = 0
p1 = [0 for _ in range(N + 1)]
q1 = 0
q = S.count(1)
p0[0] = 1
p1[0] = 1
for i in range(N):
    p0[i + 1] = (p0[i] * 2) % (q + 1)
    if S[i] == 1:
        q0 += p0[i]
        q0 %= q + 1

for i in range(N):
    p1[i + 1] = (p1[i] * 2) % (q - 1)
    if S[i] == 1:
        q1 += p1[i]
        q1 %= q - 1

r[0] = 0
for i in range(1,10 ** 5):
    qx = 0
    for i2 in range(18):
        if i >> i2 & 1:
            qx += 1
    r[i] = r[i % qx] + 1
for i in range(N):
    if S[N - i - 1] == 0:
        print(r[(q0 + p0[N-i-1]) % (q + 1)] + 1)
    else:
        print(r[(q1 - p1[N-i-1]) % (q - 1)] + 1)

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
        if X[i-1] == "1":
            x -= 2**(N-i)
        else:
            x += 2**(N-i)
        tmp = x
        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()

f = [0 for _ in range(n+1)]
for i in range(1,n+1):
  one_num = str(bin(i)).count("1")
  #print(i,one_num)
  if i%one_num == 0:
    f[i] = 1
  else:
    f[i] = f[i%one_num] + 1
base = str(int(x)).count("1")
x_num = int(x, 2)
#print(x_num)
for i in range(n):
  b = base
  #print(x[i])
  if x[i] == "0":
    b += 1
    t = x_num + 2**(n-i-1)
  else:
    b -= 1
    t = x_num - 2**(n-i-1)
  print(1+f[t%b])

Submission status: Runtime Error

Solution code:
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from functools import lru_cache
from math import factorial#, gcd
from bisect import bisect_left, bisect_right #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

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

def mn(): return -1
pops = defaultdict(mn)
dists = defaultdict(mn)

# 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
def popcnt(n):
    return bin(n).count('1')
def myf(n):
    if pops[n] != -1:
        return pops[n]
    else:
        val = popcnt(n)
        pops[n] = val
        return n%val

@lru_cache(maxsize=None)
def saiki(n):
    if n == 0:
        return 0
    else:
        n = myf(n)
        return saiki(n) + 1

if N == 1:
    if X[0] == '0':
        print(1)
        exit()
    else:
        print(0)
        exit()

bX = int(X, 2)
pc = popcnt(bX)
for i in range(N):
    one = False
    if X[i] == '1':
        one = True
        val = bX - 2**(N-i-1)
    else:
        one = False
        val = bX + 2**(N-i-1)
    if one:
        tpc = pc-1
    else:
        tpc = pc+1
    val %= tpc
    res = saiki(val)
    print(res+1)

Submission status: Runtime Error

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

def power(x, n):
    if n == 0: return 1
    value = pow1(x, int(n / 2))
    value *= value
    if n % 2 == 1: value *= x
    return value

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

counter = sum(list(map(int, x)))
number = sum([power(2, n-i-1) for i in range(n) if x[i] == '1'])

def f(num, cnt):
    if num == 0:
        return cnt
    popcount = sum(list(map(int, format(num, 'b'))))
    return f(num % popcount, cnt+1)

for i in range(n):    
    if x[i] == '0':
        m = number + power(2, n-i-1)
        print(f(m % (counter+1), 1))
    if x[i] == '1':
        m = number - power(2, n-i-1)
        print(f(m % (counter-1), 1))