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:

def popcount(n):
  return bin(n).count("1")
  
def func(n, c):
  next = n%popcount(n)
  if ans[next]!=-1:
    return ans[next]+c+1    
  c+=1
  if next == 0:
    return c
  else:
    return func(next, c)

ma = "11111111111111111111111"
maint = int(ma, 2)+1
n=int(input())
x=input()
ans = [-1]*maint
for i in range(1, maint):
  ans[i] = func(i, 0)

#print(ans[0:10])
  
for i in range(n):
  temp=list(x)
  if x[i]=="0":
    temp[i]="1"
  else:
    temp[i]="0"
  itemp = int("".join(temp), 2)
  #print(itemp)
  print(ans[itemp])

Submission status: Time Limit Exceeded

Solution code:
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

import copy

n=ni()
x=[_ for _ in input()]

def popcount(nn):
  ans=0
  while nn>0:
    if nn%2==1:
      ans+=1
    nn>>=1
  return ans

pc = dict()


def f(nn):
  ans=0
  while nn>0:
    ans+=1
    ppc=1
    if nn in pc:
      ppc = pc[nn]
    else:
      ppc = popcount(nn)
      pc[nn] = ppc
    nn=nn%ppc
  return ans

for i in range(n):
  xx = copy.copy(x)
  if xx[i]=='1':
    xx[i]='0'
  else:
    xx[i]='1'
  print(f(int(''.join(xx),2)))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
from collections import Counter

N=int(input())
X=[i for i in input()]

@lru_cache(maxsize=4*(10**5))
def _f(n):
    string=bin(n)[2:]
    popcount=Counter(string)['1']
    return n%popcount

@lru_cache(maxsize=4*(10**5))
def f(n):
    retval=0
    while n!=0:
        retval+=1
        n=_f(n)
    return retval

for i in range(N):
    if X[i]=='1':
        X[i]='0'
    else:
        X[i]='1'
    Xi="".join(X)
    n=int(Xi,2)
    print(f(n))
    if X[i]=='1':
        X[i]='0'
    else:
        X[i]='1'

Submission status: Time Limit Exceeded

Solution code:
import collections

n = int(input())
x = input()
dic = collections.defaultdict(int)
#dic_count = collections.defaultdict(int)
one_count = x.count("1")

for i in range(1,n+1):
    cnt = 0
    nm = bin(i).count("1")
    tmp = i
    while tmp:
        tmp %= nm
        nm = bin(tmp).count("1")
        cnt += 1
    dic[i] = cnt

if one_count == 1:
    cnt = 0
    for i in range(n):
        if x[i] == "1":
            print(0)
        else:
            num = int(x,2) + 2 ** (n - i - 1)
            num %= (one_count+1)
            if num != 0:
                print(dic[num]+1)
            else:
                print(1)
else:
    for i in range(n):
        tmp_count = one_count
        num = int(x,2)
        if x[i] == "1":
            num -= 2 ** (n - i - 1)
            tmp_count -= 1
        else:
            num += 2 ** (n - i - 1)
            tmp_count += 1
        num %= tmp_count
        if num != 0:
            print(dic[num]+1)
        else:
            print(1)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

import sys

sys.setrecursionlimit(4100000)

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


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


# aは1の数


@lru_cache(None)
def calc2(a):
    if a == 0:
        return 0
    return calc2(a % popcnt(a)) + 1


ans = [0] * n
cnt = x.count("1")

kotae = [0] * (cnt + 2)
for i in range(cnt + 1):
    kotae[i] = calc2(i)


for i in range(n):
    if x[i] == "1":
        temp = cnt - 1
    else:
        temp = cnt + 1
    t = 1 << (n - i - 1)
    if num ^ t:
        ans[i] = calc2((num ^ t) % temp) + 1
    else:
        ans[i] = 0
print(*ans, sep="\n")

Submission status: Time Limit Exceeded

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

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

# print('input >>')
N = int(input())
# N = 10**4

X = input()
# X = '1' * 10**4

X10 = int(X, 2)

for i, _ in enumerate(X):
    if X[i] == '0':
        X10anti = X10 + 2**(N-i-1)
    if X[i] == '1':
        X10anti = X10 - 2**(N-i-1)
    print(f(X10anti))

# print('-----output-----')

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
input = sys.stdin.readline

def bitsoncount(x):
    return bin(x).count('1')

############ ---- Input Functions ---- ############
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(list(s[:len(s) - 1]))
def invr():
    return(map(int,input().split()))

n = inp()

s = input()
x = s.count("1")

for i in range(n):
    t = x
    if(s[i] == "1"):
        s = s[:i] + "0" + s[i+1:]
        t = t-1
    else:
        s = s[:i] + "1" + s[i + 1:]

        t = t+1

    ct = 0
    num = int(s,2)
    popct = t
    while(num):
        ct = ct + 1
        num = num%popct
        popct = bitsoncount(num)
    print(ct)



    if (s[i] == "1"):
        s = s[:i] + "0" + s[i + 1:]
    else:
        s = s[:i] + "1" + s[i + 1:]

Submission status: Time Limit Exceeded

Solution code:
def func(n, s):
    x = int(s, 2)
    x ^= 2 ** n
    cnt = 0
    while x > 0:
        val = str(bin(x)).count('1')
        x %= val
        cnt += 1
    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:
def game(n):
    count = 0
    while(n>0):
        x = bin(n).count('1')
        #print(x)
        n %=x
        count+=1
    return count
    
n = int(input())
s = input()
curr  = 1;
ans = []
temp = int(s,2)
for i in range(n):
    #print(temp,end = " ")
    temp = temp ^ curr
    ans.append(game(temp))
    temp = temp ^ curr
    #print(temp)
    curr *= 2 
for i in range(n-1,-1,-1):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
memo = {}

# n = int
def popcount(n):
    return format(n, '08b').count("1")

# n = int
def f(n):
    if n == 0:
        return 0        
    elif n in memo:
        return memo[n]
    
    cnt = f(n % popcount(n)) + 1
    memo[n] = cnt
    return cnt

def resolve():
    cnt = 0
    n = int(input())
    X = input()
    x = list(X)
    for i in range(n):
        x[i] = "1" if X[i] == "0" else "0"
        print(f(int("".join(x), 2)))
        x[i] = X[i]

resolve()

Submission status: Time Limit Exceeded

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue
import numpy as np
# sympy as syp(素因数分解とか)
Mod = 1000000007
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1] 
for i in range(2, 10**5 + 1):
    fact.append((fact[-1] * i) % Mod)
    inv.append((-inv[Mod % i] * (Mod // i)) % Mod)
    factinv.append((factinv[-1] * inv[-1]) % Mod)
    
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % p
    
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[y] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)
import string
def main():  #startline-------------------------------------------
    n = int(input())
    x = input()
    xint = 0
    for i in range(len(x)):
        if x[len(x)-1-i] == "1":
            xint += 2 ** i
    def countbin(i): #f(x)を求める関数
        bin_i = bin(i)
        popcount = bin_i.count("1")
        cnt = 0
        while i != 0:
            i = i % popcount
            cnt += 1
            popcount = bin(i).count("1")
        return cnt
    for i in range(len(x)):
        if x[i] == "0":
            print(countbin(xint + 2 ** (len(x) - i - 1)))
        else:
            print(countbin(xint - 2 ** (len(x) - i - 1)))

if __name__ == "__main__":
    main() #endline===============================================

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n=int(input())
x=input()
m=int(x,2)
c=x.count("1")
l=[1]*(2*10**5+2)
for i in range(1,2*10**5+1):
    l[i]=l[i%str(bin(i)).count("1")]+1
for i in range(n):
    p=1
    if x[i]=="1":
        p=-1
    if (c+p)==0:
        print(0)
        continue
    nex=(m+p*(2**(n-i-1)))%(c+p)
    if nex==0:
        print(1)
    else:
        print(l[nex])

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    sys.setrecursionlimit(200000)
    N = int(input())
    X = int(input(),2)
    memo = {}

    def f(n):
        if n == 0:
            return 0
        if n not in memo:
            d = bin(n).count("1")
            nx = n%d
            memo[n] = f(nx)+1
        return memo[n]

    for i in range(N):
        a = N-i
        tmp = 2**(a-1)
        n = X^tmp
        print(f(n))
main()

Submission status: Time Limit Exceeded

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

X=0

for i in range(N):
  if tmp[N-1-i]=="1":
    X+=1<<i

cache={}
def popcount(n):
  s=0
  if cache.get(n)!=None:return cache.get(n)
  for i in range(N):
    if (1<<i)&n:
      s+=1
  cache[n]=n%s
  return n%s

def popnum(n):
  s=0
  while n:
    s+=1
    n=popcount(n)
  return s

for i in range(N):
  print(popnum((X^(1<<(N-1-i)))))

Submission status: Time Limit Exceeded

Solution code:
'''Author- Akshit Monga'''
n=int(input())
x=input()
for i in range(n):
    if x[i]=='1':
        temp='0'
    else:
        temp='1'
    var=x[0:i]+temp+x[i+1:]
    pivot=int(var,2)
    a=0
    while pivot:
        a+=1
        c=bin(pivot).count('1')
        pivot=pivot%c
    print(a)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
# import pysnooper
N = int(input())
s = input()


# @pysnooper.snoop()
def f(num):
    count = 0
    while num:
        divider = Counter(bin(num)[2:])['1']
        num = num % divider
        count += 1
    return count

def revert(x):
    if (x == '0'): return '1'
    else:
        return '0'

for i in range(len(s)):
    cur = s[:i] + revert(s[i]) + s[i + 1:]
    # print(cur)
    print(f(int(cur, 2)))

Submission status: Time Limit Exceeded

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

ppc = {}

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

bit = int('0b'+x,0)
for i in range(n,0,-1):      
  print(popcount(bit ^ (1 << (i-1))))

Submission status: Time Limit Exceeded

Solution code:
d = {}
def popcount(n):
    if n not in d:
        d[n] = sum(x == '1' for x in bin(n))
    return d[n]
def f(n):
    c = 0
    while n != 0:
        n %= popcount(n)
        c += 1
    return c

n, X = open(0).read().split()
n = int(n)
x = int(X, 2)
X = list(map(int, X))
c = popcount(x)
for i in range(n):
    if X[i]:
        y = x - 2**(n-i-1)
        t = c-1
    else:
        y = x + 2**(n-i-1)
        t = c+1
    if y != 0:
        y %= t
        print(f(y)+1)
    else:
        print(0)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
K = int(input(),2)
for i in range(N):
  c = K^2**(N-i-1)
  cnt = 0
  while c!=0:
    c = c%bin(c).count('1')
    cnt=cnt+1
  print(cnt)

Submission status: Time Limit Exceeded

Solution code:
K = N = int(input())
C = input()
pre = [0 for _ in range(2*10**5+1)]

for i in range(2*10**5+1):
    N = i
    ans = 0
    while N > 0:
        cnt = 0
        for c in format(N,"b"):
            if c == "1":
                cnt += 1
        N %= cnt
        ans += 1
    pre[i] = ans


for i in range(K):
    if C[i] == "1":
        X = C[:i] + "0" + C[i+1:]
    else:
        X = C[:i] + "1" + C[i+1:]

    if int(X, 2) > 2*10**5:
        cnt = 0
        for c in format(int(X, 2),"b"):
            if c == "1":
                cnt += 1
        print(pre[int(X, 2) % cnt] + 1)
    else:
        print(pre[int(X,2)])

Submission status: Time Limit Exceeded

Solution code:
from copy import copy

def f(n,cnt):
    if n==0:
        return cnt
    popcnt = bin(n).count('1')
    return f(n%popcnt,cnt+1)

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


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

    y = ''.join(y)
    m = int(y,2)
    print(f(m,0))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
from functools import lru_cache

sys.setrecursionlimit(4100000)
d = defaultdict(int)

@lru_cache(maxsize=None)
def f(x):
    if x == 0:
        return 0
    if d[x]:
        return d[x]
    
    if x % (bin(x).count('1')) == 0:
        d[x] = 1
        return 1

    d[x] = f(x % (bin(x).count('1'))) + 1

    return d[x]


def main():
    N = int(input())
    X = input()
    O = int(X, 2)
    Y = list(X)
    ans = [0] * N
    pre = 1
    for i in range(N-1,-1,-1):
        if Y[i] == '1':
            tmp = O - pre
        else:
            tmp = O + pre
        ans[i] = f(tmp)
        pre *= 2

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

dp[0]=0
dp[1]=1

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

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

for i in range(n):
    x2=x.copy()
    if x[i]=='1':
        x2[i]='0'
    else:
        x2[i]='1'
    num1=''.join(x2)
    num2=int(num1,2)
    su = sum(list(map(int,x2)))
    if su == 0:
        print('0')
        continue
    else:
        num3=num2%su
    print(dp[num3]+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

from functools import lru_cache

def popcount1(n):
    ans = 0
    while n > 0:
        ans += n & 1
        n //= 2
    return ans

bit = {}
@lru_cache(maxsize=None)
def popcount2(bits):
    if bits in bit:
        return bit[bits]

    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555)
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333)
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f)
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff)
    ans = (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff)
    bit[bits] = ans
    return bit[bits]


memo = {0: 0}
@lru_cache(maxsize=None)
def rec(n):
    if n in memo:
        return memo[n]
    
    p = popcount2(n)
    new_n = n % p
    ans = rec(new_n) + 1
    memo[n] = ans
    return memo[n]


def submit():
    n = int(input())
    x = input()
    x = int('0b' + x, 0)

    # 前準備
    for i in range(1, 200001):
        rec(i)

    ans = []
    base_bit = popcount1(x)
    bit[x] = base_bit
    for i in range(1, n + 1):
        mask = 1 << (n - i)
        xi = x ^ mask
        if x & mask:
            bit[xi] = bit[x] - 1
        else:
            bit[xi] = bit[x] + 1
        ans.append(rec(xi))

    for a in ans:
        print(a)


if __name__ == "__main__":
    submit()

Submission status: Time Limit Exceeded

Solution code:
CNT = 0
def popcount(n, bit):
    global CNT
    if n == 0:return
    CNT += 1
    new = bin(n%bit).count("1")
    popcount(n%bit, new)
    
n = int(input())
x = input()
cnt = x.count('1')
num = 0
for i in range(n):
    num += int(x[-(i + 1)]) * pow(2, i)
    
for i in range(n):
    res = 0
    if x[i] == "1":
        temp = num - pow(2, n - i - 1)
        popcount(temp, cnt - 1)
        print(CNT)
        CNT = 0
    else:
        temp = num + pow(2, n - i - 1)
        popcount(temp, cnt + 1)
        print(CNT)
        CNT = 0

Submission status: Time Limit Exceeded

Solution code:
import functools


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


@functools.lru_cache(maxsize=None)
def f(x):
    if x == 0:
        return 0
    else:
        return f(x % popcount(x)) + 1


if __name__ == "__main__":
    N = int(input())
    X = int(input(), 2)
    for i in reversed(range(N)):
        if (1 << i) & X:
            X_ = X & ~(1 << i)
        else:
            X_ = X | (1 << i)

        print(f(X_))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)

mod = 1000000007
inf = int(1e18)

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft


memo = {}

def countbit(x):
    i = 0
    cnt = 0
    while x >= 1<<i:
        if x & (1<<i):
            cnt += 1
        i += 1
    return cnt


def count(x, c):
    if c == 0:
        return 0
    s = 1
    x = x % c
    while x != 0:
        s += 1
        x = x % countbit(x)
    return s

def main():
    n = int(input())
    x = int(input(), 2)
    c = countbit(x)
    for i in range(n):
        y = x ^ (1<<(n-i-1))
        cc = (x >> (n-i-1)) & 1
        s = count(y, c - 1 if cc else c + 1)
        print(s)


main()

Submission status: Time Limit Exceeded

Solution code:
def toggleKthBit(n, k): 
  return (n ^ (1 << (k-1))) 


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

ans = -1
for i in range(N, 0, -1):
  count = 0
  ans = toggleKthBit((int(str(X), 2)), i)
  while ans != 0:
    ans = ans % bin(ans).count("1")
    count += 1
  print(count)

Submission status: Time Limit Exceeded

Solution code:

def g(n):
    c = 0
    while n > 0:
        p = 0
        n2 = n
        while n2 > 0:
            if n2%2 == 1:
                p += 1

            n2 //= 2

        n %= p
        c += 1

    return c


def h(b, m):
    x = 1
    for _ in range(b):
        x = x*2%m

    return x


def f(N, X):
    b = sum(1 if x == '1' else 0 for x in X)

    Xplus = 0
    Xminus = 0

    for x in X:
        Xplus = (Xplus*2 + (1 if x == '1' else 0))%(b+1)
        
        if b > 1:
            Xminus = (Xminus*2 + (1 if x == '1' else 0))%(b-1)

    for i in range(N):
        if X[i] == '0':
            X2 = (Xplus + h(N-i-1, b+1))%(b+1)
            print(g(X2) + 1)
        elif b > 1:
            X2 = (Xminus - h(N-i-1, b-1))%(b-1)
            print(g(X2) + 1)
        else:
            print(0)


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

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
X_base=input()
for i in range(N):
  X=X_base
  #ビット反転
  if X[i]=="0":
    X=X[0:i]+"1"+X[i+1:]
  else:
    X=X[0:i]+"0"+X[i+1:]
  c=0
  #########################
  for _ in range(10**10):
    X=str(int(X))
    if X=="0"*len(X):
      break
    else:
      popcount=X.count("1")
      X=bin(int(X,2)%popcount)
      X=X[2:]
      c+=1
  print(c)

Submission status: Time Limit Exceeded

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

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

if __name__ == '__main__':
  N = int(input())
  X = input()
  for i in range(N):
    tmp = list(X)
    if tmp[i] == "0":
      tmp[i] = "1"
    else:
      tmp[i] = "0"
    target = "".join(tmp)
    print(AnythingGoestoZero(int(target, 2)))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = input()
MAX = 2 * (10 ** 5) + 1

base = [0] * (MAX+1)
for num in range(1, MAX+1):
  cnt = 0
  bin_num = bin(num)[2:]
  for j in bin_num:
    cnt += int(j)
  p = num % cnt
  base[num] = base[p]+1

for i in range(N):
  if(X[i] == '0'):
    p = X[:i] + '1' + X[i+1:]
  else:
    p = X[:i] + '0' + X[i+1:]
  cnt = 0
  for j in range(N):
    cnt += int(p[j])
  x = int(p, 2)
  if(x <= MAX):
    print(base[x])
  else:
    print(base[x%cnt]+1)

Submission status: Time Limit Exceeded

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

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

N = int(input())
X = input()[:-1][::-1]
origin = 0
for i in range(len(X)):
    origin += int(X[i]) * (2**i)
# print(origin)


for i in list(range(N))[::-1]:
    ans = 0
    if origin >> i & 1 == 1:
        val = origin - 2 ** i
    else:
        val = origin + 2 ** i

    # print(val, i)
    while val > 0:
        # print('temp', val, bin(val).count('1'))
        val = val % bin(val).count('1')
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
li = list(input())
for i in range(n):
    if li[i] == "0":
        li[i] = "1"
    else:
        li[i] = "0"
    binew = "".join(li)
    bi10 = int(binew, 2)
    a = 0
    while bi10 > 0:
        binum = str(bin(bi10))[2:]
        bi10 = bi10 % binum.count("1")
        a += 1
    print(a)
    if li[i] == "0":
        li[i] = "1"
    else:
        li[i] = "0"

Submission status: Time Limit Exceeded

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


def popcount(x):
    # 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


# X = ['']*N
# for i in range(N):
#     X[i] = str(random.randint(0, 1))
# print("".join(X))
C = X.count("1")

dp = [0]*N
dp[0] = 0
for i in range(1, N):
    k = i % popcount(i)
    dp[i] = 1 + dp[k]


# def solve(n, d):


for i in range(N):
    if X[i] == "0":
        X[i] = '1'
        print(dp[int((''.join(X)), 2) % (C+1)] + 1)
        #tmp = dp[int((''.join(X)), 2) % (C+1)] + 1
        X[i] = '0'
    else:
        if C == 1:
            print(0)
            continue
        X[i] = '0'
        print(dp[int((''.join(X)), 2) % (C-1)] + 1)
        #tmp = dp[int((''.join(X)), 2) % (C-1)] + 1
        X[i] = '1'


# print(dp)

Submission status: Time Limit Exceeded

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

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

def f(x):
	if x == 0:
		return 0
	else:
		return 1 + f(x % popcount(x))

for i in range(1, n + 1):
	print(f(x ^ (1 << n - i)))

Submission status: Time Limit Exceeded

Solution code:
import sys
import time
import math
def inpl():
    return list(map(int, input().split()))
st = time.perf_counter()
# ------------------------------

N = int(input())
X = int(input(), 2)
a = bin(X).count('1')
for i in range(N):
	if X & 1<<(N-i-1) == 1<<(N-i-1):
		aa = a-1
	else:
		aa = a+1
	x = X ^ 1<<(N-i-1)
	if x==0:
		print(0)
		continue
	x = x % aa
	cnt = 1
	while x!=0:
		cnt +=1
		x = x%(bin(x).count('1'))
	print(cnt)

# ------------------------------
ed = time.perf_counter()
print('time:', ed-st, file=sys.stderr)

Submission status: Time Limit Exceeded

Solution code:

if __name__ == '__main__':
    n = int(input())
    s = input()

    for i in range(n):
        s2 = ""
        if s[i] == "0":
            s2="1"
        else:
            s2="0"
        s3 = s[:i]+s2+s[i+1:]
        n2 = int(s3, 2)
        count = 0
        while n2 > 0:
            n2 = n2 %  bin(n2).count("1")
            count+=1
        print(count)

Submission status: Time Limit Exceeded

Solution code:
def f(n):
	res = 0
	while n > 0:
		n = (n % bin(n)[2:].count('1'))
		res += 1
	print(res)


n = int(input())
s = list(input())

for i in range(n):
	t = list(s)
	t[i] = '1' if t[i]=='0' else '0'
	f(int(''.join(t),2))

Submission status: Time Limit Exceeded

Solution code:
def popcount(n):
    return bin(n).count('1')
def popfunc(n):
    result = 0
    while n > 0:
        result += 1
        n = n % popcount(n)
    return result

N = int(input())
divider = 2**(N-1)

X = int(input(), 2)

while divider > 0:
    print(popfunc(X^divider))
    divider = divider // 2

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = input()
cnt = x.count("1")

for i in range(n)[::-1]:
    xm = int(x, 2)
    ans = 0
    if (xm >> i)%2 == 0:
        xm += 2**i
        cnt0 = cnt+1
        while xm > 0:
            xm %= cnt0
            cnt0 = str(bin(xm)).count("1")
            ans += 1
    else:
        xm -= 2**i
        cnt1 = cnt-1
        while xm > 0:
            xm %= cnt1
            cnt1 = str(bin(xm)).count("1")
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
# import numpy as np

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

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

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

for i in range(n):
    if x[i]=='0':
        y=x[:i]+'1'+x[i+1:]
    else:
        y=x[:i]+'0'+x[i+1:]
    z=int(y, 2)
    cnt=0
    while z!=0:
        z=z%popcnt(z)
        cnt+=1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:

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


def popcount(n):
  num=list(bin(n)[2:])
  num = [int(s) for s in num]
  return sum(num)

def f(n):
  i=0
  while not n==0:
    n = n % popcount(n)
    i+=1
  return i

for i in range(1,n+1):
  if x[i-1]=="0":
    tmp="1"
  else:
    tmp="0"
  X="0b"+x[:i-1]+tmp+x[i:]
  X=int(X,2)
  print(f(X))

Submission status: Time Limit Exceeded

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

from collections import Counter
import sys

up = [0]*n
do = [0]*n

b = Counter(x)

if b["1"] >= 2:
    pr = b["1"]
    a = 1
    for i in range(n):
        up[n-1-i] = a
        a = a*2 % (pr+1)
    
    a = 1
    for i in range(n):
        do[n-1-i] = a
        a = a*2 % (pr-1)
        
    upsum,dosum = 0,0
    for i in range(n):
        upsum = (upsum + (int(x[i]) * up[i])) % (pr+1)
        dosum = (dosum + (int(x[i]) * do[i])) % (pr-1)
        
    pop = [0] * (n+1)
    for i in range(1,n+1):
        xx = bin(i)[2:]
        c = Counter(xx)
        pop[i] = i % c["1"]
        
    for i in range(n):
        if x[i] == "0":
            ss = (upsum + up[i]) % (pr+1)
            
            aa = 0
            for j in range(400):
                if ss == 0:
                    break
                else:
                    ss = pop[ss]
                    aa += 1
                    
            print(aa+1)
            
        elif x[i] == "1":
            ss = (dosum + (pr-1) - do[i]) % (pr-1)
            
            aa = 0
            for j in range(400):
                if ss == 0:
                    break
                else:
                    ss = pop[ss]
                    aa += 1
                    
            print(aa+1)
            
else:
    for j in range(n):
        if x[j] == "1":
            print(0)
        else:
            pr = b["1"]
            a = 1
            for i in range(n):
                up[n-1-i] = a
                a = a*2 % (pr+1)

            upsum = 0
            for i in range(n):
                upsum = (upsum + (int(x[i]) * up[i])) % (pr+1)

            pop = [0] * (n+1)
            for i in range(1,n+1):
                xx = bin(i)[2:]
                c = Counter(xx)
                pop[i] = i % c["1"]
                
            ss = (upsum + up[j]) % (pr+1)
            
            aa = 0
            for k in range(400):
                if ss == 0:
                    break
                else:
                    ss = pop[ss]
                    aa += 1
                    
            print(aa+1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = input()
ncnt = X.count('1')

for i in range(N):
    tmp = X
    tmpcnt = ncnt
    cnt = 0
    if tmp[i] == '0':
        tmp = tmp[:i] + '1' + tmp[i + 1:]
        tmpcnt += 1
    else:
        tmp = tmp[:i] + '0' + tmp[i + 1:]
        tmpcnt -= 1
    f = int(tmp, 2)
    while True:
        if f == 0:
            break

        m, d = divmod(f, tmpcnt)
        cnt += 1
        f = d
        tmpcnt = 0
        d1 = d
        if d != 0:
            while True:
                m1, d1 = divmod(d1, 2)
                if d1 == 1:
                    tmpcnt += 1
                if m1 == 0:
                    break
                d1 = m1
    print(cnt)

Submission status: Time Limit Exceeded

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

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