Maximum Divisors in a Range

Introduction

This blog will discuss the solution to the problem of finding the maximum divisor of two integers in a range.

Problem Statement

We are given two numbers, a and b. After that, we will be given q queries containing two integers, l and r. Let us define a set S with common divisors of a and b, which lie in the l and r. We need to find the maximum element in this set S, and if there is no element in this set, we need to print -1. So before we deep dive into the answer, we should look at an example to understand the problem better. 

Sample Example

Input:

8 12

4

2 4

3 6

2 3

12 13

Output: 

For 8 and 12, the gcd is four, and its divisors are [1, 2, 4], so the common divisors are [1, 2, 4]

In the range [2, 4], the max common divisor is 4.

In the range [3, 6], the max common divisor is 4.

In the range [2, 3], the max common divisor is 2.

In the range [12, 13], there is no common divisor between 12 and 13 so we print -1.

Approach

1. To solve this problem, of finding maximum divisors in a range. We will first find out the gcd of given numbers a,b.
2. We will find the divisors of gcd(a,b) and we will store them in an array.
3. Next, we will sort the array so that we can apply binary search on the array.
4. So will find maximum common divisor in the range [l, r] by searching for a lower bound of r and upper bound for l.

The upper bound of any number x finds the position of the immediate greater element present in the array but the array should be in increasing order.

The lower bound of any number x finds the position of the immediate smaller element present in the array but the array should be in increasing order.

1. If both lower and upper bound are the same, there is no common divisor in the range [l, r].
2. If both lower and upper bound are not the same, we will check for the previous element of the upper bound of r since the upper bound will be greater than r, but its previous element will not be greater than r.

Must Read Lower Bound in C++

Implementation in C++

// C++ code for Maximum Divisors in a Range
#include <bits/stdc++.h>
using namespace std;

// to find the lower bound of a number in an array
int lowerBound(int a[], int start, int end, int key)
{
    if (start > end)
        return end;
    int mid = (start + end) / 2;
    if (a[mid] == key)
        return mid;
    else if (a[mid] > key)
        return lowerBound(a, start, mid - 1, key);
    else
        return lowerBound(a, mid + 1, end, key);
}

// to find the upper bound of a number in an array
int upperBound(int a[], int start, int end, int key)
{
    if (start > end)
        return start;
    int mid = (start + end) / 2;
    if (a[mid] == key)
        return upperBound(a, mid + 1, end, key);
    else if (a[mid] > key)
        return upperBound(a, start, mid - 1, key);
    else
        return upperBound(a, mid + 1, end, key);
}


// driver code for  Maximum Divisors in a Range
int main()
{
    int a, b;
    cin >> a >> b;

    // inbuilt function to find gcd of two numbers
    int g = __gcd(a,b);

    //  to store the divisors of gcd
    int divisors[1000000] = {0}, count = 0;
    for (int i = 1; i <= g; i++)
        if (g % i == 0)
            divisors[count++] = i;

    int n;
    cin >> n;
    while (n--)
    {

        int low, high;
        cin >> low >> high;
      
        // to store the lower bound index of a number in an array
        int id1 = lowerBound(divisors, 0, count - 1, low);
      
        // to store the upper bound index of a number in an array
        int id2 = upperBound(divisors, 0, count - 1, high);

        if (low > divisors[id1] || count == 0)
            id1++;

        // to store the difference of both the indexes    
        int diff = id2 - id1;

        // if zero then print -1
        if (diff == 0)
            cout << "-1\n";
        // else print the divisor
        else
            cout << divisors[id2 - 1] << endl;
    }
}

Output:

Input:    
6 8
2
2 4
3 5
Output:  
2
-1

Complexity Analysis

Time Complexity: O(max(A,B)+(N(log_{2}P + log_{2}P))

Space Complexity: O(min(A, B))

Check out this problem - Next Smaller Element