Problem p02609 (python)

Fixed submission:
import sys
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    X = input()
    bit_num = X.count("1")

    X_minus = [0] * N # X_minus[i] = 2^i mod (bit_num - 1)
    X_plus = [0] * N # X_plus[i] = 2^i mod (bit_num + 1)
    X_minus[0], X_plus[0] = 1, 1
    for i in range(1, N):
        if bit_num != 1: X_minus[i] = (X_minus[i - 1] * 2) % (bit_num - 1)
        X_plus[i] = (X_plus[i - 1] * 2) % (bit_num + 1)
    #print("X_minus={}".format(X_minus))
    #print("X_plus={}".format(X_plus))

    rem_minus = 0
    rem_plus = 0
    for i in range(N):
        if X[N-i-1] == '1':
            if bit_num != 1: rem_minus = (rem_minus + X_minus[i]) % (bit_num - 1)
            rem_plus = (rem_plus + X_plus[i]) % (bit_num + 1)
    #print(rem_minus, rem_plus)

    for i in range(N):
        if X[i] == '0':
            bit = bit_num + 1
            n = (rem_plus + X_plus[-i-1]) % bit
        if X[i] == '1':
            bit = bit_num - 1
            if bit != 0: n = (rem_minus - X_minus[-i-1]) % bit
        if bit == 0 or bit == 1:
            print(bit)
            continue

        cnt = 1
        while n != 0:
            bit = bin(n).count("1")
            n %= bit
            cnt += 1
        print(cnt)




if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    X = input()
    bit_num = X.count("1")

    X_minus = [0] * N # X_minus[i] = 2^i mod (bit_num - 1)
    X_plus = [0] * N # X_plus[i] = 2^i mod (bit_num + 1)
    X_minus[0], X_plus[0] = 1, 1
    for i in range(1, N):
        if bit_num != 1: X_minus[i] = (X_minus[i - 1] * 2) % (bit_num - 1)
        X_plus[i] = (X_plus[i - 1] * 2) % (bit_num + 1)
    #print("X_minus={}".format(X_minus))
    #print("X_plus={}".format(X_plus))

    rem_minus = 0
    rem_plus = 0
    for i in range(N):
        if X[N-i-1] == '1':
            if bit_num != 1: rem_minus = (rem_minus + X_minus[i]) % (bit_num - 1)
            rem_plus = (rem_plus + X_plus[i]) % (bit_num + 1)
    #print(rem_minus, rem_plus)

    for i in range(N):
        if X[i] == '0':
            bit = bit_num + 1
            n = (rem_plus + X_plus[-i-1]) % bit
        if X[i] == '1':
            bit = bit_num - 1
            n = (rem_minus - X_minus[-i-1]) % bit
        if bit == 0 or bit == 1:
            print(bit)
            continue

        cnt = 1
        while n != 0:
            bit = bin(n).count("1")
            n %= bit
            cnt += 1
        print(cnt)




if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    X = input()
    bit_num = X.count("1")

    X_minus = [0] * N # X_minus[i] = 2^i mod (bit_num - 1)
    X_plus = [0] * N # X_plus[i] = 2^i mod (bit_num + 1)
    X_minus[0], X_plus[0] = 1, 1
    for i in range(1, N):
        if bit_num != 1: X_minus[i] = (X_minus[i - 1] * 2) % (bit_num - 1)
        X_plus[i] = (X_plus[i - 1] * 2) % (bit_num + 1)
    print("X_minus={}".format(X_minus))
    print("X_plus={}".format(X_plus))

    rem_minus = 0
    rem_plus = 0
    for i in range(N):
        if X[N-i-1] == '1':
            if bit_num != 1: rem_minus = (rem_minus + X_minus[i]) % (bit_num - 1)
            rem_plus = (rem_plus + X_plus[i]) % (bit_num + 1)
    print(rem_minus, rem_plus)

    for i in range(N):
        if X[i] == '0':
            bit = bit_num + 1
            n = (rem_plus + X_plus[-i-1]) % bit
        if X[i] == '1':
            bit = bit_num - 1
            n = (rem_minus - X_minus[-i-1]) % bit
        if bit == 0 or bit == 1:
            print(bit)
            continue

        cnt = 1
        while n != 0:
            bit = bin(n).count("1")
            n %= bit
            cnt += 1
        print(cnt)




if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
def input(): return sys.stdin.readline().strip()

def func(n):
    bin_num = bin(n).count("1")
    #print(n% bin_num)
    if n == 0: return 0
    return n % bin_num

def main():
    N = int(input())
    X = input()
    bit_num = X.count("1")

    X_minus = [0] * N
    X_plus = [0] * N
    X_minus[0], X_plus[0] = 1, 1
    rem_minus = int(X[-1])
    rem_plus = int(X[-1])
    for i in range(1, N):
        if bit_num != 1: X_minus[i] = (X_minus[i - 1] * 2) % (bit_num - 1)
        X_plus[i] = (X_plus[i - 1] * 2) % (bit_num + 1)
        if X[-i-1] == "1":
            rem_minus += X_minus[i]
            if bit_num != 1: rem_minus %= bit_num - 1
            rem_plus += X_plus[i]
            rem_plus %= bit_num + 1

    for i in range(N):
        #print("")
        #print("i={}".format(i))
        n = list(X)
        if X[i] == '0':
            n[N - i - 1] = '1'
            bin = bit_num + 1
        if X[i] == '1':
            n[N - i - 1] = '0'
            bin = bit_num - 1
        if bin == bit_num - 1: n = (rem_minus - X_minus[-i-1]) % bin
        if bin == bit_num + 1: n = (rem_plus + X_plus[-i-1]) % bin
        #print("bin={}, n={}".format(bin, n))

        if bin == 0:
            print(0)
            continue
        cnt = 1
        while n != 0:
            n = func(n)
            cnt += 1
        print(cnt)




if __name__ == "__main__":
    main()