Getting GCD of all numbers of an array except elements in a given range-CodePudding

I have written a program to calculate GCD of all numbers of an array except elements in a given range. Given an integer array and a q number of queries. Each query contains the number left and right. I need to find out the greatest common divisor of all the integers except within the given range of the query.

arr = [2, 6, 9]
query = [(0, 0), (1, 1), (1, 2)]

My Output: [3, 1, 1]
Expected Output: [3, 1, 2]

Code:

def computeGCD(a, b):
    if b == 0:
        return a
    else:
        return computeGCD(b, a%b)
    
def getGCD(arr, query):
    n = len(arr)
    left_gcd = right_gcd = [0 for i in range(n)]
    
    left_gcd[0] = arr[0]
    for i in range(1, n):
        left_gcd[i] = computeGCD(left_gcd[i-1], arr[i])
    print(left_gcd)
    
    right_gcd[n-1] = arr[n-1]
    for i in range(n-2, -1, -1):
        right_gcd[i] = computeGCD(right_gcd[i 1], arr[i])
    print(right_gcd)
    
    res = []
    for q in query:
        if q[0] == 0:
            gcd_outside_q = right_gcd[q[1] 1]
        elif q[1] == n-1:
            gcd_outside_q = left_gcd[q[0]-1]
        else:
            gcd_outside_q = computeGCD(left_gcd[q[0]-1], right_gcd[q[1] 1])
        res.append(gcd_outside_q)
    return res

getGCD(arr, query)

Please let me know what I am missing.

CodePudding user response：

The problem is with line:

left_gcd = right_gcd = [0 for i in range(n)]

This way, left_gcd and right_gcd refer to the same list. If you change one of them, the other changes too. You can check this by printing left_gcd after the right_gcd block:

...
    left_gcd[0] = arr[0]
    for i in range(1, n):
        left_gcd[i] = computeGCD(left_gcd[i-1], arr[i])
    print(left_gcd)

    right_gcd[n-1] = arr[n-1]
    for i in range(n-2, -1, -1):
        right_gcd[i] = computeGCD(right_gcd[i 1], arr[i])
    print(right_gcd)
    print(left_gcd)
...

The output is:

[2, 2, 1]
[1, 3, 9]
[1, 3, 9]

An easy way to fix this is to change it like so:

def getGCD(arr, query):
    n = len(arr)
    left_gcd = [0 for i in range(n)]
    right_gcd = [0 for i in range(n)]
...