Problem p02609 (python)

Fixed submission:
n = int(input())
x = input()
memo = {0:0}
for i in range(1, n+1):
    j = i
    a = 0
    while True:
        if j in memo:
            memo[i] = memo[j]+a
            break;
        else:
            b = 0
            k = j
            while k > 0:
                if k%2 == 1:
                    b += 1
                k //= 2
            j %= b
            a += 1
n1 = 0
for i in range(n):
    if x[i] == "1":
        n1 += 1
if n1 > 1:
    mup = [1]
    mdown = [1]
    for i in range(1, n):
        mup.append(mup[-1]*2%(n1+1))
        mdown.append(mdown[-1]*2%(n1-1))
    mup.reverse()
    mdown.reverse()
    mmup = 0
    mmdown = 0
    for i in range(n):
        mmup = (mmup+mup[i]*int(x[i]))%(n1+1)
        mmdown = (mmdown+mdown[i]*int(x[i]))%(n1-1)
    for i in range(n):
        if x[i] == "0":
            state = "up"
            n1i = n1+1
        else:
            state = "down"
            n1i = n1-1
        if state == "up":
            mm = (mmup+mup[i])%n1i
        else:
            mm = (mmdown-mdown[i])%n1i
        print(memo[mm]+1)
elif n1 == 1:
    for i in range(n):
        if x[i] == "1":
            print(0)
        else:
            if x[-1] == "0" and i != n-1:
                print(1)
            else:
                print(2)
else:
    for i in range(n):
        print(1)

Buggy submission (verdict: Runtime Error):
n = int(input())
x = input()
memo = {0:0}
for i in range(1, n+1):
    j = i
    a = 0
    while True:
        if j in memo:
            memo[i] = memo[j]+a
            break;
        else:
            b = 0
            k = j
            while k > 0:
                if k%2 == 1:
                    b += 1
                k //= 2
            j %= b
            a += 1
n1 = 0
for i in range(n):
    if x[i] == "1":
        n1 += 1
mup = [1]
mdown = [1]
for i in range(1, n):
    mup.append(mup[-1]*2%(n1+1))
    mdown.append(mdown[-1]*2%(n1-1))
mup.reverse()
mdown.reverse()
mmup = 0
mmdown = 0
for i in range(n):
    mmup = (mmup+mup[i]*int(x[i]))%(n1+1)
    mmdown = (mmdown+mdown[i]*int(x[i]))%(n1-1)
for i in range(n):
    if x[i] == "0":
        state = "up"
        n1i = n1+1
    else:
        state = "down"
        n1i = n1-1
    if state == "up":
        mm = (mmup+mup[i])%n1i
    else:
        mm = (mmdown-mdown[i])%n1i
    print(memo[mm]+1)

Buggy submission (verdict: Runtime Error):
n = int(input())
x = input()
memo = {1:1, 2:1}
n1 = 0
for i in range(n):
    if x[i] == "1":
        n1 += 1
mup = [1]
mdown = [1]
for i in range(1, n):
    mup.append(mup[-1]*2%(n1+1))
    mdown.append(mdown[-1]*2%(n1-1))
mup.reverse()
mdown.reverse()
mmup = 0
mmdown = 0
for i in range(n):
    mmup = (mmup+mup[i]*int(x[i]))%(n1+1)
    mmdown = (mmdown+mdown[i]*int(x[i]))%(n1-1)
for i in range(n):
    if x[i] == "0":
        state = "up"
        n1i = n1+1
    else:
        state = "down"
        n1i = n1-1
    if state == "up":
        mm = (mmup+mup[i])%n1i
    else:
        mm = (mmdown-mdown[i])%n1i
    count = 1
    while mm > 0:
        if mm in memo:
            count += memo[mm]
            break;
        else:
            mmm = mm
            a = 0
            while mmm > 0:
                if mmm%2 == 1:
                    a += 1
                    mmm //= 2
            memo[mm] = a
            mm %= a
            count += 1
    print(count)