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 main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    x=input().rstrip()
    p=x.count("1")
    minus=0
    plus=0
    numlst=[0]*n
    for i in range(n):
        number=2**i
        numlst[-i-1]=number
        if x[-i-1]=="1":
            plus+=number
            plus%=(p+1)
            if p!=1:
                minus+=number
                minus%=(p-1)

    def popcnt(x):
        cnt=str(bin(x)).count("1")
        x%=cnt
        return x

    for i in range(n):
        if x[i]=="0":
            amari=(plus+numlst[i]%(p+1))%(p+1)
            ans=1
            while amari>=1:
                amari=popcnt(amari)
                ans+=1
            print(ans)
        else:
            if p==1:
                print(0)
                continue
            amari=(minus-numlst[i]%(p-1))%(p-1)
            ans=1
            while amari>=1:
                amari=popcnt(amari)
                ans+=1
            print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
len = int(input())
str = input()
a = 0
global pool
pool = {}

for i in range(len):
	a += int(str[len-1-i])*2**i

def inverse(a,i):
	if (a >> i) % 2 == 1:
		return a - (1 << i)
	return a + (1 << i)

def popcount(a):
	count = 0
	while a > 0:
		count += a % 2
		a >>= 1
	return count

def req(a):
	global pool
	if a not in pool:
		pool[a] = popcount(a)
	return pool[a]

for i in range(len):
	p = inverse(a,len-i-1)
	count = 0
	while p != 0:
		p = p % req(p)
		count += 1
	print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
B = input()
B_1 = B.count("1")
mod_p1 = int(B,2) % (B_1+1)
if B_1 != 1:
    mod_m1 = int(B,2) % (B_1-1)

def calc_small(n, iter):
    iter += 1
    mod = n % bin(n).count("1")

    if mod == 0:
        return iter
    else:
        return calc_small(mod, iter)


for i in range(N):
    if B_1 == 1 and int(B[i]) == 1:
        print(0)
        continue
    mod = (mod_m1 - ((2**(N-i-1)) % (B_1-1))) % (B_1-1) if int(B[i]) == 1 else (mod_p1 + ((2**(N-i-1)) % (B_1+1))) % (B_1+1)
    iter = 1
    if mod == 0:
        print(iter)
    else:
        print(calc_small(mod, iter))

Submission status: Time Limit Exceeded

Solution code:
len = int(input())
str = input()
a = 0

for i in range(len):
	a += int(str[len-1-i])*2**i

def inverse(a,i):
	if (a >> i) % 2 == 1:
		return a - (1 << i)
	return a + (1 << i)

def popcount(a):
	count = 0
	while a > 0:
		count += a % 2
		a >>= 1
	return count

for i in range(len):
	p = inverse(a,len-i-1)
	count = 0
	while p != 0:
		p = p % popcount(p)
		count += 1
	print(count)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    x=input().rstrip()
    p=x.count("1")
    minus=0
    plus=0
    for i in range(n):
        if x[-i-1]=="1":
            plus+=2**i
            plus%=(p+1)
    if p!=1:
        for i in range(n):
            if x[-i-1]=="1":
                minus+=2**i
                minus%=(p-1)

    def popcnt(x):
        cnt=str(bin(x)).count("1")
        x%=cnt
        return x

    for i in range(n):
        if x[i]=="0":
            amari=(plus+2**(n-i-1)%(p+1))%(p+1)
            ans=1
            while amari>=1:
                amari=popcnt(amari)
                ans+=1
            print(ans)
        else:
            if p==1:
                print(0)
                continue
            amari=(minus-2**(n-i-1)%(p-1))%(p-1)
            ans=1
            while amari>=1:
                amari=popcnt(amari)
                ans+=1
            print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

if cnt1 > 1:
  x10mod_m = x10 % (cnt1-1)
  x10mod_p = x10 % (cnt1+1)
else:
  x10mod_m = 0
  x10mod_p = 0

ans = []
add_val = 1<<n
for i in range(n):
  add_val = add_val >> 1
  if x[i] == '1':
    if cnt1 == 1:
      print(0)
      continue
    cntx = cnt1-1
    mod = ( x10mod_m - add_val ) % cntx
  else:
    cntx = cnt1+1
    mod = ( x10mod_p + add_val ) % cntx
    
  cnt = 1
  mod = format(mod, 'b')
  
  while True:
    if mod == '0':
      break
    one_cnt = mod.count('1')
    mod_10 = int(mod,2)
    mod = format( mod_10 % one_cnt, 'b')
    cnt += 1
  print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
x=input().rstrip()
p=x.count("1")
minus=0
plus=0
for i in range(n):
    if x[-i-1]=="1":
        plus+=2**i
        plus%=(p+1)
if p!=1:
    for i in range(n):
        if x[-i-1]=="1":
            minus+=2**i
            minus%=(p-1)

def popcnt(x):
    cnt=str(bin(x)).count("1")
    x%=cnt
    return x

for i in range(n):
    if x[i]=="0":
        amari=(plus+2**(n-i-1)%(p+1))%(p+1)
        ans=1
        while amari>=1:
            amari=popcnt(amari)
            ans+=1
        print(ans)
    else:
        if p==1:
            print(0)
            continue
        amari=(minus-2**(n-i-1)%(p-1))%(p-1)
        ans=1
        while amari>=1:
            amari=popcnt(amari)
            ans+=1
        print(ans)

Submission status: Time Limit Exceeded

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



B_1 = B.count("1")
mod_list_m1 = []
mod_list_p1 = []

mod_m1 = 0
mod_p1 = 0
for i in range(N):
    if B_1 != 1:
        mm1 = (2**(N-i-1)) % (B_1-1)
        mod_list_m1.append(mm1)
        
    mp1 = (2**(N-i-1)) % (B_1+1)
    mod_list_p1.append(mp1)
mod_p1 = int(B,2) % (B_1+1)
if B_1 != 1:
    mod_m1 = int(B,2) % (B_1-1)

def calc_small(n, iter):
    iter += 1
    mod = n % bin(n).count("1")

    if mod == 0:
        return iter
    else:
        return calc_small(mod, iter)

for i in range(N):
    if B_1 == 1 and int(B[i]) == 1:
        print(0)
        continue
    mod = (mod_m1 - mod_list_m1[i]) % (B_1-1) if int(B[i]) == 1 else (mod_p1 + mod_list_p1[i]) % (B_1+1)
    iter = 1
    if mod == 0:
        print(iter)
    else:
        print(calc_small(mod, iter))

Submission status: Time Limit Exceeded

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

def popcount(X,ones,count): 
    #print(count,bin(X),X,ones)
    if ones==0:
        return count
    else:
      
        X=X%ones
        
        count+=1
 
        ones=str(bin(X)).count("1")
        
        return popcount(X,ones,count)
 

    
GroundOnes=x.count("1")
GroundX=int(x,2)

if GroundOnes>1:
    CaseOne= GroundX%(GroundOnes-1)
else:
    CaseOne=2

CaseZero= GroundX%(GroundOnes+1)

TwoPowerCaseOne=[]
TwoPowerCaseZero=[]

if GroundOnes>1:
    for j in range(N):
      #TwoPowerCaseOne.append(pow(2,(N-j-1) , (GroundOnes-1)))
      TwoPowerCaseOne.append(2**(N-j-1) % (GroundOnes-1))
      #TwoPowerCaseZero.append(pow(2,(N-j-1), (GroundOnes+1)))
      TwoPowerCaseZero.append(2**(N-j-1) % (GroundOnes+1))
else:
    for j in range(N):
      TwoPowerCaseZero.append(2**(N-j-1) % (GroundOnes+1))
  
    
for i in range(N):
    
    #CaseOne
    if x[i]=="1":
        ones=GroundOnes-1
        if ones>0:
            X=CaseOne-pow(2,N-i-1,ones)
        else:
            X=0
    #CaseZero
    else:
        ones=GroundOnes+1
        X=CaseZero+pow(2,N-i-1,ones)
            
 
    # print("for loop",i)
    # print("ones",ones)
    # print("new2bit",new2bit)
    #print(" ------ return --- ",popcount(X,ones,0))
    print(popcount(X,ones,0))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=input()
xx=x.count('1')
if xx!=1 and xx!=0:
    xx2=int(x,2)
    a1=xx2%(xx-1)
    a2=xx2%(xx+1)
    k=2**n
    for i in range(n):
        k//=2
        if x[i]=='0':
            aa1=(a2+k)%(xx+1)
            aa2=bin(aa1).count('1')
        else:
            aa1=(a1-k)%(xx-1)
            aa2=bin(aa1).count('1')
        if aa1==0:
            print(1)
        else:
            count=1
            while aa1!=0:
                aa1%=aa2
                aa2=bin(aa1).count('1')
                count+=1
            print(count)
elif xx==0:
    for i in range(n):
        print(1)
else:
    x1=int(x,2)
    for i in range(n):
        k=2**(n-1-i)
        if x[i]=='1':
            print(0)
        else:
            x1+=k
            x2=2
            count=0
            while x1!=0:
                x1%=x2
                x2=bin(x1).count('1')
                count+=1
            print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
LIM=200004
L=[0]*LIM

def bin_sum(Y):
    S=bin(Y)[2:]
    count=0
    for i in range(len(S)):
        count+=int(S[i])
    return count

def bin_sum2(Y):
    count=0
    for i in range(len(Y)):
        count+=int(Y[i])
    return count

for i in range(1,LIM):
    L[i]+=bin_sum(i)

def pop_num(N,b,L):
    if N==0:
        return 0
    v=N%b
    return pop_num(v,L[v],L)+1
    
M=[0]*200005
for i in range(1,200004):
    M[i]+=pop_num(i,L[i],L)
X=int(input())
Y=input()
d=bin_sum2(Y)
e=int(Y,2)%(d+1)
f=int(Y,2)%max(1,(d-1))
O=[1]*(X+2)
for i in range(1,X+1):
    O[i]=2*O[i-1]
for i in range(X):
    if int(Y[i])==1:
        b=max(d-1,1)
        flag=max(0,d-1)
        g=(f-O[X-1-i]%b+b)%b
    else:
        b=d+1
        flag=1
        g=(e+O[X-1-i])%b

    if flag==0:
        print(0)
    elif g==0:
        print(1)
    else:
        print(M[g]+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
x=input().rstrip()
p=x.count("1")
numx=0
for i in range(n):
    if x[-i-1]=="1":
        numx+=2**i
if p!=1:
    minus=numx%(p-1)
plus=numx%(p+1)

def popcnt(x):
    cnt=str(bin(x)).count("1")
    x%=cnt
    return x

for i in range(n):
    if x[i]=="0":
        amari=(plus+2**(n-i-1)%(p+1))%(p+1)
        ans=1
        while amari>=1:
            amari=popcnt(amari)
            ans+=1
        print(ans)
    else:
        if p==1:
            print(0)
            continue
        amari=(minus-2**(n-i-1)%(p-1))%(p-1)
        ans=1
        while amari>=1:
            amari=popcnt(amari)
            ans+=1
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
LIM=200004
L=[0]*LIM

def bin_sum(Y):
    S=bin(Y)[2:]
    count=0
    for i in range(len(S)):
        count+=int(S[i])
    return count

def bin_sum2(Y):
    count=0
    for i in range(len(Y)):
        count+=int(Y[i])
    return count

for i in range(1,LIM):
    L[i]+=bin_sum(i)

def pop_num(N,b,L):
    if N==0:
        return 0
    v=N%b
    return pop_num(v,L[v],L)+1
    
M=[0]*200005
for i in range(1,200004):
    M[i]+=pop_num(i,L[i],L)
X=int(input())
Y=input()
d=bin_sum2(Y)
e=int(Y,2)%(d+1)
f=int(Y,2)%max(1,(d-1))
for i in range(X):
    if int(Y[i])==1:
        b=max(d-1,1)
        flag=max(0,d-1)
        g=(f-pow(2,X-1-i)%b+b)%b
    else:
        b=d+1
        flag=1
        g=(e+pow(2,X-1-i))%b

    if flag==0:
        print(0)
    elif g==0:
        print(1)
    else:
        print(M[g]+1)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
  N = int(input())
  X = input()
  base_1_count = X.count("1")
  X_int = int(X, 2)

  for i in range(N):
    first_1_count = base_1_count
    if X[i] == "1":
      first_1_count -= 1
      Xi = X_int - 2**(N-i-1)
    else:
      first_1_count += 1
      Xi = X_int + 2**(N-i-1)
    count = 0
    num_of_1 = first_1_count
    while Xi != 0:
      Xi = Xi % num_of_1
      num_of_1 = bin(Xi).count("1")
      count += 1
    print(count)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
LIM=200004
L=[0]*LIM

def bin_sum(Y):
    S=bin(Y)[2:]
    count=0
    for i in range(len(S)):
        count+=int(S[i])
    return count

def bin_sum2(Y):
    count=0
    for i in range(len(Y)):
        count+=int(Y[i])
    return count

for i in range(1,LIM):
    L[i]+=bin_sum(i)

def pop_num(N,b,L):
    if N==0:
        return 0
    v=N%b
    return pop_num(v,L[v],L)+1
    
M=[0]*200005
for i in range(1,200004):
    M[i]+=pop_num(i,L[i],L)
X=int(input())
Y=input()
d=bin_sum2(Y)
e=int(Y,2)%(d+1)
f=int(Y,2)%max(1,(d-1))
for i in range(X):
    if int(Y[i])==1:
        b=max(d-1,1)
        flag=max(0,d-1)
        g=(f-2**(X-1-i)%b+b)%b
    else:
        b=d+1
        flag=1
        g=(e+2**(X-1-i))%b

    if flag==0:
        print(0)
    elif g==0:
        print(1)
    else:
        print(M[g]+1)

Submission status: Time Limit Exceeded

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

from collections import Counter
cnt1 = Counter( list(x) )['1']
x10 = int(x,2)

if cnt1 > 1:
  x10mod_m = x10 % (cnt1-1)
  x10mod_p = x10 % (cnt1+1)
else:
  x10mod_m = 0
  x10mod_p = 0

ans = []
add_val = 1<<n
for i in range(n):
  add_val = add_val >> 1
  if x[i] == '1':
    if cnt1 == 1:
      print(0)
      continue
    cntx = cnt1-1
    mod = ( x10mod_m - add_val ) % cntx
  else:
    cntx = cnt1+1
    mod = ( x10mod_p + add_val ) % cntx
    
  cnt = 1
  mod = format(mod, 'b')
  
  while True:
    if mod == '0':
      break
    one_cnt = Counter( list(mod) )['1']
    mod_10 = int(mod,2)
    mod = format( mod_10 % one_cnt, 'b')
    cnt += 1
  print(cnt)

Submission status: Time Limit Exceeded

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


B_1 = B.count("1")
mod_list_m1 = []
mod_list_p1 = []

mod_m1 = 0
mod_p1 = 0
for i in range(N):
    if B_1 != 1:
        mm1 = (2**(N-i-1)) % (B_1-1)
        mod_list_m1.append(mm1)
        mod_m1 += int(B[i])*mm1
    mp1 = (2**(N-i-1)) % (B_1+1)
    mod_list_p1.append(mp1)
    mod_p1 += int(B[i])*mp1

def calc_small(n, iter):
    iter += 1
    mod = n % bin(n).count("1")

    if mod == 0:
        return iter
    else:
        return calc_small(mod, iter)

for i in range(N):
    if B_1 == 1 and int(B[i]) == 1:
        print(0)
        continue
    mod = (mod_m1 - mod_list_m1[i]) % (B_1-1) if int(B[i]) == 1 else (mod_p1 + mod_list_p1[i]) % (B_1+1)
    iter = 1
    if mod == 0:
        print(iter)
    else:
        print(calc_small(mod, iter))

Submission status: Time Limit Exceeded

Solution code:
def resolve():
  N = int(input())
  X = input()
  base_1_count = X.count("1")
  X_int = int(X, 2)

  for i in range(N):
    first_1_count = base_1_count
    if X[i] == "1":
      first_1_count -= 1
      Xi = X_int - 2**(N-i-1)
    else:
      first_1_count += 1
      Xi = X_int + 2**(N-i-1)
    count = 0
    num_of_1 = first_1_count
    while Xi != 0:
      Xi = Xi % num_of_1
      num_of_1 = bin(Xi).count("1")
      count += 1
    print(count)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=input()
xx=x.count('1')
if xx!=1 and xx!=0:
    xx2=int(x,2)
    a1=xx2%(xx-1)
    a2=xx2%(xx+1)
    k=2**n
    for i in range(n):
        k//=2
        if x[i]=='0':
            kk=k%(xx+1)
            aa1=(a2+kk)%(xx+1)
            aa2=str(bin(aa1)).count('1')
        else:
            kk=k%(xx-1)
            aa1=(a1-kk)%(xx-1)
            aa2=str(bin(aa1)).count('1')
        if aa1==0:
            print(1)
        else:
            count=1
            while aa1!=0:
                aa1%=aa2
                aa2=str(bin(aa1)).count('1')
                count+=1
            print(count)
elif xx==0:
    for i in range(n):
        print(1)
else:
    x1=int(x,2)
    for i in range(n):
        k=2**(n-1-i)
        if x[i]=='1':
            print(0)
        else:
            x1+=k
            x2=2
            count=0
            while x1!=0:
                x1%=x2
                x2=str(bin(x1)).count('1')
                count+=1
            print(count)

Submission status: Time Limit Exceeded

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

def popcount(X,ones,count): 
    #print(count,bin(X),X,ones)
    if ones==0:
        return count
    else:
      
        X=X%ones
        
        count+=1
 
        ones=str(bin(X)).count("1")
        
        return popcount(X,ones,count)
 

    
GroundOnes=x.count("1")
GroundX=int(x,2)

if GroundOnes>1:
    CaseOne= GroundX%(GroundOnes-1)
else:
    CaseOne=2

CaseZero= GroundX%(GroundOnes+1)

TwoPowerCaseOne=[]
TwoPowerCaseZero=[]

if GroundOnes>1:
    for j in range(N):
      TwoPowerCaseOne.append(pow(2,(N-j-1) , (GroundOnes-1)))
      TwoPowerCaseZero.append(pow(2**(N-j-1), (GroundOnes+1)))
else:
    for j in range(N):
      TwoPowerCaseZero.append(pow(2**(N-j-1), (GroundOnes+1)))
  
    
for i in range(N):
    
    #CaseOne
    if x[i]=="1":
        ones=GroundOnes-1
        if ones>0:
            X=CaseOne-TwoPowerCaseOne[i]
        else:
            X=0
    #CaseZero
    else:
        ones=GroundOnes+1
        X=CaseZero+TwoPowerCaseZero[i]
            
 
    # print("for loop",i)
    # print("ones",ones)
    # print("new2bit",new2bit)
    #print(" ------ return --- ",popcount(X,ones,0))
    print(popcount(X,ones,0))

Submission status: Time Limit Exceeded

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

# D_1が遅かったTLE：timeで計測し、popcount(N) が遅いことを確認。
# 結論としては、bin(n).count("1") が極めて高速。ライブラリを叩こう！

import io
import sys
import math
from functools import lru_cache

def format_multi_line_answer(lst):
    ans = ""
    for y in lst:
        ans += f"{y}\n"
    return ans

# 標準が早い！文字列のカウンティングなのだが…？なぜなのか。
def popcount(n):    # N=5*10**5ケースではまだかなり遅い。
    return bin(n).count("1")

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

def reverse_one_bit(x,x_len,i):
    ii = x_len - i
    return x ^ 1<<ii

def solve(n,x,x_len):
    # implement process
    ans_l = []
    for i in range(1,n+1):
        xi = reverse_one_bit(x,x_len,i)
        ans_l.append(f(xi))
    return format_multi_line_answer(ans_l)

def main():
    # input
    n = int(input())
    xs = input()
    x_len = len(xs)
    x = int(xs,2)
    
    # process
    ans = str( solve(n,x,x_len) )
    
    # output
    print(ans)
    return ans


# import time
# time_start = [0] * 10**3
# def t_start(i=0):
#     time_start[i] = time.perf_counter()
# def t_end(str="",i=0):
#     print(f"time {str}: {time.perf_counter() - time_start[i]}")

### DEBUG I/O ###
_DEB = 0   # 1:ON / 0:OFF

_INPUT = """\
200000
"""+("01"*10**5)
# 50000
# """+("01"*(25*10**3))



_EXPECTED = """\
2
1
2
2
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
3

"""

def logd(str):
    """usage:
    if _DEB: logd(f"{str}")
    """
    if _DEB: print(f"[deb] {str}")

### MAIN ###
if __name__ == "__main__":
    if _DEB:
        sys.stdin = io.StringIO(_INPUT)
        print("!! Debug Mode !!")
    
    ans = main()

    if _DEB:
        print()
        if _EXPECTED.strip() == ans.strip(): print("!! Success !!")
        else: print(f"!! Failed... !!\nANSWER:   {ans}\nExpected: {_EXPECTED}")

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=input()
xx=x.count('1')
if xx!=1 and xx!=0:
    xx2=int(x,2)
    a1=xx2%(xx-1)
    a2=xx2%(xx+1)
    for i in range(n):
        k=2**(n-1-i)
        if x[i]=='0':
            k=k%(xx+1)
            aa1=(a2+k)%(xx+1)
            aa2=str(bin(aa1)).count('1')
        else:
            k=k%(xx-1)
            aa1=(a1-k)%(xx-1)
            aa2=str(bin(aa1)).count('1')
        if aa1==0:
            print(1)
        else:
            count=1
            while aa1!=0:
                aa1%=aa2
                aa2=str(bin(aa1)).count('1')
                count+=1
            print(count)
elif xx==0:
    for i in range(n):
        print(1)
else:
    x1=int(x,2)
    for i in range(n):
        k=2**(n-1-i)
        if x[i]=='1':
            print(0)
        else:
            x1+=k
            x2=2
            count=0
            while x1!=0:
                x1%=x2
                x2=str(bin(x1)).count('1')
                count+=1
            print(count)

Submission status: Time Limit Exceeded

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

from collections import Counter
cnt1 = Counter( list(x) )['1']
x10 = int(x,2)

if cnt1 > 1:
  x10mod_m = x10 % (cnt1-1)
  x10mod_p = x10 % (cnt1+1)
else:
  x10mod_m = 0
  x10mod_p = 0

ans = []
for i in range(n):
  if x[i] == '1':
    if cnt1 == 1:
      print(0)
      continue
    cntx = cnt1-1
    mod = ( x10mod_m - (1<<(n-i-1)) ) % cntx
  else:
    cntx = cnt1+1
    mod = ( x10mod_p + (1<<(n-i-1)) ) % cntx
    
  cnt = 1
  mod = format(mod, 'b')
  
  while True:
    if mod == '0':
      break
    one_cnt = Counter( list(mod) )['1']
    mod_10 = int(mod,2)
    mod = format( mod_10 % one_cnt, 'b')
    cnt += 1
  print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
  N = int(input())
  X = input()
  base_1_count = X.count("1")

  for i in range(N):
    tar_X = list(X)
    first_1_count = base_1_count
    if tar_X[i] == "1":
      first_1_count -= 1
      tar_X[i] = "0"
    else:
      first_1_count += 1
      tar_X[i] = "1"
    target_int = int(''.join(tar_X), 2)
    count = 0
    num_of_1 = first_1_count
    while target_int != 0:
      target_int = target_int % num_of_1
      num_of_1 = bin(target_int).count("1")
      count += 1
    print(count)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:

def resolve():
  N = int(input())
  X = input()
  base_1_count = X.count("1")

  for i in range(N):
    tar_X = list(X)
    first_1_count = base_1_count
    if tar_X[i] == "1":
      first_1_count -= 1
      tar_X[i] = "0"
    else:
      first_1_count += 1
      tar_X[i] = "1"
    target_int = int(''.join(tar_X), 2)
    count = 0
    num_of_1 = first_1_count
    while target_int != 0:
      target_int = target_int % num_of_1
      num_of_1 = bin(target_int).count("1")
      count += 1
    print(count)

if __name__ == "__main__":
  resolve()

Submission status: Time Limit Exceeded

Solution code:
import numba
from numba import jit

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

@jit
def popcount(ni):
    n_b = str(bin(ni))
    return n_b.count("1")

@jit
def ans(n,x):
    x_i = int(x, 2)
    x_orig = popcount(x_i)
    solve = 0
    for i in range(n):
        x_count = x_orig
        if x[i] == "0":
            solve = x_i+2**(n-i-1)
            x_count += 1
        else:
            solve = x_i-2**(n-i-1)
            x_count -= 1
        count = 0

        if solve != 0 :
            solve = solve % x_count
            count+=1

        while solve > 0:
            solve = solve % popcount(solve)
            count+=1

        print(count)

    
ans(n,x)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache


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


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


ret = [rec(x) for x in range(2 * 10**5 + 1)]


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

ALL_ARR = int(arr, 2)

cnt = popcnt(int(arr, 2))
init_big = ALL_ARR % (cnt + 1)
if cnt == 1:
    init_small = 0
else:
    init_small = ALL_ARR % (cnt - 1)


li = [0] * n
for i in range(n):
    if arr[i] == "0":
        li[i] = (init_big + (1 << (n - i - 1))) % (cnt + 1)
    elif ALL_ARR - (1 << (n - i - 1)) == 0 or cnt - 1 == 0:
        li[i] = "flg"
    else:
        li[i] = (init_small - (1 << (n - i - 1))) % (cnt - 1)


ans = []

for x in li:
    if x == "flg":
        ans.append(0)
    else:
        ans.append(ret[x] + 1)

print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D_fix
# CreatedDate:  2020-07-12 00:58:11 +0900
# LastModified: 2020-07-12 01:18:49 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd


def main():
    n = int(input())
    x = input()
    for i in range(1, n+1):
        s = int(x, 2)
        s ^= 1 << (n-i)
        cnt = 0
        while s:
            ama_cnt = 0
            for i in range(n):
                if s>>i & 1:
                    ama_cnt += 1
            s %= ama_cnt
            cnt += 1
        print(cnt)



if __name__ == "__main__":
    main()

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 count(n):
    ans = 0
    while n:
        ans += n % 2
        n //= 2
    return ans


ma=50000000
n_dic=[0]*ma


def f(first_n):
  i=0
  n=first_n
  while not n==0:
    if ma>n:
      if not n_dic[n]==0:
        n_dic[first_n]=n_dic[n]+i
        return n_dic[n]+i
      else:
        #n = n % popcount(n)
        n = n % count(n)
        i+=1
    else:
      #n = n % popcount(n)
      n = n % count(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))
#print(n_dic)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache


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


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


ret = [rec(x) for x in range(2 * 10**5 + 1)]


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

cnt = popcnt(int(arr, 2))
init_big = int(arr, 2) % (cnt + 1)
if cnt == 1:
    init_small = 0
else:
    init_small = int(arr, 2) % (cnt - 1)

ALL_ARR = int(arr, 2)

li = [0] * n
for i in range(n):
    if arr[i] == "0":
        li[i] = (init_big + (1 << (n - i - 1))) % (cnt + 1)
    elif ALL_ARR - (1 << (n - i - 1)) == 0 or cnt - 1 == 0:
        li[i] = "flg"
    else:
        li[i] = (init_small - (1 << (n - i - 1))) % (cnt - 1)


ans = []

for x in li:
    if x == "flg":
        ans.append(0)
    else:
        ans.append(ret[x] + 1)

print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
LIM=200004
L=[0]*LIM

def bin_sum(Y):
    S=bin(Y)[2:]
    count=0
    for i in range(len(S)):
        count+=int(S[i])
    return count

def bin_sum2(Y):
    count=0
    for i in range(len(Y)):
        count+=int(Y[i])
    return count

for i in range(1,LIM):
    L[i]+=bin_sum(i)

def pop_num(N,b,L):
    if N==0:
        return 0
    v=N%b
    return pop_num(v,L[v],L)+1
    
M=[0]*200005
for i in range(1,200004):
    M[i]+=pop_num(i,L[i],L)
X=int(input())
Y=input()
d=bin_sum2(Y)
e=int(Y,2)%(d+1)
f=int(Y,2)%max(1,(d-1))
for i in range(X):
    if Y[i]=="0":
        b=d+1
        flag=1
        g=(e+2**(X-1-i))%b
    else:
        b=max(d-1,1)
        flag=max(0,d-1)
        g=(f-2**(X-1-i)%b+b)%b
    if flag==0:
        print(0)
    elif g==0:
        print(1)
    else:
        print(M[g]+1)

Submission status: Time Limit Exceeded

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


N = int(input())
A = int(input().rstrip(), 2)


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


AL = []
for n in range(N):
    AL.append(f(n))

# print(AL)

for i in range(N)[::-1]:
    a = A ^ (1 << i)
    if a != 0:
        n = a % bin(a).count('1')
        print(AL[n]+1)
    else:
        print(AL[0])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
x = input()
#print(int(x,2))

def popcount(X,ones,count): 
    #print(count,bin(X),X,ones)
    if ones==0:
        return count
    else:
      
        X=X%ones
        
        count+=1
 
        ones=str(bin(X)).count("1")
        
        return popcount(X,ones,count)
 

    
GroundOnes=x.count("1")
GroundX=int(x,2)

if GroundOnes>1:
    CaseOne= GroundX%(GroundOnes-1)
else:
    CaseOne=2

CaseZero= GroundX%(GroundOnes+1)

TwoPowerCaseOne=[]
TwoPowerCaseZero=[]

if GroundOnes>1:
    for j in range(N):
      TwoPowerCaseOne.append(2**(N-j-1) % (GroundOnes-1))
      TwoPowerCaseZero.append(2**(N-j-1) % (GroundOnes+1))
else:
    for j in range(N):
      TwoPowerCaseZero.append(2**(N-j-1) % (GroundOnes+1))
  
for i in range(N):
    
    #CaseOne
    if x[i]=="1":
        ones=GroundOnes-1
        if ones>0:
            X=CaseOne-TwoPowerCaseOne[i]
        else:
            X=0
    #CaseZero
    else:
        ones=GroundOnes+1
        X=CaseZero+TwoPowerCaseZero[i]
    print(popcount(X,ones,0))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache


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


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


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

cnt = popcnt(int(arr, 2))
init_big = int(arr, 2) % (cnt + 1)
if cnt == 1:
    init_small = 0
else:
    init_small = int(arr, 2) % (cnt - 1)

ALL_ARR = int(arr, 2)

li = [0] * n
for i in range(n):
    if arr[i] == "0":
        li[i] = (init_big + (1 << (n - i - 1))) % (cnt + 1)
    elif ALL_ARR - (1 << (n - i - 1)) == 0 or cnt - 1 == 0:
        li[i] = "flg"
    else:
        li[i] = (init_small - (1 << (n - i - 1))) % (cnt - 1)


ans = []

for x in li:
    if x == "flg":
        ans.append(0)
    else:
        ans.append(rec(x) + 1)

print(*ans, sep="\n")

Submission status: Time Limit Exceeded

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

def popcount(ni):
    n_b = str(bin(ni))
    return n_b.count("1")

def ans(n,x):
    x_i = int(x, 2)
    x_orig = popcount(x_i)
    solve = 0
    for i in range(n):
        x_count = x_orig
        if x[i] == "0":
            solve = x_i+2**(n-i-1)
            x_count += 1
        else:
            solve = x_i-2**(n-i-1)
            x_count -= 1
        count = 0

        if solve != 0 :
            solve = solve % x_count
            count+=1

        while solve > 0:
            solve = solve % popcount(solve)
            count+=1

        print(count)

    
ans(n,x)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N=ii()
    X=input()

    x=int(X,2)
    pop_X=bin(x).count("1")

    for i in range(N):
        sign = 1
        pop_Xi = pop_X
        if X[i] == "1": 
            sign *= -1
            pop_Xi -= 1
        else:
            pop_Xi += 1
        
        if pop_Xi == 0:
            print(0)
            continue

        two = pow(2,N-1-i,pop_Xi)
        X_i = x % pop_Xi + sign * two
        X_i %= pop_Xi
        count = 1
        while X_i:
            pop_Xi = bin(X_i).count("1")
            X_i = X_i % pop_Xi
            count += 1

        print(count)



if __name__ == "__main__":
    main()