Home » Interview coding problems/challenges

GCD Queries - Greatest Common Divisor Problem

Here, we are going to find the solution of GCD Queries - Greatest Common Divisor Problem using various approaches.
Submitted by Divyansh Jaipuriyar, on April 13, 2021

Description: The problem has been asked in competitive programming platforms and the concept has been featured in interview/coding rounds of many tech companies.

Problem Statement: You are given an array A of integers of size N. You will be given Q queries where each query is represented by two integers L, R. You have to find the gcd(Greatest Common Divisor) of the array after excluding the part from range L to R inclusive (1 Based indexing). You are guaranteed that after excluding the part of the array remaining array is non-empty.

Problem Description: The problem basically wants you to utilize all elements from index 1 to L-1 and then from index R+1 to N and find their gcd also need to exclude all elements of range[L, R] if we are considering 1 based indexing for solving the given problem and if 0 based indexing then need to utilize elements from [0, L-2] and [R, n-1] that excludes elements from the range[L-1, R-1]. 

Input: The first line of input contains an integer T denoting number of test cases. For each test case, the first line will contain two space-separated integers N, Q. The next line contains N space-separated integers denoting array A. For next Q lines, each line will contain a query denoted by two space-separated integers L, R.

Output: For each query, print a single integer representing the answer to that query.

Examples:

Input:
T = 1
N = 3, Q = 3
[2,6,9]
L R	
1,1
2,2
2,2

Output:
3
1 
2

Explanation: 
For the first query, the remaining part of the array will be (6, 9).
So the answer is 3. 
For the second query, the remaining part of the array will be (2, 9).
So answer is 1.
For the third query, the remaining part of the array will be (2).
So the answer is 2.

Solution Approach

(1) Brute Force Approach:

In this approach, we will calculate the gcd of the array from index 1 to L-1 and from index R+1 to n. Since we need to skip the range [L, R] for each query.

To calculate gcd we will use the Euclid algorithm as it is very fast as compared to the brute force gcd method.

The time complexity for the Euclid algorithm is log(n).

Pseudo Code:

//Euclid gcd function.
int gcd(int a,int b)
{	
    //if b==0 then return a.
    if(b==0)
        return a
    else
        return gcd(b,a%b)
}

The time complexity for the brute force approach in the worst case is O(N) for each query therefore for Q queries overall time complexity reaches to (N*Q).

Program to illustrate the working of Brute force approach

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
//declare array for entire problem.
ll arr[100005];

//declare euclid gcd function.
ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

int main()
{
    ll t;

    cout << "Enter number of test cases: ";
    //take input.
    cin >> t;

    while (t--) {
        //take input size of array and queries.
        ll n, q;
        cout << "Enter size of array and queries count: ";
        cin >> n >> q;

        //call solve function.
        cout << "Enter elements: ";
        for (ll i = 1; i <= n; i++)
            cin >> arr[i];

        //process queries.
        cout << "Enter queries: ";
        while (q--) {
            ll l, r;
            //take input L and R.
            cin >> l >> r;
            //initialise temporary ans=0 as 0 doesn't effect our answer.
            ll ans = 0;
            //traverse through the array from 1 to L-1
            for (ll i = 1; i < l; i++)
                ans = gcd(ans, arr[i]);
            //traverse through the array from n to R+1.
            for (ll i = n; i > r; i--)
                ans = gcd(ans, arr[i]);
            //use pref[L-1] to get gcd of numbers berfore L and use
            //suf[R+1] to get gcd of number from n to R+1.
            cout << "Final Gcd: ";
            cout << ans << "\n";
        }
    }

    return 0;
}

Output

Enter number of test cases: 3
Enter size of array and queries count: 4 1
Enter elements: 1 2 3 4
Enter queries: 2 3
Final Gcd: 1
Enter size of array and queries count: 5 1
Enter elements: 2 4 6 8 10
Enter queries: 3 4
Final Gcd: 2
Enter size of array and queries count: 3 1
Enter elements: 10 20 30
Enter queries: 2 2
Final Gcd: 10

(2) Prefix and Suffix Array Approach:

In this approach, we will optimize the time complexity with the help of prefix and suffix array.

1. We will create two array prefix and suffix which will store the gcd of elements from index (i,i+1,i+2,....N) and from index(N,N-1,N-2,.....1) respectively.
2. For each query [L, R], we will take the gcd of pref[L-1] and suf[R+1] since they are storing the prefix and suffix gcd in them.
3. Since we need to avoid [L, R] range elements in our final gcd so for final result we take prefix[L-1] gcd with suffix[R+1] since prefix is storing gcd with index [0,n) and suffix is storing gcd with index(n,0].

Time complexity for the above case reduces from O(N*Q) to O(N) since for each query it takes O(1) time find gcd from [0,L) and from [R+1,n).

Space Complexity: O(n)

Program to illustrate the working of prefix and suffix array approach

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll arr[100005]; //declare array for entire problem.
ll pre[100005]; //declare pref array which stores gcd of prefixes.
ll suf[100005]; //declare suf array which stores gcd of suf.

//declare euclid gcd function.
ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

//declare solve function which takes array as parameter.
void solve(ll arr[], ll n)
{
    //take input in array arr.
    cout << "Enter elements: ";
    for (ll i = 1; i <= n; i++)
        cin >> arr[i];

    //initialise pref[0]=0 as gcd with 0 doesn't effect
    //the solution and gcd takes two parameter.

    pre[0] = 0;
    //iterate through the array and calculate gcd of prefixes.
    for (ll i = 1; i <= n; i++)
        pre[i] = gcd(pre[i - 1], arr[i]);

    suf[n + 1] = 0; //same as prefix cases.
    //iterate through the suffix array and calculated the suffix gcd.
    for (ll i = n; i >= 1; i--)
        suf[i] = gcd(suf[i + 1], arr[i]);
}

int main()
{
    ll t;

    cout << "Enter number of test cases: ";
    //take input.
    cin >> t;

    while (t--) {
        //take input size of array and queries.
        ll n, q;
        cout << "Enter size of array and queries count: ";
        cin >> n >> q;
        //call solve function.
        solve(arr, n);
        //process queries.
        cout << "Enter queries: ";
        while (q--) {
            ll l, r;
            //take input L and R.
            cin >> l >> r;
            //use pref[L-1] to get gcd of numbers berfore L and use
            //suf[R+1] to get gcd of number from n to R+1.
            cout << "Final Gcd: ";
            cout << gcd(pre[l - 1], suf[r + 1]) << "\n";
        }
    }

    return 0;
}

Output

Enter number of test cases: 1
Enter size of array and queries count: 3 3
Enter elements: 2 6 9
Enter queries: 1 1
Final Gcd: 3
2 2
Final Gcd: 1
2 3
Final Gcd: 2

Problem source: GCD Queries