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 aModM(s, mod):
    number = 0
    for i in range(len(s)):
        number = (number*10 + int(s[i]))
        number = number % m 
    return number 
def ApowBmodM(a,b,mod):
    ans = aModM(a, mod)
    mul = ans  
    for i in range(1,b):
        ans = (ans*mul) % m
    return ans 


def bruteforce(n):
    # print('n',n)
    cnt = 0
    while n:
        bi = bin(n)
        one = bi.count('1')
        n = n%one
        cnt+=1
    return cnt

n = int(input())
x = input()
x = list(x)
p = x.count('1')
x = x[-1::-1]

s = 0
for i in range(n):
    if x[i]=='1':
        b = i
        a = '2'
        m = p+1
        if b==0:
            s = (s+1)%m
        else:
            s = (s+(ApowBmodM(a,b, m)))%m
        # print(s,x[i],i)
nex = s
if p-1>0:
    s = 0
    for i in range(n):
        if x[i]=='1':
            b = i
            a = '2'
            m = p-1
            if b==0:
                s = (s+1)%m
            else:
                s = (s+(ApowBmodM(a,b, m)))%m
    prev = s
# print(nex,prev)
ans = []
for i in range(n):
    if x[i]=='0':
        cur = nex
        b = i
        a = '2'
        m = p+1
        if b==0:
            cur = (cur+1)%m
        else:
            cur = (cur+ApowBmodM(a, b, m))%m
        # print('cur',ApowBmodM(a,b,m),cur,p)
        
        ans.append(bruteforce(cur)+1)
        # print(bruteforce(cur)+1)

    else:
        if p-1>0:
            cur = prev
            b = i
            a = '2'
            m = p-1
            if b==0:
                cur = (cur-1)%m
            else:
                cur = (cur-ApowBmodM(a, b, m))%m
            # print('here',cur)
            ans.append(bruteforce(cur)+1)
        
        else:
            ans.append(0)
ans = ans[-1::-1]
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=list(input())
y=0
lis=[0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2]
#for i in range(n):
#    y+=int(x[i])

#print(y)

for i in range(n):
    tempx=x
    tempx[i]=str(int(x[i]) ^ 1)
    #if tempx[i]=='1':
    #    tempy=y+1
    #else:
    #    tempy=y-1
    if i>0:
        tempx[i-1]=str(int(tempx[i-1]) ^ 1)

    #print(tempx,x)
    tempx=int("".join(tempx),2)

    #print(tempx)
    cnt=0

    while True:
        if int(tempx)==0:
            print(cnt)
            break
        tempx%=bin(tempx).count('1')
        #print(len(tempx))
        #tempy=
        #print(tempx,'koko')
        #print(type(tempx),len(tempx))

        cnt+=1

Submission status: Time Limit Exceeded

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

n = int(input())
x = list(map(str, (input())))
X = int(''.join(x), 2)
d = {}
for i in range(n):
    if x[i] == '1':
        s = X - 2 ** (n-i-1)
    else:
        s = X + 2 ** (n-i-1)
    print(f(s))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = input()
m = int(x,2)
def two(number):
  return(bin(number)).replace('0b','')
def pop(number):
  an =0
  moto=str(two(number))
  for i in range(len(moto)):
    an=an+int(moto[i])
  return(an)
def pro(num):
  global count
  if num==0:
    print(count)
  else:
    count=count+1
    num=num%pop(num)
    pro(num)

for i in range(n):
  count =0
  m = int(x,2)
  if x[i]=='0':
    m=m+2**(n-i-1)
    pro(m)
  else:
    m=m-2**(n-i-1)
    pro(m)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n_ansl = [0]*(2*(10**5))
    for i in range(1,2*(10**5)):
    # for i in range(1,20):
        cnt = 0
        one_cnt = bin(i).count("1")
        rem = i
        while rem != 0:
            one_cnt = bin(rem).count("1")
            rem = rem%one_cnt   
            cnt += 1
        n_ansl[i] = cnt
 
    n = int(input())
    x = input()
    one_cnt = x.count('1')

    if one_cnt == 0:
        for i in range(n):
            print(1)
        exit()
    
    curr_2b_p = 1
    curr_2b_m = 1
    curr_sum_p1 = 0
    curr_sum_m1 = 0
    for i in range(n-1, -1, -1):
        if x[i] == '1':
            curr_sum_p1 += curr_2b_p
            curr_sum_m1 += curr_2b_m
            curr_sum_p1%=(one_cnt+1)
            if one_cnt > 1:
                curr_sum_m1%=(one_cnt-1)
        curr_2b_p*=2
        curr_2b_m*=2
        curr_2b_p%=(one_cnt+1)
        if one_cnt > 1:
            curr_2b_m%=(one_cnt-1)
 
        
 
    curr_2b_p = 1
    curr_2b_m = 1
    ansl = [0]*(n)
    for i in range(n-1, -1, -1):
        if x[i] == '1':
            diff = (-1)*curr_2b_m
            if one_cnt > 1:
                ans = (curr_sum_m1 + diff)%(one_cnt-1)
                ansl[i] = n_ansl[ans]+1
            else:
                ansl[i] = 0
        else:
            diff = curr_2b_p
            ans = (curr_sum_p1 + diff)%(one_cnt+1)
            ansl[i] = (n_ansl[ans]+1)
        curr_2b_p*=2
        curr_2b_m*=2
        curr_2b_p%=(one_cnt+1)
        if one_cnt > 1:
            curr_2b_m%=(one_cnt-1)
 
 
    # print(ansl)
    for a in ansl:
        print(a)
 
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def f(L):
    X=0
    T=1
    for x in L[::-1]:
        X+=T*x
        T*=2
    return X

def h(M,L):
    X=[1]*(L+1)
    for i in range(2,L+2):
        X[-i]=(X[-(i-1)]*2)%M
        
    return X

N=int(input())
X=input()
Zero="0"*N

X=list(map(int,X))

H=X.count(1)
Z=f(X)
G=1<<N

A=[]
for i in range(N):
    G>>=1
    
    if X[i]==0:
        J=H+1
    else:
        J=H-1
    
    if J==0:
        A.append(0)
        continue

    Y=Z^G
    B=h(J,N-1)

    V=0
    for i in range(1,N+1):
        V+=B[-i]*(Y%2)
        V%=J
        Y>>=1
        
    Y=V%J
    I=1
    try:
        while True:
            Y=Y%bin(Y).count("1")
            I+=1
    except ZeroDivisionError:
        A.append(I)

print("\n".join(map(str,A)))

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():
    N = in_n()
    X = in_s()
    tx = int(X, 2)

    ans = [0] * N

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

    t = 1 << N - 1
    for i in range(N):
        a = tx ^ t
        count = 0
        while a:
            if count == 0:
                a = a % one_count[i]
            else:
                a = a % bin(a).count('1')
            count += 1
        ans[i] = count
        t = t >> 1

    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def popcount(n,count=0):
    # print(n)
    if n=="0b0":
        print(count)
        return 0
    div = n.count("1")
    count+=1
    # print(n)
    return popcount(bin(int(n,2)%div),count)


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


def main():
    N = int(input())
    X = input()
    # reg = ""
    for i in range(1,N+1):
        # print("i:{0}".format(i))
        # reg +="1" 
        # pdb.set_trace()
        # n = bin((int(reg,2)^(int(X[:i],2))))+X[i:]
        n = toggle_nth_bit(int(X,2),N-i)
        # print("n:{0}".format(n)
        popcount(bin(n))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    X = input()
    MOD = sum(map(lambda x: x == '1',X))
    if MOD == 0:
        print("1" + "\n1" * (N-1))
        return 0
    if MOD == 1 and X[-1] == '1':
        print("2\n" * (N-1) + "0")
        return 0
    if MOD == 1 and X[-1] == '0':
        ans = ''
        for i in range(N):
            if X[i] == '1':
                ans += '0'
            elif i != N-1:
                ans += '1'
            else:
                ans += '2'
            if i != N-1:
                ans += '\n'
        print(ans)
        return 0
    MODP1 = MOD + 1
    MODM1 = MOD - 1
    POWEROFTWOP1 = [0] * 200001
    POWEROFTWOM1 = [0] * 200001
    POWEROFTWOP1[0] = 1
    POWEROFTWOM1[0] = 1
    for i in range(1,N):
        POWEROFTWOP1[i] = (POWEROFTWOP1[i-1] * 2) % MODP1
        POWEROFTWOM1[i] = (POWEROFTWOM1[i-1] * 2) % MODM1
    xMODP1 = 0
    xMODM1 = 0
    for i in range(N):
        if X[i] == '1':
            xMODP1 += POWEROFTWOP1[N - i - 1]
            xMODM1 += POWEROFTWOM1[N - i - 1]
            xMODP1 %= MODP1
            xMODM1 %= MODM1
    ans = ""
    for i in range(N):
        if X[i] == '0':
            anscur = xMODP1
            anscur += POWEROFTWOP1[N - i - 1]
            anscur %= MODP1
        if X[i] == '1':
            anscur = xMODM1
            anscur -= POWEROFTWOM1[N - i - 1]
            anscur %= MODM1
        cnt = 1
        while anscur != 0:
            ans2 = bin(anscur)[2:]
            oneCount = sum(map(lambda x: x == '1',ans2))
            anscur %= oneCount
            cnt += 1
        ans += str(cnt)
        if i != N-1:
            ans += '\n'
    print(ans)
                    
main()

Submission status: Time Limit Exceeded

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

n = int(input())
x = input()
z = '1' * n
o = '0' * n

if (z == x):
  u = n - 1
  d = n - 1
elif (z == o):
  u = 1
  d = 1
else:
  tmp = len(list(filter(lambda x: x == '1', x)))
  u = tmp + 1
  d = tmp - 1


def popcount(i):
  return i % len(list(filter(lambda x: x == '1', format(i, 'b'))))


def toggle(i):
  if (i == '1'):
    return '0'
  else:
    return '1'
    

def solve(i, count):
  if (i <= 2 * 10**5 and ans[i] != 0):
    return count + ans[i]
  elif (i == 0):
    return count
  else:
    return solve(popcount(i), count + 1)


def solve2(i, div):
  if (i <= 2 * 10**5):
    return ans[i]
  else:
    return ans[i % div] + 1


ans = [0] * (2 * 10 ** 5 + 1)
for i in range(1, 2 * 10 ** 5):
  ans[i] = solve(i, 0)
for i in range(n):
  if(i == 0):
    _x = toggle(x[0]) + x[1: n]
  elif (i == n - 1):
    _x = x[:i] + toggle(x[n - 1])
  else:
    _x = x[:i] + toggle(x[i]) + x[i + 1 :n]
  if(x[i] == '0'):
    print(solve2(int(_x, 2), u))
  else:
    print(solve2(int(_x, 2), d))

Submission status: Time Limit Exceeded

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

def popcount(n, cnt, dic):
    if n in dic:
        kos = dic[n]
    else:
        cnt1 = 0
        for i in str(bin(n))[2:]:
            if i == "1":
                cnt1 += 1
        dic[n] = cnt1
        kos = cnt1
    dic2 = dic
    if n != 0:
        return popcount(n%kos, cnt+1, dic2)
    else:
        return cnt
dic = {}
for i in range(1, N+1):
    mask = 1<<N-i
    x = X ^ mask
    print(popcount(x, 0, dic))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = input()
l = []
for i in range(len(X)):
    l.append(int(X[i]))
#print(l)
ans = []
def div(n, m):
    global ans
    if n==0:
        ans.append(m)
        return
    size = len(bin(n))-2
    cnt = 0
    for i in range(size):
        if n >> i & 1:
            cnt += 1
    r = n % cnt
    if r == 0:
        ans.append(m+1)
    else:
        div(r, m+1)

num = 0

for i in range(N):
    if l[i] == 1:
        num += 2**(N-i-1)
#print(num)
for i in range(N):
    if l[i] == 1:
        num -= 2**(N-i-1)
    else:
        num += 2**(N-i-1)
    div(num, 0)
    if l[i] == 1:
        num += 2**(N-i-1)
    else:
        num -= 2**(N-i-1)

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    X = input()
    N = 200000
    X = '1' * N
    MOD = sum(map(lambda x: x == '1',X))
    if MOD == 0:
        print("1" + "\n1" * (N-1))
        return 0
    if MOD == 1 and X[-1] == '1':
        print("2\n" * (N-1) + "0")
        return 0
    if MOD == 1 and X[-1] == '0':
        ans = ''
        for i in range(N):
            if X[i] == '1':
                ans += '0'
            elif i != N-1:
                ans += '1'
            else:
                ans += '2'
            if i != N-1:
                ans += '\n'
        print(ans)
        return 0
    MODP1 = MOD + 1
    MODM1 = MOD - 1
    POWEROFTWOP1 = [0] * 200001
    POWEROFTWOM1 = [0] * 200001
    POWEROFTWOP1[0] = 1
    POWEROFTWOM1[0] = 1
    for i in range(1,N):
        POWEROFTWOP1[i] = (POWEROFTWOP1[i-1] * 2) % MODP1
        POWEROFTWOM1[i] = (POWEROFTWOM1[i-1] * 2) % MODM1
    xMODP1 = 0
    xMODM1 = 0
    for i in range(N):
        if X[i] == '1':
            xMODP1 += POWEROFTWOP1[N - i - 1]
            xMODP1 %= MODP1
            xMODM1 += POWEROFTWOM1[N - i - 1]
            xMODM1 %= MODM1
    ans = ""
    for i in range(N):
        if X[i] == '0':
            anscur = xMODP1
            anscur += POWEROFTWOP1[N - i - 1]
            anscur %= MODP1
        if X[i] == '1':
            anscur = xMODM1
            anscur -= POWEROFTWOM1[N - i - 1]
            anscur %= MODM1
        cnt = 1
        while anscur != 0:
            ans2 = bin(anscur)[2:]
            oneCount = sum(map(lambda x: x == '1',ans2))
            anscur %= oneCount
            cnt += 1
        ans += str(cnt)
        if i != N-1:
            ans += '\n'
    print(ans)
                    
main()

Submission status: Time Limit Exceeded

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

#print(X)
mask = 0b1 << (N-1)
#print(mask)
ans = 0

for i in range(N):
    ans = 0
    a = X ^ mask
    #print("a:" + str(a))
    while a != 0:
        ans += 1
        num = str(bin(a)).count('1')
        #print("num:" + str(num))
        a = a % num
    mask = mask >> 1
    #print("ans:" + str(ans))
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n_ansl = [0]*(2*(10**5))
    for i in range(1,2*(10**5)):
    # for i in range(1,20):
        cnt = 0
        one_cnt = bin(i).count("1")
        rem = i
        while rem != 0:
            one_cnt = bin(rem).count("1")
            rem = rem%one_cnt   
            cnt += 1
        n_ansl[i] = cnt
 
    n = int(input())
    x = input()
    one_cnt = x.count('1')

    if one_cnt == 0:
        for i in range(n):
            print(1)
        exit()
    
    curr_2b = 1
    curr_2b_p = 1
    curr_2b_m = 1
    curr_sum = 0
    curr_sum_p1 = 0
    curr_sum_m1 = 0
    for i in range(n-1, -1, -1):
        if x[i] == '1':
            curr_sum += curr_2b
            curr_sum_p1 += curr_2b_p
            curr_sum_m1 += curr_2b_m
            curr_sum%=one_cnt
            curr_sum_p1%=(one_cnt+1)
            if one_cnt > 1:
                curr_sum_m1%=(one_cnt-1)
        curr_2b*=2
        curr_2b_p*=2
        curr_2b_m*=2
        curr_2b%=one_cnt
        curr_2b_p%=(one_cnt+1)
        if one_cnt > 1:
            curr_2b_m%=(one_cnt-1)
 
        
 
    curr_2b_p = 1
    curr_2b_m = 1
    ansl = [0]*(n)
    for i in range(n-1, -1, -1):
        if x[i] == '1':
            diff = (-1)*curr_2b_m
            if one_cnt > 1:
                ans = (curr_sum_m1 + diff)%(one_cnt-1)
                ansl[i] = n_ansl[ans]+1
            else:
                ansl[i] = 0
        else:
            diff = curr_2b_p
            ans = (curr_sum_p1 + diff)%(one_cnt+1)
            ansl[i] = (n_ansl[ans]+1)
        curr_2b_p*=2
        curr_2b_m*=2
        curr_2b_p%=(one_cnt+1)
        if one_cnt > 1:
            curr_2b_m%=(one_cnt-1)
 
 
    # print(ansl)
    for a in ansl:
        print(a)
 
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import functools

@functools.lru_cache(maxsize=20000)
def popcount(n):
    return '{:b}'.format(n).count('1')


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


def resolve(in_):
    n = int(in_.readline())
    x = int(in_.readline(), 2)
    for i in range(n - 1, -1, -1):
        v = x ^ (1 << i)
        # print(f'{x=} {v=} {1<<n=}')
        print(f(v))


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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
History = {}

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

def AnythingGoestoZero(n):
  
  if n == 0:
    count = 0
  elif n in History.keys():
    count = History[n]
  else:
    target = n % popcount(n)
    count = AnythingGoestoZero(target) + 1
    History[n] = count
  return count

if __name__ == '__main__':
  N = int(input())
  X = input()
  for i in range(N):
    tmp = list(X)
    if tmp[i] == "0":
      tmp[i] = "1"
    else:
      tmp[i] = "0"
    target = "".join(tmp)
    
    print(AnythingGoestoZero(int(target, 2)))

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():
    N = in_n()
    X = in_s()
    tx = int(X, 2)

    ans = [0] * N

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

    for i in range(N):
        a = tx ^ (1 << N - i - 1)
        count = 0
        while a:
            if count == 0:
                a = a % one_count[i]
            else:
                a = a % bin(a).count('1')
            count += 1
        ans[i] = count

    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
def funk(x, temp_count):
    if x in log_dict:
        ans = log_dict[x]
        return ans
    x_temp = x % temp_count
    if x_temp == 0:
        log_dict[x] = 1
        return 1
    temp_count = bin(x_temp).count("1")
    ans = funk(x_temp, temp_count)
    ans += 1
    log_dict[x] = ans
    return ans
n = int(input())
bit = input()
bit_list = list(bit)
count = bit.count("1")
log_dict = {0: 0, 1: 1, 2: 1, 8: 1, 6002382: 2, 3905230: 1, 10: 1, 759502: 2, 6: 1, 1283790: 2, 2070222: 1, 1677006: 2, 1742542: 2, 1775310: 2, 1824462: 2, 1816270: 2, 1803982: 2, 1810126: 2, 1807054: 2, 1807566: 2, 1808334: 2, 1807950: 2, 1808014: 2, 1808110: 2, 1808094: 2, 1808070: 2, 1808074: 2, 1808076: 1, 7: 2, 1808079: 3, 6002190: 2, 3905038: 2, 759310: 1, 1283598: 2, 2070030: 2, 4: 1, 1676814: 2, 1742350: 1, 1775118: 2, 1824270: 2, 1816078: 2, 1803790: 1, 1809934: 2, 1806862: 2, 1807374: 2, 1808142: 2, 1807918: 2, 1807902: 2, 1807878: 2, 1807882: 2, 1807884: 2, 3: 2, 1807887: 3, 6002178: 2, 3905026: 2, 759298: 2, 1283586: 2, 2070018: 2, 1676802: 2, 1742338: 2, 1775106: 2, 1824258: 2, 1816066: 2, 1803778: 2, 1809922: 2, 1806850: 2, 1807362: 2, 1808130: 1, 1808002: 2, 1807938: 2, 1807906: 2, 1807890: 1, 1807872: 1, 5: 2, 1807875: 3, 9: 2, 192069700: 3, 124960836: 1, 24297540: 2, 41074756: 3, 66240580: 2, 53657668: 2, 55754820: 1, 56803396: 2, 58376260: 2, 58114116: 3, 57720900: 3, 57917508: 1, 57819204: 1, 57835588: 2, 57860164: 2, 57856068: 2, 57854020: 2, 57852996: 3, 57852484: 2, 57852228: 3, 57852100: 3, 57851908: 3, 57852004: 2, 57851988: 3, 57851980: 2, 57851968: 2, 57851974: 2, 57851973: 3, 225624132: 2, 242401348: 2, 267567172: 2, 254984260: 3, 257081412: 3, 258129988: 2, 259702852: 2, 259440708: 3, 259047492: 1, 11: 2, 259244100: 3, 259145796: 2, 259162180: 2, 259186756: 2, 259182660: 3, 259180612: 2, 259179588: 3, 259179076: 1, 259178820: 2, 259178692: 2, 259178500: 3, 259178596: 2, 259178580: 3, 259178572: 3, 259178560: 3, 259178566: 2, 259178565: 3, 527614020: 3, 796049476: 2, 930267204: 3, 997376068: 1, 1030930500: 2, 1047707716: 3, 1072873540: 2, 1060290628: 3, 12: 1, 1062387780: 2, 1063436356: 2, 1065009220: 2, 1064747076: 2, 1064353860: 3, 1064550468: 3, 1064452164: 3, 1064468548: 1, 1064493124: 2, 1064489028: 3, 1064486980: 2, 1064485956: 2, 1064485444: 2, 1064485188: 3, 1064485060: 2, 1064484868: 3, 1064484964: 2, 1064484948: 3, 1064484940: 2, 1064484928: 1, 1064484934: 2, 1064484933: 3, 21: 1, 562949944164420: 2, 13: 2, 844424920875076: 3, 985162409230404: 3, 1055531153408068: 3, 1090715525496900: 2, 22: 2, 1108307711541316: 3, 30: 2, 1117103804563524: 3, 1121501851074628: 2, 1123700874330180: 3, 1124800385957956: 2, 1125350141771844: 2, 1125625019678788: 3, 1125762458632260: 3, 1125831178108996: 3, 1125865537847364: 2, 1125882717716548: 3, 1125891307651140: 3, 1125895602618436: 2, 1125897750102084: 3, 1125898823843908: 2, 1125899360714820: 2, 1125899629150276: 3, 1125899763368004: 3, 1125899830476868: 3, 1125899864031300: 2, 1125899880808516: 3, 1125899905974340: 1, 1125899893391428: 2, 1125899895488580: 3, 1125899896537156: 2, 1125899898110020: 3, 1125899897847876: 3, 1125899897454660: 3, 33: 2, 1125899897651268: 3, 1125899897552964: 2, 1125899897569348: 3, 19: 2, 1125899897593924: 3, 18: 1, 1125899897589828: 2, 1125899897587780: 1, 26: 2, 1125899897586756: 3, 1125899897586244: 2, 28: 2, 1125899897585988: 3, 1125899897585860: 3, 1125899897585668: 3, 14: 2, 1125899897585764: 3, 1125899897585748: 3, 25: 2, 1125899897585740: 3, 1125899897585728: 2, 1125899897585734: 3, 1125899897585733: 2}
for i in range(n):
    temp_count = count
    if bit[i] == "1":
        temp_count -= 1
        bit_list[i] = "0"
        x_bit = ''.join(bit_list)
        bit_list[i] = "1"
    else:
        temp_count += 1
        bit_list[i] = "1"
        x_bit = ''.join(bit_list)
        bit_list[i] = "0"
    x = int(x_bit, 2)
    ans = funk(x, temp_count)
    print(ans)
# print(log_dict)

Submission status: Time Limit Exceeded

Solution code:
def aModM(s, mod):
    number = 0
    for i in range(len(s)):
        number = (number*10 + int(s[i]))
        number = number % m 
    return number 
def ApowBmodM(x,y,p):
    ans = aModM(a, m)
    mul = ans  
    for i in range(1,b):
        ans = (ans*mul) % m
    return ans 


def bruteforce(n):
    # print('n',n)
    cnt = 0
    while n:
        bi = bin(n)
        one = bi.count('1')
        n = n%one
        cnt+=1
    return cnt

n = int(input())
x = input()
x = list(x)
p = x.count('1')
x = x[-1::-1]

s = 0
for i in range(n):
    if x[i]=='1':
        b = i
        a = '2'
        m = p+1
        if b==0:
            s = (s+1)%m
        else:
            s = (s+(ApowBmodM(a,b, m)))%m
        # print(s,x[i],i)
nex = s
if p-1>0:
    s = 0
    for i in range(n):
        if x[i]=='1':
            b = i
            a = '2'
            m = p-1
            if b==0:
                s = (s+1)%m
            else:
                s = (s+(ApowBmodM(a,b, m)))%m
    prev = s
# print(nex,prev)
ans = []
for i in range(n):
    if x[i]=='0':
        cur = nex
        b = i
        a = '2'
        m = p+1
        if b==0:
            cur = (cur+1)%m
        else:
            cur = (cur+ApowBmodM(a, b, m))%m
        # print('cur',ApowBmodM(a,b,m),cur,p)
        
        ans.append(bruteforce(cur)+1)
        # print(bruteforce(cur)+1)

    else:
        if p-1>0:
            cur = prev
            b = i
            a = '2'
            m = p-1
            if b==0:
                cur = (cur-1)%m
            else:
                cur = (cur-ApowBmodM(a, b, m))%m
            # print('here',cur)
            ans.append(bruteforce(cur)+1)
        
        else:
            ans.append(0)
ans = ans[-1::-1]
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys 

readline = sys.stdin.readline 

N = int(input())
X_str= input()
X = list(X_str)
bit_count = X_str.count('1')

def popcount(number, bit_counter):
    num = number
    counter = 0
    while num != 0:
        bit_con = 0
        if counter == 0:
            bit_con = bit_counter  
        else:
            bit_con = bin(num)[2:].count('1')
        num = num % bit_con
        counter += 1

    return counter

for i in range(N):
    # ビットの反転
    x_copy = X.copy()
    bit_count_n = bit_count
    if x_copy[i] == '0':
        x_copy[i] = '1'
        bit_count_n += 1
    else:
        x_copy[i] = '0'
        bit_count_n -= 1

    bit_int = int("".join(x_copy), 2)

    print(popcount(bit_int, bit_count_n))

Submission status: Time Limit Exceeded

Solution code:
import sys #追加

n=int(input())
sys.setrecursionlimit(10**6*2)

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

ans_memo=[0]*(10**6)
#print(ans_memo)
ans_memo[1]=1
ans_memo[2]=1

def DEF(x,cnt):
    global ans_memo
    #print(x,cnt,ans_memo)
    if x==0:
        return 0
    if x<10**6:    
        if ans_memo[x]!=0:
            return ans_memo[x]
        else:
            if x%(str(bin(x)).count("1"))==0:
                ans_memo[x]=1
                return 1
            else:
                tmp=DEF(x%(str(bin(x)).count("1")),cnt+1)+1
                ans_memo[x]=tmp
                return tmp
    else:
        if x%(str(bin(x)).count("1"))==0:
            return 1
        else:
            tmp=DEF(x%(str(bin(x)).count("1")),cnt+1)+1
            return tmp


ans=[]

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

#print(ans_memo)

for item in ans:
    print(item)

Submission status: Time Limit Exceeded

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

@lru_cache(maxsize=1000000000000000000)
def saiki(i, count):
    if i == 0:
        return count
    else:
        count_saiki = count
        i_bin = str(bin(i))
        i_bin_one = i_bin.count("1")
        ni = i % i_bin_one
        count_saiki += 1
        return saiki(ni, count_saiki)

x_lis = []
for i in range(n):
    x_copy = copy.copy(x)
    if x[i] == "1":
        x_copy[i] = "0"
    else:
        x_copy[i] = "1"
    x_lis.append("".join(x_copy))

for xi in x_lis:
    xi_int = int(xi, 2)
    count = 0
    print(saiki(xi_int, count))

Submission status: Time Limit Exceeded

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

dp = [-1] * 200001
dp[0] = 0
dp[1] = 1
dp[2] = 1
dp[3] = 2
dp[4] = 1
dp[5] = 2
dp[6] = 1
dp[7] = 2
dp[8] = 1
dp[9] = 2
dp[10] = 1


def popcount(n: int):
    bin_n = bin(n)
    return str(bin_n).count('1')


for i in range(N):
    count = 0
    if X[i] == '1':
        tmp = int(X)
        tmp -= 10 ** (N - i - 1)
    else:
        tmp = int(X)
        tmp += 10 ** (N - i - 1)
    tmp = int(str(tmp), 2)

    while True:
        if tmp == 0:
            print(count)
            break
        else:
            count += 1
            tmp = tmp % popcount(tmp)
            origin = tmp
            if dp[tmp] != -1:
                if tmp != origin:
                    dp[origin] = count + dp[tmp]
                print(count + dp[tmp])
                break
            else:
                count += 1
                tmp = tmp % popcount(tmp)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = list(map(int,list(str(input()))))
n = 0
nn = 0
Xlist = [0]*(2*(10**5))
for h in range(N):
    n += X[h]*(2 **(N-1-h))
    nn += X[h]

for i in range(N):
    a = 0
    aa = 0
    if (X[i] == 1):
        a = n - (2 **(N-1-i))
        aa = nn - 1
    else:
        a = n + (2 **(N-1-i))
        aa = nn + 1
    time = 0
    while a >0:

        a = a % aa
        aa = bin(a).count('1')
        time += 1
    Xlist[i] = time
for j in range(N):
    print(Xlist[j])

Submission status: Time Limit Exceeded

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

for i in range(N):
    tmp = X[:]
    tmp[i] = "0" if tmp[i] == "1" else "1"
    count = 0
    n = int("".join(tmp), 2)
    while n > 0:
        n = n % bin(n).count("1")
        count += 1
    print(count)

Submission status: Time Limit Exceeded

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


def popcnt(n):
    c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333)
    c = (c & 0x0F0F0F0F0F0F0F0F) + ((c >> 4) & 0x0F0F0F0F0F0F0F0F)
    c = (c & 0x00FF00FF00FF00FF) + ((c >> 8) & 0x00FF00FF00FF00FF)
    c = (c & 0x0000FFFF0000FFFF) + ((c >> 16) & 0x0000FFFF0000FFFF)
    c = (c & 0x00000000FFFFFFFF) + ((c >> 32) & 0x00000000FFFFFFFF)
    return c


# aは1の数


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


ans = [0] * n
cnt = x.count("1")

kotae = [0] * (cnt + 2)
for i in range(cnt + 1):
    kotae[i] = calc(i)


for i in range(n):
    if x[i] == "1":
        temp = cnt - 1
    else:
        temp = cnt + 1
    t = 1 << (n - i - 1)
    # print(num ^ t, bin(num ^ t)
    if num ^ t:
        ans[i] = kotae[(num ^ t) % temp] + 1
    else:
        ans[i] = 0
print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
bina=str(input())

def bin_a(i,bina):
    a=list(bina)
    if a[i]=='0':
        a[i]='1'
    else:
        a[i]='0'
    a="".join(a)
    return a

def count1(str):
    count=0
    n=len(str)
    for i in range(n):
        if str[i]=='1':
            count=count+1
    return count 

for i in range(n):
    count=0
    trans=bin_a(i,bina)
    while int(trans,2)!=0:
        div=count1(trans)
        bin_num = int(trans, 2)
        bin_num=bin_num%div
        trans=format(bin_num, 'b')
        count=count+1
    print(count)