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:
from functools import lru_cache

n = int(input())
x = input()
x10 = int(x, 2)
lenx = len(x)

maxbit = x.count("1")

box = [0] * (maxbit + 1)

@lru_cache(maxsize=None)
def f(i):
  cnt = 0
  while i > 0:
    if box[i] != 0:
      return box[i] + cnt
    i %= bin(i).count("1")
    cnt += 1
  return cnt

for i in range(1, maxbit + 1):
  box[i] = f(i)

for i in range(lenx):
  if x[i] == "0":
    mb = maxbit + 1
    t = x10 + 2 ** (lenx - 1 - i)
  else:
    mb = maxbit - 1
    t = x10 - 2 ** (lenx - 1 - i)
  # print(t, mb)
  if t == 0:
    print(0)
  else:
    t %= mb 
    if t == 0:
      print(1)
    else:
      ans = f(t) + 1 
      box[t] = ans
      print(ans)

Submission status: Time Limit Exceeded

Solution code:
def calc(num,c):
    s = int(num,2)
    
    ar = list(map(int,num))
    ss = sum(ar)
    

    if s % ss != 0:
        return calc(format(s%ss,'b'),c+1)
    else:
        return c+1

n = int(input())
x = input()
l = [0] * n
lc =[0] * n
c = sum(list(map(int,x)))

for i in range(n):
    if x[i] == '0':
        l[i] = x[0:i] + '1' + x[i+1:len(x)]
        lc[i] = c + 1
    else:
        l[i] = x[0:i] + '0' + x[i+1:len(x)]
        lc[i] = c-1

for i in range(n):
    if int(l[i],2) == 0:
        print(0)
    else:
        aaa = int(l[i],2) % lc[i]
        if aaa != 0:
            print(calc(            str(format(aaa,'b')),1                        ))
        else:
            print(1)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache


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


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


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

li = []

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

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

Submission status: Time Limit Exceeded

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

def popcount(n):
    r = 0
    for c in n:
        if c == '1':
            r += 1
    return r

def func(n):
    return bin(int(n,2)%popcount(n))[2:]

cf = popcount(X)

for i in range(N):
    if X[i] == '0':
        X[i] = '1'
        cf_ = cf+1
    else:
        X[i] = '0'
        cf_ = cf-1
    res = 0
    tmp = ''.join(X)
    if int(tmp,2) != 0:
        tmp = bin(int(tmp,2)%cf_)
        res += 1
    while int(tmp,2) != 0:
        tmp = func(tmp)
        res += 1
    print(res)
    if X[i] == '0':
        X[i] = '1'
    else:
        X[i] = '0'

Submission status: Time Limit Exceeded

Solution code:
CH = [0,1,1,2,1,2,1,2,1,2,1,2,1,2,2,3,1,2,1,2,1]
N = int(input())
X = input()
s = 0
for x in X:
    if x == "1":
        s += 1
num = int(X,2)
num1 = num%(s+1)
if s > 1:
    num2 = num%(s-1)
for i in range(N):
    if int(X[i])==1:
        p = s-1
        if p == 0:
            print(0)
            continue
        x = (num2-2**(N-1-i))%p
        if x > 20:
            y = x%sum(map(int,list(bin(x))[2:]))
            print(2+CH[y])
        else:
            print(1+CH[x])
    else:
        p = s+1
        x = (num1+2**(N-1-i))%p
        if x > 20:
            y = x%sum(map(int,list(bin(x))[2:]))
            print(2+CH[y])
        else:
            print(1+CH[x])

Submission status: Time Limit Exceeded

Solution code:
import copy
n=int(input())
x=input()
l1=list(x)
l=[]
for i in range(n):
    if l1[i]=="1":
        l1[i]="0"
    else:
        l1[i]="1"
    l.append(copy.deepcopy(l1))
    if l1[i]=="1":
        l1[i]="0"
    else:
        l1[i]="1"
for i in l:
    s1="".join(i)
    num=int(s1,2)
    b=s1.count("1")
    op=0
    while num!=0:
        num=num%b
        b=bin(num).count("1")
        op=op+1
    print(op)

Submission status: Time Limit Exceeded

Solution code:
def popcount(n):
    num = 0
    while n != 0:
        n = n % bin(n).count('1')
        num += 1
    print(num)

N = int(input().rstrip())
X = input().rstrip()

for i in range(N):
    if X[i] == '0':
        reverse = '1'
    else:
        reverse = '0'
    x = X[:i] + reverse + X[i+1:]
    n = int(x, 2)
    popcount(n)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
x=input()
z=[]
z=list(x)
def pop(Y):
  listy=[]
  for i in range(Y):
    listy.append(Y%2)
    Y=Y//2
  result=listy.count(1)
  return result
def times(A):
  count=0
  while A!=0:
    A=A%pop(A)
    count=count+1
  return count
sum=0
for j in range(len(z)):
  sum=sum+(int(z[j]))*(2**(len(z)-j-1))
for i in range(N):
  sum2=0
  ai=(int(z[i]))*(-1)+1
  sum2=sum+(2**(len(z)-i-1))*(ai-int(z[i]))
  print(times(sum2))

Submission status: Time Limit Exceeded

Solution code:
hint = [None] * 200000

def f(n):
    if n == 0:
        return 0
    else:
        count = 0
        while True:
            count += 1
            r = (n % str(bin(n)).count("1"))
            if r != 0:
                n = r
            else:
                return count
            
N = int(input())
X = int(input(),2)

for i in range(N):
    if hint[i] == None:
        ans = (f(X ^ (1 << (N - i - 1))))
        print(ans)
        hint[i] = ans
    else:
        print(hint[i])

Submission status: Time Limit Exceeded

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

val = 0
rui = 1
mod = 0

nagasa = 2*10**5+1
#nagasa = 5
d_li = [0]*(nagasa)

for i in range(1,nagasa):
    t_v = i
    t_m = bin(t_v).count("1")
    ans = 0
    while t_v != 0:
        if d_li[t_v] != 0:
            ans += d_li[t_v]
            break
        ans += 1
        t_v %= t_m
        #t_m = bin(t_v).count("1")
    d_li[i] = ans

#print(d_li)
#exit()
"""
for i in range(n):
    val += int(x[n-1-i])*rui
    rui *= 2
"""
val = int(x, 2)
#print(val)
#exit()

mod = bin(val).count("1")

rui = 2**(n-1)
ans_li = []
    
for i in range(n):
    t_v = val
    t_m = mod
    if int(x[i]) == 1:
        t_v -= rui
        t_m -= 1
    else:
        t_v += rui
        t_m += 1
    rui //= 2
    ans = 0
    #while t_v != 0:
    if t_v != 0:
        t_v %= t_m
        ans += 1
    
    ans += d_li[t_v]
    #t_m = bin(t_v).count("1")
    #ans_li.append(ans)
    print(ans)
    #print(ans_li)
"""
#print(ans_li)
for i in range(n):
    print(ans_li[n-1-i])
"""

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = input()  
x = int(X, 2)
for i in range(N):
  if(X[i]=="0"):
    k = x + 2**(N-i-1) 
  else:
    k = x - 2**(N-i-1)
  count = 0
  while(k!=0):
    k = k%bin(k).count("1")
    count += 1
  print(count)

Submission status: Time Limit Exceeded

Solution code:
def popcount(n):
    ans = 0
    while (n > 0):
        ans += n % 2
        n = n // 2
    return ans


N = int(input())

popcountA = [0 for x in range(2 ** N)]
for i in range(1, 2**N):
    popcountA[i] = popcount(i)


AAA = [0 for x in range(2 ** N)]
for i in range(1, 2**N):
    AAA[i] = AAA[i % popcountA[i]] + 1

X = int(input(), 2)

for i in range(N):

    Xi = X ^ (1 << (N-i-1))

    print(AAA[Xi])

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    n = int(input().strip())
    x = input().strip()

    for i in range(n):
        count = 0
        _x = list(x)
        _x[i] = "0" if _x[i] == "1" else "1"
        _x = int("".join(_x), 2)
        while not _x == 0:
            _x = int(_x % bin(_x).count("1"))
            count += 1
        print(count)

Submission status: Time Limit Exceeded

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

N = int(input())
X = input()
#x_list = []
x_list10 = []
Xx = ""
XXx = ""
remain = -1
for i in range(N):
  if X[i] == '1':
    if i == 0:
      XXx = '0' + X[i+1:]
    else:
      XXx = X[:i] + '0' + X[i+1:]
  else:
    if i == 0:
      XXx = '1' + X[i+1:]
    else:
      XXx = X[:i] + '1' + X[i+1:]  
  #x_list.append(XXx)
  x_list10.append(int(XXx, 2))
#print(x_list)  
#print(x_list10) 
#print(popcount('111'))


for i in range(N):
  cnt  = 0
  n = x_list10[i]
  int_n = bin(n)
  while n != 0:
    pop = popcount(str(int_n))
    n = n % pop
    int_n = bin(n)
    cnt += 1
  print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from functools import lru_cache

import sys
sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, X):
    @lru_cache(maxsize=None)
    def f(y):
        c = bin(y).count('1')
        if c == 0:
            return 0
        r = y % c

        return 1 + f(r)

    C = X.count('1')
    cmr = 0
    cpr = 0
    for b in X:
        cmr *= 2
        cmr += int(b)
        if C-1 == 0:
            cmr = 0
        else:
            cmr %= C - 1
        cpr *= 2
        cpr += int(b)
        cpr %= C + 1

    for i in range(N):
        t = 1
        b = 2 ** (N-i-1)
        if X[i] == '0':
            x = (cpr + b) % (C+1)
        else:
            if C-1 == 0:
                x = 0
                t = 0
            else:
                x = (cmr - b) % (C-1)
        while True:
            c = bin(x).count('1')
            # print(x, c)
            if c == 0:
                break
            x = x % c
            t += 1
        print(t)


def main():
    N = read_int()
    X = read_str()
    slv(N, X)

    # import random
    # N = 10**5
    # N *= 2
    # X = ''.join(random.choices('01', k=N))
    # print(slv(N, X))




if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
X=int(input(),2)
def f(n):
    ans=0
    while n != 0:
        ans+=1
        n2=str(bin(n)[2:])
        pop=n2.count('1')
        n=n%pop
    return ans

for i in range(1,N+1):
    j=N-i
    xi=X^2**j
    print(f(xi))

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():
    N = in_n()
    X = int(in_s(), 2)
    #N = 10**5
    #X = int('1' * N, 2)

    ans = [0] * N
    for i in range(N):
        a = X ^ (1 << N - i - 1)
        count = 0
        while a:
            a = a % bin(a).count('1')
            count += 1
        ans[i] = count

    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
pcmap={}
answermap={}

def popcount(a):
    if a in pcmap.keys():
        return pcmap[a]
    else:
        s = str(bin(a))
        pcmap[a] = s.count('1')
        return pcmap[a]

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache


@lru_cache(typed=int)
def mpower(a, b, n):
    if b == 0:
        return 1
    if b == 1:
        return a % n
    a1 = a
    k = 1
    while a1 < n and k < b:
        a1 = a1 * a
        k = k + 1

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


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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy

def popcount(x):
	count=0
	for digit in str(bin(x))[2:]:
		if digit=='1':
			count+=1
	return count

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

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

value_x= int(x, 2)
#print('!!', value_x)
for i in range(n):
	test= value_x^(2**(n-i-1))
	print(f(test))





#print(f(n))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = input()
x_int = int(x, 2)
xi = []
for i in range(n):
    if x[i] == "0":
        xi.append(x_int + 2**(n-i-1))
    else:
        xi.append(x_int - 2**(n-i-1))
def popcount(m):
    return bin(m).count("1")
for i in range(len(xi)):
    m = xi[i]
    ans = 0
    while m != 0:
        m %= popcount(m)
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy

def popcount(n):
    bin_str = bin(n)[2:]
    l = list(bin_str)
    ans = l.count('1')
    return ans


def f(n):
    ans = 0
    while n != 0:
        n = n % popcount(n)
        ans += 1
        #print(n)
    return ans

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

for i in range(n):
    buf = copy.copy(x)
    if buf[i] == '1':
        buf[i] = '0'
    else:
        buf[i] = '1'
    #num_one = buf.count('1')
    num = int('0b' + ''.join(buf), 2)
    print(f(num))

Submission status: Time Limit Exceeded

Solution code:
def func(x):
  return x.count('1')

def to_di(x):
  s = ''
  while x!=0:
    s = str(x%2)+s
    x//=2
  return s

def to_ten(s):
  num=0
  s_ = s[::-1]
  for i,d in enumerate(s_):
    num+=(2**i)*int(d)
  return num

def hanten(s,i):
  tmp_x = ''
  for j,w in enumerate(s):
    if i==j:
      tmp_x = tmp_x+str((int(w)+1)%2)
    else:
      tmp_x = tmp_x+w
  return tmp_x

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


for i in range(n):
  cnt=0
  tmp = hanten(x,i)
  while to_ten(tmp)!=0:
    tmp_num = to_ten(tmp)
    div_num = func(tmp)
    amari = tmp_num % div_num
    cnt+=1
    if amari==0:
      break
    tmp = to_di(amari)
  print(cnt)

Submission status: Time Limit Exceeded

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

def calc(num, cnt, ans):
  ans += 1
  if cnt == 0:
    return ans
  mod = num % cnt
  if mod == 0:
    return ans
  else:
    cnt = bin(mod).count('1')
    return(calc(mod, cnt, ans))

n = int(X, 2)
c = X.count('1')
for i in range(1, N+1):
  if X[i-1] == '0':
    print(calc(n+2**(N-i), c+1, 0))
  else:
    num = n-2**(N-i)
    if num == 0:
      print(0)
    else:
      print(calc(num, c-1, 0))

Submission status: Time Limit Exceeded

Solution code:
memo = {}

def func(n, s):
    v = list("1" + "0" * n)
    x = int(s, 2)
    x ^= int("".join(v), 2)
    cnt = 0
    l = [x]
    while x > 0:
        val = str(bin(x)).count('1')
        x %= val
        cnt += 1
        if x in memo:
            cnt += memo[x]
            break
        l.append(x)
    for i in range(len(l)):
        memo[l[i]] = cnt - i
    return cnt

def main():
    N = int(input())
    s = input()
    index = list(range(N))[::-1]
    for n in index:
        print(func(n, s))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=input()
ans=[]


def calc_popcount(z):
    bin_z=bin(z)[2:]
    ans=bin_z.count('1')
    return ans

for i in range(n):
    xi=x[:i]+ ('0' if x[i]=='1' else '1') + x[i+1:]
    xi=int(xi,2)
#    print(xi,x[:i]+ ('0' if x[i]=='1' else '1') + x[i+1:])
    ans_xi=0

    while(xi>0):
        xi=xi%calc_popcount(xi)
        ans_xi+=1
    ans.append(ans_xi)

for i in range(len(ans)):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
# # ####################################################################
# import io
# import sys

# _INPUT = """\
# 3
# 011

# 23
# 00110111001011011001110


# """
# sys.stdin = io.StringIO(_INPUT)
####################################################################
import sys
def _p(*_a):
  #return
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
####################################################################
def _pa(_aa):
  #return
  for _a in _aa: _p(_a)
####################################################################
N = int(input())
X = input()

from collections import defaultdict
d = defaultdict(int)
dCnt = defaultdict(int)

def popcount(n):
  if d[n] > 0: return d[n]

  rtn = 0
  while n > 0:
    if n % 2 == 1: rtn += 1
    n = n >> 1

  d[n] = rtn
  return d[n]


for n in range(N)[::-1]:
  i = 1 << n
  x = int(X, 2)
  a = b = x^i
  # _p(n, i, x, a)

  cnt = 0
  while a>0:
    if dCnt[a] > 0:
      cnt += dCnt[a]
      a = 0
    else:
      cnt += 1
      a = a % popcount(a)
      # _p(n, i, x, a)

  dCnt[b] = cnt

  print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def solve(N,X):
    ans = []
    cnt = X.count("1")

    for i in range(N):
        if X[i] == "1":
            X[i] = "0"
            ans.append(cal(X,0))
            X[i] = "1"
        else:
            X[i] = "1"
            ans.append(cal(X,0))
            X[i] = "0"
    return ans

def cal(X,rec):
    cnt = X.count("1")
    if cnt == 0:
        return rec
    else:
        amari = 0
        for i in range(len(X)):
            if X[i] == "1":
                amari += pow(2,len(X)-i-1,cnt)
                amari %= cnt
        b = bin(amari)[2:]
        Y = [b[i] for i in range(len(b))]
        return cal(Y,rec+1)

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

    ans = solve(N,X)
    for i in range(N):
        print(ans[i])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

def f(num, one_count):
    ans = 0

    while num != 0:
        if ans == 0:
            pop_count = one_count
        else:
            pop_count = bin(num).count('1')
        num %= pop_count
        ans += 1
        
    return ans

def main():
    n = i_input()
    x = s_input()

    x10 = int(x, 2)
    one_count = x.count('1')

    for i in range(n):
        if x[i] == '0':
            num = x10 + 2 ** (n-1-i)
            print(f(num, one_count+1))
        else:
            num = x10 - 2 ** (n-1-i)
            print(f(num, one_count-1))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = str(input())
x = list(X)
def popcount(x):
  l = list(bin(x))[2:]
  return l.count('1')

for n in range(N):
  xn = x.copy()
  xn[n] = str(1 - int(xn[n]))
  xn = int(''.join(map(str, xn)), 2)
  count = 0
  while xn != 0:
    xn = xn%popcount(xn)
    count += 1
  print(count)

Submission status: Time Limit Exceeded

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

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

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



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

i=0


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

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

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

def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x = x + (x >> 8) 
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f

a = X.count("1")
ap, am = a+1, a-1
Flag = True

if am == 0:
  Flag = False
  am += 1

Ap = []
Am = []
temp = 1

for i in range(N):
  if i == 0:
    Ap.append(temp%ap)
    Am.append(temp%am)
  else:
    temp *= 2
    Ap.append(temp%ap)
    Am.append(temp%am)

Aps = 0
Ams = 0

for i in range(N):
  if X[-1-i] == "1":
    Aps += Ap[i]
    Aps %= ap
    Ams += Am[i]
    Ams %= am 

for i in range(N):
  cnt = 1
  if X[i] == "1":
    if Flag:
      p = Ams - Am[-1-i]
      p %= am
    else:
      cnt -= 1
      p = 0
  else:
    p = Aps + Ap[-1-i]
    p %= ap
  temp = p
  while temp > 0:
    temp %= popcount(temp)
    cnt += 1
  print(cnt)

Submission status: Time Limit Exceeded

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

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

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

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

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

Submission status: Time Limit Exceeded

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


N = int(input())
X = int(input(), 2)


for i in range(N-1, -1, -1):
    ans = 0
    Y = X ^ (1 << i)
    while Y > 0:
        Y %= popcount(Y)
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

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

for i in range(N):
    if X[i] == '1':
        tmp = - (1<<(N-i-1))
    else:
        tmp = (1<<(N-i-1))
    
    n = int(X, 2) + tmp    
    cnt = 0
    while n != 0:
        c = 0
        for j in bin(n):
            c += j=='1'
        n %= c
        cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import copy
N = int(input())
tmp = list(input())
X = [int(s) for s in tmp]
for i in range(0,N):
  tmp = copy.deepcopy(X)
  if tmp[i] == 1:
    tmp[i] = 0
  else:
    tmp[i] = 1
  tmp = [str(n) for n in tmp]
  num = int(''.join(tmp), 2)
  count = 0
  while(num != 0):    
    num_2 = bin(num)
    c = num_2.count('1')
    num_rem = num % c
    num = num_rem
    count = count+1
  print(count)

Submission status: Time Limit Exceeded

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

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


for i in range(1,N+1):
    
    count = 0
    
    if listX[i-1] == '0':
        listX[i-1] = '1' 
        strX = ''.join(listX) #所定位置のビットを反転させて文字列化したやつ
        listX[i-1] = '0'
        x = int(strX, 2) #10進法にしたやつ
        while x > 0:
            x = x % popcount(x)
            count += 1
        print(count)
    
    else:
        listX[i-1] = '0'
        strX = ''.join(listX)
        listX[i-1] = '1'
        x = int(strX, 2)
        while x > 0:
            x = x % popcount(x)
            count += 1
        print(count)

Submission status: Time Limit Exceeded

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

for i in range(1,N+1,1):
    count = 0
    Xi = X ^ 2**(N-i)
    while Xi!=0:
        count+=1
        Xi = Xi%bin(Xi).count("1")
    counts.append(count)

for k in counts:
    print(k)

Submission status: Time Limit Exceeded

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


for i in range(n):
    ith=s[i]
    j=n-(i+1)

    if(ith=='1'):
        y=x-2**j
        nos=ones-1
    else:
        y=x+2**j
        nos=ones+1

    c=0
    while(y>0):
        y=y%nos
        z=bin(y)[2:]
        nos=z.count('1')
        c+=1
    print(c)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

t = [0]

pl = np.array([1])
tmp = [np.array([1])]
for i in range(18):
    ne = np.concatenate([tmp[-1], tmp[-1]+1])
    tmp.append(ne)
pl = np.concatenate(tmp)

for n in range(1, N+1):
    c = pl[n-1]
    t.append(1 + t[n%c])

base = X.count("1")
basex = int(X, 2)
for n in range(N):
    if X[n] == "0":
        c = base + 1
        x = basex + 2**(N-n-1)
    else:
        c = base - 1
        x = basex - 2**(N-n-1)
    
    if c == 0:
        print(0)
    else:
        print(1 + t[x%c])

Submission status: Time Limit Exceeded

Solution code:
FAST_IO = 1
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()

    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())
rrmm = lambda n: [rrm() for _ in xrange(n)]
N = rri()

num = list(rr())
count = num.count('1')
pwrTwo_plus = [0] * N 
pwrTwo_plus[0] = 1 % (count+1)
if count>1:
    pwrTwo_minus = [0] * N 
    pwrTwo_minus[0] = 1 % (count-1)  
for i in range(1, N):  
    pwrTwo_plus[i] = pwrTwo_plus[i - 1] * (2 % count)  
    pwrTwo_plus[i] %= count+1
    if count>1:
        pwrTwo_minus[i] = pwrTwo_minus[i - 1] * (2 % count)  
        pwrTwo_minus[i] %= count-1

def getMod(_str, n, k, plus) :  
    
    # To store the result  
    res = 0
    i = 0
    j = n - 1
    while (i < n) :  
  
        # If current bit is 1  
        if (_str[j] == '1') :  
  
            # Add the current power of 2  
            if plus:
                res += (pwrTwo_plus[i] )  
                res %= k  
            else:
                res += (pwrTwo_minus[i] )  
                res %= k  
              
        i += 1
        j -= 1
  
    return res  

dic = {}
def f(x):
    if x in dic:
        return dic[x]
    if x== 0:
        return 0
    tmp = x% bin(x).count('1')
    dic[x] = f(tmp)+1
    return dic[x]
    


for i in range(N):
    if num[i] =='0':
        cur_count = count+1
    else:
        cur_count =count-1
    if cur_count ==0:
        print(0)
    else:
        if num[i] =='0':
            num[i] ='1'
            cur_num = getMod(num, N, cur_count, True)
            print(f(cur_num)+1)
            num[i] ='0'
        else:
            num[i] ='0'
            cur_num = getMod(num, N, cur_count, False)
            print(f(cur_num)+1)
            num[i] ='1'