Find GCDs of given index ranges in an array in Python

From the title given above  lets  try to understand each word .GCD stands for Greatest Common Divisor .GCD=Multiplication of common factors.

 for example 36=2 x 2 x 3 x 3 , 60=2 x 2 x 3 x 5, GCD of 36 and 60 = 2 x 2 x 3 = 12

Arrays are  type of data structures and used as containers to store the items at same time .

Index ranges in python start with 0 to   n-1.

Solution:

GCD OF RANGE USING SEGMENT TREE

I have chosen this method  because it takes minimal time to preprocess and solve the query . By segment tree we can store and use it in further purpose for calculating of  gcd .

Time Complexity: O(N² + Q) preprocessing takes O(N²) time and O(Q) time to answer Q queries.
Auxiliary Space: O(N²)

Array representation of the tree is used to represent Segment Trees i.e., for each node at index i,

• The Left child is at index 2*i+1
• Right child at 2*i+2 and
• the parent is at floor((i-1)/2).

Query states in this way :

Tree will be divided in two halves-left and right. Then we run our query on it if it exceeds the range return 0. if not continue the process until we exceed the range.

SEGMENT TREE

SIMPLE EXAMPLE FOR FINDING OF GCD OF TWO NUMBERS :

# The math module contains the gcd function
import math


#Calculating the gcd of 2 numbers.
x = 32
y = 12
n = min(x,y)


gcd = 0
for i in range(1,n+1):
    if x%i == 0 and y%i == 0:
        gcd = i
        
print(f"The computed GCD of {x} and {y} is {gcd}.")

OUTPUT:

The computed GCD of 32 and 12 is 4.

 

NOW LETS DIG INTO ABOVE SOLUTION IN CODE FORMAT

import math

# To store segment tree
st = []

# A recursive function to get gcd of given
# range of array indexes. The following are parameters for
# this function.
# st --> Pointer to segment tree
# si --> Index of current node in the segment tree.
# Initially 0 is passed as root is always at index 0
# ss & se --> Starting and ending indexes of the segment
#		 represented by current node, i.e., st[index]
# qs & qe --> Starting and ending indexes of query range
def findGcd(ss, se, qs, qe, si):
    if ss > qe or se < qs:
        return 0
    if qs <= ss and qe >= se:
        return st[si]
    mid = ss + (se - ss) // 2
    return math.gcd(findGcd(ss, mid, qs, qe, si * 2 + 1),
                    findGcd(mid + 1, se, qs, qe, si * 2 + 2))

# Finding the gcd of given range
def findRangeGcd(ss, se, arr, n):
    if ss < 0 or se > n - 1 or ss > se:
        print("Invalid Arguments")
        return -1
    return findGcd(0, n - 1, ss, se, 0)

# A recursive function that constructs Segment Tree for
# array[ss..se]. si is index of current node in segment
# tree st
def constructST(arr, ss, se, si):
    if ss == se:
        st[si] = arr[ss]
        return st[si]
    mid = ss + (se - ss) // 2
    st[si] = math.gcd(constructST(arr, ss, mid, si * 2 + 1),
                    constructST(array, mid + 1, se, si * 2 + 2))
    return st[si]

# Function to construct segment tree from given array.
# This function allocates memory for segment tree and
# calls constructSTUtil() to fill the allocated memory
def constructSegmentTree(array, n):
    height = math.ceil(math.log2(n))
    size = 2 * pow(2, height) - 1
    global st
    st = [0] * size
    constructST(array, 0, n - 1, 0)
    return st

# Driver program to test above functions
array = [2, 3, 6, 9, 5]
n = len(array)

# Build segment tree from given array
constructSegmentTree(array, n)

# Starting index of range. These indexes are 0 based.
length = 1

# Last index of range. These indexes are 0 based.
range = 3

print("GCD of the given range is:", findRangeGcd(length, range, a, n))