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:
n = int(input())
x = input()
sum = x.count('1')
for i in range(n):
    if x[i]=='1':
        sum0=sum-1
        cnt=1
        str = x[:i]+'0'+x[(i+1):]
        if sum0!=0:
            p = int(str,2)%sum0
            while p:
                sum0 = bin(p).count('1')
                p = p%sum0
                cnt+=1
        else:
            cnt=0
    else:
        sum0=sum+1
        cnt=1
        str = x[:i]+'1'+x[(i+1):]
        p = int(str,2)%sum0
        while p:
            sum0 = bin(p).count('1')
            p = p%sum0
            cnt+=1
    print(cnt)

Submission status: Time Limit Exceeded

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

def toggleKthBit(n, k): 
    return (n ^ (1 << (k-1))) 
 
n,x=map(str,open(0).read().split());n=int(n)

for i in range(n,0,-1):
  ix=toggleKthBit(int(x,2),i)
  count=0
  while ix and n:
    ix=ix%f(ix)
    count+=1
  print(count)

Submission status: Time Limit Exceeded

Solution code:
memo = dict()
def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

def func(p):
    r = 0
    while p > 0:
        if p in memo:
            r += memo[p]
            break
        d = popcnt(p)
        # print(p, d)
        p %= d
        r += 1

    memo[p] = r
    return r


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

bit_total = 0
for i in range(n):
    if x[i] == "1":
        bit_total += 1

bin_num = int(x, 2)
L = [[0, 0] for _ in range(n)]  # [数, bit数]

for i in range(n):
    if x[i] == "1":
        L[i][0] = bin_num - 2**(n-i-1)
        L[i][1] = bit_total - 1
    else:
        L[i][0] = bin_num + 2 ** (n - i - 1)
        L[i][1] = bit_total + 1
# print(bit_total)
# print(L)

for i in range(n):
    p = L[i][0]
    d = L[i][1]
    ans = 0
    # print(p)
    if p > 0:
        ans += 1
        p %= d
        ans += func(p)

    print(ans)

Submission status: Time Limit Exceeded

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

NumberList = dict()
for i in range(N):
    if X[i] == '0':
        if i != 0:    
            tmp = X[:i] + '1' + X[i + 1:]
        else:
            tmp = '1' + X[i + 1:]
    else:
        if i != 0:    
            tmp = X[:i] + '0' + X[i + 1:]
        else:
            tmp = '0' + X[i + 1:]
    
    ten_m = int(tmp, 2)
    two_pop = bin(ten_m).count("1")
    
    ten_m_tmp = ten_m
    count = 0
    while ten_m != 0:
        if ten_m in NumberList:
            count += NumberList[ten_m]
            break
        ten_m = ten_m % two_pop
        two_pop = bin(ten_m).count("1")
        count += 1
    
    NumberList[ten_m_tmp] = count
    print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

n= int(input())
a=list(input())

v=a.count('1')

ans=[0]*n
A=[0]*n
# n以下の残り回数を記録
for i in range(n):
    x=i
    cnt=0
    while x>0:
        cnt+=1
        r = 0
        for j in range(19):
            if (x>>j)&1:
                r+=1
        x=x%r
    ans[i]=cnt

# 各桁をv＋１で割ったあまり
q = [0]*n
# 各桁をv-1で割ったあまり
r = [0]*n
for i in range(n):
    if a[i]=='1':
        if v!=0:
            q[i] = pow(2, n-i-1) % (v + 1)
        if v!=1:
            r[i] += pow(2, n-i-1) % (v - 1)
qq=sum(q)
rr=sum(r)

for i in range(n):
    if a[i]=='1':
        if v!=1:
            z = rr - pow(2,n-i-1)%(v-1)
            cnt = z % (v - 1)
            A[i] = 1 + ans[cnt]
    else:
        z=qq+pow(2,n-i-1)%(v+1)
        cnt=z%(v+1)
        A[i]=1+ans[cnt]

for i in A:
    print(i)

Submission status: Time Limit Exceeded

Solution code:

def popcount(n):
    base = 1
    count = 0
    
    while base <= n:
        if n & base:
            count += 1
        base <<= 1
    return count

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

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

base = 1 << (N - 1)
for _ in range(N):
    print(f(X ^ base))
    base >>= 1

Submission status: Time Limit Exceeded

Solution code:
def popcount(x):
    binary = bin(x)
    return sum([1 for c in binary if c == "1"])

def reverse_bin(X, ind):
    ret = X[:ind]
    ret += "1" if X[ind] == "0" else "0"
    ret += X[ind + 1:]

    return ret

def main():
    N = int(input())
    X_str = input()
    X = int(X_str, 2)
    for i in range(len(X_str)):
        count = 0
        X_tr = reverse_bin(X_str, i)
        x = int(X_tr, 2)
        while x != 0:
            x = x % popcount(x)
            count += 1
        print(count)
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def divbin(s,res):
  if int(s,2)==0:
    v=res
    return v
  # ss=int(s)
  val=int(s,2)
  count=bin(val).count("1")
  val%=count
  # t_str=bin(str(count))
  t_str=bin(val)
  t_str=t_str.replace("0b","")
  res+=1
  return divbin(t_str,res)


# def divbin(s,res):
#   if int(s,2)==0:
#     return
#   # ss=int(s)
#   val=int(s,2)
#   count=bin(val).count("1")
#   val%=count
#   # t_str=bin(str(count))
#   t_str=bin(val)
#   t_str=t_str.replace("0b","")
#   res+=1
#   divbin(t_str,res)
#   return

from copy import deepcopy
n=int(input())
x=input()

# c=str(bin(n))
# c=c.replace("0b","")
s=x
p=int(x)
cnt=bin(p).count("1")
x=list(x)
# print(cnt)
for i in range(len(x)):
  t=deepcopy(x)
  tmp=cnt
  ts=""
  if x[i]=="1":
    cnt-=1
    if i==0:
      ts="0"+s[i+1:]
    elif 1<=i<len(x)-1:
      ts=s[:i]+"0"+s[i+1:]
    elif i==len(x)-1:
      ts=s[:i]+"0"
  else:
    cnt+=1
    if i==0:
      ts="1"+s[i+1:]
    elif 1<=i<len(x)-1:
      ts=s[:i]+"1"+s[i+1:]
    elif i==len(x)-1:
      ts=s[:i]+"1"
  # ans=0
  # global ans
  ans=0
  ans=divbin(ts,ans)
  print(ans)



  # prev=
  # while cnt>0:

Submission status: Time Limit Exceeded

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

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


if __name__ == '__main__':
    N = int(input())
    X = input()
    num = int(X,2)
    for i in range(1,N+1):
        temp = num ^ (1 << (N-i))
        print(f(temp))

Submission status: Time Limit Exceeded

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

def func(n):
  ones = sum(list(map(int, bin(n)[2:])))
  rest = n%ones
  return rest

v = int(X,2)

for idx,x in enumerate(X):
  if x=="0":
    n = v+2**(N-idx-1)
  else:
    n = v-2**(N-idx-1)
  
  cnt = 0
  while n!=0:
    n = func(n)
    cnt += 1
  print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def bitcount(N):  # 立ってるbitの数
    bitcnt = [0]
    for _ in range(N):
        bitcnt += [i + 1 for i in bitcnt]
    return bitcnt


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

num, cnt = int(x, 2), x.count('1')
lbit = bitcount(18)
for i in range(n):
    ans = 0
    tmp = num ^ pow(2, n - (i + 1))
    ctmp = cnt - 2 * int(x[i]) + 1
    while tmp > 0:
        ans += 1
        tmp %= ctmp
        ctmp = lbit[tmp]
    print(ans)

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')
a = n % (c+1)
for i in range(1, N+1):
  if X[i-1] == '0':
    print(calc(a+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:
counts=[0, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 2, 3, 1, 2, 1, 2, 1, 1, 2, 3, 1, 2, 2, 3, 2, 2, 2, 2, 1, 2, 1, 2, 1, 2, 2, 3, 1, 2, 1, 3, 2, 2, 2, 2, 1, 2, 2, 3, 2, 2, 2, 1, 2, 2, 2, 2, 1, 2, 2, 3, 1, 2, 1, 2, 1, 1, 2, 3, 1, 2, 2, 3, 2, 2, 2, 2, 1, 1, 2, 3, 1, 2, 2, 2, 2, 2, 2, 2, 1, 3, 2, 3, 1, 2, 2, 3, 2, 2, 2, 3, 2, 2, 2, 2, 1, 2, 1, 3, 2, 2, 2, 1, 1, 2, 3, 3, 1, 2, 2, 3, 2, 3, 1, 2, 1, 2, 1, 2, 1, 2, 2, 3, 1, 2, 1, 3, 2, 2, 2, 3, 1, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 3, 3, 1, 2, 1, 3, 2, 2, 2, 2, 1, 2, 2, 2, 1, 3, 2, 2, 2, 2, 2, 2, 1, 2, 2, 3, 1, 1, 2, 2, 3, 3, 2, 2, 1, 2, 2, 3, 2, 2, 2, 2, 2]

n=int(input())
X=input()
num=int(X,2)
c=X.count('1')
for i in range(n):
    tmpn=num
    tmp1=c
    if X[i]=='0':
        tmpn+=2**(n-i-1)
        tmp1+=1
    else:
        tmpn-=2**(n-i-1)
        tmp1-=1
    count=0
    while tmpn>0:
        if tmpn<201:
            count+=counts[tmpn]
            break
        tmpn%=tmp1
        tmp1=bin(tmpn).count("1")
        count+=1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
def main():
  from sys import stdin
  n = int(stdin.readline())
  x_ = stdin.readline()[:n]
  x = int(x_, 2)
  for a in range(n):
    if x_[a] == '0':
      m = x + 2 ** (n - 1 - a)
    else:
      m = x - 2 ** (n - 1 - a)
    c = 0
    while m != 0:
      s = 0
      for i in list(str(bin(m))[2:]):
      	s += int(i)
      m = m % s
      c += 1
    print(c)

main()

Submission status: Time Limit Exceeded

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

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

from collections import defaultdict
d = defaultdict(lambda: -1)

Xmemo = defaultdict(lambda: -1)
Xmemo[0]=0

def dfs(X):
    if Xmemo[X]==-1:
        if d[X]==-1:
            popcount = bin(X).count("1")
            d[X]=popcount
        else:
            popcount = d[X]

        if popcount == 1:
            Xmemo[X]=1
            return 1
        Xmemo[X] = dfs(X%popcount)+1

    return Xmemo[X]


for i in reversed(range(0,n)):
    print(dfs(X^(1<<i) ))

Submission status: Time Limit Exceeded

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

def popctmod(n):
  return n % bin(n).count('1')


for i in range(N):
  if X[i]=='1':
    bitStr = X[:i] + '0' + X[i+1:]
  else:
    bitStr = X[:i] + '1' + X[i+1:]
  num = int(bitStr, 2)
  res = 0
  while num!=0:
    num = popctmod(num)
    res += 1
  print(res)

Submission status: Time Limit Exceeded

Solution code:
def popcount(x):
  a = bin(x)
  return a[2:].count('1')

def calc(x):
  c = 0
  while(x > 0):
    x = x % popcount(x)
    c += 1
  return c

n=int(input())
x=input()
for i in range(0,n):
  j = 0
  if x[i] == '0':
    j = 1
  k = x[:i] + str(j) + x[i+1:]
  l = int(k, 2)
  print(calc(l))

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:
def sol():
    n=int(input())
    x=input()
    chk=0
    for i,j in enumerate(x[::-1]):
        if j=="1":
            chk+=2**i
    c,d={},{}
    ans=[]
    for i,j in enumerate(x[::-1]):
        p=pow(2,i)
        if j=="1": t=chk-p
        else: t=chk+p
        s=t
        cnt=0
        while t:
            if t not in c:
                pc=bin(t).count("1")
                c[t]=pc
            else:
                pc=c[t]
            t%=pc
            cnt+=1
            if t in d:
                cnt+=d[t]
                break
        if s not in d:
            d[s]=cnt
        ans.append(cnt)
    for i in ans[::-1]:
        print(i)

if __name__=="__main__":
    sol()

Submission status: Time Limit Exceeded

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

val = 0
cnt = 0

for i in range(0,n):
    if s[i] == '1':
        cnt += 1
        val += int(2**(n-i-1))

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

for i in range(0,n):
    vall = val
    ans = 0
    if s[i] == '0':
        o = cnt + 1
        vall += int(2**(n-i-1))
        while vall != 0:
            vall = vall % (o)
            o = countSetBits(vall)
            ans += 1
    else:
        o = cnt - 1
        vall -= int(2**(n-i-1))
        while vall != 0:
            vall = vall % (o)
            o = countSetBits(vall)
            ans += 1
    print(ans)

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=bin(n)
        pop=n2.count('1')
        n=n%pop
    return ans

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

Submission status: Time Limit Exceeded

Solution code:
def popcount(num):
    bin_num = bin(num)[2:]
    count = 0
    for i in bin_num:
        count += int(i)
    return count


N = int(input())

AAA = [0 for x in range(2 ** N)]
for i in range(1, 2**N):
    AAA[i] = AAA[i % popcount(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:
n = int(input())
x = input()
c = x.count("1")
memo = [0]*(n+1)
p = [0]*n
d = 1
for i in range(n)[::-1]:
    p[i] = d
    d *= 2
s = int(x,2)
for i in range(n):
    if x[i] == "1":
        tmp = s-p[i]
        ctmp = c-1
    else:
        tmp = s+p[i]
        ctmp = c+1
    cnt = 0
    while tmp != 0:
        cnt += 1
        tmp %= ctmp
        tmp2 = tmp
        ctmp = 0
        while tmp2 != 0:
            tmp2,r = tmp2//2,tmp2%2
            ctmp += r
    print(cnt)

Submission status: Time Limit Exceeded

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

def solve(X, cnt):
    ans = 0
    x = int(X, 2)
    while x > 0:
        x %= cnt
        ans += 1
        cnt = popcnt(x)
    print(ans)

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

cnt = 0
for i in range(len(X)):
    if X[i] == '1':
        cnt += 1

X = list(X)
for i in range(len(X)):
    if X[i] == '0':
        X[i] = '1'
        solve(''.join(X), cnt+1)
        X[i] = '0'
    else:
        X[i] = '0'
        solve(''.join(X), cnt-1)
        X[i] = '1'

Submission status: Time Limit Exceeded

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

def ten(s):
    n = 0
    p = 0
    for i in range(N)[::-1]:
        n += (int(s[i]) * 2**p)
        p += 1
    return n

def popcount(n):
    cnt = 0
    while n != 0:
        if n % 2 == 1:
            cnt += 1
        n //= 2
    return cnt

for i in range(N):
    n = (1 << N-1-i) ^ ten(X)
    ans = 0
    while n != 0:
        t = popcount(n)
        n = n % t
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

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

    for i in range(N):
        count = 0
        if X[i] == "1":
            nX = int( X[:i] + "0" + X[i+1:] , 2)
        if X[i] == "0":
            nX = int(X[:i] + "1" + X[i+1:] , 2)           
        for j in range(N):
            if nX == 0:
                break
            else:
                nX %= bin(nX).count("1")              
                count += 1
        print(count)
resolve()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = '0b' + input()

for i in range(n):
    lisx = list(x)
    lisx[i+2] = str(1 - int(lisx[i+2]))
    xx = ''.join(lisx)
    intx = int(xx, 2)
    len1 = xx.count('1')

    cnt = 0
    while True:
        if intx == 0:
            print(cnt)
            break
        
        intx = intx % len1
        xx = bin(intx)
        len1 = xx.count('1')
        cnt += 1

Submission status: Time Limit Exceeded

Solution code:
n,x=int(input()),input()
o=x.count("1")
l=[0]*(o+1)
a=int(x,2)

for i in range(1,o+1):
    ret=0
    t=i
    while t:
        t%=bin(t).count("1")
        ret+=1
    l[i]=ret

c=pow(2,n-1)
for b in x:
    if b=="1":
        k=a-c
        gg=o-1
    else:
        k=a+c
        gg=o+1
    if k:
        k%=gg
        print(1+l[k])
    else:print(0)
    c//=2

Submission status: Time Limit Exceeded

Solution code:
def popcount(n):
    cnt = 0
    for i in range(n):
        if ((n >> i) & 1):
            cnt +=1
    return cnt

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

def numChange(list, i):
    num = 0
    j = 0
    while True:
        if i < 0:
            break
        num += int(list[i]) * pow_r(2, j)
        i -= 1
        j += 1
    return num

def pow_r(x, n):
    if n == 0:
        return 1
    if n % 2 == 0:
        return pow_r(x ** 2, n // 2)
    else:
        return x * pow_r(x ** 2, (n - 1) // 2)

if __name__ == "__main__":
    n = int(input())
    x = input()
    xList = list(x)
    k = len(xList) - 1
    for i in range(n):
        if xList[i] == '0':
            xList[i] = '1'
        else:
            xList[i] = '0'
        xNum = int("".join(xList), 2)
        print(f(xNum))
        if xList[i] == '0':
            xList[i] = '1'
        else:
            xList[i] = '0'

Submission status: Time Limit Exceeded

Solution code:
memo = dict()

def func(p):
    r = 0
    while p > 0:
        if p in memo:
            r += memo[p]
            break
        d = bin(p).count("1")
        # print(p, d)
        p %= d
        r += 1

    memo[p] = r
    return r


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

bit_total = 0
for i in range(n):
    if x[i] == "1":
        bit_total += 1

bin_num = int(x, 2)
L = [[0, 0] for _ in range(n)]  # [数, bit数]

for i in range(n):
    if x[i] == "1":
        L[i][0] = bin_num - 2**(n-i-1)
        L[i][1] = bit_total - 1
    else:
        L[i][0] = bin_num + 2 ** (n - i - 1)
        L[i][1] = bit_total + 1
# print(bit_total)
# print(L)

for i in range(n):
    p = L[i][0]
    d = L[i][1]
    ans = 0
    # print(p)
    if p > 0:
        ans += 1
        p %= d
        ans += func(p)

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = input()
a = []
s = int(x, 2)
k = x.count('1')

for i in range(n):
    a.append(int(x[i]))
#print(a)
#print(s)

for i in range(n):
    if int(x[i]) == 0:
        S = s + 2**(n-i-1)
        K = k + 1
    else:
        S = s - 2**(n-i-1)
        K = k - 1
    ans = 0
    while S != 0:
        S = S % str(bin(S)).count('1')
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

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

    def popcount(num):
        return bin(num).count("1")
    popc_X = popcount(X)
    pop_table = {}
    for i in range(1, N+1):
        pop_table[i] = popcount(i)
    
    def f(x, factor):
        temp = x
        count = 0
        while temp > 0:
            if temp > N:
                # print(temp, popc_X)
                temp = temp % (popc_X + factor)
                count += 1
                # print(temp)
                continue
            temp = temp % pop_table[temp]
            count += 1
        return count
    
    ans = [0]*N
    for i in range(0, N):
        xi = X ^ (1 << i)
        # print(xi, "xi")
        if xi & (1<<i):
            factor = 1
        else:
            factor = -1
        ans[N-i-1] = f(xi, factor)
    for a in ans:
        print(a)
main()

Submission status: Time Limit Exceeded

Solution code:
def popcount(x):
    cnt = 0
    while x != 0:
        cnt += 0 if x % 2 == 0 else 1
        x //= 2
    return cnt

def f(x):
    cnt = 0
    b = int(x, 2)
    while b != 0:
        n = popcount(b)
        b = b % n
        cnt += 1

    return cnt

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

for i in range(1, N+1):
    tmp = X
    c = '0' if tmp[i-1] == '1' else '1'
    tmp = tmp[:i-1] + c + tmp[i:]
    print(f(tmp))

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, int(N+1/10)):
    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:
N = int(input())
X = input()

def k_sum(n):
    ret = 0
    for i in str(n):  
        ret += int(i)
    return ret

def test(n):
    ret = 0
    while(n != 0):
        temp = k_sum(bin(n)[2:])
        n %= temp
        ret += 1
    return ret

p = int(X, 2)

ans = test(p)
for i in range(N):
    if X[i] == "1":
        print(test(p - 2 ** (N - i - 1)))
    else: 
        print(test(p + 2 ** (N - i - 1)))

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    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 = pow(2,(n-1))
        
    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)
        
if __name__ == '__main__':
    main()
"""
#print(ans_li)
for i in range(n):
    print(ans_li[n-1-i])
"""

Submission status: Time Limit Exceeded

Solution code:
from copy import copy

n = int(input())
x = input()
#x = eval("0b" + input())
#n = 2 * 10 ** 5
#x = 2**(n - 1) - 1


def popcount(num):
    s = 0
    b = num
    while b != 0:
        s += (b & 1 > 0)
        b >>= 1
    return s

x_count = x.count("1")
table = [-1] * (n + 1)

for i in range(n):
    xi = copy(x)
    if xi[i] == "1":
        xi = list(xi)
        xi[i] = "0"
        xi = "".join(xi)
        xi_count = x_count - 1
    else:
        xi = list(xi)
        xi[i] = "1"
        xi = "".join(xi)
        xi_count = x_count + 1
    xi = eval("0b" + xi)
    if xi == 0:
        print(0)
        continue
    cnt = 1
    xi %= xi_count
#    print(xi_count)
#    l = []
    while xi != 0:
#        if table[xi] != -1:
#            cnt = table[xi]
#            break
#        l.append(xi)
        cnt += 1
        xi %= popcount(xi)
#    for hoge in l:
#        table[hoge] = cnt
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n= int(input())

ans_count = [-1 for _ in range(n)]

for i in range(1,n+1):
    b = bin(i)
    b=list(b)
    a = b.count("1")
    f = i%a
    if f == 0:
        ans_count[i-1]=1
    else:
        ans_count[i-1] = ans_count[f-1]+1

ans_count = [0]+ ans_count


inp = input()
x = list(inp)

org = int(inp, 2)
if "1" in x:      
    l = x.count("1")
else:
    l = 0


# for _ in range(n):
#     print(0)

for i in range(n):
    a = x[i]
    if a=="0":
        N = org+(2**(n-i-1))
        m= N%(l+1)
        print(ans_count[m]+1)
    else:
        if l ==1:
            print(0)
        else:
            N = org-(2**(n-i-1))
            m=N%(l-1)
            print(ans_count[m]+1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    sys.setrecursionlimit(200000)
    N = int(input())
    Y = input()
    X = int(Y,2)
    memo = {}
    Ycnt = Y.count("1")
    memo2 = {}

    def f(n,cnt):
        if n == 0:
            return 0
        if n not in memo:
            d = cnt
            nx = n%d
            if nx not in memo2:
                binNx = bin(nx)
                nxCnt = binNx.count("1")
                for i in range(len(Y)-len(binNx)):
                    tmp = nx
                    tmp <<= i
                    memo2[tmp] = nxCnt
            else:
                nxCnt = memo2[nx]
            memo[n] = f(nx,nxCnt)+1
        return memo[n]

    for i in range(N):
        if Y[i] == "1":
            cnt = Ycnt - 1
        else:
            cnt = Ycnt + 1
        a = N-i
        tmp = 2**(a-1)
        n = X^tmp
        print(f(n,cnt))
main()

Submission status: Time Limit Exceeded

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

def f(n):
    return int(n.count("1"))
    
    
for i in range(N):
    counter = 0
    temp = X[:]
    if temp[i] == "0":
        temp[i] = "1"
    else:
        temp[i] = "0"
#######################
    
    while int(str(''.join(temp)), 2) != 0:
        counter += 1
        a = int(str(''.join(temp)), 2) % f(temp)
       
        
        temp = list(str(bin(a)))[:]
        

        
    print(counter)

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))

def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f

n = int(input())
x = input()
s = ''
ans = [0 for _ in range(2**n + 1)]
pop = 0
for i in x:
    if i == '1': pop += 1

for i in range(n):
    if x[i] == '0':
        s = x[:i] + '1' + x[i+1:]
        pc = pop + 1
    else:
        s = x[:i] + '0' + x[i+1:]
        pc = pop - 1
    num = int(s, 2)
    cnt = 0
    road = []
    while True:
        if num == 0:
            print(ans[int(s, 2)])
            break
        if ans[num] > 0:
            for r in road: ans[r] += ans[num]
            print(ans[int(s, 2)])
            break
        road += [num]
        num = (num%pc)
        cnt += 1
        pc = popcount(num)
        for r in road: ans[r] += 1

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=[0]*(n+1)
s=input()
num=0
def al(x):
    pop=0
    k=1
    while x>=k:
        if x&k: pop+=1
        k<<=1
    return pop
temp=0
k=1
for i in reversed(range(0,len(s))):
    if int(s[i]):
        num+=k
        temp+=1
    k<<=1
k=1
for i in reversed(range(1,n+1)):
    num1=num^k
    if num1:
        l[i]+=1
        num1%=temp+(1 if num1>num else -1)
    while num1:
        l[i]+=1
        num1%=al(num1)
    k<<=1
for i in range(1,n+1):
    print(l[i])

Submission status: Time Limit Exceeded

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

first_cnt = X.count("1")
DP = [0]*(N+1)
for i in range(1,N+1):
    DP[i] = DP[i%format(i, 'b').count("1")]+1
X_ = int(X,2)
for i in range(N):
    tmp = X_
    cnt = first_cnt
    if X[i] == "0":
        tmp += 2**(N-1-i)
        cnt += 1
    else:
        tmp -= 2**(N-1-i)
        cnt -= 1
    
    if tmp == 0:
        print("0")
        continue
    tmp %= cnt

    print(DP[tmp%cnt]+1)

Submission status: Time Limit Exceeded

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

dp=[-1]*(n+1)

dp[0]=0
dp[1]=1
co=[-1]*(n+1)

def fun(num,step):
    num2=num%sum(list(map(int,bin(num)[2:])))
    if dp[num2]!=-1:
        dp[num]=dp[num2]+step
    else:
        fun(num2,step+1)

for i in range(2,n+1):
    fun(i,1)

num1=''.join(x)
num2=int(num1,2)
su = sum(list(map(int,x)))

for i in range(n):
    num4=num2
    su2=su
    if x[i]=='1':
        num4-=2**(n-1-i)
        su2-=1
    else:
        num4+=2**(n-1-i)
        su2+=1
    if su2 == 0:
        print('0')
        continue
    elif num4<=n:
        print(dp[num4])
    else:
        num3=num4%su2
        print(dp[num3]+1)

Submission status: Time Limit Exceeded

Solution code:
import copy
n=int(input())
x=list(input())
b=[]
for i in range(2**19):
  b.append(format(i,'0'+str(19)+'b'))
ct=[0]*(n+1)
for i in range(1,n):
  ct1=0
  for j in range(len(b[i])):
    if b[i][j]=='1':
      ct1+=1
  ct[i]=i%ct1

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

moda=[]
modb=[]
modc=[]
for i in range(n):
  if CT>=2:
    moda.append(pow(2,i,CT-1))
  if CT>=1:
    modb.append(pow(2,i,CT))
  modc.append(pow(2,i,CT+1))


x.reverse()
za=0
zb=0
zc=0
for i in range(n):
  if x[i]=='1':
    if CT>=2:
      za+=moda[i]
      za%=(CT-1)
    if CT>=1:
      zb+=modb[i]
      zb%=CT
    zc+=modc[i]
    zc%=(CT+1)
x.reverse()
moda.reverse()
modc.reverse()

for i in range(n):
  y=copy.copy(x)
  y2=y[i]
  y[i]=str(1-int(y[i]))
  ct1=0
  for j in range(n):
    if y[j]=='1':
      ct1+=1
  if ct1==0:
    print(0)
  else:
    if y2=='1':
      z=copy.copy(za)
      z-=moda[i]
      z%=ct1
    else:
      z=copy.copy(zc)
      z+=modc[i]
      z%=ct1
    
    
    
    ans=1
    while z!=0:
      z=ct[z]
      ans+=1
    print(ans)