Sparse Table : Range GCD Query

Hello Everyone,

I hope you have gone through the “Sparse Table” before coming here. It’s really advisable to completely read part 1, then only continue with part 2.

Link: Sparse Table

Now,

Example Problem 2 : Range GCD Query

We have an array arr[0 . . . n-1]. We need to find the greatest common divisor in the range L and R where 0 <= L <= R <= n-1. Consider a situation when there are many range queries
Examples:

Input : arr[] = {2, 3, 5, 4, 6, 8} queries[] = {(0, 2), (3, 5), (2, 3)} Output : 1 2 1

We use below properties of GCD:

  • GCD function is associative [ GCD(a, b, c) = GCD(GCD(a, b), c) = GCD(a, GCD(b, c))], we can compute GCD of a range using GCDs of subranges.
  • If we take GCD of an overlapping range more than once, then it does not change answer. For example GCD(a, b, c) = GCD(GCD(a, b), GCD(b, c)). Therefore like minimum range query problem, we need to do only one comparison to find GCD of given range.

We build a sparse table using the same logic as above. After building the sparse table, we can find all GCDs by breaking given range in powers of 2 and add GCD of every piece to the current answer.

// C++ program to do range minimum query

// using sparse table

#include <bits/stdc++.h>

using namespace std;

#define MAX 500

// lookup[i][j] is going to store GCD of

// arr[i..j]. Ideally lookup table

// size should not be fixed and should be

// determined using n Log n. It is kept

// constant to keep code simple.

int table[MAX][MAX];

// it builds sparse table.

void buildSparseTable( int arr[], int n)

{

// GCD of single element is element itself

for ( int i = 0; i < n; i++)

table[i][0] = arr[i];

// Build sparse table

for ( int j = 1; j <= n; j++)

for ( int i = 0; i <= n - (1 << j); i++)

table[i][j] = __gcd(table[i][j - 1],

table[i + (1 << (j - 1))][j - 1]);

}

// Returns GCD of arr[L..R]

int query( int L, int R)

{

// Find highest power of 2 that is smaller

// than or equal to count of elements in given

// range.For [2, 10], j = 3

int j = ( int )log2(R - L + 1);

// Compute GCD of last 2^j elements with first

// 2^j elements in range.

// For [2, 10], we find GCD of arr[lookup[0][3]] and

// arr[lookup[3][3]],

return __gcd(table[L][j], table[R - (1 << j) + 1][j]);

}

// Driver program

int main()

{

int a[] = { 7, 2, 3, 0, 5, 10, 3, 12, 18 };

int n = sizeof (a) / sizeof (a[0]);

buildSparseTable(a, n);

cout << query(0, 2) << endl;

cout << query(1, 3) << endl;

cout << query(4, 5) << endl;

return 0;

}

Output

1
1
5