{"id":1234,"date":"2020-06-10T16:53:16","date_gmt":"2020-06-10T16:53:16","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1234"},"modified":"2022-06-17T06:23:58","modified_gmt":"2022-06-17T06:23:58","slug":"maximum-divisors-in-a-range","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/maximum-divisors-in-a-range\/","title":{"rendered":"Maximum Divisors in a Range"},"content":{"rendered":"

<\/p>\n

Concepts Used<\/h3>\n
\n

Sorting<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Hard, Mathematics<\/p>\n<\/blockquote>\n

Problem Statement (Simplified):<\/h3>\n

For a given range p<\/code> and q<\/code>, find the highest common factor of two given numbers, i.e. a<\/code> and b<\/code>. If no such number exists, return -1.<\/p>\n

Test Case<\/h4>\n
Input:\n8 12\n4\n2 10\n3 7\n2 2\n5 6\n\nOutput:\n4\n4\n2\n-1\n\nExplanation:\nFor 8 and 12, common divisors are [1,2,4].\n\nIn the range [2,10] we have 4 which is the maximum divisor in range.\n\nIn the range [3,7] we have 4 which is the maximum divisor in range.\n\nIn the range [2,2] we have 2 which is the maximum divisor in range.\n\nIn the range [5,6], there lies no divisor so we print -1.<\/code><\/pre>\n
<\/strong><\/u><\/a><\/p>\n
Solving Approach :<\/h3>\n
\n
1) The Highest common factor of any both numbers will be gcd(a,b)<\/code> and there exists no factor above this.
\n2) So, to calculate all the factors we check all number which divide a<\/code> and b<\/code> both from 1 to gcd(a,b)<\/code> and save them in an array.
\n3) We sort the array containing all common factors so that all factors are organized and searching factors in the range are easier.
\n4) Highest common factor in the given range [p,q<\/code>] can be found by searching lower bound of p<\/code> and upper bound of q<\/code>. Where,<\/p>\n
    \n
  • Upper Bound:<\/em><\/strong> Upper bound of any number K<\/code> returns the position of immediate next number which exists in the array and is just greater than K<\/code>. <\/li>\n
  • Lower Bound:<\/em><\/strong> Lower bound of any number K<\/code> returns the position of immediate previous number which exists in the array and is just smaller than K<\/code>.
    \n5) If the lower bound of p<\/code> and upper bound of q<\/code> is the same that means, there is no common factor in the range [p,q<\/code>].
    \n6) If they are not same, the Highest Common factor in range will be the previous element to element at upper bound of q<\/code>, as an element at the upper bound is greater than q<\/code>, and element previous to it will be smaller than q<\/code> and will be a common factor. Hence it is our answer, so we return the element.<\/li>\n<\/ul>\n<\/blockquote>\n
    Example<\/h3>\n
    \n
    Let given numbers be a=8<\/code> and b=12<\/code><\/p>\n
    We find gcd(a,b)<\/code> as no factor lies beyond gcd(a,b)<\/code> which divided both numbers, hence,<\/p>\n
    gcd(a,b)<\/code> = 4<\/code><\/p>\n
    We check all numbers between 1 and gcd(a,b)<\/code> which divides both of our numbers a<\/code> and b<\/code>, we save such numbers in a array,<\/p>\n
    \"\"<\/p>\n
    We also sort this array so that factors are arranged in increasing order,<\/p>\n
    \"\"<\/p>\n
    For given query p<\/code> and q<\/code>, we check lower<\/code> bound<\/code> of p<\/code> and upper<\/code> bound<\/code> of q<\/code>, let’s assume two queries<\/p>\n
      \n
    • Query-1<\/em><\/strong>:<\/li>\n<\/ul>\n
      p=5<\/code> and q=6<\/code><\/p>\n
      Here, lowerBound(p) = 4<\/code> and upperBound(q)=4<\/code>, as both values are same that means our query is beyond the range of factors, hence we return -1.<\/p>\n
        \n
      • Query-2<\/em><\/strong>:
        \np=2<\/code> and q=3<\/code><\/li>\n<\/ul>\n
        Here, lowerBound(p) = 2<\/code> and upperBound(q)=4<\/code>, as both values are not same that means our range coincides with range of factors, hence our answer lies at factor less than upperBound(q) i.e. 3.<\/p>\n<\/blockquote>\n
        Solutions<\/h3>\n
        \t\t\t\t\t\t