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 popcount(n):
  num=list(bin(n)[2:])
  num = [int(s) for s in num]
  return sum(num)

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)
        i+=1
    else:
      n = n % popcount(n)
      i+=1
  return i

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = [int(i)  for i in list(input())]
xx = X.copy()
n = 0

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

def answer(n): # 10進数を入力
    ans = 0
    while(n != 0):
        n = n%popcnt(n)
        ans += 1
    return ans

for i in range(N):
    if X[i] == 0:
        xx[i] = 1
    else:
        xx[i] = 0
#     print(xx)
    # 2進数の変換
    for jj in range(1,len(xx)+1):
        n += xx[-jj]*2**(jj-1)
    print(answer(n))
    #初期化
    n = 0
    xx = X.copy()

Submission status: Time Limit Exceeded

Solution code:
def fun(n):
    ops = 0
    while n:
        pc = format(n, 'b').count('1')
        n %= pc
        ops += 1
    return ops

n = int(input())
xs = input()

sm = int(xs, 2)
pc = xs.count('1')

mp = sm % (pc + 1)
mm = sm % (pc - 1) if pc > 1 else 0

for i, x in enumerate(xs, 1):
    df = 1 if x == '0' else -1
    pci = pc + df
    if pci == 0:
        print(0)
        continue

    #rest = pow(2, n - i, pci)
    rest = (1 << (n - i)) % pci

    if x == '0':
        smi = (mp + rest) % pci
        print(1 + fun(smi))
    else:
        smi = (mm - rest) % pci
        print(1 + fun(smi))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = input()
ans = [1 for _ in range(N)]
#original 1 count
l = 0
for k in range(N):
  if X[k] == '1':
    l+=1


intN = int(X, 2)
if l >1:
  N1 = intN %(l-1)
N0 = intN % (l+1)


start = []
if N == 1:
  if X[0] == '1':
    print(0)
    exit()
  else:
    print(1)
    exit()

else:
  for k in range(N):
    if X[k] == '1':
      if l == 1:
        ans[k] = 0
        ia =0
      else:  
        ia = (N1 - pow(2,N-k-1))%(l-1)
    else:
      ia = (N0 + pow(2, N-k-1))%(l+1)
    start.append(ia)
"""
ml = len(bin(l+1))-2
poplist = [0 for _ in range(N)]
t = 1
while t < N + 1:
  t *= 2
  for k in range(t//2, N, t):
    for j in range(t//2):
      if k+j>N-1:
        break
      poplist[k+j] += 1
"""

def popcount(n):
  c = 0
  n = bin(n)[2:]
  for k in range(len(n)):
    if n[k] == '1':
      c+=1
  return c

for k in range(len(start)):
  for count in range(10*5):
    if start[k] == 0:
      ans[k] += count
      break
    else:
      start[k] = start[k] % popcount(start[k])

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

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)

li = [0] * n
for i in range(n):
    if arr[i] == "0":
        li[i] = (init_big + (1 << (n - i - 1))) % (cnt + 1)
    elif int(arr[:i] + str(1 ^ int(arr[i])) + arr[i + 1:], 2) == 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:
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)


def solve(N: int, X: str):
    memo = {}
    def popcount(v):
        if v == 0:
            return 0
        if v in memo:
            return memo[v]
        tmp, b = v, 0
        while tmp > 0:
            b += tmp % 2
            tmp //= 2
        if v % b == 0:
            memo[v] = 1
            return 1
        memo[v] = 1 + popcount(v % b)
        return memo[v]
    X = X[::-1]
    bits = 0
    for i in range(N):
        if X[i] == '1':
            bits += 1

    sums = [0, 0]
    for i in range(N):
        if X[i] == '1':
            if bits > 1:
                sums[0] += pow(2, i, bits - 1)
                sums[0] %= bits - 1
            sums[1] += pow(2, i, bits + 1)
            sums[1] %= bits + 1

    #print(bits, sums)
    ret = []
    for i, x in enumerate(X):
        if bits == 1 and x == '1':
            ret.append(0)
        else:
            if x == '1':
                v = (sums[0] - (1 << i)) % (bits - 1)
            else:
                v = (sums[1] + (1 << i)) % (bits + 1)
            #print(i, x, v)
            ret.append(1 + popcount(v))

    ret.reverse()
    for r in ret:
        print(r)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = next(tokens)  # type: str
    solve(N, X)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = input()
ans = [1 for _ in range(N)]
#original 1 count
l = 0
for k in range(N):
  if X[k] == '1':
    l+=1


intN = int(X, 2)
if l >1:
  N1 = intN %(l-1)
N0 = intN % (l+1)


start = []
if N == 1:
  if X[0] == '1':
    print(0)
    exit()
  else:
    print(1)
    exit()

else:
  for k in range(N):
    if X[k] == '1':
      if l == 1:
        ans[k] = 0
        ia =0
      else:  
        ia = (N1 - pow(2,N-k-1))%(l-1)
    else:
      ia = (N0 + pow(2, N-k-1))%(l+1)
    start.append(ia)

ml = len(bin(l+1))-2
poplist = [0 for _ in range(N)]
t = 1
while t < N + 1:
  t *= 2
  for k in range(t//2, N, t):
    for j in range(t//2):
      if k+j>N-1:
        break
      poplist[k+j] += 1


for k in range(len(start)):
  for count in range(10*5):
    if start[k] == 0:
      ans[k] += count
      break
    else:
      start[k] = start[k] % poplist[start[k]]

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

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")

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)

Submission status: Time Limit Exceeded

Solution code:
def readinput():
    n=int(input())
    x=input()
    return n,x


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

def f(n):
    #print(n)
    if n==0:
        return 0
    else:
        m=n%popcount(n)
        return f(m)+1

def main(n,x):
    intx=int(x,2)
    ans=[]
    b=1
    for i in range(n):
        y=intx^b
        ans.append(f(y))
        b=b*2
    return reversed(ans)

def makeFtbl(n):
    Ftbl=[0]*(n+1)
    Ftbl[1]=1
    Ftbl[2]=1
    for i in range(3,n+1):
        m=i%popcount(i)
        Ftbl[i]=Ftbl[m]+1
    return Ftbl

def main2(n,x):
    Ftbl=makeFtbl(n)
    intx=int(x,2)
    return [0]

popinit=False
popdict={}
def popcounts(x):
    global popinit
    global popdict
    '''文字列xに含まれる'1'の数を返す
    '''
    if x.find('0b')!=-1:
        x=x[2:]
    if not popinit:
        popdict[x]=x.count('1')
        for i in range(len(x)):
            ibit=int(x[i],2)
            jbit=ibit^1
            y=x[:i]+str(jbit)+x[i+1:]
            if ibit==1:
                popdict[y]=popdict[x]-1
            else:
                popdict[y]=popdict[x]+1
        popinit=True
    if x in popdict.keys():
        return popdict[x]
    else:
        return x.count('1')

def fs(n):
    #print(n)
    if n==0:
        return 0
    else:
        binn=bin(n)[2:]
        m=n%popcounts(binn)
        return fs(m)+1

def main3(n,x):
    intx=int(x,2)
    ans=[]
    b=1
    for i in range(n):
        y=intx^b
        ans.append(fs(y))
        b=b*2
    return reversed(ans)

if __name__=='__main__':
    n,x=readinput()
    ans=main3(n,x)
    for a in ans:
        print(a)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
X = input()
pc = X.count('1')
nx = int(X, 2)

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

tmp = pow(2, n)
nxp = nx%(pc+1)
nxm = nx%(pc-1) if pc > 1 else 0
for i in range(n-1, -1, -1):
    if (nx>>i)&1:
        # 2**iを引く
        if pc-1 == 0:
            print(0)
            continue
        p = pow(2, i, pc-1)
        r = (nx-p)%(pc-1)
    else:
        # 2**iを足す
        r = (nx+pow(2, i, pc+1))%(pc+1)

    if r > 0:
        print(f(r) + 1)
    else:
        print(1)

Submission status: Time Limit Exceeded

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

import sys
sys.setrecursionlimit(300000)


def solve(N: int, X: str):
    memo = {}
    def popcount(v):
        if v == 0:
            return 0
        if v in memo:
            return memo[v]
        tmp, b = v, 0
        while tmp > 0:
            b += tmp % 2
            tmp //= 2
        if v % b == 0:
            memo[v] = 1
            return 1
        memo[v] = 1 + popcount(v % b)
        return memo[v]
    X = X[::-1]
    bits = 0
    for i in range(N):
        if X[i] == '1':
            bits += 1

    sums = [0, 0]
    for i in range(N):
        if X[i] == '1':
            if bits > 1:
                sums[0] += pow(2, i, bits - 1)
                sums[0] %= bits - 1
            sums[1] += pow(2, i, bits + 1)
            sums[1] %= bits + 1

    #print(bits, sums)
    ret = []
    for i, x in enumerate(X):
        if bits == 1 and x == '1':
            ret.append(0)
        else:
            if x == '1':
                v = (sums[0] - (1 << i)) % (bits - 1)
            else:
                v = (sums[1] + (1 << i)) % (bits + 1)
            #print(i, x, v)
            ret.append(1 + popcount(v))

    ret.reverse()
    for r in ret:
        print(r)
    return


def solve_(N: int, X: str):
    #memo = [[-1] * 20 for _ in range(20)]
    memo = {}
    def popcount(v, b):
        if v in memo and b in memo[v]:
            return memo[v][b]
        if not v in memo:
            memo[v] = {}
        if v % b == 0:
            memo[v][b] = 1
            return 1
        next_v = v % b
        tmp = next_v
        c = 0
        while tmp > 0:
            c += tmp % 2
            tmp //= 2
        ret = 1 + popcount(next_v, c)
        memo[v][b] = ret
        return ret

    X = X[::-1]
    count = 0
    for i in range(N):
        if X[i] == '1':
            count += 1

    s = 0
    for i in range(N):
        if X[i] == '1':
            s += pow(2, i, count)
            s %= count

    memo[count] = {}
    memo[count]
    ret = []
    for i, x in enumerate(X):
        if x == '1':
            v = N - (1 << i)
            b = count - 1
        else:
            v = N + (1 << i)
            b = count + 1
        print(i, i, x)
        print(v, b)
        ret.append(popcount(v, b))
    ret.reverse()
    for r in ret:
        print(r)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = next(tokens)  # type: str
    solve(N, X)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
f = [0 for i in range(200005)]

def num(a):
    res = 0
    while a:
        if(a&1==1): res = res+1
        a >>= 1
    return res

def pre():
    f[1] = f[2] = 1
    for i in range(1,200005):
        f[i] = 1+f[i%num(i)]

def kpow(a,b):
    res = 1
    while b:
        if b&1: res *= a
        a *= a
        b >>= 1
    return res

def main():
    pre()

    n = eval(input())
    s = input()
    cnt = 0
    for ch in s:
        if ch=='1': cnt = cnt+1
    dec = int(s,2)
    s1 = list(s)
    for i in range(n):
        cnt1 = cnt
        d = dec
        if s1[i]=='0':
            cnt1 += 1
            d += kpow(2,n-i-1)
        else:
            cnt1 -= 1
            d -= kpow(2,n-i-1)
        if d < 200005: print(f[d])
        else: print(1+f[d%cnt1])

main()

Submission status: Time Limit Exceeded

Solution code:
f = [0 for i in range(200005)]

def num(a):
    res = 0
    while a:
        if(a&1==1): res = res+1
        a >>= 1
    return res

def pre():
    f[1] = f[2] = 1
    for i in range(1,200005):
        f[i] = 1+f[i%num(i)]

def main():
    pre()

    n = eval(input())
    s = input()
    cnt = 0
    for ch in s:
        if ch=='1': cnt = cnt+1
    dec = int(s,2)
    s1 = list(s)
    for i in range(n):
        cnt1 = cnt
        d = dec
        if s1[i]=='0':
            cnt1 += 1
            d += pow(2,n-i-1)
        else:
            cnt1 -= 1
            d -= pow(2,n-i-1)
        if d < 200005: print(f[d])
        else: print(1+f[d%cnt1])

main()

Submission status: Time Limit Exceeded

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

def popcount(X,ones,count): 
 
    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)
 
for i in range(N):
    if x[i]=="1":
        #x_ith="0"
        ones=GroundOnes-1
        X=GroundX-2**(N-i-1)
    else:
        #x_ith="1"
        ones=GroundOnes+1
        X=GroundX+2**(N-i-1)
            
 
    # 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=str(input())
pop=[0]

for i in range(1,n):
    ni=0
    a=i
    while a:
        a&=(a-1)
        ni+=1
    nii=i%ni
    pop.append(pop[nii]+1)

x1=int(x,2)    

x2=x.count('1')

for i in range(n):
    if x[i]=='1':
        x3=x2-1
        xi=x1-2**(n-1-i)
    else:
        x3=x2+1
        xi=x1+2**(n-1-i)
    if xi!=0:
        xi=xi%x3
        ans=pop[xi]+1
        print(ans)
    else:
        print(0)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = input()
ans = [1 for _ in range(N)]
#original 1 count
l = 0
for k in range(N):
  if X[k] == '1':
    l+=1


intN = int(X, 2)
if l >1:
  N1 = intN %(l-1)
N0 = intN % (l+1)


start = []
if N == 1:
  if X[0] == '1':
    print(0)
    exit()
  else:
    print(1)
    exit()

else:
  for k in range(N):
    if X[k] == '1':
      if l == 1:
        ans[k] = 0
        ia =0
      else:  
        ia = (N1 - pow(2,N-k-1))%(l-1)
    else:
      ia = (N0 + pow(2, N-k-1))%(l+1)
    start.append(ia)

ml = len(bin(l+1))-2
poplist = [[] for _ in range(ml)]
poplist[0] = [0,1]
for k in range(1, ml):
  for m in range(k):
    poplist[k] += poplist[m]
  for m in range(len(poplist[k])):
    poplist[k][m] += 1

newpoplist = []
for _ in range(len(poplist)):
  newpoplist += poplist[_] 

for k in range(len(start)):
  for count in range(10*5):
    if start[k] == 0:
      ans[k] += count
      break
    else:
      start[k] = start[k] % newpoplist[start[k]]

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

Submission status: Time Limit Exceeded

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

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

    X_int = int(X, 2)
    pcount_X = popcount(X_int)

    for i,bit in enumerate(X):
        mask = 1 << (N-i-1)
        Xi = X_int ^ mask

        pcount_Xi = pcount_X + (-1)**int(bit)

        n = Xi
        pcount_n = pcount_Xi
        ans = 0
        while n > 0:
            ans += 1
            n %= pcount_n
            pcount_n = popcount(n)
        print(ans)

main()

Submission status: Time Limit Exceeded

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


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

stack = {}


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


for i in range(N)[::-1]:
    a = A ^ (1 << i)
    # print(a)
    if a not in stack.keys():
        stack[a] = f(a)
        print(stack[a])
    else:
        print(stack[a])

Submission status: Time Limit Exceeded

Solution code:
import sys


def popcount(n):
    return '{:b}'.format(n).count('1')


def f(n, firstpopcount):
    if not n:
        return 0
    i = 1
    n %= firstpopcount
    # print(f'{n=}')
    while n:
        i += 1
        n %= popcount(n)
    return i


def resolve(in_):
    n = int(in_.readline())
    x = int(in_.readline(), 2)
    xpopcount = popcount(x)
    for i in range(n - 1, -1, -1):
        s = 2 ** i
        v = x ^ s

        if v & s:
            firstpopcount = xpopcount + 1
        else:
            firstpopcount = xpopcount - 1

        # print(f'{x=:b} {v=:b} {1<<i=:b}')
        print(f(v, firstpopcount))


def main():
    resolve(sys.stdin.buffer)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
X = input()
pc = X.count('1')
nx = int(X, 2)

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

tmp = pow(2, n)
for i in range(n-1, -1, -1):
    # ibit目を反転させる # つまり2**iを引く
    tmp //= 2
    if (nx>>i)&1:
        if nx-tmp == 0:
            print(0)
            continue
        r = (nx-tmp)%(pc-1)
    else:
        r = (nx+tmp)%(pc+1)

    if r > 0:
        print(f(r) + 1)
    else:
        print(1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
X = input()
pc = X.count('1')
nx = int(X, 2)

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

tmp = pow(2, n)
for i in range(n-1, -1, -1):
    # ibit目を反転させる # つまり2**iを引く
    tmp //= 2
    if (nx>>i)&1:
        if nx-tmp == 0:
            print(0)
            continue
        r = (nx-tmp)%(pc-1)
    else:
        r = (nx+tmp)%(pc+1)

    if r > 0:
        print(f(r) + 1)
    else:
        print(1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = list(input())
X_list = []

count = [0]*N
for i in range(N):
    ans = X[:]
    if ans[i] == '0':
        ans[i] = '1'
    else:
        ans[i] = '0'
    X_list.append(int(''.join(ans),2))

while(sum(X_list)>0):
    for i in range(N):
        if X_list[i] != 0:
            count[i] += 1
            X_list[i] = X_list[i] % bin(X_list[i]).count('1')

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

Submission status: Time Limit Exceeded

Solution code:
def change_num(tmp, i):
    if tmp[i] == "0":
        return int(tmp, 2)+pow(2, N-i-1)
    else:
        return int(tmp, 2)-pow(2, N-i-1)


def popcount(num):
    tmp1 = bin(num)
    tmp2 = tmp1[2:]
    return tmp2.count("1")


N = int(input())
X = input()
flag = 0

for i in range(N):
    tmp = change_num(X, i)
    # num1 = str(tmp).count("1")
    num1 = popcount(tmp)
    while tmp > 0:
        # print(f"tmp={tmp},num1={num1}")
        tmp = tmp % num1
        num1 = popcount(tmp)
        flag += 1
    print(flag)
    flag = 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 = bin(a).count('1')
        a = a%b
        c += 1
    print(c)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
from sys import flags
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
x=list(input())
cnt=Counter(x)
x2=int("".join(x),2)
one=cnt["1"]
# print(x)
# print(math.log2(2*10**5))
# print(cnt)
# print(x2,one)
lst=[0]*(2*10**5+10)
# lst[0]=-1
flaglst=[0,0]
if one-1!=0:
    flaglst[0]=x2%(one-1)
flaglst[1]=x2%(one+1)
# print(flaglst)

for i in range(2*10**5):
    now=i+1
    ans=0
    while now:
        cnt2=0
        m=0
        while now>=pow(2,m):
            if now&1<<m:
                cnt2+=1
            m+=1
        now%=cnt2
        ans+=1
    lst[i+1]=ans
# # print(lst[:100])

for i in range(n):
    tmp=0
    if x[i]=="1":
        tmp=flaglst[0]
        if one-1!=0:
            tmp-=pow(2,n-1-i,one-1)
            tmp%=one-1
        else:
            print(0)
            continue
    else:
        tmp=x2%(one+1)
        tmp+=pow(2,n-1-i)
        tmp%=one+1
    # print(tmp,pow(2,n-1-i),one)

    print(lst[tmp]+1)

Submission status: Time Limit Exceeded

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

    r = X.count("1")
    r0 = r-1
    r1 = r+1
    ans = []
    for i in range(N):
        if X[i] == '0':
            ans.append(f((X_10 % r1 + pow(2, N-1-i)) % r1))
        else:
            if r == 1:
                ans.append(0)
            else:
                ans.append(f((X_10 % r0 - pow(2, N-1-i)) % r0))
    
    print(*ans, sep='\n')

def f(N):
    cnt = 1
    while N != 0:
        N = N % popcount(N)
        cnt += 1
    
    return cnt

def popcount(N):
    b = bin(N)
    cnt = 0
    for i in range(2,len(b)):
        if b[i] == '1':
            cnt += 1

    return cnt

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
m=input()
x=int(m,2)
li=list(m)
def popcount(x):
  return bin(x).count("1")
def check(a):
  co=1
  while a!=0:
    co+=1
    a%=popcount(a)
  return co
jpop=popcount(x)
if jpop==0:
  flag=True
jppp=jpop+1
jppm=jpop-1
jop=x%jppp
if jppm<=0:
  jom=-1
else:
  jom=x%jppm

for i in range(n):
  nijo=2**(n-1-i)
  if li[i]=="0":
    a=jop+nijo%jppp
    if a>=jppp:
      a-=jppp
  else:
    if jom==-1:
      print(0)
      continue
    a=jom-nijo%max(jppm,1)
    if a<0:
      a+=jppm
  if a==0:
    print(1)
    continue
  print(check(a))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
X=input()
for i in range(N):
    Xi = int(X[:i] + str(1-int(X[i])) + X[i+1:], 2)
    ans = 0
    while Xi!=0:
        Xi = Xi % bin(Xi).count('1')
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
H = {0:0, 1:1}
def getInts():
    return [ int(x) for x in input().split() ]

def complement(c):
    if c=='1':
        return '0'
    else:
        return '1'

def pop(n):
    return "{0:b}".format(n).count('1')

def toZero(n):
    global H
    if n in H:
        return H[n]
    r = 1 + toZero(n%pop(n))
    H[n] = r
    return r

[N] = getInts()
X = input()
X = list(X)
Xp1 = X.count('1')+1
Xp2 = X.count('1')-1
for i in range(N):
    X[i] = complement(X[i])
    n = int("".join(X),2)
    if n in H:
        print(H[n])
    else:
        if X[i]=='1':
            print(toZero(n%Xp1)+1)
        else:
            print(toZero(n%Xp2)+1)
    X[i] = complement(X[i])

Submission status: Time Limit Exceeded

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


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

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

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
from collections import defaultdict

N = int(input())
X = input().strip()

D = defaultdict(int)
D[0] = 0


@lru_cache(maxsize=200005)
def f(x, ans):
    ans += 1
    b = str(bin(x)[2:])
    c = b.count('1')
    m = x % c
    if m == 0:
        return ans
    return f(m, ans)


for i in range(1, 200001):
    D[i] = f(i, 0)


cnt1 = X.count('1')
base = int(X, 2)

for i in reversed(range(N)):
    k = 1 << i
    if X[N - i - 1] == '1':
        n = base - k
        cnt = cnt1 - 1
    else:
        n = base + k
        cnt = cnt1 + 1
    if n == 0:
        print(0)
    else:
        m = n % cnt
        if m == 0:
            print(1)
        else:
            print(f(m, 1))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = input()
ans = [1 for _ in range(N)]
#original 1 count
l = 0
for k in range(N):
  if X[k] == '1':
    l+=1


intN = int(X, 2)
if l >1:
  N1 = intN %(l-1)
N0 = intN % (l+1)


start = []
if N == 1:
  if X[0] == '1':
    print(0)
    exit()
  else:
    print(1)
    exit()
  start.append(ia)

else:
  for k in range(N):
    if X[k] == '1':
      if l == 1:
        ans[k] = 0
        ia =0
      else:  
        ia = (N1 - (2**(N-k-1)))%(l-1)
    else:
      ia = (N0 + (2**(N-k-1)))%(l+1)
    start.append(ia)

ml = len(bin(l+1))-2
poplist = [[] for _ in range(ml)]
poplist[0] = [0,1]
for k in range(1, ml):
  for m in range(k):
    poplist[k] += poplist[m]
  for m in range(len(poplist[k])):
    poplist[k][m] += 1

newpoplist = []
for _ in range(len(poplist)):
  newpoplist += poplist[_] 

for k in range(len(start)):
  for count in range(10*5):
    if start[k] == 0:
      ans[k] += count
      break
    else:
      start[k] = start[k] % newpoplist[start[k]]

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    x = input()
    
    val = 0
    rui = 1
    mod = 0
    
    nagasa = 2*10**5+1
    #nagasa = 5
    d_li = [0]*(nagasa)
    
    for i in range(1,nagasa):
        t_v = i
        t_m = bin(t_v).count("1")
        ans = 0
        while t_v != 0:
            if d_li[t_v] != 0:
                ans += d_li[t_v]
                break
            ans += 1
            t_v %= t_m
            #t_m = bin(t_v).count("1")
        d_li[i] = ans
    
    #print(d_li)
    #exit()
    """
    for i in range(n):
        val += int(x[n-1-i])*rui
        rui *= 2
    """
    val = int(x, 2)
    #print(val)
    #exit()
    
    mod = bin(val).count("1")
    
    rui = pow(2,(n-1))
    
    t_v_p = val % (mod+1)
    if mod == 1:
        t_v_m = 0
    else:
        t_v_m = val % (mod-1)
        
    for i in range(n):
        ans = 0
        #t_v = val
        #t_m = mod
        if int(x[i]) == 1:
            if mod == 1:
                t_v = 0
            else:
                t_v = t_v_m
                t_v -= rui
                #t_v -= rui % (mod-1)
                t_v %= (mod-1)
                ans += 1
                #t_m -= 1
        else:
            t_v = t_v_p
            t_v += rui
            #print(t_v,rui)
            #t_v += rui % (mod+1)
            t_v %= (mod+1)
            ans += 1
            #t_m += 1
        rui //= 2
        #print(t_v,mod)
        #while t_v != 0:
        """
        if t_v != 0:
            if int(x[i]) == 1:
                if mod == 1:
                    t_v = 0
                else:
                    t_v %= mod-1
            else:
                t_v %= mod + 1
            #t_v %= t_m
            ans += 1
        """
        ans += d_li[t_v]
        #t_m = bin(t_v).count("1")
        #ans_li.append(ans)
        print(ans)
        #print(ans_li)
        
if __name__ == '__main__':
    main()
"""
#print(ans_li)
for i in range(n):
    print(ans_li[n-1-i])
"""

Submission status: Time Limit Exceeded

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


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

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

Submission status: Time Limit Exceeded

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

def solve(a, pc):
    ans = 0
    while a != 0:
        a = a % pc
        pc = bin(a).count('1')
        ans += 1
    return ans
        
pc = bin(x).count('1')
pc_p = pc + 1
pc_m = pc - 1

for i in reversed(range(n)):
    if x_bin[n-i-1] == '1':
        a = x - pow(2, i)
        print(solve(a, pc_m))
    else:
        a = x + pow(2, i)
        print(solve(a, pc_p))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
from collections import defaultdict

N = int(input())
X = input().strip()

D = defaultdict(int)
D[0] = 0


@lru_cache(maxsize=200005)
def f(x, ans):
    ans += 1
    b = str(bin(x)[2:])
    c = b.count('1')
    m = x % c
    if m == 0:
        return ans
    return f(m, ans)


for i in range(1, 200001):
    D[i] = f(i, 0)

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