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

f = dict()

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

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

Submission status: Time Limit Exceeded

Solution code:

N = int(input())
X = input()
ans_dic = {}

for n in range(N):
    s = X[:n]
    if X[n] == "0":
        s += "1"
    else:
        s += "0"
    s += X[n+1:]
    ans = 0
    while True:
        one = list(s).count("1")
        num = int(s, 2)
        if one == 0:
            break

        amari = num % one
        if amari == 0:
            ans += 1
            break
        else:
            s = str(bin(amari))[2:]
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def popcount(y, n):
  now_n = n
  c = 0
  while(y!=0):
    y = y%now_n
    now_n = bin(y)[2:].count('1')
    c += 1
  return c
    
  

n = int(input())
x = input()
init_n = x.count('1')
intx = int(x, 2)
i2 = pow(2, n-1)
for i in range(n):
  now_n = 0
  now_x = 0
  if(x[i] == '1'):
    now_n = init_n -1
    now_x = intx - i2
  else:
    now_n = init_n +1
    now_x = intx + i2
  print(popcount(now_x, now_n))
  i2 //=2

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N = int(input())
    X = input()
    X_10 = int(X,2)
    ans = []
    for i in range(N):
        if X[i] == '0':
            ans.append(f(X_10 + pow(2, N-1-i)))
        else:
            ans.append(f(X_10 - pow(2, N-1-i)))
    
    print(*ans, sep='\n')

def f(N):
    cnt = 0
    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:
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from functools import lru_cache
from math import factorial#, gcd
from bisect import bisect_left, bisect_right #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

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

def mn():
    return -1
pops = defaultdict(mn)
dists = defaultdict(mn)

# 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
def popcnt(n):
    return bin(n).count('1')
def myf(n):
    if pops[n] != -1:
        return pops[n]
    else:
        val = popcnt(n)
        pops[n] = val
        return n%val

@lru_cache(maxsize=None)
def saiki(n):
    if n == 0:
        return 0
    else:
        n = myf(n)
        return saiki(n) + 1

bX = int(X, 2)
for i in range(N):
    if X[i] == '1':
        val = bX - 2**(N-i-1)
    else:
        val = bX + 2**(N-i-1)
    res = saiki(val)
    print(res)

Submission status: Time Limit Exceeded

Solution code:
# n = int(input())
n = 2 * 10**5

# s = input()
s = ''.join(['1' for i in range(n)])


bin = int(s, 2)
memo = dict()

def popCount(value):

    count = 0
    current = value
    history = [current]
    while current != 0:
        if current in memo:
            return count + memo[current]
        pop = format(current, 'b').count('1')
        m = current % pop
        current = m
        history.append(current)
        count += 1
    for i, a in enumerate(history):
        memo.update({a: count-i})
    return count


result = []
for i in range(n):
    if s[i] == '1':
        val = bin - 2**(n-1 - i)
    else:
        val = bin + 2**(n-1 - i)

    result.append(popCount(val))

print(*result, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import copy
N = int(input())
x = list(input())

def popcount(s):
    return s.count('1')

ans = []
for i in range(N):
    X = copy.deepcopy(x)
    X[i] = '1' if X[i]=='0' else '0'
    f = 0
    n = int(''.join(X), 2)
    while n != 0:
        n = n % popcount(bin(n))
        f += 1
    print(f)

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 = 0
for i, bit in enumerate(x[::-1]):
    num += int(bit) * pow(2, i)
lbit = bitcount(18)
cnt = x.count('1')

for i in range(n):
    ans = 0
    tmp = num ^ pow(2, n - (i + 1))
    ctmp = cnt - 2 * int(x[i]) + 1
    while tmp > 0:
        ans += 1
        tmp %= ctmp
        ctmp = lbit[tmp]
    print(ans)

Submission status: Time Limit Exceeded

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

def solve(a):
    pc = bin(a).count('1')
    if pc == 0:
        return 0
    elif pc == 1:
        return 1
    return solve(a % pc) + 1
        
for i in reversed(range(n)):
    a = 1 << i ^ x
    print(solve(a))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
#N, K = (int(i) for i in input().split())
#B = [int(x) for x in input().split()]
#A = [[int(i) for i in input().split()] for i in range(N)]

divmemo = {}
def popcountdiv(n):
    if n in divmemo:
        return divmemo[n]
    res = n % (bin(n).count("1"))
    divmemo[n] = res
    return res

memo = {}
def f(n):
    if n == 0:
        return 0
    if n in memo:
        return memo[n]
    else:
        res = f(popcountdiv(n))
        memo[n] = res+1
        return 1 + res

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

for i in range(N):
    print(f(int(X[:i] + str((int(X[i])+1)%2)+ X[i+1:] , 2)))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=str(input())
x1=0
for i in range(n):
    if int(x[i])&1:
        x1+=2**(n-1-i)
for i in range(n):
    xi=(2**(n-1)>>i)^x1
    count=0
    while xi:
        popi=0
        a=xi
        while a:
            a&=(a-1)
            popi+=1
        xi%=popi
        count+=1
    print(count)

Submission status: Time Limit Exceeded

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

su = s.count('1')
sun = int(s,2)


table = [0]*200001
table[1] = 1
for i in range(2,200001):
    table[i] = 1 + table[i % bin(i).count('1')]

def pow(n,e,mod):
    ret=1
    b=n
    while e > 0:
        if e % 2 == 1:
            ret = ret * b % mod
        b = b * b % mod
        e = e//2
    return ret

for i in range(n):
    if s[i] == '0':
        print(1+table[(sun+pow(2,n-1-i,su+1))%(su+1)])
    else:
        if su-1 == 0:
            print(0)
        else:
            print(1+table[(sun-pow(2,n-1-i,su-1)+su-1)%(su-1)])

Submission status: Time Limit Exceeded

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

#print(x)

def popcount(x):
    #print()
    return bin(x).count("1")

#dic[num] = f(num)
dic = {0: 0, 1: 1, 2: 1}

def f(x):
    #print(x)
    if x in dic:
        #print("!", x, dic[x])
        return dic[x]
    else:
        next_x = x % popcount(x)
        ans = f(next_x) + 1
        dic[x] = ans
        return ans

for i in range(n):
    keta = n - i - 1
    bit = 2 ** keta
    trans_num = num ^ bit
    #print(bin(num), bin(bit), bin(trans_num))
    #print("ans", f(trans_num))
    print(f(trans_num))


"""
for i in range(1000):
    print("i", i, "pop", popcount(i))
"""

Submission status: Time Limit Exceeded

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

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

@lru_cache(maxsize=None)
def f(m):
    if m == 0:
        return 0
    else:
        amari = m % popcount(m)
        return 1 + f(amari)
    
for i in range(n):
    moji = x
    if moji[i] == "1":
        moji = moji[:i] + "0" + moji[i+1:]
    else:
        moji = moji[:i] + "1" + moji[i+1:]
    print(f(int(moji, 2)))

Submission status: Time Limit Exceeded

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

def popcount(n):
    return bin(n).count('1')
memo = {1:1}
def f_count(n):
    ans = 0
    while n != 0:
        if n in memo:
            ans += memo[n]
            return ans
        n %= popcount(n)
        ans += 1
    return(ans)

for i in range(N):
    co_x = X.copy()
    if co_x[i] == "1":
        co_x[i] = "0"  
    else:
        co_x[i] = "1"
    num = int("".join(co_x), 2)
    print(f_count(num))

Submission status: Time Limit Exceeded

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

t = [0]
for n in range(1, N+1):
    b = bin(n)[2:]
    c = b.count("1")
    t.append(1 + t[n%c])

base = X.count("1")
basex = int(X, 2)
for n in range(N):
    if X[n] == "0":
        c = base + 1
        x = basex + 2**(N-n-1)
    else:
        c = base - 1
        x = basex - 2**(N-n-1)
    
    if c == 0:
        print(0)
    else:
        print(1 + t[x%c])

Submission status: Time Limit Exceeded

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

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

def solve(N, X):
    X_oct = int(X, 2)
    X_one_count = X.count("1")
    # X_one_count = popcount(X)

    memo = {}
    for i, x in enumerate(X):
        if x == '1':
            X_current = X_oct - 2 ** (N-1-i)
            X_one_current = X_one_count - 1
        elif x == '0':
            X_current = X_oct + 2 ** (N - 1 - i)
            X_one_current = X_one_count + 1

        X_target = X_current
        if X_one_current == 0:
            print(0)
            continue

        count = 0
        while True:
            X_current = X_current % X_one_current
            X_one_current = popcount(X_current)
            count += 1

            if X_current == 0:
                break

            if X_current in memo:
                count += memo[X_current]
                break
        memo[X_target] = count
        print(count)

    return

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

def solve():
    N = II()
    bb = input()
    X = list(map(int, bb))
    # print(X)
    num = int(bb, 2)
    # print(num)
    # return

    bit = sum(X)
    one_bit_cnt = {num: bit}
    f_cnt = {0: 0}

    def popcount(n):
        return sum( list(map(int, list(bin(n).replace('0b', '')))))

    def f(n, pop, c=0):
        # print(n, pop, c)
        if n == 0:
            return c

        cnt = f_cnt.get(n, -1)
        if cnt == -1:
            n = n % pop
            pop = one_bit_cnt.get(n, -1)
            if pop == -1:
                pop = popcount(n)
                one_bit_cnt[n] = pop
            cnt = f(n, pop, c+1)
            f_cnt[n] = cnt - c - 1
        else:
            return cnt + c
        return cnt

    ex = N-1
    for i, x in enumerate(X):
        if x == 1:
            n = num - pow(2, ex)
            pop = bit - 1
        else:
            n = num + pow(2, ex)
            pop = bit + 1
        one_bit_cnt[n] = pop
        # print(n, pop)
        fc = f_cnt.get(n, -1)
        if fc != -1:
            print(fc)
        else:
            fc = f(n, pop)
            print(fc)
            f_cnt[n] = fc

        ex -= 1
        # print(f_cnt)
    # print(f_cnt)

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=input()
xx=x.count('1')
xx2=int(x,2)
k=2**n
for i in range(n):
    k//=2
    if x[i]=='0':
        xxx=xx+1
        xxx2=xx2+k
    else:
        xxx=xx-1
        xxx2=xx2-k
    count=0

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

Submission status: Time Limit Exceeded

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

#%%
def popcount(n):
    ans = 0
    temp = format(n, "b")
    for i in temp:
        if i == "1":
            ans += 1

    return ans

def f(n):
    cnt = 0
    temp = n
    while temp != 0:
        temp = temp % popcount(temp)
        cnt += 1

    return cnt

A = []
for i in range(N):
    if X[i] == "1":
        XX = list(X)
        XX[i] = "0"
        A.append("".join(XX))

    elif X[i] == "0":
        XX = list(X)
        XX[i] = "1"
        A.append("".join(XX))

#%%
for i in A:
    ans = f(int(i, 2))
    print(ans)

Submission status: Time Limit Exceeded

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

def rev(num, i):
  i = N - 1 - i
  return num ^ (1 << i)

for i in range(N):
  X = rev(X, i)
    
  fn = X
  cnt = 0
  
  while fn != 0:
    fn = fn % bin(fn).count("1")
    cnt += 1
  print(cnt)
  
  X = rev(X, i)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

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

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

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:


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 _ in range(n):
            print(1)
        exit()
    
    c2bl = [1]*n
    c2blp = [1]*n
    c2blm = [1]*n

    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):
        c2bl[i] = curr_2b
        c2blp[i] = curr_2b_p
        c2blm[i] = curr_2b_m
        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 = 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
            diff = (-1)*c2blm[i]
            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
            diff = c2blp[i]
            ans = (curr_sum_p1 + diff)%(one_cnt+1)
            ansl[i] = (n_ansl[ans]+1)
        # curr_2b *= 2
        # 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)


    # print(ansl)
    for a in ansl:
        print(a)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy
N = int(input())
line = list(input())
for i in range(N):
    tmp = copy.copy(line)
    if tmp[i] == '0':
        tmp[i] = '1'
    elif tmp[i] == '1':
        tmp[i] = '0'
    else:
        print("error: tmp includes except 0 or 1")
        exit()
    cnt = tmp.count('1')
    if cnt == 0:
        print(0)
        continue
    num2 = int(''.join(tmp))
    num10 = int(str(num2), 2)
    devide = num10 % cnt
    devideCnt = 1
    while devide != 0:
        num10 = devide
        num2 = bin(num10)
        cnt = list(num2).count('1')
        devide = num10 % cnt
        devideCnt += 1
    print(devideCnt)

Submission status: Time Limit Exceeded

Solution code:

n = input()
s = input()

hanten = 1 << int (n) - 1;
for i in range(int(n)):
    cal = (int(s, 2) ^ hanten)
    count = 0
    while (cal != 0):
        cal = cal % bin(cal).count('1')
        count = count + 1
#       print( str(i) + ">" + str(count) + ">>>" + str(cal))    
    print(count)
    hanten = hanten >> 1

Submission status: Time Limit Exceeded

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

def count(n, c):
    i = 0
    while c != 0:
        n = n % c
        c = bin(n % c)
        c = str(c)
        a = 0
        for s in c:
            if s == '1':
                a += 1
        c = a
        i += 1
    return i

cnt = 0
for s in x:
    if s == '1':
        cnt += 1

for i in range(n):
    if x[i] == '1':
        xi = x[:i] + '0' + x[i+1:]
        xi = int(xi, 2)
        c = cnt - 1
    else:
        xi = x[:i] + '1' + x[i+1:]
        xi = int(xi, 2)
        c = cnt + 1
    
    print(count(xi, c))

Submission status: Time Limit Exceeded

Solution code:
def pop(x):
    c = 0
    while x != 0:
        b = sum(i == '1' for i in format(x,'b'))
        x = x%b
        c += 1
    return c

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

Submission status: Time Limit Exceeded

Solution code:
# Coding is about expressing your feeling, and
# there is always a better way to express your feeling_feelme
import sys
import math
# sys.stdin=open('input.txt','r')
# sys.stdout=open('output2.txt','w')
from sys import stdin,stdout
from collections import deque,defaultdict
from math import ceil,floor,inf,sqrt,factorial,gcd,log2
from copy import deepcopy
ii1=lambda:int(stdin.readline().strip())
is1=lambda:stdin.readline().strip()
iia=lambda:list(map(int,stdin.readline().strip().split()))
isa=lambda:stdin.readline().strip().split()
mod=int(1e9 + 7)
def invert(number,k):
    # m = (m) | (m - 1)
    mask=1<<(k-1)
    # print(mask)
    res = number ^ mask
    return res
def fun(num):
    count=0
    while num>=0:
        a=bin(num).count('1')
        if a==0:
            break
        ans=num%a
        num=ans
        count+=1
        if num==0:
            break
    print(count)

n=ii1()
s=is1()
ss='0b'+s
nums=int(ss,2)
# print(nums)
for i in range(n):
    ans=invert(nums,n-i)
    # print(ans)
    fun(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


from functools import lru_cache

@lru_cache(maxsize=None)
def binbin(binn):
    return bin(binn).count("1")


def popcount(n, nc):
    if n == 0:
        return 0
    return 1 + popcount(n % nc, binbin(n % nc))

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

    x = int(X, 2)
    xc = X.count("1")
    for i in range(N):
        if X[i] == '0':
            print(popcount(x + (2 ** (N - i - 1)), xc + 1))
        else:
            print(popcount(x - (2 ** (N - i - 1)), xc - 1))



    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=input()
cnt=0
X=int(x,2)
for i in range(n):
  if x[i]=='1':
    cnt+=1
    
def pop(m):
  return str(bin(m))[2:].count('1')

def func(m):
  cnt=0
  while m>0:
    m=m%pop(m)
    cnt+=1
  return cnt
    
for i in range(n):
  Cnt=cnt
  y=X
  if x[i]=='1':
    Cnt-=1
    y-=2**(n-i-1)
  else:
    y+=2**(n-i-1)
  print(func(y))

Submission status: Time Limit Exceeded

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


def f(cnt):
    if (cnt > 0):
        p_count = bin(cnt).count('1')
        return f(cnt % p_count) + 1
    else:
        return 0


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

Submission status: Time Limit Exceeded

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

def one(y):
    ans = 0
    for i in y:
        if i == "1":
            ans += 1
    return ans

def popcount(y):
    ans = 0
    yint = int(y,2)
    while yint != 0:
        ans += 1
        count = one(bin(yint))
        yint = yint % count
    return ans

j = 0
for i in range(n):
    xAfter = x
    if xAfter[j] == "0":
        xAfter = x[:j] + '1' +x[j+1:]
    elif xAfter[j] == "1":
        xAfter = x[:j] + '0' +x[j+1:]
    ans = popcount(xAfter)
    print(ans)
    j += 1

Submission status: Time Limit Exceeded

Solution code:
# itne me hi thakk gaye?
n = int(input())
org = list(input())
ans = []
# print(org)
def compute(s, pc):
    # print("PC : ", pc)
    ans = 0
    s = s[::-1]
    for i in range(len(s)):
        if s[i] == '1':
            ans = (ans + pow(2, i, pc))%pc
    return ans% pc
for i in range(n):
    tmp = org[:]
    if org[i] == '1':
        tmp[i] = '0'
    else:
        tmp[i] = '1'
    count = 0
    pc = tmp.count('1')
    if pc == 1:
        ans.append(count + 1)
        continue
    if pc == 0:
        ans.append(count)
        continue
    curr_number = compute(tmp, pc)
    app = False
    while(curr_number != 0):
        tmp = list(bin(curr_number)[2:])
        count += 1
        pc = tmp.count('1')
        if (pc == 1):
            ans.append(count + 1)
            app = True
            break
        if (pc == 0):
            app = True
            ans.append(count)
            break
        curr_number = compute(tmp, pc)
    if not app:
        ans.append(count+1)
# print(ans)
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
def toggleKthBit(n, k): 
  return (n ^ (1 << (k-1))) 

def popcount(x):
    c = 0
    while x:
        x &= x - 1
        c += 1

    return c
N = int(input())
X = int(input())

ans = -1
for i in range(N, 0, -1):
  count = 0
  ans = toggleKthBit((int(str(X), 2)), i)
  while ans != 0:
    ans = ans % popcount(ans)
    count += 1
  print(count)

Submission status: Time Limit Exceeded

Solution code:

#!/usr/bin/python
# -*- coding: utf-8 -*-

import numpy as np

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

def int_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(map(int,input().split())))
    return np.array(x)

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

f = {0:0}

for i in range(0,N):
    newX = list(X)
    if newX[i] == "0":
        newX[i] = "1"
    else:
        newX[i] = "0"

    X_int = 0

    for i,x in enumerate(newX[::-1]):
        X_int += 2**i*int(x)

    ans = 0

    while X_int != 0:
        if X_int in f.keys():
            ans += f[X_int]
            break
        X_int = X_int%popcnt1(X_int)
        ans += 1

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = int(input(),2)
b = int(2**(n-1))
pc = 0
d = []
c = x
for i in range(n):
    d.append(c&1)
    if c&1 == 1:
        pc += 1
    c=c>>1
# print(pc,d)
for i in range(n):
    if d[-i-1]==0:
        m = 1
    else:
        m = -1
    temppc = pc+m
    temp = x^b
    ans = 0
    # print(temp,x,b)
    while temp:
        # print(temp)
        # print(i,temp,ans,temppc)
        # print(temp)
        # s = str(bin(temp))
        # print(temp,popcount(temp))
        if temppc == 0:
            break
        temp = temp % temppc
        ans += 1
        c = temp
        temppc = 0
        while c:
            if c&1 == 1:
                temppc += 1
            c=c>>1
        # print(temp,s)
        # break
    b=b>>1
    print(ans)

Submission status: Time Limit Exceeded

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


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


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

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = int(input())
A = [0] * (n+1)
#A = list(map(int, input().split()))
#l, r, d = map(int, input().split())
x = int(str(x),2)
def popcnt1(n):
    return bin(n).count("1")

for i in range(1,n+1):
  ans = 0
  A[i] = x ^ 2**(n-i)
  while A[i] != 0:
    A[i] = A[i] % popcnt1(A[i])
    ans += 1
  print(ans)

Submission status: Time Limit Exceeded

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

n = int(input())
x = input()
#b = list(map(int, input().split()))
#n, m = map(int, input().split())
#s = input()
#s,t = input().split()
#a = [int(input()) for _ in range(n)]
#
#readline = sys.stdin.readline
#n,m = [int(i) for i in readline().split()]
#ab = [[int(i) for i in readline().split()] for _ in range(n)]

def countSetBits(n): 
    count = 0
    while (n): 
        count += n & 1
        n >>= 1
    return count

MAX_X = 10**7
CSB = [0]*MAX_X

# convert base-2 binary number string to int
x = int(x,2)

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

ans = []

for i in range(0,n):
    tmp_x = toggle_nth_bit(x,i)
    tmp_n = countSetBits(tmp_x)
    tmp = 0
    while tmp_x > 0:
        tmp_x %= tmp_n
        tmp_n = countSetBits(tmp_x)
        tmp += 1
    ans.append(tmp)
    
print(*ans[::-1])

Submission status: Time Limit Exceeded

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

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

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

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

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

Submission status: Time Limit Exceeded

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


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

X_int = int(X, 2)

for i,bit in enumerate(X):
    mask = 2**(N-i-1) * (-1)**(int(bit))
    Xi = X_int + mask

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

Submission status: Time Limit Exceeded

Solution code:


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

def calc(num):
    ans = 0
    while num > 0:
        ans += 1
        num = num % bin(num).count("1")
    return ans

for i in range(N):
    x = list(X)
    if x[i] == '0':
        x[i] = '1'
    else:
        x[i] = '0'
    xx = "".join(x)
    print(calc(int(xx, 2)))