Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

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

Constraints

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

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

Input

Input is given from Standard Input in the following format:

N
X

Output

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

Sample Input 1

3
011

Sample Output 1

2
1
1

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

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

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

Sample Input 2

23
00110111001011011001110

Sample Output 2

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



Sample input:
3
011


Sample output:
2
1
1

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
#N, K = (int(i) for i in input().split())
#B = [int(x) for x in input().split()]
#A = [[int(i) for i in input().split()] for i in range(N)]


def f(x, cur):
    #print(x, cur)
    if x == 0:
        return cur
    return f(x%bin(x).count("1"), cur+1)

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

Xint = int(X, 2)
popcountX = X.count("1")
#print("test", Xint, popcountX)

for i in range(N):
    if X[i] == "0":
        #print("arg", Xint%(popcountX+1), (2**(N-1-i))%(popcountX+1))
        print(f((Xint%(popcountX+1) + (2**(N-1-i))%(popcountX+1))%(popcountX+1), 1))
    else:
        if popcountX == 1:
            print(0)
        else:
            print(f((Xint%(popcountX-1) - (2**(N-1-i))%(popcountX-1))%(popcountX-1), 1))

Submission status: Time Limit Exceeded

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

X_int = int(X_bin, 2)  # bin => int


def calc_bin_cnt(next_int):
    next_bin = bin(next_int)[2:]
    # popcount
    cnt = 0
    for i in next_bin:
        if i == '1':
            cnt += 1
    return cnt


def calc_ans(next_int, cnt=None):
    if next_int == 0:
        return 0
    if cnt is None:
        cnt = calc_bin_cnt(next_int)
    next_int = next_int % cnt
    if next_int > 0:
        ans = calc_ans(next_int) + 1
    else:
        ans = 1
    return ans


X_cnt = calc_bin_cnt(X_int)
for i in range(N):
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1)), X_cnt-1))
    else:
        print(calc_ans(X_int + (2**(N-i-1)), X_cnt+1))

Submission status: Time Limit Exceeded

Solution code:
import sys


N = int(input())
X_bin = input()

X_int = int(X_bin, 2)  # bin => int
# popcount
X_cnt = 0
for i in X_bin:
    if i == '1':
        X_cnt += 1
dp = {0: 0, 1: 1}
bin_cnt = {}

sys.setrecursionlimit(10**5)


def calc_bin_cnt(next_int):
    if next_int in bin_cnt.keys():
        cnt = bin_cnt[next_int]
    else:
        next_bin = format(next_int, 'b')
        # popcount
        cnt = 0
        for i in next_bin:
            if i == '1':
                cnt += 1
    return cnt


def calc_ans(next_int, cnt=None):
    key = next_int
    if key in dp.keys():
        ans = dp[key]
    else:
        if cnt is None:
            cnt = calc_bin_cnt(next_int)
        else:
            bin_cnt[key] = cnt
        bin_cnt[next_int] = cnt
        next_int = next_int % cnt
        if next_int > 0:
            ans = calc_ans(next_int) + 1
        else:
            ans = 1
        dp[key] = ans
    return ans


for i in range(N):
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1)), X_cnt-1))
    else:
        print(calc_ans(X_int + (2**(N-i-1)), X_cnt+1))

Submission status: Time Limit Exceeded

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

X_int = int(X_bin, 2)  # bin => int
dp = {}


def calc_ans(next_int):
    key = next_int
    if key in dp.keys():
        return dp[key]
    ans = 0
    while next_int > 0:
        next_bin = format(next_int, 'b')
        # popcount
        cnt = 0
        for i in next_bin:
            if i == '1':
                cnt += 1
        next_int = next_int % cnt
        next_bin = format(next_int, 'b')
        ans += 1
    dp[key] = ans
    return ans


for i in range(N):
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1))))
    else:
        print(calc_ans(X_int + (2**(N-i-1))))

Submission status: Time Limit Exceeded

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

X_int = int(X_bin, 2)  # bin => int


def calc_ans(next_int):
    ans = 0
    while next_int > 0:
        next_bin = format(next_int, 'b')
        # popcount
        cnt = 0
        for i in next_bin:
            if i == '1':
                cnt += 1
        next_int = next_int % cnt
        next_bin = format(next_int, 'b')
        ans += 1
    return ans


for i in range(N):
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1))))
    else:
        print(calc_ans(X_int + (2**(N-i-1))))

Submission status: Time Limit Exceeded

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

f_list = [0 for i in range(N)]

def popcount(n) :
  return bin(n)[2:].count('1')

def f(n) :
  if n == 0 :
    return 0
  elif f_list[n] != 0 :
    return f_list[n]
  else :
    index = n % popcount(n)
    f_list[n] = f(index) + 1
    return f_list[n]
    
for i in range(N) :
  if X[i] == '0' :
    temp_X = X[:i] + '1' + X[i+1:]
  else :
    temp_X = X[:i] + '0' + X[i+1:]
  n = int(temp_X, 2)
  if n < N :
    print(f(n))
  else :
    print(f(n % popcount(n)) + 1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

f_list = [0 for i in range(N)]

def popcount(n) :
  return sum(np.array(list(bin(n)))[2:] == '1')

def f(n) :
  if n == 0 :
    return 0
  elif f_list[n] != 0 :
    return f_list[n]
  else :
    index = n % popcount(n)
    f_list[n] = f(index) + 1
    return f_list[n]
    
for i in range(N) :
  temp_X = list(X)
  if temp_X[i] == '0' :
    temp_X[i] = '1'
  else :
    temp_X[i] = '0'
  n = int(''.join(temp_X), 2)
  if n < N :
    print(f(n))
  else :
    print(f(n % popcount(n)) + 1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

f = [0 for i in range(N)]

def popcount(n) :
  return sum(np.array(list(bin(n)))[2:] == '1')


for i in range(1, N) :
  index = i % popcount(i)
  f[i] = f[index] + 1
  
  
  
for i in range(N) :
  temp_X = list(X)
  if temp_X[i] == '0' :
    temp_X[i] = '1'
  else :
    temp_X[i] = '0'
  n = int(''.join(temp_X), 2)
  if n < N :
    print(f[n])
  else :
    print(f[n % popcount(n)] + 1)

Submission status: Time Limit Exceeded

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

#10進数に変換
decX = int(strX,2)

#1の数をカウント
pop_c = strX.count('1')

# X % popcount+1
f_p = decX % (pop_c + 1)

# X % popcount-1(0になる時は0)
if pop_c == 1:
  f_m = 0
else:
  f_m = decX % (pop_c - 1)

for i in range(0,N):
  if strX[i] == '0':
    pop_a = (f_p + (2**(N-1-i)) % (pop_c + 1)) % (pop_c + 1) 
    Ans = 1
    
  elif pop_c == 1:
    pop_a = 0
    Ans = 0
    
  else:
    pop_a = f_m - (2**(N-1-i)) % (pop_c - 1)
    if pop_a < 0:
      pop_a = pop_a + pop_c - 1
    Ans = 1
  
  while pop_a > 0:
    wkpop = bin(pop_a).count('1')
    pop_a = pop_a % wkpop
    Ans += 1
  
  print(Ans)

Submission status: Time Limit Exceeded

Solution code:
def myPow(x, n):
  if n == 0:
    return 1

  K = 1
  while n > 1:
    if n % 2 != 0:
      K *= x

    x *= x
    n //= 2

  return K * x



N = int(input())
strX = input()

#10進数に変換
decX = int(strX,2)

#1の数をカウント
pop_c = strX.count('1')

# X % popcount+1
f_p = decX % (pop_c + 1)

# X % popcount-1(0になる時は0)
if pop_c == 1:
  f_m = 0
else:
  f_m = decX % (pop_c - 1)

for i in range(0,N):
  if strX[i] == '0':
    exp = myPow(2,(N-1-i))
    pop_a = (f_p + (exp % (pop_c + 1))) % (pop_c + 1) 
    Ans = 1
    
  elif strX[i] == '1' and pop_c == 1:
    pop_a = 0
    Ans = 0
    
  else:
    exp = myPow(2,(N-1-i))
    pop_a = f_m - (exp % (pop_c - 1))
    if pop_a < 0:
      pop_a = pop_a + pop_c - 1
    Ans = 1
  
  while pop_a > 0:
    wkpop = bin(pop_a).count('1')
    pop_a = pop_a % wkpop
    Ans += 1
  
  print(Ans)

Submission status: Time Limit Exceeded

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

#10進数に変換
decX = int(strX,2)

#1の数をカウント
pop_c = strX.count('1')

# X % popcount+1
f_p = decX % (pop_c + 1)

# X % popcount-1(0になる時は0)
if pop_c == 1:
  f_m = 0
else:
  f_m = decX % (pop_c - 1)

for i in range(0,N):
  if strX[i] == '0':
    pop_a = (f_p + ((2**(N-1-i)) % (pop_c + 1))) % (pop_c + 1) 
    Ans = 1
    
  elif strX[i] == '1' and pop_c == 1:
    pop_a = 0
    Ans = 0
    
  else:
    pop_a = f_m - (2**(N-1-i) % (pop_c - 1))
    if pop_a < 0:
      pop_a = pop_a + pop_c - 1
    Ans = 1
  
  while pop_a > 0:
    wkpop = bin(pop_a).count('1')
    pop_a = pop_a % wkpop
    Ans += 1
  
  print(Ans)

Submission status: Time Limit Exceeded

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

#10進数に変換
decX = int(strX,2)

#1の数をカウント
pop_c = strX.count('1')

# X % popcount+1
f_p = decX % (pop_c + 1)

# X % popcount-1(0になる時は0)
if pop_c == 1:
  f_m = 0
else:
  f_m = decX % (pop_c - 1)

for i in range(0,N):
  if strX[i] == '0':
    pop_a = (f_p + (2**(N-1-i)) % (pop_c + 1)) % (pop_c + 1) 
    Ans = 1
    
  elif strX[i] == '1' and pop_c == 1:
    pop_a = 0
    Ans = 0
    
  else:
    pop_a = f_m - (2**(N-1-i)) % (pop_c - 1)
    if pop_a < 0:
      pop_a = pop_a + pop_c - 1
    Ans = 1
  
  while pop_a > 0:
    wkpop = bin(pop_a).count('1')
    pop_a = pop_a % wkpop
    Ans += 1
  
  print(Ans)

Submission status: Time Limit Exceeded

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

#10進数に変換
decX = int(strX,2)

#1の数をカウント
pop_c = strX.count('1')

# X % popcount+1
f_p = decX % (pop_c + 1)

# X % popcount-1(0になる時は0)
if pop_c == 1:
  f_m = 0
else:
  f_m = decX % (pop_c - 1)

#(2**i)÷popcountを保存するリストを作成
f_tp = [0] * N  
f_tm = [0] * N  

for i in range(0,N):
  f_tp[i] = (2**(N-1-i)) % (pop_c + 1) 
  if pop_c - 1 == 0:
    f_tm[i] = 0
  else:
    f_tm[i] = (2**(N-1-i)) % (pop_c - 1) 

  
for i in range(0,N):
  if strX[i] == '0':
    pop_a = (f_p + f_tp[i]) % (pop_c + 1) 
    Ans = 1
    
  elif strX[i] == '1' and pop_c == 1:
    pop_a = 0
    Ans = 0
    
  else:
    pop_a = f_m - f_tm[i]
    if pop_a < 0:
      pop_a = pop_a + pop_c - 1
    Ans = 1
  
  while pop_a > 0:
    wkpop = bin(pop_a).count('1')
    pop_a = pop_a % wkpop
    Ans += 1
  
  print(Ans)

Submission status: Time Limit Exceeded

Solution code:
def popcount(x):
    return bin(x).count("1")
def solve(n):
    if n == 0:
        return 0
    return 1+solve(n % popcount(n))

N = int(input())
X = input()
num_x = int(X, 2)
p_cnt = X.count('1')
if p_cnt == 1:
    for i in range(N):
        if X[i] == '1':
            print(0)
        elif i == N-1:
            print(2)
        else:
            print(1)
    exit()
r0_p = num_x % (p_cnt+1)
r0_m = num_x % (p_cnt-1)
for i in range(N):
    if X[i] == '0':
        c_p_cnt = p_cnt+1
        r = r0_p + (2**(N-1-i) % c_p_cnt)
    else:
        c_p_cnt = p_cnt-1
        if c_p_cnt == 0:
            print(0)
            continue
        r = r0_m - (2**(N-1-i) % c_p_cnt)
    print(1 + solve(r % c_p_cnt))

Submission status: Time Limit Exceeded

Solution code:
MAX = 2*10**5
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
s_map = [0 for i in range(MAX+1)]
def solve(n):
    if n == 0:
        return 1
    if s_map[n] > 0:
        return s_map[n]
    s_map[n] = 1 + solve(n % popcount(n))
    return s_map[n]

N = int(input())
X = input()
num_x = int(X, 2)
p_cnt = X.count('1')
for i in range(N):
    c_p_cnt = p_cnt+1 if X[i] == '0' else p_cnt-1
    x = num_x + 2**(N-1-i) if X[i] == '0' else num_x - 2**(N-1-i)
    if x == 0:
        print(0)
    else:
        print(solve(x % c_p_cnt))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
num = input()
X = int(num,2)
c = num.count('1')
def A(s):
    if s == 0:
        return 1
    return A(s%(bin(s).count('1'))) + 1
if c==1:
  for i in range(N):
    if num[i] == '1':
      print(0)
    elif i == N-1:
      print(2)
    else:
      print(1)
  exit()
Y = X
amari1 = X%(c+1)
amari2 = Y%(c-1)
for i in range(N):
    if num[i] == '1':
        print(A((amari2-2**(N-1-i))%(c-1)))
    else:
        print(A((amari1+2**(N-1-i))%(c+1)))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
num = input()
X = int(num,2)
c = num.count('1')
def A(s):
    if s == 0:
        return 1
    return A(s%(bin(s).count('1'))) + 1
if c==1:
  for i in range(N):
    if num[i] == '1':
      print(0)
    elif i == N-1:
      print(2)
    else:
      print(1)
  exit()
amari1 = X%(c+1)
amari2 = X%(c-1)
for i in range(N):
    if num[i] == '1':
        print(A((amari2-2**(N-1-i))%(c-1)))
    else:
        print(A((amari1+2**(N-1-i))%(c+1)))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
num = input()
X = int(num,2)
c = num.count('1')
def A(s):
    if s == 0:
        return 1
    return A(s%(bin(s).count('1'))) + 1
if c==1:
  for i in range(N):
    if num[i] == '1':
      print(0)
    elif i == N-1:
      print(2)
    else:
      print(1)
  exit()
amari1 = X%(c+1)
amari2 = X%(c-1)
for i in range(N):
    if num[i] == '1':
        ans = A((amari2-2**(N-1-i))%(c-1))
        print(ans)
    else:
        ans = A((amari1+2**(N-1-i))%(c+1))
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
num = input()
X = int(num,2)
c = num.count('1')
def A(s):
    if s == 0:
        return 1
    else:
        return A(s%(str(bin(s)).count('1'))) + 1
amari1 = X%(c+1)
if c != 1:
    amari2 = X%(c-1)
    for i in range(N):
        if num[i] == '1':
            ans = A((amari2-2**(N-1-i))%(c-1))
            print(ans)
        else:
            ans = A((amari1+2**(N-1-i))%(c+1))
            print(ans)
else:
    for i in range(N):
        if num[i] == '1':
            print(0)
        else:
            ans = A((amari1+2**(N-1-i))%(c+1))
            print(ans)

Submission status: Time Limit Exceeded

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

decX = int(strX,2)
cnt = strX.count('1')

for i in range(0,N):
  if strX[i] == '0':
    pop = (decX + 2**(N-1-i)) % (cnt + 1)
    Ans = 1
    
  elif strX[i] == '1' and cnt == 1:
    pop = 0
    Ans = 0
    
  else:
    pop = (decX - 2**(N-1-i)) % (cnt - 1)
    Ans = 1
  
  while pop > 0:
    wkcnt = bin(pop).count('1')
    pop = pop % wkcnt
    Ans += 1
  
  print(Ans)

Submission status: Time Limit Exceeded

Solution code:
# this is the fourth task 
def popcount(n):
    return bin(n).count('1')

def rettozero(n,count=0):
    if (n==0):
        return count 
    n %= popcount(n)
    count += 1
    return rettozero(n,count)

length=int(input())
b=input()

#val=0
#for x,y in enumerate(b[::-1],0):
#    val += 2**x * int(y)
#print(val)
#print(int(b,2))
val=int(b,2)
for i in range(length):
    prev=b[i]
    loopval=val
    if (prev=="1") :
        #loopval -=2**(length-i-1)
        loopval -= pow(2, length-i-1)
    else :
        #loopval += 2**(length-i-1)
        loopval +=pow(2, length-i-1)
    c=rettozero(loopval)
    print(c)

Submission status: Time Limit Exceeded

Solution code:
# this is the fourth task 
def popcount(n):
    return bin(n).count('1')

def rettozero(n,count=0):
    if (n==0):
        return count 
    n %= popcount(n)
    count += 1
    return rettozero(n,count)

length=int(input())
b=input()

val=0
for x,y in enumerate(b[::-1],0):
    val += 2**x * int(y)

for i in range(length):
    prev=b[i]
    loopval=val
    if (prev=="1") :
        #loopval -=2**(length-i-1)
        loopval -= pow(2, length-i-1)
    else :
        #loopval += 2**(length-i-1)
        loopval +=pow(2, length-i-1)
    c=rettozero(loopval)
    print(c)

Submission status: Time Limit Exceeded

Solution code:
# this is the fourth task 
def popcount(n):
    return bin(n).count('1')

def rettozero(n,count=0):
    if (n==0):
        return count 
    n %= popcount(n)
    count += 1
    return rettozero(n,count)

length=int(input())
b=input()

val=0
for x,y in enumerate(b[::-1],0):
    val += 2**x * int(y)

for i in range(length):
    prev=b[i]
    loopval=val
    if (prev=="1") :
        loopval -=2**(length-i-1)
    else :
        loopval += 2**(length-i-1)
    c=rettozero(loopval)
    print(c)

Submission status: Time Limit Exceeded

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

decX = int(strX,2)
cnt = strX.count('1')

cnt_sp = cnt + 1
cnt_sm = cnt - 1


for i in range(0,N):
  if strX[i] == '0':
    wkstr = strX[:i] + '1' + strX[i+1:N+1]
    wkcnt = cnt_sp
  else:
    wkstr = strX[:i] + '0' + strX[i+1:N+1]
    wkcnt = cnt_sm
  
  if wkcnt == 0:
    Ans = 0
    pop = 0
  else:
    wkdec = int(wkstr,2)
    pop = wkdec % wkcnt
    Ans = 1
  
  while pop > 0:
    wkcnt = bin(pop).count('1')
    pop = pop % wkcnt
    Ans += 1
  
  print(Ans)

Submission status: Time Limit Exceeded

Solution code:
# this is the fourth task 
def popcount(bits):
    return bits.count(1)

def rettozero(count, bits, value):
    cnt=popcount(bits)
    if (cnt==0):
        return count 
    new = value%cnt
    return rettozero(count+1, list(map(int, bin(new)[2:])), new)

_=input()
b=list(map(int, input()))
val=0
for x,y in enumerate(b[::-1],0):
    val += 2**x * y

length=len(b)

for i in range(length):
    prev=b[i]
    loopval=val

    if (prev==1) :
        b[i]=0
        loopval -=2**(length-i-1)
    else :
        b[i]=1
        loopval += 2**(length-i-1)

    c=rettozero(0, b, loopval)
    print(c)
    b[i]=prev

Submission status: Time Limit Exceeded

Solution code:
# this is the fourth task 
def rettozero(count, bitstr):
    cnt=bitstr.count('1')
    if (cnt==0):
        return count 
    new = int(''.join(bitstr), base=2)%cnt
    return rettozero(count+1, bin(new)[2:])



_=input()
b=[x for x in input()]
x=''.join(b)
x=int(x,base=2)

for i in range(len(b)):
    prev=b[i]
    if (int(prev)) :
        b[i]='0' 
    else :
        b[i]='1'
    c=rettozero(0, b)
    print (c)
    b[i]=prev

Submission status: Time Limit Exceeded

Solution code:
def f(n):
    tmp=n
    cnt=0
    while tmp>0:
        strtmp=format(tmp,'b')
        tmp=tmp%int(strtmp.count('1'))
        cnt+=1
    return cnt


N=int(input())
X=input()
for i in range(N):
    Xi=list(X)
    if Xi[i]=="1":
        Xi[i]="0"
    elif Xi[i]=="0":
        Xi[i]="1"
    x="".join(Xi)
    print(f(int(x,2)))

Submission status: Time Limit Exceeded

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

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

for j in range(n-1, -1, -1):
  print(f(s ^ (1 << j)))

Submission status: Time Limit Exceeded

Solution code:
numBits = int(input())
bitString = input()

def calculateAndPrintPopcount(n):
  popCount = 0
  while(n > 0):
    n %= bin(n).count('1')
    popCount += 1
  return popCount

count1 = bitString.count('1')
x = int(bitString,2)
xPlus = x % (count1 + 1)
if (count1 - 1) == 0:
  xMinus = 0
else:
  xMinus = x % (count1 - 1)

for i in range(numBits)  :
  if bitString[i] == '0':
    print(calculateAndPrintPopcount( (x + pow(2,numBits-1-i,(count1+1))) % (count1+1) ) + 1)
  else:
    if (count1-1) == 0:
      print(0)
    else:
      print(calculateAndPrintPopcount( (x - pow(2,numBits-1-i,(count1-1)) ) % (count1-1) ) +1)

Submission status: Time Limit Exceeded

Solution code:
numBits = int(input())
bitString = input()

def calculateAndPrintPopcount(n):
  popCount = 0
  while(n > 0):
    n %= bin(n).count('1')
    popCount += 1
  return popCount

count1 = bitString.count('1')
x = int(bitString,2)

for i in range(numBits)  :
  if bitString[i] == '0':
    print(calculateAndPrintPopcount( (x + pow(2,numBits-1-i,(count1+1))) % (count1+1) ) + 1)
  else:
    if (count1-1) == 0:
      print(0)
    else:
      print(calculateAndPrintPopcount( (x - pow(2,numBits-1-i,(count1-1)) ) % (count1-1) ) +1)

Submission status: Time Limit Exceeded

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

def reverse(x, i):
    xl = list(x)
    xl[i] = "0" if xl[i] == "1" else "1"
    return "".join(xl)

def binstr2int(x):
    return int(x, 2)

def int2binstr(x):
    return "{0:b}".format(x)

def popcount(x):
    # x : int
    xs = int2binstr(x)
    pcount = sum([b == "1" for b in list(xs)])
    return pcount

def func(n):
    # n: int
    count = 0
    while n != 0:
        n = n % popcount(n)
        count += 1
    return count

for i in range(N):
    x = binstr2int(reverse(X, i))
    print(func(x))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
xs = input().rstrip("\n")
 
x = int("0b" + xs, 2)
 
p = xs.count('1')
 
if p >= 2:
    m = {0:(x % (p-1)), 1:(x % (p+1)), }
else:
    m = {0:0, 1:(x % (p+1)), }
 
bit_count_cache = {}
count_cache = {0: 0, 1: 1}
 
def bitcount(number):
    if not number in bit_count_cache:
        bit_count_cache[number] = bin(number).count('1')
    return bit_count_cache[number]
 
def count(number):
    if not number in count_cache:
      count_cache[number] = count(number % bitcount(number)) + 1
    return count_cache[number]
 
counts = {}
a = 1
for i in range(n, 0,-1):
    b = x & a
    if b == 0:
        counts[i] = count((m[1] + a % (p + 1)) % (p+1)) + 1
    else:
        current_p = p - 1
        if current_p > 0:
            counts[i] = count( (m[0] - a % (p - 1)) % (p-1) ) + 1
        else:
            counts[i] = 0
    a *= 2
for i in range(1, n+1):
    print(counts[i])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
xs = input().rstrip("\n")

x = int("0b" + xs, 2)

p = xs.count('1')

if p >= 2:
    m = {0:(x % (p-1)), 1:(x % (p+1)), }
else:
    m = {0:0, 1:(x % (p+1)), }

bit_count_cache = {}
count_cache = {0: 0, 1: 1}

def bitcount(number):
    if number in bit_count_cache:
        return bit_count_cache[number]
    bit_count_cache[number] = bin(number).count('1')
    return bit_count_cache[number]

def count(number):
    if number == 0:
      return 0
    else:
      return count(number % bitcount(number)) + 1

counts = {}
a = 1
for i in range(n, 0,-1):
    b = x & a
    if b == 0:
        counts[i] = count((m[1] + a % (p + 1)) % (p+1)) + 1
    else:
        current_p = p - 1
        if current_p > 0:
            counts[i] = count( (m[0] - a % (p - 1)) % (p-1) ) + 1
        else:
            counts[i] = 0
    a *= 2
for i in range(1, n+1):
    print(counts[i])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
xs = input().rstrip("\n")

x = int("0b" + xs, 2)

p = xs.count('1')

if p >= 2:
    m = {0:(x % (p-1)), 1:(x % (p+1)), }
else:
    m = {0:0, 1:(x % (p+1)), }

bit_count_cache = {}
count_cache = {0: 0, 1: 1}

def bitcount(number):
    if number in bit_count_cache:
        return bit_count_cache[number]
    bit_count_cache[number] = bin(number).count('1')
    return bit_count_cache[number]

def count(number):
    if number in count_cache:
        return count_cache[number]
    total = 0
    current = number
    hist = []
    while not current in count_cache:
        b_count = bitcount(current)
        current = current % b_count
        hist.insert(0, current)
        total += 1
    total += count_cache[current]
    count_cache[number] = total
    for i in range(1,len(hist)):
        count_cache[hist[i]] = count_cache[current] + i
      
    return total
counts = {}
a = 1
for i in range(n, 0,-1):
    b = x & a
    if b == 0:
        counts[i] = count((m[1] + a % (p + 1)) % (p+1)) + 1
    else:
        current_p = p - 1
        if current_p > 0:
            counts[i] = count( (m[0] - a % (p - 1)) % (p-1) ) + 1
        else:
            counts[i] = 0
    a *= 2
for i in range(1, n+1):
    print(counts[i])

Submission status: Time Limit Exceeded

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

pnumber = 0
pcount = 0
for i in range(n):
  if x[i] == '1':
    pnumber += 2 ** (n - i - 1)
    pcount += 1
d1 = pnumber % (pcount + 1)
lst = [(pcount + 1), (pcount - 1), d1]
if lst[1] > 0:
  d2 = pnumber % (pcount - 1)
  lst.append(d2)

for i in range(n):
  ans = 0
  if x[i] == '0':
    count = lst[0]
    d = 2 ** (n - i - 1) % count
    number = (lst[2] + d) % count
  if x[i] == '1':
    count = lst[1]
    if count > 0:
      d = 2 ** (n - i - 1) % count
      number = (lst[3] - d) % count
  if count > 0:
    ans += 1
    while number > 0:
      d = number
      count = 1
      while d > 1:
        if d % 2 == 1:
          count += 1
        d //= 2
      number %= count
      ans += 1
  print(ans)

Submission status: Time Limit Exceeded

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

lst = []
number = 0
count = 0
for i in range(n):
  if x[i] == '1':
    number += 2 ** (n - i - 1)
    count += 1
lst.append(number)
lst.append(count)

for i in range(n):
  ans = 0
  number = lst[0]
  count = lst[1]
  if x[i] == '0':
    number += 2 ** (n - i - 1)
    count += 1
  if x[i] == '1':
    number -= 2 ** (n - i - 1)
    count -= 1
  while number > 0:
    number %= count
    ans += 1
    d = number
    count = 1
    while d > 1:
      if d % 2 == 1:
        count += 1
      d //= 2
  print(ans)

Submission status: Time Limit Exceeded

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

for i in range(n):
  number = 0
  ans = 0
  count = 0
  for j in range(n):
    if j == i:
      if x[i] == '0':
        number += 2 ** (n - i - 1)
        count += 1
    else:
      if x[j] == '1':
        number += 2 ** (n - j - 1)
        count += 1
  while number > 0:
    number %= count
    ans += 1
    d = number
    count = 1
    while d > 1:
      if d % 2 == 1:
        count += 1
      d //= 2
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy

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

popcounts=2**(2*10**5+1)

def popcount(n):
    while n%2==0:
        n=n//2
    return format(n, 'b').count('1')

def f(n):
    count=0
    while n!=0:
        p=popcount(n)
        n=n%p
        count+=1
    return count

for i in range(0,N):
    X2=copy.copy(X)
    X2=list(X2)

    if X2[i]=='0':
        X2[i]='1'
    else:
        X2[i]='0'

    X2="".join(X2)
    X2=int(X2, 2)
    
    print(f(X2))

Submission status: Time Limit Exceeded

Solution code:
import copy

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


def popcount(n):
    return format(n, 'b').count('1')

def f(n):
    count=0
    while n!=0:
        p=popcount(n)
        n=n%p
        count+=1
    return count

for i in range(0,N):
    X2=copy.copy(X)
    X2=list(X2)

    if X2[i]=='0':
        X2[i]='1'
    else:
        X2[i]='0'

    X2="".join(X2)
    X2=int(X2, 2)
    
    print(f(X2))

Submission status: Time Limit Exceeded

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

x0 = int('0b'+x,0)

ceil = 2*10**5+2
ppc = [0]*(ceil)

def popcount(n):    
  if n == 0:
    return 0
  if ppc[n] != 0:
    return ppc[n]
    
  b = bin(n).count('1')  
  tmp = n%b
  ppc[n] = popcount(tmp) + 1
  return ppc[n]

c1 = bin(x0).count('1')  
p = 1
ans = []
for i in range(n):  
  if x[n-i-1] == '1':    
    tmp = x0 - p
    if c1-1 == 0:
      tmp = 0
    else:
      tmp2 = tmp % (c1 - 1)
  else:
    tmp = x0 + p  
    tmp2 = tmp % (c1 + 1)
    
  if tmp > ceil:      
    ans.append(popcount(tmp2)+1)    
  else:
    ans.append(popcount(tmp))    
  p *= 2
  

for i in range(n):
  print(ans[-1-i])

Submission status: Time Limit Exceeded

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

x0 = int('0b'+x,0)

ceil = 2*10**5+2
ppc = [0]*(ceil)

def popcount(n):    
  if n == 0:
    return 0
  if ppc[n] != 0:
    return ppc[n]
    
  b = bin(n).count('1')  
  tmp = n%b
  ppc[n] = popcount(tmp) + 1
  return ppc[n]

c1 = bin(x0).count('1')  
for i in range(n):
  p = 2 ** (n - i - 1)
  if x[i] == '1':    
    tmp = x0 - p
    if c1-1 == 0:
      tmp = 0
    else:
      tmp2 = tmp % (c1 - 1)
  else:
    tmp = x0 + p  
    tmp2 = tmp % (c1 + 1)
    
  if tmp > ceil:      
    print(popcount(tmp2)+1)
  else:
    print(popcount(tmp))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
xs = input().rstrip("\n")

x = int("0b" + xs, 2)

bit_count_cache = {}
count_cache = {0: 0, 1: 1}

def bitcount(number):
    if number in bit_count_cache:
        return bit_count_cache[number]
    bit_count_cache[number] = bin(number).count('1')
    return bit_count_cache[number]

def count(number):
    if number in count_cache:
        return count_cache[number]
    total = 0
    current = number
    hist = []
    while not current in count_cache:
        b_count = bitcount(current)
        current = current % b_count
        hist.insert(0, current)
        total += 1
    total += count_cache[current]
    count_cache[number] = total
    for i in range(1,len(hist)):
        count_cache[hist[i]] = count_cache[current] + i
      
    return total

answers = {}
a = 1
for i in range(n, 0, -1):
    answers[i] = count(x ^ a)
    a *= 2
for i in range(1, n+1):
    print(answers[i])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
xs = input().rstrip("\n")
x = int("0b" + xs, 2)

bit_count_cache = {}
count_cache = {0: 0, 1: 1}

def bitcount(number):
    if number in bit_count_cache:
        return bit_count_cache[number]
    bit_count_cache[number] = bin(number).count('1')
    return bit_count_cache[number]

def count(number):
    if number in count_cache:
        return count_cache[number]
    total = 0
    current = number
    while not current in count_cache:
        b_count = bitcount(current)
        current = current % b_count
        total += 1
    total += count_cache[current]
    count_cache[number] = total
    return total

for i in range(1, n + 1):
    a = 2**(n - i)
    print(count(x ^ a))