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()
def printf(x,i):
  if x[i]=='1':
    return int(x,2)-2**(N-i-1)
  else:
    return int(x,2)+2**(N-i-1)
def popcount(n):
  return bin(n).count('1')
def f(n):
  count=0
  while n!=0:
    n = n % popcount(n)
    count+=1
  return count
for a in range(N):
  print(f(printf(X,a)))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
n = int(input())
x = input()

def popcount(n):
    a = bin(n)
    return a[2:].count("1")

@lru_cache(maxsize=None)
def func(n):
    cnt = 0
    while n > 0:
        cnt += 1
        n = n % popcount(n)
    return cnt

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

Submission status: Time Limit Exceeded

Solution code:
"""
NTC here
"""


#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase

profile = 0
pypy = 1


def iin(): return int(input())


def lin(): return list(map(int, input().split()))



def main():
    T = 1
    while T:
        T -= 1
        dp = {}
        n = iin()
        a = list(map(int, list(input())))
        ans = []
        def calc(a, md):
            ch = len(a)-1
            rm = 0
            for i in a:
                if i:
                    rm = (rm+ pow(2, ch, md))%md
                ch -= 1
            return rm%md
        
        def bin_calc(a):
            ans = []
            while a:
                ans.append(a&1)
                a >>= 1
            return ans[::-1]
        sm = sum(a)
        # count = 0
        for i in range(n):
            sol = 0
            s1 = sm - a[i]
            a[i] = + (not a[i])
            s1 += a[i]
            a1 = a
            dp1 = []
            while s1:
                # count += 1
                # print(a1, s1)
                sol += 1
                rm = calc(a1, s1)
                
                if rm:
                    if rm in dp:
                        sol += dp[rm]
                        break
                    dp1.append(rm)
                    a1 = bin_calc(rm)
                    s1 = sum(a1)
                else:
                    break
            a[i] = + (not a[i])
            for i, j in enumerate(dp1):
                dp[j] = sol-i-1
            ans.append(sol)
        print(*ans, sep='\n')
        # print(count)





    
        










    




                

        

 
 
 
 
 
 
# region fastio
 
BUFSIZE = 8192
 
 
class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 
if pypy:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
    input = lambda: sys.stdin.readline().rstrip("\r\n")
 
# endregion
 
if __name__ == "__main__":
    if profile:
        import cProfile
        cProfile.run('main()')
    else:
        main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = input()
for i in range(n):
    s = list(x)
    if x[i]=="0": s[i]="1"
    else: s[i]="0"
    s = "".join(s)
    res = int(s, 2)
    cnt = 0
    while res>0:
        cnt += 1
        res = res%bin(res).count("1")
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def f(n):
    if n == 0:
        return 1
    elif n in d:
        return d[n]
    else:
        popcount = str(bin(n)).count('1')
        d[n] = max(1, f(n % popcount) + 1)
        return d[n]

n = int(input())
x = str(input())
d = {}
for i in range(n):
    s = ''
    for j in range(n):
        if i != j:
            s += x[j]
        else:
            if x[i] == '1':
                s += '0'
            else:
                s += '1'
    xx = int(s, 2)
    print(f(xx) - 1)

Submission status: Time Limit Exceeded

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

Y = int(X, 2)
Z = list(map(int,list(X)))

for i in range(N):
    if Z[i]==0:
        Xi = Y + 2**(N-i-1)
    else:
        Xi = Y - 2**(N-i-1)
        
    ans = 0
        
    while Xi>0:
        Xi %= bin(Xi).count("1")
        ans += 1
        
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
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の数


def calc(a):
    cnt = 1
    while a > 0:
        # print(a)
        temp = popcnt(a)
        a = a % temp
        cnt += 1
    return cnt


def calc2(a):
    cnt = 0
    while a > 0:
        temp = popcnt(a)
        a = a % temp
        cnt += 1
    return cnt


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)
    # print(num ^ t, bin(num ^ t)
    if num ^ t:
        ans[i] = kotae[(num ^ t) % temp] + 1
    else:
        ans[i] = 0
print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache

sys.setrecursionlimit(10 ** 5)

n = int(input())
x = int(input(), 2)
ans = [0] * n

@lru_cache(maxsize=None)
def popcnt(n):
    return bin(n).count("1")

for i in range(n):
    tmp = x
    if (tmp >> (n-i-1)) & 1:
        tmp &= ~(1 << (n-i-1))
    else:
        tmp |= (1 << (n-i-1))
    cnt = 0
    while tmp != 0:
        cnt += 1
        c = popcnt(tmp)
        tmp = tmp % c
    ans[i] = cnt

for v in ans:
    print(v)

Submission status: Time Limit Exceeded

Solution code:
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    n=int(input())
    x=input()

    digit=x.count('1')+1
    l=[0]*digit

    def F(n):
        cnt=0
        while True:
            if n==0: break
            n%=bin(n).count('1')
            cnt+=1
        return cnt
    
    Rem=[0]*digit
    for i in range(digit):
        Rem[i]=F(i)
    
    for i in reversed(range(len(x))):
        tenx=int(x,2)
        nx=tenx^(2**i)
        if bin(nx).count('1')==0:
            print(0)
            continue
        else:
            rem=nx%(bin(nx).count('1'))
            if rem==0: print(1)
            else: print(Rem[rem]+1)



    
resolve()

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache


@lru_cache(maxsize=100000)
def popcount(n):
    return bin(n).count('1')


@lru_cache(maxsize=100000)
def f(n):
    if n == 0:
        return 0
    else:
        n = n % popcount(n)
        return f(n) + 1


N = int(input())
S = input()
S_int = int(S, 2)
for i in range(N-1, -1, -1):
    target = S_int ^ (1 << i)
    print(f(target))

Submission status: Time Limit Exceeded

Solution code:
import copy
def popcount(n):
    count=0
    while(n!=0):
        if n%2:
            count+=1
        n=n//2
    return count

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

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

for i in range(N):
    c=copy.copy(X)
    c[i]=str((int(c[i])+1)%2)
    print(f_n(int(''.join(c), 2)))

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

def popcount(n):
  s=0
  for i in range(N):
    if (1<<i)&n:
      s+=1
  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:
#AIsing2020 d

import sys,math,collections,itertools,copy
input = sys.stdin.readline


def popcount(n):
    bin_str = bin(n)
    cou1 = bin_str.count('1')
    return cou1

def count(nc):
    co = 0
    while nc >0:
        cou1 = popcount(nc)
        nc = nc%cou1
        co +=1
    return co

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

for i in range(N):
    Y = copy.copy(X)
    if Y[i] == '1':
        Y[i] = '0'
    else:
        Y[i] = '1'
    s = '0b'+"".join(Y)
    a =int(s,2)
    co = count(a)
    print(co)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

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

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

for i in range(lenx):
  if x[i] == "0":
    t = x10 + 2 ** (lenx - 1 - i)
  else:
    t = x10 - 2 ** (lenx - 1 - i)
  print(f(t))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain, product
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    N=ii()
    X=input()
    def popcount(n):
        return bin(n).count('1')
    def f(n):
        ret = 0
        while n:
            n = n % popcount(n)
            ret += 1
        return ret
    for i in range(N):
        x = X[:i] + ('0' if X[i]=='1' else '1') + X[i+1:]
        x = int(x, base=2)
        print(f(x))





main()

Submission status: Time Limit Exceeded

Solution code:
def function(n,k):
  m=int(n,2)
  c=n.count("1")
  if c==0:
    return k
  k+=1
  if m%c==0:
    return k
  else:
    return function(bin(m%c)[2:],k)
N=int(input())
X=list(input())
for i in range(N):
  if X[i]=="1":
    X[i]="0"
  else:
    X[i]="1"
  print(function("".join(X),0))
  if X[i]=="1":
    X[i]="0"
  else:
    X[i]="1"

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = list(input())
for i in range(n):
    num = x[0:]
    if num[i] == '1':
        num[i] = '0'
    else:
        num[i] = '1'
    num = ''.join(num)
    number = int(num, 2)
    ans = 0
    while number != 0:
        binary = format(number, 'b')
        ones = str(binary).count('1')
        number = number % ones
        ans += 1
    print(ans)

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")
for i in range(n):
    che=1
    p=1
    if x[i]=="1":
        p=-1
    if (c+p)==0:
        print(0)
        continue
    nex=(m+p*(2**(n-i-1)))%(c+p)
    while nex!=0:
        nex=nex%str(bin(nex)).count("1")
        che+=1
    print(che)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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


def popcount(n):
    bin_str = bin(n)
    return bin_str.count('1')
# print(popcount(N))

cnt = 0
def func(n):
    global cnt
    if n == 0:
        return cnt
    n = n % popcount(n)
    cnt += 1
    return func(n)
# print(func(7))

def toggle_nth_bit(num: int, n: int):
    return num ^ (1 << n)


for i in range(N-1, -1,-1):
    n = toggle_nth_bit(int(X, 2), i)
    ans = func(n)
    print(ans)
    cnt -= ans

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = str(input())
from functools import lru_cache

@lru_cache(maxsize=1000000)
def popcount(y):
    return bin(y).count("1")

@lru_cache(maxsize=1000000)
def f(m):
    if m == 0:
        return 0
    else:
        amari = m % popcount(m)
        return 1 + f(amari)
    
for i in range(n):
    moji = list(x)
    if moji[i] == "1":
        moji[i] = "0"
    else:
        moji[i] = "1"
    str_moji = "".join(moji)
    print(f(int(str_moji, 2)))

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    x = input()
    
    def popcount(n):
        n = format(n, 'b')
        return n.count('1')
    
    for i in range(n):
        x2 = list(x)
        x2[i] = str(int(x[i])^1)
        x2 = int(''.join(x2), 2)
        ans = 0
        while x2 != 0:
            x2 = x2 % popcount(x2)
            ans += 1
        print(ans)
    
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = int(input(),2)
l = [0]+[-1]*(N)

for n in range(1,N+1):
    l[n] = l[n%(bin(n).count('1'))]+1
a = [0]*N
for i in range(N):
    x = X^(1<<i)
    a[N-1-i] = l[x] if x<=N else l[x%(bin(x).count('1'))]+1
for x in a:
    print(x)

Submission status: Time Limit Exceeded

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

B = 2**20 - 1

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


def calc(p):
    cnt = 0
    while p != 0:
        p = p % popcount(p)
        cnt += 1
    return cnt


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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# hello worldと表示する
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
n=I()
lis=list(SI())
orig=0
for i in range(n):
    if lis[i]=="0":
        lis[i]=0
    else:
        lis[i]=1
orcount=sum(lis)
for i in range(n):
    j=n-i-1
    if lis[i]==1:
        orig+=2**j
#print(orig)
dp=[0 for i in range(n)]
dp[0]=1
for i in range(1,n):
    #u=count1(i+1)
    count=0
    j=0
    while 2**j<=i+1:
        if ((i+1)>>j) %2==1:
            count+=1
        j+=1
    z=1
    if (i+1)%count==0:
        dp[i]=z
    else:
        dp[i]=z+dp[(i+1)%count-1]
#print(dp)
for i in range(n):
    if lis[i]==0:
        num=orig+2**(n-i-1)
        pr=orcount+1
    else:
        num=orig-2**(n-i-1)
        pr=orcount-1
    #print(num,pr)
    if pr==0:
        print(0)
    elif num%pr==0:
        print(1)
    else:
        print(1+dp[num%pr-1])

Submission status: Time Limit Exceeded

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


n = int(input())
X = input()
x = int(X, 2)
basecount = popcount(x)

for i in range(n-1, -1, -1):
    pair = 1 << i
    Xi = x ^ pair
    if x & pair:
        mod = basecount-1
    else:
        mod = basecount+1

    if Xi:
        Xi %= mod
        count = 1
        while Xi:
            mod = popcount(Xi)
            Xi %= mod
            count += 1
        print(count)
    else:
        print(0)

Submission status: Time Limit Exceeded

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


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


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

for i in range(N):
    if X[i] == "1":
        tmp = "0"
    else:
        tmp = "1"
    newX = X[:i] + tmp + X[i+1:]
    print(f(int(newX,2)))

Submission status: Time Limit Exceeded

Solution code:
import sys 
input = lambda:sys.stdin.readline().strip()
def perform(n):
    ans =  1
    val = n.count('1')
    if val==0:
        return 0
    temp = 0
    for i in range(len(n)):
        temp+=pow(2,i,val)*int(n[len(n)-1-i])
        temp%=val
    while temp!=0:
        ans+=1
        temp = temp%(bin(temp).count('1'))
    return ans
n = int(input())
x = list(input())
for i in range(n):
    if x[i]=='0':
        x[i] = '1'
    else:
        x[i] = '0'
    print(perform(x))
    # print(int(''.join(x),2))
    if x[i]=='0':
        x[i] = '1'
    else:
        x[i] = '0'

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

def pc(n,t):
    if n==0:
        return t
    return pc(n//2,t+n%2)

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

for i in range(N):
    if X[i]=="0":
        x2=x+2**(N-i-1)
        p=pc(x2,0)
    else:
        x2=x-2**(N-i-1)
        p=pc(x2,0)
    ans=0
    while x2>0:
        x2%=p
        p=pc(x2,0)
        ans+=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = input()
# compute initial hamming
def ham(n):
    c = 0
    while n:
        c += 1
        n &= n - 1
    return c

initial_ham = 0
for i in x:
    if i == '1':
        initial_ham += 1
# also compute initial evaluation
initial_val = int(x, 2)
tmp = 1<<n
for i in range(n):
    tmp //= 2
    if x[i] == '0':
        cur_val = initial_val + tmp
        cur_ham = initial_ham + 1
    else:
        cur_val = initial_val - tmp
        cur_ham = initial_ham - 1
    ans = 0
    while cur_val != 0:
        ans += 1
        cur_val %= cur_ham
        cur_ham = ham(cur_val)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n = int(input())
    x = input()
    for i in range(n):
        if x[i] == '1':
            tmp = x[:i] + '0' + x[i+1:]
        else:
            tmp = x[:i] + '1' + x[i+1:]
        tmp = int(tmp,2)
        cnt = 0
        while 1:
            if tmp == 0:
                print(cnt)
                break
            tmp = tmp%format(tmp, 'b').count('1')
            cnt += 1


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# itne me hi thakk gaye?
n = int(input())
org = list(input())
ans = []
# print(org)
def compute(s, pc):
    ans = 0
    s = s[::-1]
    for i in range(len(s)):
        if s[i] == '1':
            ans += pow(2, i, pc)
        ans = (ans % pc)
    return ans% pc
for i in range(n):
    tmp = org[:]
    if org[i] == '1':
        tmp[i] = '0'
    else:
        tmp[i] = '1'
    curr_number = int(''.join(tmp), 2)
    count = 0
    pc = tmp.count('1')
    while(curr_number != 0):
        # print(tmp, curr_number, pc)
        curr_number = compute(tmp, pc)
        tmp = list(bin(curr_number)[2:])
        count += 1
        pc = tmp.count('1')
    ans.append(count)
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=input()
def pop(k):
  c=0
  r=k
  while r>0:
    c+=r%2
    r//=2
  return c
def f(k):
  m=int(k,2)
  c=0
  while m>0:
    c+=1
    m=m%pop(m)
  return c
for i in range(n):
  if x[i]=="1":
    y=x[:i]+"0"+x[i+1:]
  else:
    y=x[:i]+"1"+x[i+1:]
  print(f(y))

Submission status: Time Limit Exceeded

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

def popcount(n):
    a = bin(n)
    return a[2:].count("1")

def func(n):
    cnt = 0
    while n > 0:
        cnt += 1
        n = n % popcount(n)
    return cnt

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

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())
    X = readline().strip()

    n = int(X, 2)
    p = X.count('1')

    ans = [0] * N
    for i in range(N):
        if X[i] == '1':
            m = n - pow(2, N - i - 1)
            q = p - 1
        else:
            m = n + pow(2, N - i - 1)
            q = p + 1
        
        while m:
            ans[i] += 1
            m %= q
            q = bin(m).count('1')
            
    print(*ans, sep='\n')
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
N=int(input())
X=int(input(),2)

@lru_cache(maxsize = None)
def popcount(n):
    ret = 0
    while n > 0:
        ret += n & 1
        n >>= 1
    return ret

@lru_cache(maxsize = None)
def f(n):
    ret = 0
    while n > 0:
        n = n % popcount(n)
        ret += 1
    return ret

ans = []
for i in range(N):
    ans.append(f(X ^ (1<<i)))
for i in reversed(ans):
    print(i)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout

int_in = lambda: int(stdin.readline())
arr_in = lambda: [int(x) for x in stdin.readline().split()]
mat_in = lambda rows: [arr_in() for _ in range(rows)]
str_in = lambda: stdin.readline().strip()
out = lambda o: stdout.write("{}\n".format(o))
arr_out = lambda o: out(" ".join(map(str, o)))
bool_out = lambda o: out("YES" if o else "NO")
tests = lambda: range(1, int_in() + 1)
case_out = lambda i, o: out("Case #{}: {}".format(i, o))


cache = {}
def popcount(n):
    if n in cache:
        return cache[n]
    pop = bin(n).count("1")
    result = popcount(n % pop) + 1
    cache[n] = result
    return result


def solve(n, x):
    cache[0] = 0
    for i in range(n):
        flip = 1 << (n-i-1)
        curr = x ^ flip
        yield popcount(curr)


if __name__ == "__main__":
    n = int_in()
    x = int(stdin.readline(), 2)
    result = solve(n, x)
    for item in result:
        out(item)

Submission status: Time Limit Exceeded

Solution code:

#!/usr/bin/python
# -*- coding: utf-8 -*-

import numpy as np

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

def int_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(map(int,input().split())))
    return np.array(x)

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

X_int = 0

for i in range(0,N):
    newX = list(X)
    if newX[i] == "0":
        newX[i] = "1"
    else:
        newX[i] = "0"

    for i,x in enumerate(newX[::-1]):
        X_int += 2**i*int(x)

    ans = 0

    while X_int != 0:
        X_int = X_int%popcnt1(X_int)
        ans += 1

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
bi=input()
for i in range(len(bi)):
    if i!=len(bi)-1:
        if bi[i]=='1':
            k=bi[:i]+'0'+bi[i+1:]
        else:
            k=bi[:i]+'1'+bi[i+1:]
    else:
        if bi[i]=='1':
            k=bi[:i]+'0'
        else:
            k=bi[:i]+'1'
    m=k
    l=0
    t=20
    while True:
        c=m.count('1')
        if c==0:
            print(l)
            break
        c=int(m,2)%c
        m=bin(c)
        l+=1

Submission status: Time Limit Exceeded

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

def solve(N, X):
    X_oct = int(X, 2)
    X_one_count = X.count("1")

    memo = {}
    for i, x in enumerate(X):
        if x == '1':
            X_current = X_oct - 2 ** (N-1-i)
            X_one_current = X_one_count - 1
        elif x == '0':
            X_current = X_oct + 2 ** (N - 1 - i)
            X_one_current = X_one_count + 1

        if X_one_current == 0:
            print(0)
            continue

        count = 0
        while True:
            X_current = X_current % X_one_current
            X_one_current = bin(X_current).count("1")
            count += 1

            if X_current == 0:
                break

            if X_current in memo:
                count += memo[X_current]
                break

        print(count)

    return

def main():
    N = int(input())
    X = input()
    solve(N, X)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    def f(n):
        n = int(''.join(n), 2)
        c = 0
        while n != 0:
            n %= sum(list(map(int, bin(n)[2:])))
            c += 1
        print(c)
    rev = lambda x: '1' if x == '0' else '0'
    n = int(input())
    X = list(input())
    X[0] = rev(X[0])
    f(X)
    for i in range(n - 1):
        X[i] = rev(X[i])
        X[i + 1] = rev(X[i + 1])
        f(X)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = input()
def popcount(n):
  n = format(n, 'b')
  s = str(n)
  return s.count('1')
def f(n):
  cnt = 0
  while n != 0:
    n = n % popcount(n)
    cnt += 1
  return cnt
for i in range(N):
  listx = list(X)
  if listx[i] == '0':
    listx[i] = '1'
    rex = int(''.join(listx), 2)
  else:
    listx[i] = '0'
    rex = int(''.join(listx), 2)
  print(f(rex))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

s = input()


bin = int(s, 2)
memo = dict()

def popCount(value):

    count = 0
    current = value
    while current != 0:
        if current in memo:
            return memo[current]
        pop = format(current, 'b').count('1')
        m = current % pop
        current = m
        count += 1
    memo.update({value: count})
    return count

for i in range(n):
    if s[i] == '1':
        val = bin - 2**(n-1 - i)
    else:
        val = bin + 2**(n-1 - i)

    print(popCount(val))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = list(input())
zuru = [1,1,2,1,2,1,2,1,2,1]

for i in range(len(x)):
  y = x.copy()
  if x[i] == "0":
    y[i] = "1"
  else:
    y[i] = "0"
  n = int("".join(y), 2)
  count = 0
  while n != 0:
    one_num = bin(n)
    n = n % one_num.count("1")
    count += 1
    if 0 < n <=10:
      count += zuru[n-1]
      break
  print(count)

Submission status: Time Limit Exceeded

Solution code:
def popcount(n):
    bin_n = format(n, "b")
    ans = 0
    for e in bin_n:
        if e=="1":
            ans += 1
    return ans

N = int(input())
bin_X = input()

pop = 0
for e in bin_X:
    if e=="1":
        pop += 1


for i in range(N):
    if bin_X[i] == "0":
        bin_new = bin_X[:i] + "1" + bin_X[i+1:]
        pop_new = pop + 1
    else:
        bin_new = bin_X[:i] + "0" + bin_X[i+1:]
        pop_new = pop - 1
    #print(bin_new)
    new = int(bin_new, 2)
    #print(new)
    if new == 0:
        ans = 0
    else:
        ans = 1
        new = new % pop_new
        while True:
            if new == 0:
                break
            ans += 1
            new = new % popcount(new)
        
    print(ans)