Table of Contents
Problem Statement
The problem ‘GCDs of given index ranges in an array” states that you are given an integer array and some range queries. The problem statement asks to find out the Greatest Common Divisor of the sub-array so formed within the range.
Example
arr[] = {10, 5, 18, 9, 24}
Query: {(0, 1), (2, 4), (0, 3)}5 3 1
Explanation
The greatest common divisor of the first query ranges from 0 and 1, so the GCD of 10 and 5 is 5.
The GCD of the second query ranges from 2 and 4, so the GCD of 18, 9, 24 is 3.
The greatest common divisor of the first query ranges from 0 and 3, so the GCD is 1.
Algorithm
- Start with a section arr[0] to arr[n-1], and continue partitioning into equal parts. Each time we partition the current section into equal parts. Then recursively call for the two parts. And for each such segment, we store the greatest common divisor value in a segment tree.
- Build a segment tree which will be filled aside from the last level.
- Each node of the segment tree stores the GCD of all the elements corresponding to a certain range.
- For finding out the query of GCD, if the node’s range will be in startQuery and endQuery, then return the value in node.
- Else if, the range is not valid, then return the null or -1.
- Else return the recursive call of GCD function.
Explanation
We are given an integer array and q number of queries. Each query contains the range as startQuery and endQuery. Within this range, we have to find out the greatest common divisor of all the numbers that satisfy the given range. For this we are going to build the segment tree, we will be solving the queries in the efficient time of log N*log n.
We will start building the segment tree from the 0th position of the array to the last position of the array, and the important part is dividing the array into two halves. We will continue dividing it until the length of the array is one, then in the next step recursively call the function to both of the parts of the array. Here we will be storing the greatest common divisor in a node of a tree. All the internal nodes will not be null, except leaf nodes. The tree so formed will be a binary tree. Because there are two parts of the array at every node level. But compared to a binary tree, where the nodes represent a range instead of a single number.
For each query of the Greatest Common Divisor given, we check if the range of the node is within the range of startQuery and the endQuery. Then we will return the value in the node of the segment tree. We also have a second condition where if the range of the node is outside of the range startQuery range and the endQuery range. Then we will return the -1 or a null value. And to make the function continuously progressive, we will recursively call the node’s both child, left and right. Then find out the greatest common divisor of the returned value from the nodes.
Code
C++ code to find GCDs of given index ranges in an array
#include<iostream>
#include<math.h>
using namespace std;
int *segTree;
int gcd(int a, int b)
{
if (a < b)
{
int temp = b;
b = a;
a = temp;
}
if (b==0)
return a;
return gcd(b,a%b);
}
int getGCDOfNumber(int startNode, int endNode, int startQuery, int endQuery, int si)
{
if (startNode>endQuery || endNode < startQuery)
return 0;
if (startQuery<=startNode && endQuery>=endNode)
return segTree[si];
int mid = startNode+(endNode-startNode)/2;
return gcd(getGCDOfNumber(startNode, mid, startQuery, endQuery, si*2+1),
getGCDOfNumber(mid+1, endNode, startQuery, endQuery, si*2+2));
}
int findRangeGcd(int startNode, int endNode, int arr[],int n)
{
if (startNode<0 || endNode > n-1 || startNode>endNode)
{
cout << "Invalid Arguments" << "\n";
return -1;
}
return getGCDOfNumber(0, n-1, startNode, endNode, 0);
}
int buildSegementTree(int arr[], int startNode, int endNode, int si)
{
if (startNode==endNode)
{
segTree[si] = arr[startNode];
return segTree[si];
}
int mid = startNode+(endNode-startNode)/2;
segTree[si] = gcd(buildSegementTree(arr, startNode, mid, si*2+1),
buildSegementTree(arr, mid+1, endNode, si*2+2));
return segTree[si];
}
int *constructendNodegmentTree(int arr[], int n)
{
int height = (int)(ceil(log2(n)));
int size = 2*(int)pow(2, height)-1;
segTree = new int[size];
buildSegementTree(arr, 0, n-1, 0);
return segTree;
}
int main()
{
int a[] = {10, 5, 18, 9, 24};
int n = sizeof(a)/sizeof(a[0]);
constructendNodegmentTree(a, n);
int l = 0, r = 1;
cout << "Greatest Common Divisor is: ";
cout << findRangeGcd(l, r, a, n) << "\n";
l = 2;
r = 4;
cout << "Greatest Common Divisor is: ";
cout << findRangeGcd(l, r, a, n) << "\n";
l = 0;
r = 3;
cout << "Greatest Common Divisor is: ";
cout << findRangeGcd(l, r, a, n) << "\n";
return 0;
}
Greatest Common Divisor is: 5 Greatest Common Divisor is: 3 Greatest Common Divisor is: 1
Java code to find GCDs of given index ranges in an array
import java.io.*;
public class GCDOfNumber
{
private static int[] segTree;
public static int[] buildSegmentTree(int[] arr)
{
int height = (int)Math.ceil(Math.log(arr.length)/Math.log(2));
int size = 2*(int)Math.pow(2, height)-1;
segTree = new int[size];
SegementTree(arr, 0, arr.length-1, 0);
return segTree;
}
public static int SegementTree(int[] arr, int startNode,
int endNode, int si)
{
if (startNode==endNode)
{
segTree[si] = arr[startNode];
return segTree[si];
}
int mid = startNode+(endNode-startNode)/2;
segTree[si] = gcd(SegementTree(arr, startNode, mid, si*2+1),
SegementTree(arr, mid+1, endNode, si*2+2));
return segTree[si];
}
private static int gcd(int a, int b)
{
if (a < b)
{
int temp = b;
b = a;
a = temp;
}
if (b==0)
return a;
return gcd(b,a%b);
}
public static int findRangeGcd(int startNode, int endNode, int[] arr)
{
int n = arr.length;
if (startNode<0 || endNode > n-1 || startNode>endNode)
throw new IllegalArgumentException("Invalid arguments");
return findGcd(0, n-1, startNode, endNode, 0);
}
public static int findGcd(int startNode, int endNode, int startQuery, int endQuery, int si)
{
if (startNode>endQuery || endNode < startQuery)
return 0;
if (startQuery<=startNode && endQuery>=endNode)
return segTree[si];
int mid = startNode+(endNode-startNode)/2;
return gcd(findGcd(startNode, mid, startQuery, endQuery, si*2+1),
findGcd(mid+1, endNode, startQuery, endQuery, si*2+2));
}
public static void main(String[] args)throws IOException
{
int[] a = {10, 5, 18, 9, 24};
buildSegmentTree(a);
int l = 0, r = 1;
System.out.println("Greatest Common Divisor is: "+findRangeGcd(l, r, a));
l = 2;
r = 4;
System.out.println("Greatest Common Divisor is: "+findRangeGcd(l, r, a));
l = 0;
r = 3;
System.out.println("Greatest Common Divisor is: "+findRangeGcd(l, r, a));
}
}
Greatest Common Divisor is: 5 Greatest Common Divisor is: 3 Greatest Common Divisor is: 1
Complexity Analysis
Time Complexity
O(n log n + log n * log(min(a, b))) where “n” is the number of nodes and “a” and “b” are nodes whose GCD is calculated during the merge operation. O(n logn) time is spent for construction and O(log n) to answer each query and then O(log(min(a,b))) time for finding gcd.
Space Complexity
O(n) where “n” is the nodes. Space is spent in the construction of a segment tree.