Problem p02609 (python)

Fixed submission:
memo = {}
def f(x):
    if x==0:
        return 0
    if x==1:
        return 1
    if x in memo:
        return memo[x]
    k = sum(list(map(int,list(bin(x)[2:]))))
    memo[x] = 1+f(x%k)
    return memo[x]
    
N = int(input())
X = input().strip()
n = sum(list(map(int,list(X))))
if n==0:
    for i in range(N):
        print(1)
elif n==1:
    D = {i:0 for i in range(N)} # mod n+1
    D[0] = 1
    for i in range(1,N):
        D[i] = (D[i-1]*2)%(n+1)
    cnt1 = 0
    for i in range(N):
        if X[i]=="1":
            print(0)
        else:
            a = (cnt1+D[N-1-i])%(n+1)
            print(1+f(a))
else:
    C = {i:0 for i in range(N)}  # mod n-1
    C[0] = 1
    for i in range(1,N):
        C[i] = (C[i-1]*2)%(n-1)
    D = {i:0 for i in range(N)} # mod n+1
    D[0] = 1
    for i in range(1,N):
        D[i] = (D[i-1]*2)%(n+1)
    cnt0 = 0
    cnt1 = 0
    for i in range(N):
        if X[i]=="1":
            cnt0 = (cnt0+C[N-1-i])%(n-1)
            cnt1 = (cnt1+D[N-1-i])%(n+1)
    for i in range(N):
        if X[i]=="1":
            a = (cnt0-C[N-1-i])%(n-1)
            print(1+f(a))
        else:
            a = (cnt1+D[N-1-i])%(n+1)
            print(1+f(a))

Buggy submission (verdict: Runtime Error):
def pc(x):
    cnt = 0
    for i in range(len(x)):
        if x[i]=="1":
            cnt += 1
    return cnt
def f(n,j):
    if n==0:
        return 0
    cnt = 1
    n = n%j
    y = bin(n)[2:]
    while n%pc(y)!=0:
        cnt += 1
        n = n%pc(y)
        y = bin(n)[2:]
    return cnt+1
N = int(input())
X = input().strip()
k = 0
for i in range(N):
    if X[i]=="1":
        k += 1
n = int(X,2)
for i in range(N):
    if X[i]=="0":
        m = n+2**(N-1-i)
        j = k+1
    else:
        m = n-2**(N-1-i)
        j = k-1
    print(f(m,j))

Buggy submission (verdict: Runtime Error):
N = int(input())
A = list(map(int,input().split()))
A = [A[i]-(i+1) for i in range(N)]
A = sorted(A)
C = {}
for i in range(N):
    a = A[i]
    if a not in C:
        C[a] = 0
    C[a] += 1
def f(x):
    if x==0:
        return 0
    cnt = 0
    for a in C:
        cnt += abs(x-a)*C[a]
    return cnt
l = A[0]
r = A[-1]
y1 = f(l)
while r>l:
    midl = (2*l+r)//3
    midr = (l+2*r)//3
    B = sorted([(l,f(l)),(midl,f(midl)),(midr,f(midr)),(r,f(r))],key=lambda x:x[1])
    x1,y1 = B[0]
    x2,y2 = B[1]
    if x1>x2:
        r = x1
        l = x2
    else:
        r = x2
        l = x1
print(y1)

Buggy submission (verdict: Runtime Error):
def pc(x):
    cnt = 0
    for i in range(len(x)):
        if x[i]=="1":
            cnt += 1
    return cnt
def f(n):
    y = bin(n)[2:]
    cnt = 0
    while n%pc(y)!=0:
        cnt += 1
        n = n%pc(y)
        y = bin(n)[2:]
    return cnt+1
N = int(input())
X = input().strip()
n = int(X,2)
for i in range(N):
    if X[i]=="0":
        m = n+2**(N-1-i)
    else:
        m = n-2**(N-1-i)
    print(f(m))

Buggy submission (verdict: Runtime Error):
memo = {}
def f(x):
    if x==0:
        return 0
    if x==1:
        return 1
    if x in memo:
        return memo[x]
    k = sum(list(map(int,list(bin(x)[2:]))))
    memo[x] = 1+f(x%k)
    return memo[x]
    
N = int(input())
X = input().strip()
n = sum(list(map(int,list(X))))
C = {i:0 for i in range(N)}  # mod n-1
C[0] = 1
for i in range(1,N):
    C[i] = (C[i-1]*2)%(n-1)
D = {i:0 for i in range(N)} # mod n+1
D[0] = 1
for i in range(1,N):
    D[i] = (D[i-1]*2)%(n+1)
cnt0 = 0
cnt1 = 0
for i in range(N):
    if X[i]=="1":
        cnt0 = (cnt0+C[N-1-i])%(n-1)
        cnt1 = (cnt1+D[N-1-i])%(n+1)
for i in range(N):
    if X[i]=="1":
        a = (cnt0-C[N-1-i])%(n-1)
        print(1+f(a))
    else:
        a = (cnt1+D[N-1-i])%(n+1)
        print(1+f(a))