Problem:


Score : 400 points

Problem Statement

Let \mathrm{popcount}(n) be the number of 1s in the binary representation of n.
For example, \mathrm{popcount}(3) = 2, \mathrm{popcount}(7) = 3, and \mathrm{popcount}(0) = 0.

Let f(n) be the number of times the following operation will be done when we repeat it until n becomes 0: "replace n with the remainder when n is divided by \mathrm{popcount}(n)." (It can be proved that, under the constraints of this problem, n always becomes 0 after a finite number of operations.)

For example, when n=7, it becomes 0 after two operations, as follows:

\mathrm{popcount}(7)=3, so we divide 7 by 3 and replace it with the remainder, 1.

\mathrm{popcount}(1)=1, so we divide 1 by 1 and replace it with the remainder, 0.

You are given an integer X with N digits in binary.
For each integer i such that 1 \leq i \leq N, let X_i be what X becomes when the i-th bit from the top is inverted.
Find f(X_1), f(X_2), \ldots, f(X_N).

Constraints

1 \leq N \leq 2 \times 10^5

X is an integer with N digits in binary, possibly with leading zeros.

Input

Input is given from Standard Input in the following format:

N
X

Output

Print N lines. The i-th line should contain the value f(X_i).

Sample Input 1

3
011

Sample Output 1

2
1
1

X_1 = 7, which will change as follows: 7 \rightarrow 1 \rightarrow 0. Thus, f(7) = 2.

X_2 = 1, which will change as follows: 1 \rightarrow 0. Thus, f(1) = 1.

X_3 = 2, which will change as follows: 2 \rightarrow 0. Thus, f(2) = 1.

Sample Input 2

23
00110111001011011001110

Sample Output 2

2
1
2
2
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
3



Sample input:
3
011


Sample output:
2
1
1

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)


def solve(N: int, X: str):
    memo = {}
    def popcount(v):
        if v == 0:
            return 0
        if v in memo:
            return memo[v]
        tmp, b = v, 0
        while tmp > 0:
            b += tmp % 2
            tmp //= 2
        if v % b == 0:
            memo[v] = 1
            return 1
        memo[v] = 1 + popcount(v % b)
        return memo[v]
    X = X[::-1]
    bits = 0
    for i in range(N):
        if X[i] == '1':
            bits += 1

    sums = [0, 0]
    for i in range(N):
        if X[i] == '1':
            sums[0] += pow(2, i, bits - 1)
            sums[0] %= bits - 1
            sums[1] += pow(2, i, bits + 1)
            sums[1] %= bits + 1

    #print(bits, sums)
    ret = []
    for i, x in enumerate(X):
        if x == '1':
            v = (sums[0] - (1 << i)) % (bits - 1)
        else:
            v = (sums[1] + (1 << i)) % (bits + 1)
        #print(i, x, v)
        ret.append(1 + popcount(v))

    ret.reverse()
    for r in ret:
        print(r)
    return


def solve_(N: int, X: str):
    #memo = [[-1] * 20 for _ in range(20)]
    memo = {}
    def popcount(v, b):
        if v in memo and b in memo[v]:
            return memo[v][b]
        if not v in memo:
            memo[v] = {}
        if v % b == 0:
            memo[v][b] = 1
            return 1
        next_v = v % b
        tmp = next_v
        c = 0
        while tmp > 0:
            c += tmp % 2
            tmp //= 2
        ret = 1 + popcount(next_v, c)
        memo[v][b] = ret
        return ret

    X = X[::-1]
    count = 0
    for i in range(N):
        if X[i] == '1':
            count += 1

    s = 0
    for i in range(N):
        if X[i] == '1':
            s += pow(2, i, count)
            s %= count

    memo[count] = {}
    memo[count]
    ret = []
    for i, x in enumerate(X):
        if x == '1':
            v = N - (1 << i)
            b = count - 1
        else:
            v = N + (1 << i)
            b = count + 1
        print(i, i, x)
        print(v, b)
        ret.append(popcount(v, b))
    ret.reverse()
    for r in ret:
        print(r)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = next(tokens)  # type: str
    solve(N, X)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

n = int(input())
x = input()
z = '1' * n
o = '0' * n
X = int(x, 2)

if (z == x):
  u = n - 1
  d = n - 1
elif (o == x):
  u = 1
  d = 1
else:
  tmp = len(list(filter(lambda x: x == '1', x)))
  u = tmp + 1
  d = tmp - 1


def popcount(i):
  return i % len(list(filter(lambda x: x == '1', format(i, 'b'))))


def solve(i, count):
  if (i <= 2 * 10**5 and ans[i] != 0):
    return count + ans[i]
  elif (i == 0):
    return count
  else:
    return solve(popcount(i), count + 1)


def solve2(i, div):
  if (i <= 2 * 10**5):
    return ans[i]
  else:
    return ans[i % div] + 1


ans = [0] * (2 * 10 ** 5 + 1)
_u = (2 * 10 ** 5) // u
U = X % u + (u * _u) + u
_d = (2 * 10 ** 5) // d
D = X % d + (d * _d) * 2 + d * 2
Us = [0] * (2 * 10 ** 5)
Ds = [0] * (2 * 10 ** 5)
for i in range(1, 2 * 10 ** 5 + 4):
  ans[i] = solve(i, 0)
  
Us[0] = 1 % u
Ds[0] = 1 % d
for i in range(1, 2 * 10 ** 5):
  Us[i] = (Us[i-1] * 2) % u
  Ds[i] = (Ds[i-1] * 2) % d

for i in range(n):
  if(X <= 2 * 10 ** 5 + 1):
    if(x[i] == '0'):
      print(solve2(X + 2 ** (n - i - 1), u))
    else:
      if (d == 0):
        print(0)
      else:
        print(solve2(X - 2 ** (n - i - 1), d))
  else:
    if(x[i] == '0'):
      print(solve2(U + Us[n-i-1], u))
    else:
      if (d == 0):
        print(0)
      else:
        print(solve2(D - Ds[n-i-1], d))

Submission status: Runtime Error

Solution code:
def popcnt(x):
    return bin(x).count("1")


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


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

cnt = popcnt(int(arr, 2))
init_big = int(arr, 2) % (cnt + 1)
init_small = int(arr, 2) % (cnt - 1)

li = []
for i in range(n):
    if arr[i] == "0":
        li.append((init_big + (1 << (n - i - 1))) % (cnt + 1))
    else:
        li.append((init_small - (1 << (n - i - 1))) % (cnt - 1))


ans = []

for x in li:
    ans.append(rec(x) + 1)

if int(arr, 2) == 1:
    ans[-1] = 0

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

Submission status: Runtime Error

Solution code:
from collections import Counter

N = int(input())
X = input()
cnt = X.count('1')
memo = [0]*(N+1)
memo2 = [[0]*(N+1) for _ in range(2)]
memo2[0][1] = memo2[1][1] = 1

if cnt == 0:
  for _ in range(N):
    print(1)
  exit()

for i in range(1,N+1):
  if i == 1:
    memo2[0][i] = 1 % (cnt-1)
    memo2[1][i] = 1 % (cnt+1)
  else:
    memo2[0][i] = memo2[0][i-1]*2 % (cnt-1)
    memo2[1][i] = memo2[1][i-1]*2 % (cnt+1)
  t = 0
  a = i
  while a > 0:
    b = bin(a).count('1')
    a %= b
    t += 1
  memo[i] = t
  
X1 = 0
X_1 = 0
for i in range(1,N+1):
  if X[N-i] == '1':
    X1 += memo2[1][i]
    X_1 += memo2[0][i]
    X1 %= cnt+1
    X_1 %= cnt-1
    
for i in range(N,0,-1):
  Y = 0
  if X[N-i] == '1':
    Y = X_1 - memo2[0][i]
    if Y < 0:
      Y += cnt - 1
    print(memo[Y]+1)
  else:
    Y = X1 + memo2[1][i]
    Y %= cnt + 1
    print(memo[Y]+1)

Submission status: Runtime Error

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

n = int(input())
x = input()
z = '1' * n
o = '0' * n
X = int(x, 2)

if (z == x):
  u = n - 1
  d = n - 1
elif (o == x):
  u = 1
  d = 1
else:
  tmp = len(list(filter(lambda x: x == '1', x)))
  u = tmp + 1
  d = tmp - 1


def popcount(i):
  return i % len(list(filter(lambda x: x == '1', format(i, 'b'))))


def solve(i, count):
  if (i <= 2 * 10**5 and ans[i] != 0):
    return count + ans[i]
  elif (i == 0):
    return count
  else:
    return solve(popcount(i), count + 1)


def solve2(i, div):
  if (i <= 2 * 10**5):
    return ans[i]
  else:
    return ans[i % div] + 1


ans = [0] * (2 * 10 ** 5 + 1)
_u = (2 * 10 ** 5) // u
U = X % u + (u * _u) + u
_d = (2 * 10 ** 5) // d
D = X % d + (d * _d) * 2 + d * 2
Us = [0] * (2 * 10 ** 5)
Ds = [0] * (2 * 10 ** 5)
for i in range(1, 2 * 10 ** 5 + 1):
  ans[i] = solve(i, 0)
  
Us[0] = 1 % u
Ds[0] = 1 % d
for i in range(1, 2 * 10 ** 5):
  Us[i] = (Us[i-1] * 2) % u
  Ds[i] = (Ds[i-1] * 2) % d

for i in range(n):
  if(X <= 2 * 10 ** 5 + 1):
    if(x[i] == '0'):
      print(solve2(X + 2 ** (n - i - 1), u))
    else:
      if (d == 0):
        print(0)
      else:
        print(solve2(X - 2 ** (n - i - 1), d))
  else:
    if(x[i] == '0'):
      print(solve2(U + Us[n-i-1], u))
    else:
      if (d == 0):
        print(0)
      else:
        print(solve2(D - Ds[n-i-1], d))

Submission status: Runtime Error

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()


N=int(input())
X=input()
C=X.count("1")

lst=[]
for x in [C-1,C+1]:

    if C<=0:
        lst.append(-1)
    else:
        Z=0
        p=1
        for i in range(N):
            if X[-i-1]=="1":
                Z+=p
            p*=2
            p%=x
            Z%=x
        lst.append(Z)

#print(lst)
fac1=[1]
fac2=[1]
C1=C-1
C2=C+1
for i in range(N):
    fac1.append(fac1[-1]*2%C1)
    fac2.append(fac2[-1]*2%C2)

for i in range(N):

    _C=C+(1 if X[i]=="0"  else -1 )
    if  X[i]=="0":
        lstidx=1
    else:
        lstidx=0

    idx=(N-1-i)

    value=lst[lstidx]+(fac2[idx] if  X[i]=="0" else fac1[idx])
    #print(lst[lstidx],value)
    count=0
    while value:
        count+=1
        value%=_C
        _C=0
        bit=value
        while bit:
            _C+=bit&1
            bit>>=1
    print(max(count,1))

Submission status: Runtime Error

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()


N=int(input())
X=input()
C=X.count("1")

lst=[]
for x in [C-1,C+1]:

    if C<=0:
        lst.append(-1)
    else:
        Z=0
        p=1
        for i in range(N):
            if X[-i-1]=="1":
                Z+=p
            p*=2
            Z%=x
        lst.append(Z)

#print(lst)
fac1=[1]
fac2=[1]
C1=C-1
C2=C+1
for i in range(N):
    fac1.append(fac1[-1]*2%C1)
    fac2.append(fac2[-1]*2%C2)

for i in range(N):

    _C=C+(1 if X[i]=="0"  else -1 )
    if  X[i]=="0":
        lstidx=1
    else:
        lstidx=0

    idx=(N-1-i)

    value=lst[lstidx]+(fac2[idx] if  X[i]=="0" else fac1[idx])
    #print(lst[lstidx],value)
    count=0
    while value:
        count+=1
        value%=_C
        _C=0
        bit=value
        while bit:
            _C+=bit&1
            bit>>=1
    print(max(count,1))

Submission status: Runtime Error

Solution code:
# coding: utf-8
from collections import defaultdict, deque


def popcount(x):
    x -= (x >> 1) & 0x55555555
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f
    x += x >> 8
    x += x >> 16
    return x & 0x3f


def solve(*args: str) -> str:
    n = int(args[0])
    x = args[1]

    ret = []
    dp = defaultdict(int)
    x_count = x.count('1')
    x_dec = int(x, 2)

    x_mod_set = x_dec % (x_count+1)
    x_mod_reset = x_dec % (x_count-1)
    xor_set = 1 % (x_count+1)
    xor_reset = 1 % (x_count-1)
    for i in range(n):
        bitcount = x_count + (1 if x[-1-i] == '0' else -1)
        if bitcount == 0:
            ret.append(0)
            continue

        m = (x_mod_set + xor_set
             if x[-1-i] == '0' else
             x_mod_reset - xor_reset) % bitcount
        deq = deque([m])

        count = 1
        while m:
            deq.append(m)
            if 0 < dp[m]:
                count += dp[m]
                break

            m = m % popcount(m)
            count += 1

        ret.append(str(count))

        while deq:
            dp[deq.popleft()] = count
            count -= 1

        xor_set = (xor_set << 1) % (x_count+1)
        xor_reset = (xor_reset << 1) % (x_count-1)

    return '\n'.join(ret[::-1])


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Runtime Error

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

n = int(input())
x = input()
z = '1' * n
o = '0' * n
X = int(x, 2)

if (z == x):
  u = n - 1
  d = n - 1
elif (o == x):
  u = 1
  d = 1
else:
  tmp = len(list(filter(lambda x: x == '1', x)))
  u = tmp + 1
  d = tmp - 1


def popcount(i):
  return i % len(list(filter(lambda x: x == '1', format(i, 'b'))))


def solve(i, count):
  if (i <= 2 * 10**5 and ans[i] != 0):
    return count + ans[i]
  elif (i == 0):
    return count
  else:
    return solve(popcount(i), count + 1)


def solve2(i, div):
  if (i <= 2 * 10**5):
    return ans[i]
  else:
    return ans[i % div] + 1


ans = [0] * (2 * 10 ** 5 + 1)
_u = (2 * 10 ** 5) // u
U = X % u + (u * _u) + u
_d = (2 * 10 ** 5) // d
D = X % d + (d * _d) * 2 + d * 2
Us = [0] * (2 * 10 ** 5)
Ds = [0] * (2 * 10 ** 5)
for i in range(1, 2 * 10 ** 5 + 1):
  ans[i] = solve(i, 0)
  
Us[0] = 1 % u
Ds[0] = 1 % d
for i in range(1, 2 * 10 ** 5):
  Us[i] = (Us[i-1] * 2) % u
  Ds[i] = (Ds[i-1] * 2) % d

for i in range(n):
  if(X <= 2 * 10 ** 5 + 1):
    if(x[i] == '0'):
      print(solve2(X + 2 ** (n - i - 1), u))
    else:
      print(solve2(X - 2 ** (n - i - 1), d))
  else:
    if(x[i] == '0'):
      print(solve2(U + Us[n-i-1], u))
    else:
      print(solve2(D - Ds[n-i-1], d))

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
    v=N%b
    return pop_num(v,L[v],L)+1
    
M=[0]*200005
for i in range(1,200005):
    M[i]+=pop_num(i,L[i],L)
X=int(input())
Y=input()
d=bin_sum2(Y)+1
c=bin_sum2(Y)-1
e=int(Y,2)%d
f=int(Y,2)%c
for i in range(X):
    if Y[i]=="0":
        b=d
        g=(e+2**(X-1-i))%d
    else:
        b=c
        g=(f-2**(X-1-i)%c+c)%c
    if d==1:
        print(0)
    elif g==0:
        print(1)
    else:
        print(M[g]+1)

Submission status: Runtime Error

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

n = int(input())
x = input()
z = '1' * n
o = '0' * n
X = int(x, 2)

if (z == x):
  u = n - 1
  d = n - 1
elif (o == x):
  u = 1
  d = 1
else:
  tmp = len(list(filter(lambda x: x == '1', x)))
  u = tmp + 1
  d = tmp - 1


def popcount(i):
  return i % len(list(filter(lambda x: x == '1', format(i, 'b'))))


def solve(i, count):
  if (i <= 2 * 10**5 and ans[i] != 0):
    return count + ans[i]
  elif (i == 0):
    return count
  else:
    return solve(popcount(i), count + 1)


def solve2(i, div):
  if (i <= 2 * 10**5):
    return ans[i]
  else:
    return ans[i % div] + 1


ans = [0] * (2 * 10 ** 5 + 1)
_u = (2 * 10 ** 5) // u
U = X % u + (u * _u) + u
_d = (2 * 10 ** 5) // d
D = X % d + (d * _d) + d * 2
Us = [0] * (2 * 10 ** 5)
Ds = [0] * (2 * 10 ** 5)
for i in range(1, 2 * 10 ** 5 + 1):
  ans[i] = solve(i, 0)
  
Us[0] = 1 % u
Ds[0] = 1 % d
for i in range(1, 2 * 10 ** 5):
  Us[i] = (Us[i-1] * 2) % u
  Ds[i] = (Ds[i-1] * 2) % d

for i in range(n):
  if(X <= 2 * 10 ** 5 + 1):
    if(x[i] == '0'):
      print(solve2(X + 2 ** (n - i - 1), u))
    else:
      print(solve2(X - 2 ** (n - i - 1), d))
  else:
    if(x[i] == '0'):
      print(solve2(U + Us[n-i-1], u))
    else:
      print(solve2(D - Ds[n-i-1], d))

Submission status: Runtime Error

Solution code:
# coding: utf-8
from collections import defaultdict, deque


def popcount(x):
    assert x.bit_length() <= 32
    x -= (x >> 1) & 0x55555555
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f
    x += x >> 8
    x += x >> 16
    return x & 0x3f


def solve(*args: str) -> str:
    n = int(args[0])
    x = args[1]

    ret = []
    dp = defaultdict(int)
    x_count = x.count('1')
    x_dec = int(x, 2)

    x_mod_set = x_dec % (x_count+1)
    x_mod_reset = x_dec % (x_count-1)
    xor_set = 1 % (x_count+1)
    xor_reset = 1 % (x_count-1)
    for i in range(n):
        bitcount = x_count + (1 if x[-1-i] == '0' else -1)
        if bitcount == 0:
            ret.append(0)
            continue

        m = (x_mod_set + xor_set
             if x[-1-i] == '0' else
             x_mod_reset - xor_reset) % bitcount
        deq = deque([m])

        count = 1
        while m:
            deq.append(m)
            if 0 < dp[m]:
                count += dp[m]
                break

            m = m % popcount(m)
            count += 1

        ret.append(str(count))

        while deq:
            dp[deq.popleft()] = count
            count -= 1

        xor_set = (xor_set << 1) % (x_count+1)
        xor_reset = (xor_reset << 1) % (x_count-1)

    return '\n'.join(ret[::-1])


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Runtime Error

Solution code:
from collections import Counter

N = int(input())
X = input()
cnt = X.count('1')
memo = [0]*(N+1)
memo2 = [[0]*(N+1) for _ in range(2)]
memo2[0][1] = memo2[1][1] = 1

for i in range(1,N+1):
  if i == 1:
    memo2[0][i] = 1 % (cnt-1)
    memo2[1][i] = 1 % (cnt+1)
  else:
    memo2[0][i] = memo2[0][i-1]*2 % (cnt-1)
    memo2[1][i] = memo2[1][i-1]*2 % (cnt+1)
  t = 0
  a = i
  while a > 0:
    b = bin(a).count('1')
    a %= b
    t += 1
  memo[i] = t
  
X1 = 0
X_1 = 0
for i in range(1,N+1):
  if X[N-i] == '1':
    X1 += memo2[1][i]
    X_1 += memo2[0][i]
    X1 %= cnt+1
    X_1 %= cnt-1
    
for i in range(N,0,-1):
  Y = 0
  if X[N-i] == '1':
    Y = X_1 - memo2[0][i]
    if Y < 0:
      Y += cnt - 1
    print(memo[Y]+1)
  else:
    Y = X1 + memo2[1][i]
    Y %= cnt + 1
    print(memo[Y]+1)

Submission status: Runtime Error

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

n = int(input())
x = input()
z = '1' * n
o = '0' * n
X = int(x, 2)

if (z == x):
  u = n - 1
  d = n - 1
elif (o == x):
  u = 1
  d = 1
else:
  tmp = len(list(filter(lambda x: x == '1', x)))
  u = tmp + 1
  d = tmp - 1


def popcount(i):
  return i % len(list(filter(lambda x: x == '1', format(i, 'b'))))


def solve(i, count):
  if (i <= 2 * 10**5 and ans[i] != 0):
    return count + ans[i]
  elif (i == 0):
    return count
  else:
    return solve(popcount(i), count + 1)


def solve2(i, div):
  if (i <= 2 * 10**5):
    return ans[i]
  else:
    return ans[i % div] + 1


ans = [0] * (2 * 10 ** 5 + 1)
_u = (2 * 10 ** 5) // u
U = X % u + (u * _u) + u
_d = (2 * 10 ** 5) // d
D = X % d + (d * _d) + d
Us = [0] * (2 * 10 ** 5)
Ds = [0] * (2 * 10 ** 5)
for i in range(1, 2 * 10 ** 5 + 1):
  ans[i] = solve(i, 0)
  
Us[0] = 1 % u
Ds[0] = 1 % d
for i in range(1, 2 * 10 ** 5):
  Us[i] = (Us[i-1] * 2) % u
  Ds[i] = (Ds[i-1] * 2) % d

for i in range(n):
  if(X <= 2 * 10 ** 5 + 1):
    if(x[i] == '0'):
      print(solve2(X + 2 ** (n - i - 1), u))
    else:
      print(solve2(X - 2 ** (n - i - 1), d))
  else:
    if(x[i] == '0'):
      print(solve2(U + Us[n-i-1], u))
    else:
      print(solve2(D - Ds[n-i-1], d))

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
    v=N%b
    return pop_num(v,L[v],L)+1
    
M=[0]*200002
for i in range(1,200002):
    M[i]+=pop_num(i,L[i],L)
X=int(input())
Y=input()
d=bin_sum2(Y)+1
c=bin_sum2(Y)-1
e=int(Y,2)%d
f=int(Y,2)%c
for i in range(X):
    if Y[i]=="0":
        b=d
        g=(e+2**(X-1-i))%d
    else:
        b=c
        g=(f-2**(X-1-i)%c+c)%c
        if g<0:
            g+=c
    if d==1:
        print(0)
    elif g==0:
        print(1)
    else:
        print(M[g]+1)

Submission status: Runtime Error

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

n = int(input())
x = input()
z = '1' * n
o = '0' * n
X = int(x, 2)

if (z == x):
  u = n - 1
  d = n - 1
elif (o == x):
  u = 1
  d = 1
else:
  tmp = len(list(filter(lambda x: x == '1', x)))
  u = tmp + 1
  d = tmp - 1


def popcount(i):
  return i % len(list(filter(lambda x: x == '1', format(i, 'b'))))


def solve(i, count):
  if (i <= 2 * 10**5 and ans[i] != 0):
    return count + ans[i]
  elif (i == 0):
    return count
  else:
    return solve(popcount(i), count + 1)


def solve2(i, div):
  if (i <= 2 * 10**5):
    return ans[i]
  else:
    return ans[i % div] + 1


ans = [0] * (2 * 10 ** 5 + 1)
_u = (2 * 10 ** 5) // u
U = X % u + (u * _u) + u
_d = (2 * 10 ** 5) // d
D = X % d + (d * _d) * d
Us = [0] * (2 * 10 ** 5)
Ds = [0] * (2 * 10 ** 5)
for i in range(1, 2 * 10 ** 5 + 1):
  ans[i] = solve(i, 0)
  
Us[0] = 1 % u
Ds[0] = 1 % d
for i in range(1, 2 * 10 ** 5):
  Us[i] = (Us[i-1] * 2) % u
  Ds[i] = (Ds[i-1] * 2) % d

for i in range(n):
  if(X <= 2 * 10 ** 5 + 1):
    if(x[i] == '0'):
      print(solve2(X + 2 ** (n - i - 1), u))
    else:
      print(solve2(X - 2 ** (n - i - 1), d))
  else:
    if(x[i] == '0'):
      print(solve2(U + Us[n-i-1], u))
    else:
      print(solve2(D - Ds[n-i-1], d))

Submission status: Runtime Error

Solution code:
from numba import njit

#@njit('i8(i8)', cache=True)
def popcount(n):
    a = 0
    while n != 0:
        a += n & 1
        n >>= 1
    return a

#@njit('i8(i8)', cache=True)
def fun(n):
    ops = 0
    while n:
        pc = popcount(n)
        n %= pc
        ops += 1
    return ops

n = int(input())
xs = list(map(int, input()))

from functools import reduce
sm = reduce(lambda x,y: x*2+y, xs)
pc = xs.count(1)

# pcの差分を出した後の剰余計算を速くするため、事前にmod pc+1, mod pc-1を計算しておく
mp = sm % (pc + 1)
mm = sm % (pc - 1) if pc > 0 else 0

for i in range(n):
    df = 1 if xs[i] == 0 else -1
    pci = pc + df
    if pci == 0:
        print(0)
        continue

    rest = pow(2, n - i - 1, pci)

    if xs[i] == 0:
        smi = (mp + rest) % pci
        print(1 + fun(smi))
    else:
        smi = (mm - rest) % pci
        print(1 + fun(smi))

Submission status: Runtime Error

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()


N=int(input())
X=input()
C=X.count("1")

lst=[]
for x in [C-1,C+1]:

    if C<=0:
        lst.append(-1)
    else:
        Z=0
        p=1
        for i in range(N):
            if X[-i-1]=="1":
                Z+=p
            p*=2
            Z%=x
        lst.append(Z)

#print(lst)
for i in range(N):

    _C=C+(1 if X[i]=="0"  else -1 )
    if  X[i]=="0":
        lstidx=1
    else:
        lstidx=0

    idx=(N-1-i)

    value=lst[lstidx]+(pow(2,idx,_C) if  X[i]=="0" else -pow(2,idx,_C))
    #print(lst[lstidx],value)
    count=0
    while value:
        count+=1
        value%=_C
        _C=0
        bit=value
        while bit:
            _C+=bit&1
            bit>>=1
    print(max(count,1))

Submission status: Runtime Error

Solution code:
from numba import njit

#@njit('i8(i8)', cache=True)
def popcount(n):
    a = 0
    while n != 0:
        a += n & 1
        n >>= 1
    return a

#@njit('i8(i8)', cache=True)
def fun(n):
    ops = 0
    while n:
        pc = popcount(n)
        n %= pc
        ops += 1
    return ops

n = int(input())
xs = list(map(int, input()))

from functools import reduce
sm = reduce(lambda x,y: x*2+y, xs)
pc = xs.count(1)

# pcの差分を出した後の剰余計算を速くするため、事前にmod pc+1, mod pc-1を計算しておく
mp = sm % (pc + 1)
mm = sm % (pc - 1) if pc > 0 else 0

for i in range(n):
    df = 1 if xs[i] == 0 else -1
    pci = pc + df

    rest = pow(2, n - i - 1, pci)

    if xs[i] == 0:
        smi = (mp + rest) % pci
        print(1 + fun(smi))
    else:
        smi = (mm - rest) % pci
        print(1 + fun(smi))

Submission status: Runtime Error

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

def solve(a, pc):
    ans = 0
    while a != 0:
        a = a % pc
        pc = bin(a).count('1')
        ans += 1
    return ans
        
pc = bin(x).count('1')
pc_p = pc + 1
pc_m = pc - 1

for i in reversed(range(n)):
    if x_bin[n-i-1] == '1':
        a = (x - pow(2, i)) % pc_m
        print(solve(a, bin(a).count('1')) + 1)
    else:
        a = (x + pow(2, i)) % pc_p
        print(solve(a, bin(a).count('1')) + 1)

Submission status: Runtime Error

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()


N=int(input())
X=input()
C=X.count("1")

lst=[]
for x in [C-1,C+1]:

    if C<0:
        lst.append(-1)
    else:
        Z=0
        p=1
        for i in range(N):
            if X[-i-1]=="1":
                Z+=p
            p*=2
            Z%=x
        lst.append(Z)

#print(lst)
for i in range(N):

    _C=C+(1 if X[i]=="0"  else -1 )
    if  X[i]=="0":
        lstidx=1
    else:
        lstidx=0

    idx=(N-1-i)

    value=lst[lstidx]+(pow(2,idx,_C) if  X[i]=="0" else -pow(2,idx,_C))
    #print(lst[lstidx],value)
    count=0
    while value:
        count+=1
        value%=_C
        _C=0
        bit=value
        while bit:
            _C+=bit&1
            bit>>=1
    print(max(count,1))

Submission status: Runtime Error

Solution code:
n = int(input())
x0 = input()
for i in range(n):
  x = x0[:i] +str(1-int(x0[i])) +x0[i+1:]
  k=0
  while x != '0':
    k = k +1
    x_oct = int(x, 2)
    x_pop = x.count('1')
    x = x_oct %x_pop
    x = format(x, 'b')
  print(k)

Submission status: Runtime Error

Solution code:
from numba import njit

@njit('i8(i8)', cache=True)
def popcount(n):
    a = 0
    while n != 0:
        a += n & 1
        n >>= 1
    return a

@njit('i8(i8)', cache=True)
def fun(n):
    ops = 0
    while n:
        pc = popcount(n)
        n %= pc
        ops += 1
    return ops

n = int(input())
xs = list(map(int, input()))

from functools import reduce
sm = reduce(lambda x,y: x*2+y, xs)
pc = xs.count(1)

# pcの差分を出した後の剰余計算を速くするため、事前にmod pc+1, mod pc-1を計算しておく
mp = sm % (pc + 1)
mm = sm % (pc - 1) if pc > 0 else 0

for i in range(n):
    df = 1 if xs[i] == 0 else -1
    pci = pc + df

    rest = pow(2, n - i - 1, pci)

    if xs[i] == 0:
        smi = (mp + rest) % pci
        print(1 + fun(smi))
    else:
        smi = (mm - rest) % pci
        print(1 + fun(smi))

Submission status: Runtime Error

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

n = int(input())
x = input()
z = '1' * n
o = '0' * n
X = int(x, 2)

if (z == x):
  u = n - 1
  d = n - 1
elif (o == x):
  u = 1
  d = 1
else:
  tmp = len(list(filter(lambda x: x == '1', x)))
  u = tmp + 1
  d = tmp - 1


def popcount(i):
  return i % len(list(filter(lambda x: x == '1', format(i, 'b'))))


def solve(i, count):
  if (i <= 2 * 10**5 and ans[i] != 0):
    return count + ans[i]
  elif (i == 0):
    return count
  else:
    return solve(popcount(i), count + 1)


def solve2(i, div):
  if (i <= 2 * 10**5):
    return ans[i]
  else:
    return ans[i % div] + 1


ans = [0] * (2 * 10 ** 5 + 1)
Us = [0] * (2 * 10 ** 5)
Ds = [0] * (2 * 10 ** 5)
for i in range(1, 2 * 10 ** 5 + 1):
  ans[i] = solve(i, 0)
  
Us[0] = 1 % u
Ds[0] = 1 % d
for i in range(1, 2 * 10 ** 5):
  Us[i] = (Us[i-1] * 2) % u
  Ds[i] = (Ds[i-1] * 2) % d

for i in range(n):
  if(X <= 2 * 10 ** 5 + 1):
    if(x[i] == '0'):
      print(solve2(X + 2 ** (n - i - 1), u))
    else:
      print(solve2(X - 2 ** (n - i - 1), d))
  else:
    if(x[i] == '0'):
      print(solve2(X + Us[n-i-1], u))
    else:
      print(solve2(X - Ds[n-i-1], d))

Submission status: Runtime Error

Solution code:
def popcount(ans, total, count):
    extra = total % ans
    if extra == 0:
        return count
    newtwo = []
    newextra = extra
    while extra != 0:
        newtwo.append(extra%2)
        extra = extra // 2
    count += 1
    newtwo.reverse()
    return popcount(sum(newtwo), newextra, count)
    
   
I = int(input())
two = tuple(map(int,input()))

for i in range(I):
    newtwo = list(two)
    if two[i] == 0:
        newtwo[i] = 1
        j = I
        l = 0
        ans = 0
        while j > 0:
            ans += 2**(j-1) * newtwo[l]
            j-=1
            l+= 1
        num = sum(newtwo)
        n = popcount(num, ans, 1)
        print(n)
    else:
        newtwo[i] = 0
        j = I
        l = 0
        ans = 0
        while j > 0:
            ans += 2**(j-1)* newtwo[l]
            j-=1
            l+= 1
        num = sum(newtwo)
        n = popcount(num, ans, 1)
        print(n)

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
y = int(x, 2)
pc = x.count('1')

xi = [0 for _ in range(n)]
pci = [0 for _ in range(n)]

for i in range(n):
    if x[i] == '1':
        pci[i] = pc - 1
        xi[i] = (y - 2 ** (n - i - 1)) % pci[i]
    else:
        pci[i] = pc + 1
        xi[i] = (y + 2**(n-i-1)) % pci[i]

for i in range(n):
    count = 1
    tmp_x = xi[i]
    tmp_pc = bin(tmp_x).count('1')
    while tmp_x > 0:
        tmp_x = tmp_x % tmp_pc
        tmp_pc = bin(tmp_x).count('1')
        count += 1
    print(count)

Submission status: Runtime Error

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

def count1(str):
    count=0
    n=len(str)
    for i in range(n):
        if str[i]=='1':
            count=count+1
    return count 

pop_bina=count1(bina)
num=int(bina,2)
trans1=num%(pop_bina+1)
trans2=num%(pop_bina-1)
for i in range(n):
    if bina[i]=='0':
        trans=(trans1+(2**(n-i-1))%(pop_bina+1))%(pop_bina+1)
    else:
        trans=(trans2-(2**(n-i-1))%(pop_bina-1))%(pop_bina-1)
    count=1
    while trans!=0:
        b_trans=format(trans, 'b')
        div=count1(b_trans)
        trans=trans%div
        count=count+1
    print(count)

Submission status: Runtime Error

Solution code:
#

import sys
input=sys.stdin.readline

def main():
    N=int(input())
    X=input().strip("\n")
    cnt=[0]*N
    for i in range(1,N):
        n=i
        while(n>0):
            pc=0
            for j in range(19):
                if (n>>j)&1==1:
                    pc+=1
            n%=pc
            cnt[i]+=1
    pc=X.count("1")
    if pc==0:
        for i in range(N):
            print(1)
        exit()

    rp=[0]*N
    rn=[0]*N
    for i in range(N):
        rp[i]=pow(2,i,pc+1)
        if pc!=1:
            rn[i]=pow(2,i,pc-1)
    rp=rp[::-1]
    rn=rn[::-1]
            
    Xrp=0
    Xrn=0
    for i in range(N):
        if X[i]=="1":
            Xrp=(Xrp+rp[i])%(pc+1)
            Xrn=(Xrn+rn[i])%(pc-1)
            
    for i in range(N):
        if X[i]=="1":
            if pc==1:
                print(0)
                continue
            r=Xrn-rn[i]
            print(cnt[r%(pc-1)]+1)
        else:
            r=Xrp+rp[i]
            print(cnt[r%(pc+1)]+1)
    
    
    
if __name__=="__main__":
    main()

Submission status: Runtime Error

Solution code:
def popcount(n):
    return bin(n).count("1")
  
def f(n):
  if n==1:
    return 1
  if n==0:
    return 0
  r=n%popcount(n)
  return (f(r)+1)
  
n=int(input())
x=input()
x_num=int(x,2)
pc=x.count("1")
mp=pc-1
pc+=1
mn=2**(n-1)
f1={}
for m in range(n):
  if x[m]=="1":
    r=x_num-mn
    r2=r%mp
  else:
    r=x_num+mn
    r2=r%pc
  mn//=2
  if r2 in f1:
    f2=f1[r2]
  else:
    f2=f(r2)+1
    f1[r2]=f2  
  print(f2)