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()

x_num = int(X, 2)
cnt1 = X.count('1')

p_zero = x_num % (cnt1 + 1)
p_one = x_num % (cnt1 - 1)


def f(cnt):
    if (cnt > 0):
        pcount = p_count(cnt)
        return f(cnt % pcount) + 1
    else:
        return 0


def p_count(x):
    cnt = 0
    while (x > 0):
        if x % 2 != 0:
            cnt += 1
        x //= 2
    return cnt


def f1(x):
    cnt = 0
    while (x > 0):
        x %= bin(x).count('1')
        cnt += 1
    return cnt


for i, x in enumerate(list(X)):
    if (x == '1'):
        #x_num = int(''.join(X), 2)
        if cnt1 - 1 > 0:
            xxx = (p_one - pow(2, (N - (i + 1)), cnt1 - 1)) % (cnt1 - 1)
            xxx += cnt1 - 1 if xxx < 0 else 0
            print(f1(xxx) + 1)
        else:
            print(0)
    else:
        #x_num = int(''.join(X), 2)
        xxx = (p_zero - pow(2, (N - (i + 1)), cnt1 + 1)) % (cnt1 + 1)
        xxx += cnt1 + 1 if xxx < 0 else 0
        print(f1(xxx) + 1)

Submission status: Runtime Error

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

x_num = int(X, 2)
cnt1 = X.count('1')

p_zero = x_num % (cnt1 + 1)
p_one = x_num % (cnt1 - 1)


def f(cnt):
    if (cnt > 0):
        pcount = p_count(cnt)
        return f(cnt % pcount) + 1
    else:
        return 0


def p_count(x):
    cnt = 0
    while (x > 0):
        if x % 2 != 0:
            cnt += 1
        x //= 2
    return cnt


def f1(x):
    cnt = 0
    while (x > 0):
        x %= bin(x).count('1')
        cnt += 1
    return cnt


for i, x in enumerate(list(X)):
    if (x == '1'):
        #x_num = int(''.join(X), 2)
        if cnt1 - 1 > 0:
            xxx = (p_one - pow(2, (N - (i + 1)), cnt1 - 1)) % (cnt1 - 1)
            xxx += cnt1 - 1 if xxx < 0: else: 0
            print(f1(xxx) + 1)
        else:
            print(0)
    else:
        #x_num = int(''.join(X), 2)
        xxx = (p_zero - pow(2, (N - (i + 1)), cnt1 + 1)) % (cnt1 + 1)
        xxx += cnt1 + 1 if xxx < 0: else: 0
        print(f1(xxx) + 1)

Submission status: Runtime Error

Solution code:

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


def popcount(n):
    ans = 0
    temp = format(n, "b")
    for i in temp:
        if i == "1":
            ans += 1

    return ans

def f(n):
    cnt = 0
    temp = n
    while temp != 0:
        temp = temp % pop_memo[temp] #popcountの計算結果をメモすることで高速化できる
        cnt += 1

    return cnt

pop_memo = [0] * (2 ** N + 1)
for i in range(2 ** N + 1):
    pop_memo[i] = popcount(i)

memo = 0
for i in X:
    if i == "1":
        memo += 1

for i in range(N):
    if X[i] == "1":
        tem = int(X, 2) - (2 ** (N - i - 1))
        tem = f(tem)
        print(tem)

    elif X[i] == "0":
        tem = int(X, 2) + (2  ** (N - i - 1))
        tem = f(tem)
        print(tem)

Submission status: Runtime Error

Solution code:
N = int(input())
X = list(str(input()))
n = 0
nn = 0
for h in range(N):
    n += int(X[h])*(2 **(N-1-h))
nn = bin(n).count('1')
a = 0
aa = 0
for i in range(N):
    if (X[i] == "1"):
        aa = nn - 1
        a = (n - (2 **(N-1-i))) % aa

    else:
        aa = nn + 1
        a = (n + (2 **(N-1-i))) % aa

    time = 0
    while a >0:
        a = a % aa
        aa = bin(a).count('1')
        if a == 0:
            break
        time += 1
    print(time+1)

Submission status: Runtime Error

Solution code:
n = int(input())
X = input()
x = int(X,2)
bitx = bin(x).count('1')
 
ans = [0]*(bitx+1)
for i in range(1,len(ans)):
    ans[i] = 1 + ans[i%bin(i).count('1')]
#print(ans)
l = []
bitp = bitx + 1
bitm = bitx - 1
xmp = 0
xmm = 0
 
for i in range(n):
    if X[i] == '1':
        xmp += pow(2, n-(i+1), bitp)
        xmm += pow(2, n-(i+1), bitm)
        
for i in range(n):
    if X[i] == '1':
        if bitm == 0:
            l.append(str(0))
        else:
        	xm = (xmm - pow(2,n-i-1,bitm)) % bitm
        	l.append(str(1+ans[xm]))
    else:
        xm = (xmp + pow(2,n-i-1,bitp))%bitp
        l.append(str(1+ans[xm]))

    #print(1+ans[t])
print('\n'.join(l))

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
original_pop_count = x.count('1')
one_pop_count = original_pop_count-1
zero_pop_count = original_pop_count+1

one_mod = 0
zero_mod= 0
for b in x:
    one_mod=(one_mod*2+int(b))%one_pop_count
    zero_mod=(zero_mod*2+int(b))%zero_pop_count
#予めf[i]を計算する
f = [0]*220000
pop_count = [0]*220000
for i in range(1,220000):
    pop_count[i]= pop_count[i//2] + i%2
    f[i] = f[i%pop_count[i]]+1
one_pow2 = [1]*220000
zero_pow2 = [1]*220000
for i in range(1,220000):
    one_pow2[i] = one_pow2[i-1]*2%one_pop_count
    zero_pow2[i] = zero_pow2[i-1]*2%zero_pop_count


for i in range(n-1,-1,-1):
    if x[n-1-i]=='1':
        nxt = one_mod
        nxt-=one_pow2[i]
        nxt%=one_pop_count
        print(f[nxt]+1)
    if x[n-1-i]=='0':
        nxt = zero_mod
        nxt+=zero_pow2[i]
        nxt%=zero_pop_count
        print(f[nxt]+1)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

import sys
import math

def saiki(n,saiki_one_count,do_count):
    do_count += 1
    mod = n % saiki_one_count
    if mod == 0:
        return do_count
    saiki_one_count = bin(mod).count("1")
    return saiki(mod,saiki_one_count,do_count)
def main():
    input = sys.stdin.readline
    N = int(input())
    x = input()
    x_list = list(x)[:-1]
    x_list = [int(value) for value in x_list]
    one_count = x_list.count(1)
    sum_x = 0
    for i in range(len(x_list)):
        if x_list[N -1 - i] == 1:
            sum_x += 2 ** i
    zero_convert = sum_x%(one_count+1)
    one_convert = sum_x%(one_count+1)

    for i in range(len(x_list)):
        current_sum_x = 0
        current_one_count = 0
        if x_list[i] == 0:
            current_one_count = one_count + 1
            current_sum_x = zero_convert + pow(2,N-i-1,current_one_count)
        else:
            current_one_count = one_count - 1
            current_sum_x = one_convert + pow(2,N-i-1,current_one_count)
        do_count = saiki(current_sum_x,current_one_count,0)
        print(do_count)
    return


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

memo = {0:0, 1:1, 2:1}
def calc(x):
  global memo
  if x in memo:
    return memo[x]
  c = bin(x).count('1')
  y = x % c
  res = calc(y) + 1
  memo[x] = res
  return res

for i in range(3, 2*10**5 + 1):
  calc(i)

N = int(input())
X = input()
X_int = int(X, 2)
c = X.count('1')
X_list = list(X)
ans = []
digit = 1 << (N - 1)
for i, x in enumerate(X_list):
  if x == '0':
    ans.append(calc((X_int+digit)%(c+1))+1)
  else:
    ans.append(calc((X_int-digit)%(c-1))+1)
  
  digit >>= 1

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

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
count_1 = x.count('1')
value = [0, 0]
x_int = int(x, 2)
value[0] = x_int % (count_1 - 1) if count_1 > 1 else 0
value[1] = x_int % (count_1 + 1)
for i in range(n):
    if x[i] == '0':
        tmp = (pow(2, n - i - 1, count_1 + 1) + value[1]) % (count_1 + 1)
    else:
        tmp = (-pow(2, n - i - 1, count_1 - 1) + value[0]) % (count_1 - 1)
    ans = 1
    while tmp > 0:
        tmp = tmp % (bin(tmp).count('1'))
        ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()   
              
memo = {}     
x_val = int(X, 2)
pc_x = X.count('1')
              
x_mod_pc_x_plus_1 = x_val % (pc_x + 1)
x_mod_pc_x_minus_1 = x_val % (pc_x - 1)
              
for i in range(N):
    if X[i] == '1':
        pc = pc_x - 1
        if pc == 0:
            print(0)
            continue
        val = (x_mod_pc_x_minus_1 - pow(2, N-i-1, pc)) % pc
    else:     
        pc = pc_x + 1
        val = (x_mod_pc_x_plus_1 + pow(2, N-i-1, pc)) % pc
    ans = 1   
    while val > 0:
        val %= bin(val).count('1')
        ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
count_1 = x.count('1')
value = [0, 0]
value[0] = int(x, 2) % (count_1 - 1) if count_1 > 1 else 0
value[1] = int(x, 2) % (count_1 + 1)
for i in range(n):
    div = 1 if x[i] == '0' else -1
    tmp = (pow(2, n - i - 1, count_1 + div) + value[div*(-1)]) % (count_1 + div)
    ans = 1
    while tmp > 0:
        tmp = tmp % (bin(tmp).count('1'))
        ans += 1
    print(ans)

Submission status: Runtime Error

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

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

pops = popcount(x)
x_pop_p = x%(pops + 1)
try:
    x_pop_m = x%(pops - 1)
except:
    x_pop_m = 0
for i in reversed(range(0,n)):
    if x_s[i] == '1':
        tmp = (x_pop_m - pow(2,i,(pops - 1)))%(pops - 1)
    else:
        tmp = (x_pop_p + pow(2,i,(pops + 1))) % (pops + 1)
    if tmp == 0:
        print(1)
        continue
    cnt = 2
    tmp %= popcount(tmp)
    while tmp > 0:
        cnt += 1
        if tmp == 0:
            print(cnt-1)
            continue
        tmp %= popcount(tmp)
    print(cnt)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

import sys
import math

def saiki(n,saiki_one_count,do_count):
    do_count += 1
    mod = n % saiki_one_count
    if mod == 0:
        return do_count
    saiki_one_count = bin(mod).count("1")
    return saiki(mod,saiki_one_count,do_count)
def main():
    input = sys.stdin.readline
    N = int(input())
    x = input()
    x_list = list(x)[:-1]
    x_list = [int(value) for value in x_list]
    one_count = x_list.count(1)
    sum_x = 0
    for i in range(len(x_list)):
        if x_list[N -1 - i] == 1:
            sum_x += 2 ** i

    for i in range(len(x_list)):
        current_sum_x = 0
        current_one_count = 0
        if x_list[i] == 0:
            current_one_count = one_count + 1
            current_sum_x = sum_x + 2 ** (N - 1 - i)
        else:
            current_one_count = one_count - 1
            current_sum_x = sum_x - 2 ** (N - 1 - i)
        do_count = saiki(current_sum_x,current_one_count,0)
        print(do_count)
    return


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
#DEBUG=True
DEBUG=False
if DEBUG:
    f=open("202007_2nd/D_input.txt")
else:
    f=sys.stdin
#from 2nd count
def cnt_func(num):
    cnt=0
    while num:
        num%=bin(num).count("1")
        cnt+=1
    return cnt+1
n=int(f.readline().strip())
s=f.readline().strip()
input_val=int(s,2)
input_one_count=s.count("1")
#Base value
zero_first=input_val%(input_one_count+1)
one_first=input_val%(input_one_count-1) if input_one_count>1 else 0
ans=0
for idx,emt in enumerate(s):
    p=n-idx-1
    if emt=="0": #inverted to "1"
        ans=cnt_func((zero_first+(pow(2,p,input_one_count+1)))%(input_one_count+1))
    else: #inverted to "2"
        ans=cnt_func((one_first-(pow(2,p,input_one_count-1)))%(input_one_count-1))
    print(ans)
f.close()

Submission status: Runtime Error

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

def popcount(n):
    return n.count("1")

def popcount2(n):
    ans = 0
    while n:
        ans += n % 2
        n //= 2
    return ans

pops = popcount(x)
x_pop_p = x%(pops + 1)
try:
    x_pop_m = x%(pops - 1)
except:
    x_pop_m = 0
for i in reversed(range(0,n)):
    bit = x^(1<<i)
    if bit == 0:
        print(0)
        continue
    if x&(1<<i):
        tmp = (x_pop_m - pow(2,i,(pops - 1)))%(pops - 1)
    else:
        tmp = (x_pop_p + pow(2,i,(pops + 1))) % (pops + 1)
    if tmp == 0:
        print(1)
        continue
    cnt = 2
    tmp %= popcount(tmp)
    while tmp > 0:
        cnt += 1
        if tmp == 0:
            print(cnt-1)
            continue
        tmp %= popcount(tmp)
    print(cnt)

Submission status: Runtime Error

Solution code:

import sys
import copy

import numpy as np
sys.setrecursionlimit(1000000000)


def main():
    n = int(input())
    X = list(input())

    def popcount(n: int) -> int:
        return list(f'{n:b}').count('1')

    ppcs = np.full(int('1'*n, 2) + 1, -1)
    ppcs[0:2] = [0, 1]

    for i in range(n):
        x = copy.deepcopy(X)
        if x[i] == '1':
            x[i] = '0'
        else:
            x[i] = '1'

        cnt = 0
        val = int("".join(x), 2)
        defval = val
        while True:
            if ppcs[val] >= 0:
                cnt += ppcs[val]
                ppcs[defval] = cnt
                break
            else:
                val = val % popcount(val)
                cnt += 1
        print(cnt)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n):
  res = [None] * n
  for i in range(n):
    res[i] = II()
  return res
def LIR(n):
  res = [None] * n
  for i in range(n):
    res[i] = LI()
  return res
def FR(n):
  res = [None] * n
  for i in range(n):
    res[i] = IF()
  return res
def LIR(n):
  res = [None] * n
  for i in range(n):
    res[i] = IF()
  return res
def LIR_(n):
  res = [None] * n
  for i in range(n):
    res[i] = LI_()
  return res
def SR(n):
  res = [None] * n
  for i in range(n):
    res[i] = S()
  return res
def LSR(n):
  res = [None] * n
  for i in range(n):
    res[i] = LS()
  return res
mod = 1000000007
inf = float('INF')

#solve
def solve():
  def f(n, c):
    tmp = n % c
    t = tmp
    b = 0
    while tmp:
      if tmp & 1:
        b += 1
      tmp //= 2
    if t:
      return f(t, b) + 1
    else:
      return 1
  n = II()
  a = S()
  b = 0
  for ai in a:
    if ai == "1":
      b += 1
  a = a[::-1]
  bp = 0
  bm = 0
  if b != 1:
    for i, ai in enumerate(a):
      if ai == "1":
        bp += pow(2, i, b + 1)
        bm += pow(2, i, b - 1)
        bp %= b + 1
        bm %= b - 1
    ans = []
    for i, ai in enumerate(a):
      if ai == "1":
        tmpbm = bm - pow(2, i, b - 1)
        tmpbm %= b - 1
        ans.append(f(tmpbm, b - 1))
      else:
        tmpbp = bp + pow(2, i, b + 1)
        tmpbp %= b + 1
        ans.append(f(tmpbp, b + 1))
    for ai in ans[::-1]:
      print(ai)
    return
  else:
    raise EnvironmentError
    for i, ai in enumerate(a):
      if ai == "1":
        bp += pow(2, i, b + 1)
        bp %= b + 1
    ans = []
    for i, ai in enumerate(a):
        tmpbp = bp + pow(2, i, b + 1)
        tmpbp %= b + 1
        ans.append(f(tmpbp, b + 1))
    for ai in ans[::-1]:
      print(ai)
    return


#main
if __name__ == '__main__':
  solve()

Submission status: Runtime Error

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


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

    X_int = int(X, 2)

    pcount_X = popcount(X_int)

    pcount_X_pls1 = pcount_X + 1
    pcount_X_mns1 = pcount_X - 1
    
    X_pls1_mod = X_int % pcount_X_pls1
    X_mns1_mod = X_int % pcount_X_mns1

    for i,bit in enumerate(X):
        bit = int(bit)
        if bit == 0:
            pcount_Xi = pcount_X_pls1
        else:
            pcount_Xi = pcount_X_mns1
            if pcount_Xi == 0:
                print(0)
                continue

        if bit == 0:
            n = (X_pls1_mod + pow(2, N-i-1, pcount_Xi)) % pcount_Xi
        else:
            n = (X_mns1_mod - pow(2, N-i-1, pcount_Xi)) % pcount_Xi

        ans = 1
        while n > 0:
            ans += 1
            n %= popcount(n)
        print(ans)
        
main()

Submission status: Runtime Error

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

fn = dict()

def f(n, count):
    if n in fn:
        # print('exist')
        return fn[n]
    # binary = bin(n)[2:]
    pop = bin(n).count('1')
    # for b in binary:
    #     if b == '1':
    #         pop += 1
    if n == 0:
        return 0
    count += 1
    if n%pop == 0:
        fn[n] = 1
        return count
    else:
        # print(n ,count, n%pop)
        # if n%pop in fn:
        #     print('exist')
        #     return fn[n%pop]
        # else:
        x = f(n%pop, count)
        # fn[n%pop] = x- count
        fn[n] = x
        return x

popcount = X.count('1')
f_1 = int(X, 2)%(popcount+1)
if popcount == 1:
    f_0 = 0
else:
    f_0 = int(X, 2)%(popcount-1)
# print(int(X, 2), f_1, f_0)

for i in range(N):
    # X_i = X[:]
    diff = 0
    d = N-1 -i
    if X[i] == '1':
        if popcount-1 == 0:
            ans = 0
        else:
            diff = pow(2, d)%(popcount-1)
            n = int(X,2)-pow(2, d)
            # print(i,d,  popcount-1, f_0, diff)
            ans = f((f_0-diff)%(popcount-1), 0) +1
            # X[i] = '0'
    else:
        diff = pow(2, d)%(popcount+1)
        n = int(X,2)+pow(2, d)

        # print(i,d,  pow(2, d), popcount+1, f_1, diff)
        ans = f((f_1+diff)%(popcount+1), 0) +1
        # X[i] = '1'
    # X_i = ''.join(X_i)
    # n = int(X_i, 2)
    # if n == 0:
    #     ans = 0
    # else:
    #     ans = f(n, 0)
    fn[n] = ans
    print(ans)
    # print(fn)
# print(fn)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n):
  res = [None] * n
  for i in range(n):
    res[i] = II()
  return res
def LIR(n):
  res = [None] * n
  for i in range(n):
    res[i] = LI()
  return res
def FR(n):
  res = [None] * n
  for i in range(n):
    res[i] = IF()
  return res
def LIR(n):
  res = [None] * n
  for i in range(n):
    res[i] = IF()
  return res
def LIR_(n):
  res = [None] * n
  for i in range(n):
    res[i] = LI_()
  return res
def SR(n):
  res = [None] * n
  for i in range(n):
    res[i] = S()
  return res
def LSR(n):
  res = [None] * n
  for i in range(n):
    res[i] = LS()
  return res
mod = 1000000007
inf = float('INF')

#solve
def solve():
  def f(n, c):
    tmp = n % c
    t = tmp
    b = 0
    while tmp:
      if tmp & 1:
        b += 1
      tmp //= 2
    if t:
      return f(t, b) + 1
    else:
      return 1
  n = II()
  a = S()
  b = 0
  for ai in a:
    if ai == "1":
      b += 1
  a = a[::-1]
  bp = 0
  bm = 0
  for i, ai in enumerate(a):
    if ai == "1":
      bp += pow(2, i, b + 1)
      bm += pow(2, i, b - 1)
      bp %= b + 1
      bm %= b - 1
  ans = []
  for i, ai in enumerate(a):
    if ai == "1":
      tmpbm = bm - pow(2, i, b - 1)
      tmpbm %= b - 1
      ans.append(f(tmpbm, b - 1))
    else:
      tmpbp = bp + pow(2, i, b + 1)
      tmpbp %= b + 1
      ans.append(f(tmpbp, b + 1))
  for ai in ans[::-1]:
    print(ai)
  return


#main
if __name__ == '__main__':
  solve()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n):
  res = [None] * n
  for i in range(n):
    res[i] = II()
  return res
def LIR(n):
  res = [None] * n
  for i in range(n):
    res[i] = LI()
  return res
def FR(n):
  res = [None] * n
  for i in range(n):
    res[i] = IF()
  return res
def LIR(n):
  res = [None] * n
  for i in range(n):
    res[i] = IF()
  return res
def LIR_(n):
  res = [None] * n
  for i in range(n):
    res[i] = LI_()
  return res
def SR(n):
  res = [None] * n
  for i in range(n):
    res[i] = S()
  return res
def LSR(n):
  res = [None] * n
  for i in range(n):
    res[i] = LS()
  return res
mod = 1000000007
inf = float('INF')

#solve
def solve():
  def f(n, c):
    tmp = n % c
    t = tmp
    b = 0
    while tmp:
      if tmp & 1:
        b += 1
      tmp //= 2
    if t:
      return f(t, b) + 1
    else:
      return 1
  n = II()
  a = S()
  b = 0
  for ai in a:
    if ai == "1":
      b += 1
  a = a[::-1]
  bp = 0
  bm = 0
  for i, ai in enumerate(a):
    if ai == "1":
      bp += pow(2, i, b + 1)
      bm += pow(2, i, b - 1)
      bp %= b + 1
      bm %= b - 1
      print(bp, bm)
  ans = []
  for i, ai in enumerate(a):
    if ai == "1":
      tmpbm = bm - pow(2, i, b - 1)
      tmpbm %= b - 1
      ans.append(f(tmpbm, b - 1))
    else:
      tmpbp = bp + pow(2, i, b + 1)
      tmpbp %= b + 1
      ans.append(f(tmpbp, b + 1))
  for ai in ans[::-1]:
    print(ai)
  return


#main
if __name__ == '__main__':
  solve()

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

n=int(input())
xs=input()
xj=xs.count("1")

x=int(xs,2)
xip=x%(xj+1)
if xj!=0:
    xim=x%(xj-1)

i1=1<<n
for i in range(n-1,-1,-1):
    i1=i1>>1
    xi=x^i1
    if xi==0:
        print(0)
        continue
    if xs[n-1-i]=="0":
        pxi=xj+1
        xi=(xip+i1%pxi)%pxi
    elif xj==1:
        print(0)
        continue
    else:
        pxi=xj-1
        xi=(xim-i1%pxi)%pxi
    xi=xi%pxi
    if xi==0:
        print(1)
        continue
    icnt=1
    while xi>0:
#        print("i",i,"xi",xi,"icnt",icnt)
        icnt+=1
        xi=xi%(bin(xi).count("1"))
    print(icnt)

Submission status: Runtime Error

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

fn = dict()

def f(n, count):
    # binary = bin(n)[2:]
    pop = bin(n).count('1')
    # for b in binary:
    #     if b == '1':
    #         pop += 1
    if n == 0:
        return 0
    count += 1
    if n%pop == 0:
        return count
    else:
        # print(n ,count, n%pop)
        if n%pop in fn:
            # print('exist')
            return fn[n%pop]
        else:
            x = f(n%pop, count)
            fn[n%pop] = x- count
            fn[n] = x
            return x

popcount = X.count('1')
f_1 = int(X, 2)%(popcount+1)
f_0 = int(X, 2)%(popcount-1)
# print(int(X, 2), f_1, f_0)

for i in range(N):
    # X_i = X[:]
    diff = 0
    d = N-1 -i
    if X[i] == '1':
        if popcount-1 == 0:
            ans = 0
        else:
            diff = pow(2, d)%(popcount-1)
            # print(i,d,  popcount-1, f_0, diff)
            ans = f((f_0-diff)%(popcount-1), 0) +1
            # X[i] = '0'
    else:
        diff = pow(2, d)%(popcount+1)
        # print(i,d,  pow(2, d), popcount+1, f_1, diff)
        ans = f((f_1+diff)%(popcount+1), 0) +1
        # X[i] = '1'
    # X_i = ''.join(X_i)
    # n = int(X_i, 2)
    # if n == 0:
    #     ans = 0
    # else:
    #     ans = f(n, 0)
    # fn[n] = ans
    print(ans)
    # print(fn)
# print(fn)

Submission status: Runtime Error

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

fn = dict()

def f(n, count):
    # binary = bin(n)[2:]
    pop = bin(n).count('1')
    # for b in binary:
    #     if b == '1':
    #         pop += 1
    if n == 0 or pop == 0:
        return 0
    count += 1
    if n%pop == 0:
        return count
    else:
        # print(n ,count, n%pop)
        if n%pop in fn:
            # print('exist')
            return fn[n%pop]
        else:
            x = f(n%pop, count)
            fn[n%pop] = x- count
            fn[n] = x
            return x

popcount = X.count('1')
f_1 = int(X, 2)%(popcount+1)
f_0 = int(X, 2)%(popcount-1)
# print(int(X, 2), f_1, f_0)

for i in range(N):
    # X_i = X[:]
    diff = 0
    d = N-1 -i
    if X[i] == '1':
        diff = pow(2, d)%(popcount-1)
        # print(i,d,  popcount-1, f_0, diff)
        ans = f((f_0-diff)%(popcount-1), 0) +1
        # X[i] = '0'
    else:
        diff = pow(2, d)%(popcount+1)
        # print(i,d,  pow(2, d), popcount+1, f_1, diff)
        ans = f((f_1+diff)%(popcount+1), 0) +1
        # X[i] = '1'
    # X_i = ''.join(X_i)
    # n = int(X_i, 2)
    # if n == 0:
    #     ans = 0
    # else:
    #     ans = f(n, 0)
    # fn[n] = ans
    print(ans)
    # print(fn)
# print(fn)

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
#from collections import deque

def sum_count(arr):
    mem = arr[:]
    while True:
        if len(mem) == 1:break
        tmp = []
        while True:
            if len(mem) == 1:
                tmp.append(mem[-1])
                mem = tmp[:]
                break
            if len(mem) == 0:
                mem = tmp[:]
                break
            x1, x2 = mem.pop(), mem.pop()
            tmp.append(int(x1) + int(x2))

    return int(mem[0])

def run():
    N = int(input())
    X = list(input())[::-1]
    lis_bf = []
    lis_af = []
    count1 = sum_count(X)
    sum_val_bf, sum_val_af = 0, 0
    if count1 <= 1:
        for i in range(N):
            tmp_af = 0, 0
            if int(X[i]):
                tmp_af = pow(2, i, count1 + 1)
            lis_af.append(tmp_af)
            sum_val_af += tmp_af
            sum_val_af %= count1 + 1

        for i in list(range(N))[::-1]:
            ans = 0
            if X[i] == '1':
                print(0)
                continue
            else:
                next_val = (sum_val_af + pow(2, i, count1 + 1)) % (count1 + 1)
            # print(next_val)
            ans += 1
            # print(f'i : {i}, next_val : {next_val}')
            while True:
                if next_val == 0: break
                val = next_val
                count_n = sum_count(list(bin(val)[2:]))
                next_val = val % count_n
                ans += 1
                # print(f'next_val : {next_val}')
            print(ans)
        return None

    for i in range(N):
        tmp_bf, tmp_af = 0,0
        if int(X[i]):
            tmp_bf = pow(2, i , count1-1)
            tmp_af = pow(2, i, count1+1)
        lis_bf.append(tmp_bf)
        lis_af.append(tmp_af)
        sum_val_bf += tmp_bf
        sum_val_bf %= count1-1
        sum_val_af += tmp_af
        sum_val_af %= count1 + 1

    for i in list(range(N))[::-1]:
        ans = 0
        if X[i] == '1':
            next_val = (sum_val_bf - lis_bf[i]) % (count1-1)
        else:
            next_val = (sum_val_af + pow(2, i, count1+1)) % (count1+1)
        #print(next_val)
        ans += 1
        #print(f'i : {i}, next_val : {next_val}')
        while True:
            if next_val == 0:break
            val = next_val
            count_n = sum_count(list(bin(val)[2:]))
            next_val = val % count_n
            ans += 1
            #print(f'next_val : {next_val}')
        print(ans)


if __name__ == "__main__":
    run()

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

n=int(input())
xs=input()
xj=xs.count("1")

x=int(xs,2)
xip=x%(xj+1)
xim=x%(xj-1)

i1=1<<n
for i in range(n-1,-1,-1):
    i1=i1>>1
    xi=x^i1
    if xi==0:
        print(0)
        continue
    if xs[n-1-i]=="0":
        pxi=xj+1
#        xi=(xip+i1%pxi)%pxi
#        xi=(xip+i1)%pxi
    else:
        pxi=xj-1
#        xi=(xim-i1%pxi)%pxi
#        xi=(xim-i1)%pxi
    xi=xi%pxi
    if xi==0:
        print(1)
        continue
    icnt=1
    while xi>0:
#        print("i",i,"xi",xi,"icnt",icnt)
        icnt+=1
        xi=xi%(bin(xi).count("1"))
    print(icnt)

Submission status: Runtime Error

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

fn = dict()

def f(n, count):
    # binary = bin(n)[2:]
    pop = bin(n).count('1')
    # for b in binary:
    #     if b == '1':
    #         pop += 1
    if n == 0:
        return 0
    count += 1
    if n%pop == 0:
        return count
    else:
        # print(n ,count, n%pop)
        if n%pop in fn:
            # print('exist')
            return fn[n%pop]
        else:
            x = f(n%pop, count)
            fn[n%pop] = x- count
            # fn[n] = x
            return x

popcount = X.count('1')
f_1 = int(X, 2)%(popcount+1)
f_0 = int(X, 2)%(popcount-1)
# print(int(X, 2), f_1, f_0)

for i in range(N):
    # X_i = X[:]
    diff = 0
    d = N-1 -i
    if X[i] == '1':
        diff = pow(2, d)%(popcount-1)
        # print(i,d,  popcount-1, f_0, diff)
        ans = f((f_0-diff)%(popcount-1), 0) +1
        # X[i] = '0'
    else:
        diff = pow(2, d)%(popcount+1)
        # print(i,d,  pow(2, d), popcount+1, f_1, diff)
        ans = f((f_1+diff)%(popcount+1), 0) +1
        # X[i] = '1'
    # X_i = ''.join(X_i)
    # n = int(X_i, 2)
    # if n == 0:
    #     ans = 0
    # else:
    #     ans = f(n, 0)
    # fn[n] = ans
    print(ans)
    # print(fn)
# print(fn)