Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Brute Force Approach
3.1.
Implementation in C++
3.1.1.
Output
4.
Complexity Analysis
4.1.
Time Complexity
4.2.
Space Complexity
5.
Sparse Table(Optimal Approach)
5.1.
Algorithm
5.2.
Implementation in C++
5.2.1.
Output
6.
Complexity Analysis
6.1.
Time Complexity
6.2.
Space Complexity
7.
Frequently Asked Questions
7.1.
What is a sparse table?
7.2.
What is the time complexity of creating a sparse array?
7.3.
What is the full form of GCD, and what is its other name?
7.4.
Give the relationship between the GCD and the LCM of two numbers, a and b.
7.5.
Can a sparse table be used on dynamic elements?
8.
Conclusion
Last Updated: Mar 27, 2024
Medium

Range GCD Query Using Sparse Table

Author Ujjawal Gupta
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

In this blog, we will study the problem range gcd query and tackle it using different ways. Range query problems are a fascinating as well as an essential topic. Range query based-coding problems are widely asked in coding contests and various coding interviews. 

 

Problem Statement

You are given an array ‘ARR’ of size ‘N’ and ‘Q’ queries where each query consists of two integers ‘L’ and ‘R’ (0 <= L <= R <= N). for each query, your task is to find the greatest common divisor (GCD) of subarray starting from L-th index and ending at Rth index. The number of queries may be vast.

Example 

Let, ARR = {3,6,9,4,1,4} and Q = 2. Each query is as follows:

  • L = 1 and R = 2, here the gcd of subarray {6,9} is 3. 
  • L=2 and R = 5, here the gcd of subarray {9,4,1,4} is 1.
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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;
}

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

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;
}

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:

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!

 

Previous article
Range Min Using Sparse Table
Next article
Find median of row-wise sorted matrix
Live masterclass