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: Runtime Error

Solution code:
n=int(input())
x=int(input(),2)
if x==0b1:
  print(0)
  exit()
def nth_bit(num,n):
    return num ^ (1 << n)
def popdividenumber(n):
    ans=0
    while True:
        n=n%(bin(n).count("1"))
        ans+=1
        if n==0:
            return ans
for i in range(1,n+1):
    xi=nth_bit(x,n-i)
    print(popdividenumber(xi))

Submission status: Runtime Error

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

def p(num):
    return bin(num).count("1")



def solve(num):
    cnt=0
    now=num
    for i in range(100):
        if now==0:
            break
        now%=p(now)
        cnt+=1
    return cnt

init_p = x.count("1")
mod=(init_p+1) * (init_p-1)

decx=0
for i in range(n):
    if x[i]=="1":
        decx+=pow(2,(n-1-i),mod)

for i in range(n):
    now_x=decx
    if x[i]=="0":
        now_p=init_p+1
        now_x+=pow(2,n-1-i)
    else:
        now_p=init_p-1
        now_x-=pow(2,n-1-i)

    now_x%=now_p
    print(solve(now_x)+1)

Submission status: Runtime Error

Solution code:
import copy
def popcount(x):
    count = 0
    for i in range(len(x)):
        if x[i] == '1':
            count+=1
    return count

def mod_pop(l):
    count = 0
    mylist = list('0b')
    mylist.extend(l)
    x = "".join(mylist)
    while True:
        ten = int(x,2)
        y = ten % popcount(x)
        x = str(bin(y)[2::])
        count+=1
        if y == 0 :
            break
    return count


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

for i in range(N):
    # 初期化
    fx = copy.copy(X)
    if X[i] == '0':
        fx[i] = '1'
    else:
        fx[i] = '0'
    print(mod_pop(fx))

Submission status: Runtime Error

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


def arrayTo2(A):
    ans = 0
    l = len(A)
    for i in range(l):
        if (A[i] == '1'):
            ans += 2 ** (l-i-1)

    return ans


N = int(input())

popcountA = [0]*(2**N)
for i in range(1, 2**N):
    popcountA[i] = popcount(i)


X = input()

for i in range(N):
    Xi = []
    for j in range(N):
        if (i == j):
            if (X[i] == '0'):
                Xi.append('1')
            else:
                Xi.append('0')
        else:
            Xi.append(X[j])

    ans = 0
    n = arrayTo2(Xi)
    while (n > 0):
        n = n % popcountA[n]
        ans += 1

    print(ans)

Submission status: Runtime Error

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


def bitsoncount(i):
    assert 0 <= i < 0x100000000
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24
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 % bitsoncount(ans)
    count += 1
  print(count)

Submission status: Runtime Error

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

def f(n):
    ret=0
    original=n
    while True:
        n=n%popcount(n)
        if n in memo:
            memo[original]=ret+memo[n]
            return memo[original]
        if n!=0:
            ret+=1
        else:
            ret+=1
            break
    memo[original]=ret
    return ret

N=int(input())
X=input()
bit=[""]*N
for i in range(N):
    bit[i]=X[i]

n=int(X,2)
memo={}
for i in range(N):
    tmp=n
    if bit[i]=="0":
        tmp+=2**(N-i-1)
    else:
        tmp-=2**(N-i-1)
    print(f(tmp))

Submission status: Runtime Error

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


def sousa(num, ans):
    num_b = format(num, 'b')
    cnt_s = num_b.count("1")
    num %= cnt_s
    if num == 0:
        print(ans)
    else:
        sousa(num, ans + 1)


for i in range(n):
    temp = list(x)
    if temp[i] == "1":
        temp[i] = "0"
    else:
        temp[i] = "1"
    temp = int("".join(temp), 2)
    sousa(temp, 1)

Submission status: Runtime Error

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')
    
    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 = 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 *= 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: Runtime Error

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

bitNum = 0
for bit in x:
    if bit == "1":
        bitNum+=1
valSum = 0
for i in range(len(x)):
    if x[i] == "1":
        valSum += 2**(len(x)-1-i)


mapP = {}
for i in range(len(x)):
    count = 0
    if x[i] == "1":
        val = valSum-(2**(len(x)-1-i))
        popC = bitNum-1
    else:
        val = valSum+(2**(len(x)-1-i))
        popC = bitNum+1
    while True:
        newVal = val % popC
        newbitL = list(format(newVal, 'b'))
        newPopC = 0
        for b in newbitL:
            if b == "1":
                newPopC += 1
        count += 1
        if newVal == 0:
            break
        val = newVal
        popC = newPopC
    print(count)

Submission status: Runtime Error

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)

    print(1 + t[x%c])

Submission status: Runtime Error

Solution code:
M={0:0}
def popcount(n):
    return n.count("1")

D={0:0}
def f(n):
    if n in D:
        return D[n]
    
    T=[n]
    N=n
    while N>0 and N not in D:
        N%=popcount(N)
        T.append(N)

    t=D[N]
    for i in range(-2,-(len(T)+1),-1):
        D[T[i]]=t+(-i-1)
    return D[n]
    
def g(L):
    A=0
    u=1
    for i in range(N):
        A+=L[-(i+1)]*u
        u*=2
    return A

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

for i in range(N):
    if X[i]=="0":
        Y=X[:i]+"1"+X[i+1:]
    else:
        Y=X[:i]+"0"+X[i+1:]

    I=0
    while Y!="0":
        Y=bin(int(Y,2)%popcount(Y))[2:]
        I+=1
    print(I)

Submission status: Runtime Error

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

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

N = INT()
S = list(input())
X = int(''.join(S), 2)
S = S[::-1]
base = S.count('1')

for i in range(N-1, -1, -1):
    cur = X ^ (1<<i)
    cnt = 1
    if S[i] == '1':
        cur %= base - 1
    else:
        cur %= base + 1
    while cur:
        cur %= popcount(cur)
        cnt += 1
    print(cnt)

Submission status: Runtime Error

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

def ppc(k): #k:2進数 bin
  cnt1 = sum( [1*(j == "1") for j in k] )
  k_10 = int(k, 2) #１０進数
  return format( k_10 % cnt1, 'b') #2adic

for i in range(n):
  ly = list(x)
  if ly[i] == '0':
    ly[i] = '1'
    y = ''.join(ly)
  else:
    ly[i] = '0'
    y = ''.join(ly)
  cnt = 0
  while True:
    y = ppc(y)
    cnt += 1
    if y == '0':
      break
  print(cnt)

Submission status: Runtime Error

Solution code:
import copy

N = int(input())
G = list(input())


def count_one(num):
    return bin(num)[1:].count('1')


one_count = 0
for x in G:
    if x == '1':
        one_count += 1

for i in range(N):
    #print(' i : ' + str(i))
    ans = 0
    X = copy.deepcopy(G)
    tmp = one_count
    if X[i] == '1':
        X[i] = '0'
        tmp -= 1
    else:
        X[i] = '1'
        tmp += 1
    base_10 = int(''.join(X), 2)
    while True:
        base_10 %= tmp
        ans += 1
        if base_10 == 0:
            print(ans)
            break
        tmp = list(bin(base_10)[2:]).count('1')
        # print(tmp)

Submission status: Runtime Error

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

A = 0
for i in range(N):
    A += (2**(N-i-1))*int(X[i])


def func(x):
    cnt = 0
    for i in range(N):
        if (x>>i)&1==1:
            cnt += 1

    mm = x%cnt
    # print(x,mm,cnt)

    if mm==0:
        return 1

    else:
        return func(mm)+1 

cnt = 0
for i in range(N):
    if (A>>i)&1==1:
        cnt += 1

for i in range(N-1,-1,-1):
    mm = A^(1<<i)
    # print("mm {}".format(mm))
    print(func(mm))

Submission status: Runtime Error

Solution code:
import sys #追加

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

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

ans_memo=[0]*(2**(n+2))
#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 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

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: Runtime Error

Solution code:
n = int(input())
x = input()
value = [0, 1]
for i in range(2, 2 * (10 ** 5) + 1):
    ans = 1
    i = i % bin(i).count('1')
    value.append(ans + value[i])

for i in range(n):
    t = x[:i] + ('0' if x[i] == '1' else '1') + x[i + 1:]
    ans = 1
    t = (int(t, 2) % (t.count('1')))
    print(ans + value[t])

Submission status: Runtime Error

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)
print(base)
print(basex)
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)

    print(1 + t[x%c])

Submission status: Runtime Error

Solution code:
cnt = 0

def recfunc(p, q):
    global cnt
    cnt += 1
    if p%q == 0:
        pass
    else:
        p = p%q
        q = bin(p).count('1')
        recfunc(p, q)

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

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

for i in range(N):
    tmp = list(X)
    if tmp[i] == '1':
        tmp[i] = '0'
    elif tmp[i] == '0':
        tmp[i] = '1'

    tmp = "".join(tmp)

    tmp10 = int(tmp, 2)
    tmpcnt = tmp.count('1')

    recfunc(tmp10, tmpcnt)
    print(cnt)
    cnt = 0

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10 ** 9)

mm = {}

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

def f(n):
    n%=popcorn(n)
    return n
    
def nf(n,count):
    if(n == 0):
        return count
    elif(n in mm):
        count += mm[n]
        return count
    else:
        n%=popcorn(n)
        return nf(n,count+1)


n = int(input())
a = input()
moto = int(a,2)
for i in range(n-1,0-1,-1):
    if(a[n-1-i] == "0"):
        k=moto+2**i
    else:
        k=moto-2**i
    mo = f(k)
    if(mo in mm):
        print(mm[mo])
        continue
    else:
        count = nf(mo,1)
        print(count)
        mm[mo]=count

Submission status: Runtime Error

Solution code:
N=int(input())
X=input()
X10=int(X,2)
one=X.count('1')
a=X10%(one-1)
b=X10%(one+1)
c=one-1
d=one+1
def popcount(n):
  c=format(n,'b').count('1')
  return n%c
def f(n):
  count=0
  while n>0:
    n=popcount(n)
    count+=1
  return count

for i in range(N):
  if X[i]=='1':
    Y=(a-pow(2,N-i-1,c))%c
    print(f(Y)+1)
  if X[i]=='0':
    Y=(b+pow(2,N-i-1,d))%d
    print(f(Y)+1)

Submission status: Runtime Error

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

a=2**n
for i in range(n):
    a//=2
    m=x^a
    ans=1
    l=bin(m).count("1")
    while m%l!=0:
        m=m%l
        l=bin(m).count("1")
        ans+=1
    print(ans)

Submission status: Runtime Error

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

dp = [0] * (2 ** N + 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)
    origin = tmp

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

Submission status: Runtime Error

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


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


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


def f(n):
    cnt = 0
    res = True
    while res:
        n = popcount(n)
        cnt += 1
        if n == 0:
            res = False
    return cnt


for i in range(N):
    tmp = toggle_nth_bit(X, N - i)
    print(f(tmp))

Submission status: Runtime Error

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')
    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[2:]).count('1')
        devide = num10 % cnt
        devideCnt += 1
    print(devideCnt)

Submission status: Runtime Error

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


def count_ones_by_shift(num):
    num = (num & 0x55555555) + ((num & 0xAAAAAAAA) >> 1)
    num = (num & 0x33333333) + ((num & 0xCCCCCCCC) >> 2)
    num = (num & 0x0F0F0F0F) + ((num & 0xF0F0F0F0) >> 4)
    num = (num & 0x00FF00FF) + ((num & 0xFF00FF00) >> 8)
    num = (num & 0x0000FFFF) + ((num & 0xFFFF0000) >> 16)
    return num


def main():
    n = int(input().strip())
    x = int(input().strip(), 2)

    for i in range(n, 0, -1):
        xi = x ^ (1 << (i - 1))

        ans = 1
        c = count_ones_by_shift(xi)
        while xi % c != 0:
            xi = xi % c
            c = count_ones_by_shift(xi)
            ans += 1
        print(ans)


if __name__ == '__main__':
    main()