Problem p02609 (python)

Fixed submission:
def main():
    n = int(input())
    x = input()
    k = int(x, 2)
    p = x.count("1")
    if p > 1:
        kp0 = k % (p - 1)
    kp1 = k % (p + 1)
    f = [0] * (n + 1)
    for i in range(1, n + 1):
        f[i] = f[i % bin(i).count("1")] + 1
    for i in range(n):
        if x[i] == "1":
            pi = p - 1
            if pi == 0:
                print(0)
                continue
            print(f[(kp0 - pow(2, n - i - 1, pi)) % pi] + 1)
        else:
            pi = p + 1
            print(f[(kp1 + pow(2, n - i - 1, pi)) % pi] + 1)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def mpower(a, b, n):
    if b == 0:
        return 1
    if b == 1:
        return a % n
    a1 = a
    k = 1
    while a1 < n and k < b:
        a1 = a1 * a
        k = k + 1

    a1 = a1 % n
    b1 = b // k
    a2 = a
    b2 = b % k
    return (mpower(a1, b1, n)*mpower(a2, b2, n)) % n


def main():
    n = int(input())
    x = input()
    k = int(x, 2)
    p = x.count("1")
    kp0 = k % (p - 1)
    kp1 = k % (p + 1)
    f = [0] * (n + 1)
    for i in range(1, n + 1):
        f[i] = f[i % bin(i).count("1")] + 1
    for i in range(n):
        if x[i] == "1":
            pi = p - 1
            if pi == 0:
                print(0)
                continue
            print(f[(kp0 - mpower(2, n - i - 1, pi)) % pi] + 1)
        else:
            pi = p + 1
            print(f[(kp1 + mpower(2, n - i - 1, pi)) % pi] + 1)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def mpower(a, b, n):
    if b == 0:
        return 1
    if b == 1:
        return a % n
    a1 = a
    k = 1
    while a1 < n and k < b:
        a1 = a1 * a
        k = k + 1

    a1 = a1 % n
    b1 = b // k
    a2 = a
    b2 = b % k
    return (mpower(a1, b1, n)*mpower(a2, b2, n)) % n


def main():
    n = int(input())
    x = input()
    k = int(x, 2)
    p = x.count("1")
    kp = [k % (p - 1), k % (p + 1)]
    f = [0] * (n + 1)
    for i in range(1, n + 1):
        f[i] = f[i % bin(i).count("1")] + 1
    for i in range(n):
        if x[i] == "1":
            if p - 1 == 0:
                print(0)
                continue
            print(f[(kp[0] - mpower(2, n - i - 1, pi)) % pi] + 1)
        else:
            pi = p + 1
            print(f[(kp[1] + mpower(2, n - i - 1, pi)) % pi] + 1)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():
    n = int(input())
    x = input()
    p = x.count("1")
    f = [0] * (n + 1)
    for i in range(1, n + 1):
        f[i] = f[i % bin(i).count("1")] + 1
    for i in range(n):
        xi = x[:i] + str(1 - int(x[i])) + x[i + 1:]
        pi = p + int(xi[i]) * 2 - 1
        print(f[int(xi, 2) % pi] + 1)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():
    n = int(input())
    x = input()
    p = x.count("1")
    f = [0] * (n + 1)
    for i in range(1, n + 1):
        f[i] = f[i % bin(i).count("1")] + 1
    for i in range(n):
        xi = x[:i] + str(1 - int(x[i])) + x[i + 1:]
        pi = p + int(xi[i]) * 2 - 1
        print(f[int(xi, 2) % pi] + 1)


if __name__ == '__main__':
    main()