Maximum Divisor

Last Updated on March 11, 2022 by Ria Pathak

Concepts Used

Segment Trees, GCD

Difficulty Level

Medium

Problem Statement :

Given an array of N elements and Q queries. In each query, two values is given l and r. We have to find a maximum positive integer x where arr[l]%x = arr[l+1]%x =...=arr[r]%x = 0.

See original problem statement here

Solution Approach :

Introduction :

We have to find a number x which completely divides all the elements within a given range. There is a term in mathematics for x, can you guess what is it? For those who has answer GCD they are right. Now our problem breaks down to finding the GCD within a given range.

Idea is to construct a segment tree with the leaf nodes having the array values and intermediate nodes stores the GCD of the current subarray range.

Method 1 (Brute force):

We can calculate the GCD in the given range l to r for every query. This approach will work fine for smaller array sizes and queries, as it takes linear time for finding the gcd of the values for single query. As the size of the input increases this apprach will be huge drawback.

Method 2 (Segment Tree):

As the number of queries and array size is too large for linear search in every query, we will use segment tree to solve this problem.
A Segment Tree is a data structure which allows answering range queries very effectively over a large input. Each query takes logarithmic time. Range queries includes sum over a range, or finding a minimum value over a given range etc. Query be of any type we can use segment trees and modify it accordingly.
Leaf nodes of the tree stores the actual array values and intermediate nodes stores the information of subarrays with is require to solve the problem. Lets say if we have to find a sum between different ranges, so now the intermediate nodes will store the sum of the current subarray. We fill the nodes by recursively calling left and right subtree (dividing into segements), untill there is a single element left, which can be directly assigned the value of the array. Array representation of the tree is used to represent segment tree, where (i*2)+1 represents the left node and (i*2)+2 represents right node, parent will be represented by (i-1)/2 for every index i.
We will construct our tree by starting at the original array and dividing it into two halves (left and right), untill there is a single element left (leaf) which can directly be filled with a[i] for any index i. Now for every range say l to r, we will store the gcd of the current range in the node.
Now that our tree is constructed, we will answer queries (gcd of the given range). The queries can be of 3 types:

1. The range of the tree exactly matches with the query, in this case we will return the value stored in this node.
2. The range either belongs to the left or right node, in this case we will make two recursive calls for left and right subtrees respectively.
3. The range overlaps with two of more ranges, in this case we are forced to go to the lower levels of both the subtrees and find the gcd of the range which fits the current range and finally return the gcd of the values returned by both subtrees.

Algorithm :

construct():

• if the current node is a leaf (subarray contains single element), assign the value directly, (tree[curr]= arr[l]).
• break the tree into two halves by recursively calling for left and right subtree, construct(l,mid) and construct(mid+1,r)
• fill the current node with the gcd of left & right node. (tree[curr] = GCD(LeftSubtree , RightSubtree).

RMQ():

• if range is within the current range, return the value stored in node.
• if current range is outside the boundaries, return -1.
• else return the gcd of left & right subtrees.

Complexity Analysis :

In segment tree, preprocessing time is O(n) and worst time to for range minimum query is equivalent to the height of the tree.
The space complexity is O(n) to store the segment tree.

Solutions:

#include <stdio.h>
#include<math.h>
#include<stdlib.h>

int *st; 

int gcd(int a, int b) 
{ 
    if (b == 0) 
        return a; 
    return gcd(b, a % b);  
} 


int findGcd(int ss, int se, int qs, int qe, int si) 
{ 
    if (ss>qe || se < qs) 
        return 0; 
    if (qs<=ss && qe>=se) 
        return st[si]; 
    int mid = ss+(se-ss)/2; 
    return gcd(findGcd(ss, mid, qs, qe, si*2+1),findGcd(mid+1, se, qs, qe, si*2+2)); 
} 


int findRangeGcd(int ss, int se, int arr[],int n) 
{ 
    if (ss<0 || se > n-1 || ss>se) 
    { 
        return -1; 
    } 
    return findGcd(0, n-1, ss, se, 0); 
} 

int constructST(int arr[], int ss, int se, int si) 
{ 
    if (ss==se) 
    { 
        st[si] = arr[ss]; 
        return st[si]; 
    } 
    int mid = ss+(se-ss)/2; 
    st[si] = gcd(constructST(arr, ss, mid, si*2+1), 
                constructST(arr, mid+1, se, si*2+2)); 
    return st[si]; 
} 


int *constructSegmentTree(int arr[], int n) 
{ 
int height = (int)(ceil(log2(n))); 
int size = 2*(int)pow(2, height)-1; 
st = (int *)malloc(sizeof(int)*size);
constructST(arr, 0, n-1, 0); 
return st; 
} 


int main() 
{ 
  int t;
  scanf("%d",&t);
  while(t--)
  {
      int n;
      scanf("%d",&n);
      int arr[n];
      for(int i=0;i<n;i++)
       scanf("%d",&arr[i]);

      constructSegmentTree(arr, n); 

      int q;
      scanf("%d",&q);
      while(q--)
      {
        int l,r;
        scanf("%d %d",&l,&r);
         l-=1;
         r -=1;
        printf("%d\n",findRangeGcd(l, r, arr, n)); 
      }
  }

    return 0; 
} 

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


int *st; 

int gcd(int a, int b) 
{ 
    if (b == 0) 
        return a; 
    return gcd(b, a % b);  
} 


int findGcd(int ss, int se, int qs, int qe, int si) 
{ 
    if (ss>qe || se < qs) 
        return 0; 
    if (qs<=ss && qe>=se) 
        return st[si]; 
    int mid = ss+(se-ss)/2; 
    return gcd(findGcd(ss, mid, qs, qe, si*2+1),findGcd(mid+1, se, qs, qe, si*2+2)); 
} 


int findRangeGcd(int ss, int se, int arr[],int n) 
{ 
    if (ss<0 || se > n-1 || ss>se) 
    { 
        return -1; 
    } 
    return findGcd(0, n-1, ss, se, 0); 
} 


int constructST(int arr[], int ss, int se, int si) 
{ 
    if (ss==se) 
    { 
        st[si] = arr[ss]; 
        return st[si]; 
    } 
    int mid = ss+(se-ss)/2; 
    st[si] = gcd(constructST(arr, ss, mid, si*2+1),constructST(arr, mid+1, se, si*2+2)); 
    return st[si]; 
} 


int *constructSegmentTree(int arr[], int n) 
{ 
int height = (int)(ceil(log2(n))); 
int size = 2*(int)pow(2, height)-1; 
st = new int[size]; 
constructST(arr, 0, n-1, 0); 
return st; 
} 

int main() 
{ 
  int t;
  cin>>t;
  while(t--)
  {
      int n;
      cin>>n;
      int arr[n];
      for(int i=0;i<n;i++)
       cin>>arr[i];

      constructSegmentTree(arr, n); 

      int q;
      cin>>q;
      while(q--)
      {
        int l,r;
        cin>>l>>r;
         l-=1;
         r -=1;
        cout << findRangeGcd(l, r, arr, n) << "\n"; 
      }
  }

    return 0; 
} 

import java.util.*;
import java.io.*;


public class Main 
{ 
    private static int[] st; // Array to store segment tree 

    public static int[] constructSegmentTree(int[] arr) 
    { 
        int height = (int)Math.ceil(Math.log(arr.length)/Math.log(2)); 
        int size = 2*(int)Math.pow(2, height)-1; 
        st = new int[size]; 
        constructST(arr, 0, arr.length-1, 0); 
        return st; 
    } 

    public static int constructST(int[] arr, int ss, 
                                int se, int si) 
    { 
        if (ss==se) 
        { 
            st[si] = arr[ss]; 
            return st[si]; 
        } 
        int mid = ss+(se-ss)/2; 
        st[si] = gcd(constructST(arr, ss, mid, si*2+1), 
                    constructST(arr, mid+1, se, si*2+2)); 
        return st[si]; 
    } 

    // Function to find gcd of 2 numbers. 
    private static int gcd(int a, int b) 
    { 
        if (a < b) 
        { 
            // If b greater than a swap a and b 
            int temp = b; 
            b = a; 
            a = temp; 
        } 

        if (b==0) 
            return a; 
        return gcd(b,a%b); 
    } 

    public static int findRangeGcd(int ss, int se, int[] arr) 
    { 
        int n = arr.length; 

        if (ss<0 || se > n-1 || ss>se) 
            throw new IllegalArgumentException("Invalid arguments"); 

        return findGcd(0, n-1, ss, se, 0); 
    } 

    public static int findGcd(int ss, int se, int qs, int qe, int si) 
    { 
        if (ss>qe || se < qs) 
            return 0; 

        if (qs<=ss && qe>=se) 
            return st[si]; 

        int mid = ss+(se-ss)/2; 

        return gcd(findGcd(ss, mid, qs, qe, si*2+1), 
                findGcd(mid+1, se, qs, qe, si*2+2)); 
    } 

    // Driver Code 
    public static void main(String[] args)throws IOException 
    { 
      Scanner sc = new Scanner(System.in);
      int t = sc.nextInt();
      while(t-->0)
      {
        int n = sc.nextInt();
          int[] a = new int[n];
          for(int i=0;i<n;i++)
           a[i] = sc.nextInt();

          constructSegmentTree(a); 
      int q = sc.nextInt();
      while(q-->0)
      {
            int l = sc.nextInt()-1; // Starting index of range. 
            int r = sc.nextInt()-1; //Last index of range. 
            System.out.println(findRangeGcd(l, r, a)); 
      }
      }
    } 
}

[forminator_quiz id="2293"]