1.
Introduction
1.1.
Problem Statement
1.2.
Sample Example
2.
Approach
2.1.
Implementation in C++
2.1.1.
Complexity Analysis
3.
4.
Key takeaways
Last Updated: Mar 27, 2024

# 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

Q1. What is a heap?

Ans. Heap is a tree-based data structure. More precisely, it is a particular case of a balanced binary tree that stores the tree’s nodes in a specific order.

Q2. What is a priority queue?

Ans. The priority queue is similar to the regular queue. The only difference is that the priority queue stores elements in a particular order of priority where the top element has the highest priority.

Q3. What is a queue?

Ans. The queue is also a linear data structure, and it is based on the principle of FIFO (First in First Out)

## Key takeaways

In this article, we discussed the problem find maximum divisors in a range. We have discussed its approach and its space and time complexities. We hope you have gained a better understanding of the solution to this problem and, now it is your responsibility to solve the problem and try some new and different approaches to this problem.

Until then, Keep Learning and Keep Coding.

Live masterclass