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()
xx=x.count('1')
xx2=0
k1=2**n
for i in range(n):
    k1//=2
    xx2+=k1*int(x[i])
k=2**n
for i in range(n):
    k//=2
    if x[i]=='0':
        xxx=xx+1
        xxx2=xx2+k
    else:
        xxx=xx-1
        xxx2=xx2-k
    count=0

    while xxx2!=0:
        xxx2%=xxx
        xxx=str(bin(xxx2)).count('1')
        count+=1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(300000)

memp = {}
def popcount(n):
    if n == 0:
        return 0

    global memp
    if n not in memp:
        memp[n] = (n & 1) + popcount(n >> 1)
    return memp[n]

memf = {}
def f(x):
    if x == 0:
        return 0

    global memf
    if x not in memf:
        memf[x] = f(x % popcount(x)) + 1
    return memf[x]

n = int(input())
x = input().rstrip()

ans = []
for j in range(n):
    i = n - 1 - j
    a = str(1 - int(x[i]))
    b = x[:i] + a + x[i+1:]
    ans.append(f(int(b, 2)))
for j in range(n):
    i = n - 1 - j
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
import copy
n = int(input())
x0 = list(input())
def count1(n):
  LIST = list(str(bin(n)))
  cnt = LIST.count("1")
  return cnt
for i in range(n):
  x1 = copy.copy(x0)
  if x0[i] == "0":
    x1[i] = "1"
  else:
    x1[i] = "0"
  x1 = "".join(x1)
  cnt1 = x1.count("1")
  x1 = int(x1, 2)
  cnt_ans = 0
  while x1 != 0:
    x1 %= cnt1
    cnt1 = count1(x1)
    cnt_ans += 1
  print(cnt_ans)

Submission status: Time Limit Exceeded

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

from functools import lru_cache


def popcount(bits: str):
    return len([elm for elm in bits if elm == '1'])


cache = dict()

@lru_cache(maxsize=100000)
def f(num):
    if num == 0:
        return 0
    else:
        # if not cache.get(num % pc, None) is None:
        #     return cache[num % pc]
        pc = popcount('{:b}'.format(num))
        ret = 1 + f(num % pc)
        # cache[num % pc] = ret
        return ret


def reverse_bit(bits: str, digit):
    def toggle(a):
        if a == '1':
            return '0'
        else:
            return '1'

    ret = list(bits)
    ret[digit-1] = toggle(bits[digit-1])
    return ''.join(ret)

def convert(x: str):
    ans = 0
    i = 0
    for elm in list(x)[::-1]:
        if elm == '1':
            ans += 2 ** i
        i += 1
    return ans


answers = {}

for i in range(1, N+1):
    bits = reverse_bit(X, i)
    # pc = popcount(bits)
    # print(f'# {bits} {convert(bits)} {pc}')
    x = convert(bits)
    if not answers.get(x, None) is None:
        print(answers[x])
        continue
    ret = f(x)
    answers[x] = ret
    print(ret)

Submission status: Time Limit Exceeded

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


def f(cnt):
    if (cnt > 0):
        pcount = p_count(cnt)
        return f(cnt % pcount) + 1
    else:
        return 0


def p_count(x):
    cnt = 0
    while (x > 0):
        if x % 2 != 0:
            cnt += 1
        x //= 2
    return cnt


for i, x in enumerate(X):
    if (x == '1'):
        X[i] = '0'
        num = int(''.join(X), 2)
        print(f(num))
        X[i] = '1'
    else:
        X[i] = '1'
        num = int(''.join(X), 2)
        print(f(num))
        X[i] = '0'

Submission status: Time Limit Exceeded

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

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

for i in range(n):
    if x[i] == '1':
        print(f(int('0b' + x[:i] + '0' + x[i+1:], 0)))
    else:
        print(f(int('0b' + x[:i] + '1' + x[i+1:], 0)))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = input()
for i in range(n):
    a = int(x[:i] + '1' + x[i+1:] if x[i] == '0' else x[:i] + '0' + x[i+1:],2)
    c = 0
    while a != 0:
        b = sum(i == '1' for i in format(a,'b'))
        a = a%b
        c += 1
    print(c)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
import random
from collections import deque
from decimal import *
import queue

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	X = inputStr()
	X_lin = list(X)

	ans = []
	mem = {}
	for i in range(N):
		tmpX = X_lin
		if X[i] == "1":
			tmpX = X[:i] + "0" + X[i+1:]
		else:
			tmpX = X[:i] + "1" + X[i+1:]

		oct = int(tmpX, 2)
		oct_mae = oct

		ans_tmp = 0
		if oct in mem:
			ans_tmp = mem[oct]
		else:
			while True:
				if oct == 0:
					break
				tmp = bc(oct)
				oct = oct % tmp
				ans_tmp += 1
				if oct == 0:
					break
				if oct in mem:
					ans_tmp += mem[oct]
					break

		if oct_mae in mem:
			pass
		else:
			mem[oct_mae] = ans_tmp

		ans.append(ans_tmp)

	for i in ans:
		print(i)
	#print(mem)

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

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:

def cal_cnt(num):
  cnt = 0
  for bit in format(num, 'b'):
    if bit == '1':
      cnt += 1

  return cnt


def main():
  n = int(input())
  src = input()
  base = int(src, 2)
  base_cnt = 0
  for bit in src:
    if bit == '1':
      base_cnt += 1

  memo = tuple(map(cal_cnt, range(n)))

  dp = [None] * n
  dp[0] = 0

  def popcount(num, cnt):
    if num < n and dp[num] is not None:
      return dp[num]

    nxt = num % cnt
    res = 1 + popcount(nxt, memo[nxt])
    if num < n:
      dp[num] = res

    return res

  for i in range(n - 1, -1, -1):
    num, cnt = (base + 2 ** i, base_cnt + 1) if src[n - i - 1] == '0' else (base - 2 ** i, base_cnt -1)
    print(popcount(num, cnt))


main()

Submission status: Time Limit Exceeded

Solution code:
memo = {0: 0}
def fun(num):
    if num in memo: return memo[num]
    tmp = num % bin(num).count("1")
    cnt = 1 + fun(tmp)
    memo[num] = cnt
    return cnt       
    
N = int(input())
X = int(input(), 2)
for i in range(N):        
    xi = X ^ ((2**(N-1)) >> i)
    cnt = fun(xi)
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#import math
#import collections
#import bisect
#from collections import deque
#from copy import copy, deepcopy


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


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

    ans = 0
    flip = 2 ** N
    memo_dict = {}
    for i in range(0, N):
        flip = flip >> 1
        tmp = flip ^ decX
        ans = 0
        tmp_list = []
        while(1):
            tmp_list.append(tmp)
            if tmp in memo_dict:
                ans += memo_dict[tmp]
                break
            if tmp == 0:
                break
            tmp %= popcount(tmp)
            ans += 1

        #print(tmp_list, ans)
        for i, t in enumerate(tmp_list):
            memo_dict[t] = ans - i
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy
N = int(input())
X = input()  
x = int(X, 2)

def popcount(n):
    return bin(n).count("1")
def func(n):
  count = 0
  while(n!=0):
    n = n%popcount(n)
    count += 1
  return count

for i in range(N):
  temp = copy.copy(X)
  if(temp[i]=="0"):
    k = x + 2**(N-i-1) 
  else:
    k = x - 2**(N-i-1)
  print(func(k))

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.read
from itertools import accumulate
from copy import deepcopy
def main():
    n = int(input())
    x = list(input())
    for i1 in range(n):
        x2 = deepcopy(x)
        if x2[i1] == '1':
            x2[i1] = '0'
        else:
            x2[i1] = '1'
        x3 = int("".join(x2), 2)
        r = 0
        while x3:
            r += 1
            p = bin(x3).count('1')
            x3 = x3 % p
        print(r)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
import math  # gcdもあるよ
from collections import deque
from collections import defaultdict
from copy import deepcopy
from itertools import accumulate #リストを与えると累積和を返す
def input(): return sys.stdin.readline().rstrip()
from functools import lru_cache #メモ化

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

@lru_cache(maxsize=None)
def f_count(n, ans = 0):
    #print(n, popcount(n))
    if n != 0:
        ans = f_count(n % (popcount(n)), ans + 1)
    return ans

def main():
    n = int(input())
    x = input()
    x_10 = int(x, 2)
    #print(x_10)
    x = list(x)
    for i in range(n):
        if x[i] == "0":
            print(f_count(x_10 + 2 ** (n - 1 - i), ans = 0))
        else:
            print(f_count(x_10 - 2 ** (n - 1 - i), ans = 0))

   # print(f_count("""ここに反転した数字を入れる""", ans = 0))
    return 0

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache


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


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


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

li = []

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

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

Submission status: Time Limit Exceeded

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

def main():
    N= int(input())
    X = input()
    for i in range(N):
        A = ''
        if X[i] == '1':
            A = X[:i] + '0' + X[i+1:]
        else:
            A = X[:i] + '1' + X[i+1:]
        c = int(A,2)
        cnt = 0
        while(c > 0):
            c = c % popcount(c)
            cnt += 1
        print(cnt)
if __name__ == '__main__':
    main()

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
for i in reversed(range(0,len(s))):
    num+=int(s[i])*(1<<(len(s)-i-1))
k=1
temp=al(num)
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()
fl = {}


def popcount(n):
    s = str(format(n, "b"))
    return s.count("1")


def f(n):
    cnt = 0
    while n > 0:
        n = n % popcount(n)
        if str(n) in fl:
            cnt += fl[n]
            break
        cnt += 1

    fl[n] = cnt
    return cnt


def getX(m, i):
    s = (ord(x[i]) % 2 + 1) % 2
    s = x[:i] + str(s) + x[i + 1:]
    return int(s, 2)


for i in range(n):
    rx = getX(x, i)
    print(f(rx))

Submission status: Time Limit Exceeded

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

f = dict()

def function(x):
    global f
    if x in f:
        return f[x]
    if x == 0:
        return 0
    cnt = 0
    for i in range(len(str(bin(x)))-2):
        if (x>>i) & 1 == 1:
            cnt += 1
    if x % cnt == 0:
        f[x] = 1
        return 1
    else:
        f[x] = function(x % cnt) + 1
        return f[x]

for i in range(N):
    if i == N-1:
        if X[i] == '1': 
            x = X[:i] + '0'
        else:
            x = X[:i] + '1'
    else:
        if X[i] == '1': 
            x = X[:i] + '0' + X[i+1:]
        else:
            x = X[:i] + '1' + X[i+1:]
    # print(x, int(x, 2))
    print(function(int(x, 2)))
# print(f)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

x = input()
ans = []


def popcount(s):
    count = 0
    binary = str(bin(s))
    for i in range(len(binary)):
        if binary[i] == "1":
            count += 1
    return count


def f(n):
    count = 0
    while(n != 0):
        if popcount(n) == 0:
            break
        n = n % popcount(n)
        count += 1
    ans.append(count)


for i in range(n):
    num = int(x, 2)
    if x[n-i-1] == "1":
        num -= 2**i
    else:
        num += 2**i
    f(int(num))


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

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
Xinput=list(input())
Xs=[0]*N
for i in range(N):
  Xs[i]=Xinput

for i in range(N):
  a=[]
  if Xinput[i]=="0":
    a+=Xinput[:i]+["1"]+Xinput[i+1:]
  else:
    a+=Xinput[:i]+["0"]+Xinput[i+1:]
  Xs[i]="".join(a)

def procount(n10):
  nbin=list(str(bin(n10)))[2:]
  return nbin.count("1")

def f(nbin):
  n10=int(nbin,2)
  cnt=0
  while n10>0:
    n10=n10%procount(n10)
    cnt+=1
  return cnt

for i in range(N):
  print(f(Xs[i]))

Submission status: Time Limit Exceeded

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


def f(x, px):
    moto = x
    if ansl[x] != -1:
        return ansl[x]
    x = x % px
    if popl[x] == -1:
        px = popcnt(x)
        popl[x] = px
    else:
        px = popl[x]
    ans = f(x, px)+1
    ansl[moto] = ans
    return ans


n = int(input())
x = input()
xx = x
nx = int(x, 2)
pnx = popcnt(nx)

ansl = [-1]*(2*10**5+10)
popl = [-1]*(2*10**5+10)
ansl[0] = 0
for i in range(n):
    if i == 0:
        a = 1 << (n-1)
    else:
        a = a >> 1
    x = nx ^ a
    if xx[i] == "1":
        px = pnx-1
    else:
        px = pnx+1
    ans = 0
    if x != 0:
        x = x % px
        moto = x
        if popl[x] == -1:
            px = popcnt(x)
            popl[x] = px
        else:
            px = popl[x]
        ans = f(x, px)+1
        ansl[moto] = ans-1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  aaa=S()
  s=[int(x) for x in aaa]

  ans=[]
  for i in range(n):
    _s=copy.deepcopy(s)
    x=_s[i]
    if x==1:
      _s[i]=0
    else:
      _s[i]=1

    cnt=0

    a=0
    cnt1=0
    # 1の数を数える、10進数変換する
    for i,x in enumerate(_s[::-1]):
      if x==1:
        cnt1+=1
      a+=2**i*x

    # 最初から0の場合は終わり（０回）
    if cnt1==0:
      ans.append(0)
      continue

    # 余りを撮る
    b=a%cnt1
    _s=[]
    if b==0:
      ans.append(1)
      continue

    counter=1
    while True:
      _b=b
      div2De1_cnt=0
      while True:
        if _b%2==0:
          pass
        else:
          div2De1_cnt+=1
        _b//=2
        if _b==0:
          break

      if div2De1_cnt==0:
        ans.append(counter)
        break
      counter+=1
      b%=div2De1_cnt

    # print('cnt1:'+str(cnt1))
    # print('b:'+str(b))

    

  for x in ans:
    print(x)

main()
# print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys #追加
n=int(input())
sys.setrecursionlimit(10**6*2)

s=input()
X=int(s,2)
ans=[]


def DEF(x,cnt):
    global ans_memo
    #print(x,cnt,ans_memo)
    if x==0:
        return 0    
    else:
        if x%(str(bin(x)).count("1"))==0:
            return 1
        else:
            tmp=DEF(x%(str(bin(x)).count("1")),cnt+1)+1
            return tmp

ans=[]

for i in range(n):
    tmp=2**(n-i-1)
    tmp_num=X
    #1の時
    if tmp&tmp_num:
        tmp_num-=tmp
        #print(bin(tmp_num),n-i-1)
        ans.append(DEF(tmp_num,0))
        
    else:
        tmp_num+=tmp
        #print(bin(tmp_num),n-i-1)
        ans.append(DEF(tmp_num,0))

#print(ans_memo)

for item in ans:
    print(item)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict

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

def f(n):
    init = n
    cnt = 0
    while n != 0:
        n %= Counter(bin(n))['1']
        cnt += 1
    return cnt

for i in range(N):
    if X[i] == '1':
        tmp = - (1<<(N-i-1))
        n = int(X, 2) + tmp
    else:
        tmp = (1<<(N-i-1))
        n = int(X, 2) + tmp
    print(f(n))

Submission status: Time Limit Exceeded

Solution code:
def f_n(n):
  ans = 0
  while n > 0:
    n = n%bin(n).count("1")
    ans += 1
  return ans
  
n = int(input())
x = input()

for i in range(n):
  x1 = x[0:i] if i != 0 else ""
  x3 = x[i+1:] if i != n-1 else ""
  x2 = '0' if x[i]=='1' else '1'
  print(f_n(int(x1+x2+x3, 2)))

Submission status: Time Limit Exceeded

Solution code:
History = {}

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

def AnythingGoestoZero(n):
  count = 0
  target = n
  while target != 0:
    if target in History.keys():
      count += History[target]
      break
    else:
      count += 1
    target = target % popcount(target)
  if n in History.keys():
    History[n] = count
  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:
import copy
N = int(input())
X = list(input())

def f(num):
    ii = 0
    while num!=0:
        num = num % str(bin(num)).count('1')
        ii+=1
    return ii

for i in range(N):
    X2 = copy.copy(X)
    if X[i] == '0':
        X2[i] = '1'
    elif X[i] == '1':
        X2[i] = '0'
    X3 = "".join(X2)
    print(f(int(X3,2)))

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    #n=int(input())
    #a,b=map(int,input().split())
    #x=list(map(int,input().split()))
    #a=[list(map(lambda x:int(x)%2,input().split())) for _ in range(h)]

    def calc(x):#xは数字
        if x==0:
            return 0
        xn=x
        x=bin(x)[2:]
        cnt=sum(list(map(int,list(x))))
        if xn%cnt==0:
            return 1
        else:
            return calc(xn%cnt)+1
    
    n=int(input())    
    x=input()
    cnt=sum(list(map(int,list(x))))
    x=int(x,2)
    ans=[]
    for i in range(n):
        if x>>i&1:
            ans.append(calc(x-2**i))
        else:
            ans.append(calc(x+2**i))
    print(*ans[::-1],sep='\n')

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

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

for i in range(n):
    temp = x
    one = one_num
    if temp[i] == "1":
        temp = temp[:i] + "0" + temp[i+1:]
        one -= 1
    else:
        temp = temp[:i] + "1" + temp[i+1:]
        one += 1
    x_dec = int(temp,2)
    ans = 0
    
    while x_dec != 0:
        x_dec = x_dec%(one)
        one = str(bin(x_dec)).count("1")
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def reverse(string):
    string = "".join(reversed(string))
    return string
def bitsoncount(x):
    return bin(x).count('1')
n = int(input())
x = input()
x=reverse(x)
num =0
cnt =0
for i in range(n):
    if(x[i]=='1'):
        cnt+=1
    bit = int(x[i])
    if(bit==1):
        num = num|(1<<i)
a = list()
for i in range(n):
    nn = num
    ans=0
    cn = cnt
    if(x[i]=='1'):
        cn-=1
        nn = nn&~(1<<i)
    else:
        cn+=1
        nn = nn|(1<<i)
    #print(cn)
    while nn>0:
        cn = bitsoncount(nn)
        nn = nn%cn
        ans+=1
    #print(ans)
    a.append(ans)
a.reverse()
for i in range(n):
    print(a[i])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = str(input())
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)
    cnt = 0
    while xx > 0:
        p = str(bin(xx)).count('1')
        xx %= p
        cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

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

for i in range(N-1,-1,-1):
    re_X = X^(2**i)#ビット反転した数
    ans = 0
    while re_X != 0:
        pop = bin(re_X).count("1")
        re_X = re_X % pop
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = input()
d = {}
onenum = 0
for i in range(N):
  if(X[i]=="1"):
    onenum += 1

for i in range(N):
  r = X[:i]
  l = X[i+1:]
  if(X[i]=="1"):
    tempx = r + "0" + l
    temponenum = onenum - 1
  else:
    tempx = r + "1" + l
    temponenum = onenum + 1
  tempx = int(tempx, 2)
  if(tempx not in d):
    ans = 0
    n = tempx
    pathlist = [tempx]
    firstroopflag = 1
    while(n>0):
      if(firstroopflag == 1):
        n = n % temponenum
        pathlist.append(n)
        ans += 1
        firstroopflag = 0
      else:
        if(n in d):
          ans += d[n]
          break
        else:
          n = n % bin(n).count("1")
          pathlist.append(n)
          ans += 1
    for j in range(len(pathlist)):
      if(pathlist[j] != 0 and pathlist[j] not in d):
        d[pathlist[j]] = ans - j
    print(ans)
  else:
    print(d[tempx])

Submission status: Time Limit Exceeded

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

k = [0,1,1,2,1,2,1,2,1,2,1,2,1,2,2,3,1,2,1] #18まで
one = [0]*N

c = 0
for i in range(N):
    if X[i] == "1":
        c += 1
for i in range(N):
    if X[i] == "1":
        one[i] = c-1
    else:
        one[i] = c+1
#print(one)

b1 = bin_num = int(X, 2)

for i in range(N):
    if X[i] == "0":
        B1 = b1 + 2**(N-1-i)
    else:
        B1 = b1 - 2**(N-1-i)
    #print(B1)
    if B1 == 0:
        print(0)
        continue
    else:
        B2 = B1%one[i]
    x = format(B2, 'b')
    #print(x)
    S = len(str(x))

    c2 = 0
    for j in range(S):
        if x[j] == "1":
            c2 += 1

    if c2 == 0:
        print(1)
    else:
        print(2+k[B2%c2])

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=input()
X=0
cnt=0

for i in range(N):
  if S[N-1-i]=='1':
    X+=1<<i
    cnt+=1

for i in range(N):
  Y=X
  cntcnt=cnt
  if S[i]=='0':
    Y+=1<<(N-1-i)
    cntcnt+=1
  else:
    Y-=1<<(N-1-i)
    cntcnt-=1
  ans=0
  while Y!=0:
    Y=Y%cntcnt
    cntcnt=bin(Y).count('1')
    ans+=1
  print(ans)

Submission status: Time Limit Exceeded

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

    def f(x):
        c = 0
        while x:
            c += 1
            x = x % bin(x).count('1')
        return c
    for i in range(N):
        print(f(X ^ (1 << (N - 1 - i))))


main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = list(input())
for i in range(N):
  X_ = X.copy()
  count = 0
  if X_[i] == "0":
    X_[i]="1"
  else:
    X_[i]="0"
  while(int("".join(X_),2)>0):
    count += 1
    l = X_.count("1")
    X_ = bin(int("".join(X_), 2)%l)
  print(count)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

n = int(input())

x = input()

c = x.count('1')

L = {}


for i in range(n):
    #print(int(str(x[:i]+str((int(x[i])+1)%2)+x[i+1:]),2))
    a = int(str(x[:i]+str((int(x[i])+1)%2)+x[i+1:]),2)
    b = 0
    if x[i] == '1':
        b = c-1
    else:
        b = c+1
    cnt = 0
    h = a
    while True:
        #print(a,h,b)
        if h==0:
            
            print(cnt)
            L[a] = cnt
            break
        h = h%b
        cnt += 1
        if h in L:
            cnt += L[h]
            print(cnt)
            L[a] = cnt
            break
        b = bin(h).count('1')

Submission status: Time Limit Exceeded

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

def popcount(n):
    cnt = 0
    while n != 0:
        cnt += 1
        n = n % bin(n).count('1')
        if n in memo:
            cnt += memo[n]
            break
        
    return cnt

memo = {}

for i in range(N):
    temp_X = [l for l in X]
    if temp_X[i] == '0':
        temp_X[i] = '1'
    else:
        temp_X[i] = '0'
    temp_X = ''.join(temp_X)
    
    n = int(temp_X, 2)
    memo.setdefault(n, 0)
    
    output = popcount(n)
    print(output)
    memo[n] = output

Submission status: Time Limit Exceeded

Solution code:
import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())

def Main():
    n = I()
    x = S()

    for rep in range(n):
        tmp = '1' if x[rep]=='0' else '0'
        itg = int(x[:rep] + tmp + x[rep+1:],2)

        c = 0
        while itg!=0:
            itg %= bin(itg).count('1')
            c += 1
        
        print(c)
    return

if __name__=='__main__':
    Main()

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]
    ori_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[ori_bit] = ans
    return ans


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 rec2(n):
    if n in memo:
        return memo[n]
    
    p = bit[n]
    new_n = n % p
    ans = memo[new_n] + 1
    memo[n] = ans
    return memo[n]


def submit():
    n = int(input())
    xs = list(input())
    x = int('0b' + "".join(xs), 0)

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

    ans = []
    base_bit = popcount1(x)
    bit[x] = base_bit
    mask = 1 << (n - 1)
    for i in range(1, n + 1):
        if xs[i - 1] == "0":
            xi = x + mask
            bit[xi] = bit[x] + 1
            xs[i - 1] = "0"
        else:
            xs[i - 1] = "0"
            xi = x - mask
            bit[xi] = bit[x] - 1
            xs[i - 1] = "1"
        ans.append(rec2(xi))
        mask >>= 1

    for a in ans:
        print(a)


if __name__ == "__main__":
    submit()

Submission status: Time Limit Exceeded

Solution code:
import copy

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

if __name__ == "__main__":
    N = int(input())
    X = list(input())

    for i in range(N):
        if X[i] == '1':
            X[i] = '0'
        else:
            X[i] = '1'
        pop = int(''.join(X), 2)
        f = 0
        while pop!=0:
            f += 1
            pop = pop % popcount(pop)

        print(f)
        if X[i] == '1':
            X[i] = '0'
        else:
            X[i] = '1'

Submission status: Time Limit Exceeded

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

bbb=x.count('1')
bn = int(x, 2)

for i in range(n):
    waru = bbb
    count = 0
    if x[i] == '1':
        num = bn - 2**(n-i-1)
        waru -= 1
    else:
        num = bn + 2**(n-i-1)
        waru += 1

    while waru != 0:
        num = num%waru
        waru = str(bin(num)).count('1')
        count += 1
    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()

max_pop = 200000
pop_list = [0] * (max_pop+1)
for i in range(1, max_pop+1):
    pop_list[i] = popcount(i)

ans_list = [0] * (max_pop+1)
for i in range(1, max_pop+1):
    new = i
    ans = 0
    while True:
        if new == 0:
            break
        ans += 1
        new = new % pop_list[new]
    ans_list[i] = ans

pop = 0
X = 0
for i in range(N):
    if bin_X[i]=="1":
        pop += 1
        X += 2**(N-i-1)


for i in range(N):
    if bin_X[i] == "0":
        new = X + 2**(N-i-1)
        pop_new = pop + 1
    else:
        new = X - 2**(N-i-1)
        pop_new = pop - 1
    #print(new)
    if new == 0:
        ans = 0
    else:
        new = new % pop_new
        ans = ans_list[new] + 1
        
    print(ans)

Submission status: Time Limit Exceeded

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

cnt = 0
def func(n):
    global cnt
    if n == 0:
        return cnt
    n = n % bin(n).count('1')
    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