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, X = open(0).read().split()
n = int(n)
x = int(X, 2)
X = list(map(int, X))

def popcount(q):
    c = 0
    while q:
        q, r = divmod(q, 2)
        c += r
    return c

ma = 2 * 10**5 + 1
dp = [0] * ma
for i in range(1, ma):
    dp[i] = dp[i % popcount(i)] + 1

c = popcount(x)
a = x % (c+1)
if c == 1:
    for i in range(n):
        if X[i]:
            print(0)
        else:
            print(dp[(a + pow(2, n-i-1, c+1)) % (c+1)] + 1)
else:
    b = x % (c-1)
    for i in range(n):
        if X[i]:
            print(dp[(b - pow(2, n-i-1, c-1)) % (c-1)] + 1)
        else:
            print(dp[(a + pow(2, n-i-1, c+1)) % (c+1)] + 1)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

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

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

for i in range(n - 1, -1, -1):
  pb = b ^ (1 << i)
  print(f(pb))

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):
        bit = int(bit)
        pcount_Xi = pcount_X + (-1)**bit

        if pcount_Xi == 0:
            print(0)
            continue

        if bit == 0:
            n = ((X_int % pcount_Xi) + pow(2, N-i-1, pcount_Xi)) % pcount_Xi
        else:
            n = ((X_int % pcount_Xi) - pow(2, N-i-1, pcount_Xi)) % pcount_Xi

        ans = 1
        while n > 0:
            ans += 1
            n %= popcount(n)
        print(ans)
        
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

n=int(input())
xs=input()
xj=xs.count("1")

x=int(xs,2)

i1=1<<n
for i in range(n-1,-1,-1):
    i1=i1>>1
    xi=x^i1
    if xs[n-1-i]=="0":
        pxi=xj+1
    else:
        pxi=xj-1
    if xi==0:
        print(0)
    else:
        xi=xi%pxi
        if xi==0:
            print(1)
        else:
            icnt=1
            while xi>0:
                icnt+=1
                xi=xi%bin(xi).count("1")
            print(icnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = input()
x = int(a,2)
c1 = a.count("1")

poplis = {0:0}
countlis = {0:0}
xlis = {}

for i in range(n):
    if a[i] == "0":
        xlis[i] = 0
    else:
        xlis[i] = 1

for i in range(1,210000):
    poplis[i] = i % bin(i).count("1")
    countlis[i] = countlis[poplis[i]] + 1

for i in range(n):

    if xlis[i] == 0:
        c2 = c1 + 1
        ans = x + 2 ** (n - 1 - i)
    else:
        c2 = c1 - 1
        ans = x - 2 ** (n - 1 - i)
    if c2 > 0:
        ans = ans % c2
        ans = countlis[ans] + 1
    else:
        ans = 0

    print(ans)

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):
        bit = int(bit)
        pcount_Xi = pcount_X + (-1)**bit

        if pcount_Xi == 0:
            print(0)
            continue

        n = ((X_int % pcount_Xi) + (pow(2, N-i-1, pcount_Xi) * (-1)**bit)) % pcount_Xi

        ans = 1
        while n > 0:
            ans += 1
            n %= popcount(n)
        print(ans)
        
main()

Submission status: Time Limit Exceeded

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

xn = X.count('1')
x10 = int(X,2)

def f(one, ten):
    c = 0
    while ten:
        c += 1
        ten %= one
        one = str(bin(ten)).count('1')
    print(c)


for i,j in enumerate(X):
    k = N - 1 - i
    if j == '1':
        f(xn - 1, x10 - (2**k))
    elif j == '0':
        f(xn + 1, x10 + (2**k))

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

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

i1=1<<n
for i in range(n-1,-1,-1):
#    xi=x^(1<<i)
    i1=i1>>1
    xi=x^i1
#    print(xi,popcount(xi),xi%popcount(xi))
    icnt=0
    while xi>0:
        icnt+=1
        xi=xi%bin(xi).count("1")
    print(icnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = input()
x = int(a,2)
c1 = a.count("1")

poplis = {0:0}
countlis = {0:0}

for i in range(1,210000):
    poplis[i] = i % bin(i).count("1")
    countlis[i] = countlis[poplis[i]] + 1

for i in range(n):

    if a[i] == "0":
        c2 = c1 + 1
        ans = x + 2 ** (n - 1 - i)
    else:
        c2 = c1 - 1
        ans = x - 2 ** (n - 1 - i)
    if c2 > 0:
        ans = ans % c2
        ans = countlis[ans] + 1
    else:
        ans = 0

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = input()
x = int(a,2)
c1 = a.count("1")

poplis = [0]*210000
countlis = [0] * 210000

for i in range(1,210000):
    poplis[i] = i % bin(i).count("1")
    countlis[i] = countlis[poplis[i]] + 1

for i in range(n):

    if a[i] == "0":
        c2 = c1 + 1
        ans = x + 2 ** (n - 1 - i)
    else:
        c2 = c1 - 1
        ans = x - 2 ** (n - 1 - i)
    if c2 > 0:
        ans = ans % c2
        ans = countlis[ans] + 1
    else:
        ans = 0

    print(ans)

Submission status: Time Limit Exceeded

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

for i in range(n-1,-1,-1):
    xi=x^(1<<i)
#    print(xi,popcount(xi),xi%popcount(xi))
    icnt=0
    while xi>0:
        icnt+=1
        xi=xi%bin(xi).count("1")
    print(icnt)

Submission status: Time Limit Exceeded

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

def popcount(x):
    tmp = x
    count = 0
    while tmp > 0:
        if tmp & 1 == 1:
            count += 1
        tmp >>= 1
    
    return count

def f(j):
    cnt = 0
    while j:
        j %= bin(j).count("1")
        cnt += 1
    return cnt

def pow_k(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x

tmp_pop_X = X.count('1')
X_tmp = int(X,2)

for i in range(N):
    if X[i] == '0':
        X_next = X_tmp + pow_k(2,N-1-i)
        X_pop_next = tmp_pop_X + 1
    else:
        X_next = X_tmp - pow_k(2,N-1-i)
        X_pop_next = tmp_pop_X - 1
        
    if X_pop_next == 0:
        print(0)
        continue
        
    X_next = X_next % X_pop_next
    ans = 1
    
    #while X_next != 0:
    #    X_next = X_next % popcount(X_next)
    #    ans += 1
    print(ans + f(X_next))

Submission status: Time Limit Exceeded

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

def popcount(x):
    tmp = x
    count = 0
    while tmp > 0:
        if tmp & 1 == 1:
            count += 1
        tmp >>= 1
    
    return count

def pow_k(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x

tmp_pop_X = X.count('1')
X_tmp = int(X,2)

for i in range(N):
    if X[i] == '0':
        X_next = X_tmp + pow_k(2,N-1-i)
        X_pop_next = tmp_pop_X + 1
    else:
        X_next = X_tmp - pow_k(2,N-1-i)
        X_pop_next = tmp_pop_X - 1
        
    if X_pop_next == 0:
        print(0)
        continue
        
    X_next = X_next % X_pop_next
    ans = 1
    
    while X_next != 0:
        X_next = X_next % popcount(X_next)
        ans += 1
        
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

memo={}

def f(n):
    if n==0:
        return 0
    elif n in memo:
        return memo[n]
    else:
        pc = format(n, 'b').count('1')
        nn=n%pc
        ret = f(nn)+1
        memo[n]=ret
        return ret

def main():
    N = int(input())
    X = list(input())
    for i in range(N):
        xi = X[:]
        if X[i]=='1':
            xi[i]='0'
        elif X[i]=='0':
            xi[i]='1'
        print(f(int(''.join(xi),2)))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = input()
zero_pop = X.count('1') + 1
one_pop = X.count('1') - 1
one_mod, zero_mod = 0, 0

for b in X:
    if one_pop != 0:
        one_mod = (one_mod * 2 + int(b)) % one_pop
    zero_mod = (zero_mod * 2 + int(b)) % zero_pop

pop = {0:0}
def popcount(n):
    if n in pop:
        return pop[n]
    pop[n] = popcount(n // 2) + n % 2
    return pop[n]
memo = {0:0}
def f_count(n):
    if n in memo:
        return memo[n]
    memo[n] = f_count(n % popcount(n)) + 1
    return memo[n]
for i in range(N):
    if X[i] == '1' and one_pop == 0:
        print(0)
        continue
    if X[i] == '1':
        x = one_mod
        x -= 2 ** (N-1-i) % one_pop
        x %= one_pop
    elif X[i] == '0':
        x = zero_mod
        x += 2 ** (N-1-i) % zero_pop
        x %= zero_pop
    
    print(f_count(x) + 1)

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):
        bit = int(bit)
        pcount_Xi = pcount_X + (-1)**bit
        mask = 1 << (N-i-1)
        n = X_int + (mask * (-1)**bit)

        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:
#!/usr/bin python3
# -*- coding: utf-8 -*-

memo={}

def f(n):
    if n==0:
        return 0
    elif n in memo:
        return memo[n]
    else:
        pc = format(n, 'b').count('1')
        return f(n%pc)+1

def main():
    N = int(input())
    X = list(input())
    for i in range(N):
        xi = X[:]
        if X[i]=='1':
            xi[i]='0'
        elif X[i]=='0':
            xi[i]='1'
        print(f(int(''.join(xi),2)))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

xn = X.count('1')
on = xn + 1
zn = xn - 1
x10 = int(X,2)

def f(one, ten):
    c = 0
    while ten:
        c += 1
        ten = ten % one
        one = str(bin(ten)).count('1')
    print(c)


for i,j in enumerate(X):
    k = N - 1 - i
    if j == '1':
        f(zn, x10 - (2**k))
    elif j == '0':
        f(on, x10 + (2**k))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

def f(n):
    ret = 0
    while n>0:
        pc = format(n, 'b').count('1')
        n = n%pc
        ret += 1
    return ret

def main():
    N = int(input())
    X = list(input())
    for i in range(N):
        xi = X[:]
        if X[i]=='1':
            xi[i]='0'
        elif X[i]=='0':
            xi[i]='1'
        print(f(int(''.join(xi),2)))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

def f(n):
    ret = 0
    while n>0:
        pc = format(n, 'b').count('1')
        n = n%pc
        ret += 1
    return ret

def main():
    N = int(input())
    X = list(input())
    for i in range(N):
        xi = X[:]
        if X[i]=='1':
            xi[i]='0'
        elif X[i]=='0':
            xi[i]='1'
        print(f(int(''.join(xi),2)))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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


def f(n, popcount_1):
    count = 0
    if popcount_1 == 0:
        return 0
    else:
        n = n%popcount_1
        count += 1
    
    while n!=0:
        n = n%popcount(n)
        count += 1
    return count


X_popcount = popcount(X)
for i in range(N):
    X_i = X ^ (1<<(N-i-1))
    if X>>(N-i-1)&1 == 1:
        ans = f(X_i, X_popcount-1)
    else:
        ans = f(X_i, X_popcount+1)
    print(ans)

Submission status: Time Limit Exceeded

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

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

x_pop = popcount(x)
for i in reversed(range(0,n)):
    bit = x^(1<<i)
    if x&(1<<i):
        tmp_pop = x_pop - 1
    else:
        tmp_pop = x_pop + 1
    if tmp_pop == 0:
        print(0)
        continue
    tmp = bit % tmp_pop
    if tmp == 0:
        print(1)
        continue
    cnt = 2
    tmp_pop = popcount(tmp)
    if tmp_pop == 0:
        print(cnt-1)
        continue
    tmp = tmp % tmp_pop
    while tmp > 0:
        cnt += 1
        tmp_pop = popcount(tmp)
        if tmp_pop == 0:
            print(cnt-1)
            continue
        tmp %= tmp_pop
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = input()
n = sum([(2 ** i) * int(x) for i,x in enumerate(reversed(X))])

from functools import lru_cache

@lru_cache(maxsize=None)
def popcount(x):
    return bin(x)[2:].count('1')
    
@lru_cache(maxsize=None)
def f(x):
    cnt = 0
    
    while x:
        cnt += 1
        x %= popcount(x)
    return cnt

for i in reversed(range(N)):
    x = n ^ (1<<i)
    print(f(x))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
binary = input()
num = int(binary, 2)

ppcnt = binary.count('1')
for dig in range(n-1, -1, -1):
    ans = 0
    if binary[n-1 - dig] == '1':
        pp = ppcnt - 1
    else:
        pp = ppcnt + 1
    target = num ^ (1 << dig)
    while target > 0:
        target %= pp
        pp = bin(target).count('1')
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
N = int(input())
S = input()

c = S.count('1')
m = int('0B'+S, 0)

@lru_cache(maxsize=None)
def calc(a, ans):
    if a == 0: return ans
    ans += 1
    m = bin(a).count('1')
    return calc(a%m, ans)
    
for i in range(N):
    if S[i] == '1': b = c - 1
    else: b = c + 1
    if S[i] == '1':
        a = m - 2**(N - 1 - i)
    else: a = m + 2**(N - 1 - i)

    print(calc(a, 0))

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

n=int(input())
xs=input()
#xk=list(map(int,list(xs)))
xj=xs.count("1")

x=int(xs,2)

nmax=2*10**5
xmem=[0]*(nmax+1)
for i in range(n-1,-1,-1):
    xi=x^(1<<i)
    pxi=xj
    if xs[n-1-i]=="0":
        pxi=pxi+1
    else:
        pxi=pxi-1
    if xi==0:
        print(0)
    else:
        xi=xi%pxi
        if xi==0:
            print(1)
        else:
            if xi<nmax and xmem[xi]>0:
                print(xmem[xi])
            else:
                xii=xi
                icnt=1
                while xi>0:
                    icnt+=1
                    xi=xi%(bin(xi).count("1"))
                xmem[xii]=icnt
                print(icnt)

Submission status: Time Limit Exceeded

Solution code:
def popcount(n):
    count = 0
    if n != 0:
        while n > 0:
            count += 1
            n = n % bin(n).count("1")
    return count


n = int(input())
a = input()
x = int(a,2)
c1 = a.count("1")

for i in range(n):

    if a[i] == "0":
        c2 = c1 + 1
        ans = x + 2 ** (n - 1 - i)
    else:
        c2 = c1 - 1
        ans = x - 2 ** (n - 1 - i)
    if c2 > 0:
        ans = ans % c2
        ans = popcount(ans) + 1
    else:
        ans = 0

    print(ans)

Submission status: Time Limit Exceeded

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

c = S.count('1')
m = int('0B'+S, 0)

def calc(a, ans):
    if a == 0: return ans
    ans += 1
    m = bin(a).count('1')
    return calc(a%m, ans)
    
for i in range(N):
    if S[i] == '1': b = c - 1
    else: b = c + 1
    if S[i] == '1':
        a = m - 2**(N - 1 - i)
    else: a = m + 2**(N - 1 - i)

    print(calc(a, 0))

Submission status: Time Limit Exceeded

Solution code:
def popcount(n):
    count = 0
    if n != 0:
        while n > 0:
            count += 1
            n = n % bin(n).count("1")
    return count


n = int(input())
a = input()
x = int(a,2)
c1 = bin(x).count("1")

for i in range(n):

    if a[i] == "0":
        c2 = c1 + 1
        ans = x + 2 ** (n - 1 - i)
    else:
        c2 = c1 - 1
        ans = x - 2 ** (n - 1 - i)
    if c2 > 0:
        ans = ans % c2
        ans = popcount(ans) + 1
    else:
        ans = 0

    print(ans)

Submission status: Time Limit Exceeded

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

def popcount(x):
    tmp = x
    count = 0
    while tmp > 0:
        if tmp & 1 == 1:
            count += 1
        tmp >>= 1
    
    return count

def pow_k(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x

tmp_pop_X = X.count('1')

for i in range(N):
    if X[i] == '0':
        X_next = int(X,2) + pow_k(2,N-1-i)
        X_pop_next = tmp_pop_X + 1
    else:
        X_next = int(X,2) - pow_k(2,N-1-i)
        X_pop_next = tmp_pop_X - 1
        
    if X_pop_next == 0:
        print(0)
        continue
        
    X_next = X_next % X_pop_next
    ans = 1
    
    while X_next != 0:
        X_next = X_next % popcount(X_next)
        ans += 1
        
    print(ans)

Submission status: Time Limit Exceeded

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

poptbl=[0]*(2*10**5+1)
def popcount(x):
    global poptbl
    if poptbl[x]!=0:
        return poptbl[x]
    
    poptbl[x]=bin(x).count('1')
    return poptbl[x]

ftbl=[0]*(2*10**5+1)
def f(x):
    global ftbl

    if ftbl[x]!=0:
        return ftbl[x]
    
    #print('f(x), x: {}'.format(x))
    if x==0:
        return 0
    else:
        ans=f(x%popcount(x))+1
        #print(ans)
        ftbl[x]=ans
        return ans    

def main():
    n=int(input())
    x=input()
    m=x.count('1')
    #print('m: {}'.format(m))
    xint=int(x,2)
    #print('xint: {}'.format(xint))
    if m!=1:
        xmodm1=xint%(m-1)
    else:
        xmodm1=1
    xmodp1=xint%(m+1)
    ans=[]
    b=2**(n-1)
    for i in range(n):
        if x[i]=='1':
            if m==1:
                a=0
                ans.append(a)
            else:
                xx=( xmodm1 + (m-1) -b%(m-1) )%(m-1)
                #ans.append(f(xx)+1)
                a=f(xx)+1
                ans.append(a)
        else:
            xx=( xmodp1 + b%(m+1) )%(m+1)
            #ans.append(f(xx)+1)
            a=f(xx)+1
            ans.append(a)
        b=b//2
        print(a)
    return ans

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

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

n=int(input())
xs=input()
#xk=list(map(int,list(xs)))
xj=xs.count("1")

x=int(xs,2)

for i in range(n-1,-1,-1):
    xi=x^(1<<i)
    pxi=xj
    if xs[n-1-i]=="0":
        pxi=pxi+1
    else:
        pxi=pxi-1
    if xi==0:
        print(0)
    else:
        xi=xi%pxi
        if xi==0:
            print(1)
        else:
            icnt=1
            while xi>0:
                icnt+=1
                xi=xi%(bin(xi).count("1"))
            print(icnt)

Submission status: Time Limit Exceeded

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

poptbl=[0]*(2*10**5+1)
def popcount(x):
    global poptbl
    if poptbl[x]!=0:
        return poptbl[x]
    
    poptbl[x]=bin(x).count('1')
    return poptbl[x]

ftbl=[0]*(2*10**5+1)
def f(x):
    global ftbl

    if ftbl[x]!=0:
        return ftbl[x]
    
    #print('f(x), x: {}'.format(x))
    if x==0:
        return 0
    else:
        ans=f(x%popcount(x))+1
        #print(ans)
        ftbl[x]=ans
        return ans    

def main():
    n=int(input())
    x=input()
    m=x.count('1')
    #print('m: {}'.format(m))
    xint=int(x,2)
    #print('xint: {}'.format(xint))
    if m!=1:
        xmodm1=xint%(m-1)
    else:
        xmodm1=1
    xmodp1=xint%(m+1)
    ans=[]
    b=2**(n-1)
    for i in range(n):
        if x[i]=='1':
            if m==1:
                ans.append(0)
            else:
                xx=( xmodm1 + (m-1) -b%(m-1) )%(m-1)
                ans.append(f(xx)+1)
        else:
            xx=( xmodp1 + b%(m+1) )%(m+1)
            ans.append(f(xx)+1)
        b=b//2
    return ans

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

Submission status: Time Limit Exceeded

Solution code:
def popcount(n):
    count = 0
    if n != 0:
        while n > 0:
            count += 1
            n = n % bin(n).count("1")
    return count


n = int(input())
a = input()
x = int(a,2)
c1 = bin(x).count("1")

for i in range(n):

    if a[i] == "0":
        c2 = c1 + 1
        ans = x + 2 ** (n - 1 - i)
    else:
        c2 = c1 - 1
        ans = x - 2 ** (n - 1 - i)
    if c2 > 0:
        ans = ans % c2
        ans = popcount(ans) + 1
    else:
        ans = 0

    print(ans)

Submission status: Time Limit Exceeded

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

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

x_pop = popcount(x)
for i in reversed(range(0,n)):
    try:
        if x&(1<<i):
            tmp_pop = x_pop - 1
        else:
            tmp_pop = x_pop + 1
        tmp = (x^(1<<i)) % tmp_pop
        if tmp <= 0:
            print(1)
            continue
        cnt = 2
        tmp = tmp % popcount(tmp)
        while tmp > 0:
            cnt += 1
            tmp %= popcount(tmp)
        print(cnt)
    except:
        print(0)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = input()
zero_pop = X.count('1') + 1
one_pop = X.count('1') - 1
pop = {0:0}
def popcount(n):
    if n in pop:
        return pop[n]
    pop[n] = popcount(n // 2) + n % 2
    return pop[n]
memo = {0:0}
def f_count(n):
    if n in memo:
        return memo[n]
    memo[n] = f_count(n % popcount(n)) + 1
    return memo[n]
for i in range(N):
    x = int(X, 2)
    if X[i] == '1' and one_pop == 0:
        print(0)
        continue
    if X[i] == '1':
        x -= 2 ** (N-1-i)
        x %= one_pop
    elif X[i] == '0':
        x += 2 ** (N-1-i)
        x %= zero_pop
    
    print(f_count(x) + 1)

Submission status: Time Limit Exceeded

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

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

x_pop = popcount(x)
for i in reversed(range(0,n)):
    try:
        if x&(1<<i):
            tmp_pop = x_pop - 1
        else:
            tmp_pop = x_pop + 1
        tmp = (x^(1<<i)) % tmp_pop
        if tmp <= 0:
            print(1)
            continue
        cnt = 2
        tmp2 = tmp % popcount(tmp)
        while tmp2 > 0:
            tmp = tmp2
            cnt += 1
            tmp2 %= popcount(tmp2)
        print(cnt)
    except:
        print(0)

Submission status: Time Limit Exceeded

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

poptbl=[0]*(2*10**5+1)
def popcount(x):
    global poptbl
    if poptbl[x]!=0:
        return poptbl[x]
    
    poptbl[x]=bin(x).count('1')
    return poptbl[x]

ftbl=[0]*(2*10**5+1)
def f(x):
    global ftbl

    if ftbl[x]!=0:
        return ftbl[x]
    
    #print('f(x), x: {}'.format(x))
    if x==0:
        return 0
    else:
        ans=f(x%popcount(x))+1
        #print(ans)
        ftbl[x]=ans
        return ans    

def main(n,x):
    m=x.count('1')
    #print('m: {}'.format(m))
    xint=int(x,2)
    #print('xint: {}'.format(xint))
    if m!=1:
        xmodm1=xint%(m-1)
    else:
        xmodm1=1
    xmodp1=xint%(m+1)
    ans=[]
    b=2**(n-1)
    for i in range(n):
        if x[i]=='1':
            if m==1:
                ans.append(0)
            else:
                xx=( xmodm1 + (m-1) -b%(m-1) )%(m-1)
                ans.append(f(xx)+1)
        else:
            xx=( xmodp1 + b%(m+1) )%(m+1)
            ans.append(f(xx)+1)
        b=b//2
    return ans

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

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

n=int(input())
xs=input()
#xk=list(map(int,list(xs)))
xj=xs.count("1")

x=int(xs,2)

for i in range(n-1,-1,-1):
    xi=x^(1<<i)
    pxi=xj
    if xs[n-1-i]=="0":
        pxi=pxi+1
    else:
        pxi=pxi-1
    if xi==0:
        print(0)
    else:
        xi=xi%pxi
        if xi==0:
            print(1)
        else:
            icnt=1
            while xi>0:
                icnt+=1
                xi=xi%(bin(xi).count("1"))
            print(icnt)

Submission status: Time Limit Exceeded

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

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

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

lst = [list(x) for _ in range(N)]

for i in range(N):
    if lst[i][i] == "1":
        lst[i][i] = "0"
    else:
        lst[i][i] = "1"
    lst[i] = "".join(lst[i])

for i in range(N):
    M = int(lst[i], 2)
    print(f(M))

Submission status: Time Limit Exceeded

Solution code:
def popcount(n):
    ret = 0
    while n:
        if n % 2:
            ret += 1
        n //= 2
    return ret

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

n = int(input())
s = input()
i = 0
for j in range(n):
    i += (2**j) * int(s[n - 1 - j])

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

Submission status: Time Limit Exceeded

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

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

ftbl=[0]*(2*10**5+1)
def f(x):
    global ftbl

    if ftbl[x]!=0:
        return ftbl[x]
    
    #print('f(x), x: {}'.format(x))
    if x==0:
        return 0
    else:
        ans=f(x%popcount(x))+1
        #print(ans)
        ftbl[x]=ans
        return ans    

def main(n,x):
    m=x.count('1')
    #print('m: {}'.format(m))
    xint=int(x,2)
    #print('xint: {}'.format(xint))
    if m!=1:
        xmodm1=xint%(m-1)
    else:
        xmodm1=1
    xmodp1=xint%(m+1)
    ans=[]
    b=2**(n-1)
    for i in range(n):
        if x[i]=='1':
            if m==1:
                ans.append(0)
            else:
                xx=( xmodm1 + (m-1) -b%(m-1) )%(m-1)
                ans.append(f(xx)+1)
        else:
            xx=( xmodp1 + b%(m+1) )%(m+1)
            ans.append(f(xx)+1)
        b=b//2
    return ans

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

Submission status: Time Limit Exceeded

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

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

def f(x):
    #print('f(x), x: {}'.format(x))
    if x==0:
        return 0
    else:
        ans=f(x%popcount(x))+1
        #print(ans)
        return ans    

def main(n,x):
    m=x.count('1')
    #print('m: {}'.format(m))
    xint=int(x,2)
    #print('xint: {}'.format(xint))
    if m!=1:
        xmodm1=xint%(m-1)
    else:
        xmodm1=1
    xmodp1=xint%(m+1)
    ans=[]
    b=2**(n-1)
    for i in range(n):
        if x[i]=='1':
            if m==1:
                ans.append(0)
            else:
                xx=( xmodm1 + (m-1) -b%(m-1) )%(m-1)
                ans.append(f(xx)+1)
        else:
            xx=( xmodp1 + b%(m+1) )%(m+1)
            ans.append(f(xx)+1)
        b=b//2
    return ans

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

Submission status: Time Limit Exceeded

Solution code:
import sys
#input = sys.stdin.readline
def input(): return sys.stdin.readline().strip()

n=int(input())
xs=input()
#xk=list(map(int,list(xs)))
xj=xs.count("1")

x=int(xs,2)

def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f

for i in range(n-1,-1,-1):
    xi=x^(1<<i)
    pxi=xj
    if xs[n-1-i]=="0":
        pxi=pxi+1
    else:
        pxi=pxi-1
#    print(i,xi,"pxi",pxi)
    if xi==0:
        print(0)
    else:
#        print("i",i,"xi",xi,"pxi",pxi)
        xi=xi%pxi
#        print("--i",i,"xi",xi,"pxi",pxi)
        if xi==0:
            print(1)
        else:
#            print("i",i,"xi",xi,"pxi",pxi)
#            print(i,pxi,xi,popcount(xi),xi%popcount(xi))
            icnt=1
            while xi>0:
                icnt+=1
#                print(i,pxi,xi,popcount(xi),xi%popcount(xi))
                xi=xi%popcount(xi)
            print(icnt)