Range GCD Query Using Sparse Table

Brute Force Approach

The naive approach is to traverse the whole subarray and calculate the gcd of all the elements in that subarray. This approach takes O(N*Q) as there are ‘Q’ queries, and all the elements of the f subarray are traversed in each query. This approach is not efficient when the number of queries is huge.

Implementation in C++

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

long long arr[100005];

long long gcd(long long m, long long n)
{
    if (n == 0)
        return m;
    else
        return gcd(n, m % n);
}

int main()
{
    long long t;
    cout<<"Enter number of testcases"<<endl;
    cin >> t; 

    while (t--) {
        long long N, q;
        cout<<"Enter number of elements"<<endl;
        cin>>N;
        cout<<"Enter number of queries"<<endl;
        cin>>q;
   // Take the input of elements and queries
        cout << "Enter elements: ";
        for (long long i = 1; i <= N; i++)
            cin >> arr[i];

        cout << "Enter queries: ";
        while (q--) {
            long long l, r;
            cin >> l >> r;
            Long long res = 0;
        //The traversal of array takes place from 1 to L-1 and N to R+1    

            for (long long i = 1; i < l; i++)
                res = gcd(res, arr[i]);
           
            for (long long i = N; i > r; i--)
                res = gcd(res, arr[i]);
            cout << "The result is ";
            cout << res <<endl;
        }
    }
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Explanation

If the query demands the answers from index 0 to 2 and the array in the input is 3,4,5,7,2, the program finds the gcd(3,4,5) which is 1.

Output

Complexity Analysis

Time Complexity

The time complexity of brute force will be O(N * Q), where ‘N’ is the size of the array ‘ARR’ and ‘Q’ is the number of queries.

Space Complexity

It will perform the operation in O(N), where ‘N’ is the size of the array ‘ARR.’

This proves to be a slow approach when large queries are involved and gives Time Limit Exceeded. We have another approach based on the sparse table. Before moving further, let's discuss what a spare table is.

Sparse Table(Optimal Approach)

Sparse table is the 2-dimensional array say, SPARSE[N][16] where SPARSE[i][j] stores the result from ith index to (i + 2 ^ j )the index. Creating a sparse table takes O(N*log(M)), where ‘M’ is the maximum element in the array. We need to fill each bit of number that takes log(M) time. Hence there are total ‘N’ elements, so the total time complexity of creating the sparse table is O(N * log(M)) time. For any query, say {L, R}, find the highest power of 2, say P, which is less than (R - L). GCD of SPARSE[L][P] and SPARSE[R - P +1][P]. In this case, the time complexity for processing the query is O(1).

Intuition: The interval of (l,r) gets broken down into smaller intervals of power 2. We tend to compute the GCD of all these intervals and recombine it together. This is the basic intuition in the sparse table.

Algorithm

• Define a function buildSparseTable():
  • Function details:
    • Takes ‘ARR,’ ‘N’ and ‘SPARSE’ as a parameter.
  • Working: 
    • Iterate loop from i = 0 to i < N:
      • SPARSE[i][0] = arr[i]
    • Iterate loop from j = 0 to 16:
      • Iterate another loop from i = 0 to i < N:
      • SPARSE[i][j] = gcd of SPARSE[i][j-1] and SPARSE[i + (1 << (j - 1))][j - 1]).
• Define a function QUERY():
  • Create variable j = log2(R - L + 1).
  • Return gcd of SPARSE[L][j] and SPARSE[i + (1 << (j - 1))][j - 1].
• Call the above function for each query.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
 
/* Define Function to build sparse table */
void buildSparseTable(vector<int> &arr, int n, vector<vector<int>> &sparse)
{
    for (int i = 0; i < n; i++)
        sparse[i][0] = arr[i];
 
    /* Build sparse table*/
    for (int m = 1; m < 16; m++)
        for (int i = 0; i <= n - (1 << m); i++)
 
            /* Updating the value of gcd. */
            sparse[i][m] = __gcd(sparse[i][m - 1],
                                 sparse[i + (1 << (m - 1))][m - 1]);
}
 
/* Query Processed */
int query(int L, int R, vector<vector<int>> &sparse)
{
    /* The maximum power of range that is less than 2 */
    int m = (int)log2(R - L + 1);
    return __gcd(sparse[L][m], sparse[R - (1 << m) + 1][m]);
}
 
int main()
{
 
    /* Taking the number of elements in a vector as an input. */
    int n;
    cout<<"Number of elements"<<endl;
    cin >> n;
 
    /* Taking an array as an input. */
    vector<int> arr(n);
    cout<<"Enter Elements"<<endl;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
 
    /* Creating two dimensional array as an input. */
    vector<vector<int>> sparse(n, vector<int>(16));
    int q;
    buildSparseTable(arr, n, sparse);
    cout<<"Enter Number of queries"<<endl;
    cin >> q;
    while (q--)
    {
        int l, r;
        cout<<"Enter Queries"<<endl;
        cin >> l >> r;
 
        /* Function call */
        cout<<"The result is  ";
        cout << query(l, r, sparse) << endl;
    }
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Complexity Analysis

Time Complexity

O(N * log(M)), where ‘N’ is the size of the array ‘ARR’ and ‘M’ is the maximum element in the array. O(1) to process any query as discussed above.

Space Complexity

O(N * log(M)), where ‘N’ is the size of the array ‘ARR’ and ‘M’ is the maximum element in the array. As creating vector of size N * log(M) takes O(N * log(M)) extra space.

Also see,  Rabin Karp Algorithm

Frequently Asked Questions

What is a sparse table?

Sparse table is the 2-dimensional array say, SPARSE[N][16] where SPARSE[i][j] stores the result from ith index to (i + 2 ^ j )th index.

What is the time complexity of creating a sparse array?

Creating a sparse table takes O(N*log(M)) where ‘M’ is the maximum element in the array and N is the size of the array.

What is the full form of GCD, and what is its other name?

GCD stands for the greatest common factor. The other name of GCD is HCF, which is the highest common factor.

Give the relationship between the GCD and the LCM of two numbers, a and b.

The product of the GCD and LCM of two numbers is equal to the product of the two numbers itself.

Can a sparse table be used on dynamic elements?

No, it only works when the elements are not changing or static.

Conclusion

In this blog, we learned the problem Range gcd query. We have discussed the brute-force approach. After that, we discussed solving the problem using the sparse table in O(1) searching time.

Recommended Readings:

• Binary Search
• Dynamic Programming
• Book Allocation Problem
• Plates Between Candles
• Find the subarray with t
   

Therefore learning never stops, and there is a lot more to learn.

So head to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Coding!