greatest common divisor in an interval

Suppose x and y are two numbers. In this case, x is said to be a divisor of y if y returns a zero remainder when divided by x. The largest divisor occurring in an interval is the divisor of the largest number of elements in the interval.

Problem Statement

Given an interval [a, b]. Find the largest divisor that occurs in the range containing a and b (other than "1"). Returns 1 if all divisors occur the same number of times.

Example 1

Input [2, 5]

Output 2

Explanation - Divisors of 2 = {1, 2}, divisors of 3 = {1, 3}, divisors of 4 = {1, 2, 4}, divisors of 5 ={1,5}. 2 is the most frequent divisor.

Example 2

Input [2, 5]

Output 2

Explanation - Divisors of 2 = {1, 2}, divisors of 3 = {1, 3}, divisors of 4 = {1, 2, 4}, divisors of 5 ={1,5}. 2 is the most frequent divisor.

Method 1: Brute force cracking

A brute force way to solve this problem is to find all divisors of all numbers in the interval and store them in a map along with the number of occurrences.

algorithm

Process divisor (num)

• For i = 1 to n1/2 1

• If num%i == 0

• If num/i == i

• If i is not in the map, insert (i, 1)

• Otherwise mapping[i]

• other

• If i is not in the map, insert (i, 1)

• Otherwise mapping[i]

• If num/i is not in the map, insert (num/i, 1)

• Other maps[num/i]

Process maxDivisors (a, b)

• For n = a to b

• Divisor (n)

• map.erase(1)

• Divisor = 1, count = int_min

• For each element in the map

• if it.value > count

• count = it.value

• Divisor = it.key

Example: C implementation

In the following program, we find the divisors of each number in the divisors() function and the largest occurring divisor in the maxdivisor() function.

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

// map storing occurrence of each divisor
unordered_map<int, int> occ;

// function to find all the divisors of a number and store it in map
void divisors(int num){
   for (int i = 1; i <= (sqrt(num) + 1); i++)    {
   
      // checking if i is divisor of num
      if (num % i == 0)        {
      
         // checking if num has identical divisors i.e. if i*i == num
         // if identical divisors then save only one
         if (num / i == i) {
            if (occ.find(i) == occ.end()) {
               occ.insert(make_pair(i, 1));
            }
            else{
               occ[i]++;
            }
         }
         else{
         
            // saving divisor i
            if (occ.find(i) == occ.end()) {
               occ.insert(make_pair(i, 1));
            }
            else{
               occ[i]++;
            }
            
            // saving the divisor of num corresponding to i
            if (occ.find(num / i) == occ.end()) {
               occ.insert(make_pair(num / i, 1));
            }
            else{
               occ[num / i]++;
            }
         }
      }
   }
}

// function to find maximum occurring divisor in an interval
int maxDivisor(int a, int b){
   for (int n = a; n <= b; n++){
      divisors(n);
   }
   
   // deleting all occurrences of 1 as 1 is not to be returned until the interval is [1,1]
   occ.erase(1);
   
   // divisor set as 1 for edge case scenario when interval is [1,1]
   int div = 1, cnt = INT_MIN;
   for (auto it = occ.begin(); it != occ.end(); it++) {
      if (it->second > cnt) {
         cnt = it->second;
         div = it->first;
      }
   }
   return div;
}
int main(){
   int a = 4, b = 7;
   cout << "For the interval [" << a << ", " << b << "] maximum occurring divisor = ";
   cout << maxDivisor(a, b);
   return 0;
}

Output

For the interval [4, 7] maximum occurring divisor = 2

Time complexity - O(n3/2), because for each number in the interval, to find the divisor, a loop of complexity O(n1/2) is performed.

Space complexity - O(n), map space.

Method 2

The above method can be further optimized by reducing the time to fill the map with each occurrence of the divisor. Instead of finding the divisor of each number, you can learn the occurrence of each divisor in the interval by calculating the lower and upper bounds of the interval.

Let us take the interval [2, 5] as an example.

The set of possible divisors is from 1 to 5. Therefore, 1 = 5/1 - 2/1 1 = 4 occurs. It appears that 2 = 5/2 - 2/2 1 = 2. It appears that 3 = 5/3 - 2/3 = 1. It appears that 4 = 5/4 - 2/4 = 1. It appears that 5 = 5/5 - 2/5 = 1.

The above can be formalized as,

If lower bound% divisor == 0 then occ = upper bound/divisor - lower bound/divisor 1

Others occ = upper bound/divisor - lower bound/divisor

algorithm

Process maxDivisor (a, b)

• For i = 2 to b

• If a%i == 0

• Number of times = b/i - a/i 1

• other

• Number of times = b/i - a/i

• map.insert(i, times)

• Divisor = 1, count = int_min

• For each element in the map

• if it.value > count

• count = it.value

• Divisor = it.key

Example: C implementation

In the following program, instead of finding the divisors of a number in reverse order, we find for each divisor how many multiples it has in the interval.

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

// function to find maximum occurring divisor in an interval
int maxDivisor(int a, int b){

   // map used to store occurrences of divisors
   unordered_map<int, int> occ;
   for (int i = 2; i <= b; i++){
      int times;
      if (a % i == 0){
         times = (b / i) - (a / i) + 1;
      }
      else{
         times = (b / i) - (a / i);
      }
      occ.insert(make_pair(i, times));
   }

   // divisor set as 1 for edge case scenario when interval is [1,1]
   int div = 1, cnt = INT_MIN;
   for (auto it = occ.begin(); it != occ.end(); it++){
      if (it->second > cnt){
         cnt = it->second;
         div = it->first;
      }
   }
   return div;
}
int main(){
   int a = 1, b = 10;
   cout << "For the interval [" << a << ", " << b << "] maximum occurring divisor = ";
   cout << maxDivisor(a, b);
   return 0;
}

Output

For the interval [1, 10] maximum occurring divisor = 2

Method 3

A very simple solution to this problem is shown below,

In any interval of size > 1, half the numbers (every even number) will have 2 as the divisor.

So it can be used as follows.

algorithm

Process maxDivisors (a, b)

• if a == b

• ans = a

• other

• ans = 2

Example: C implementation

In the following program, we implement the observation that every even number has 2 as a divisor.

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

// function to find the maximum occurring divisor in an interval
int maxDivisor(int a, int b){
   if (a == b){
      return a;
   } else {
      return 2;
   }
}
int main(){
   int a = 1, b = 10;
   cout << "For the interval [" << a << ", " << b << "] maximum occurring divisor = ";
   cout << maxDivisor(a, b);
   return 0;
}

Output

For the interval [1, 10] maximum occurring divisor = 2

in conclusion

In short, in order to find the largest divisor in an interval, we can use the above method, the time range is from O(n3/2) to O(1), and the space range is from O(n) to O(1).

The above is the detailed content of greatest common divisor in an interval. For more information, please follow other related articles on the PHP Chinese website!