Finding numbers with given gcd and lcm [closed]

Question

I am solving a question in which we are given the LCM and HCF and two numbers 'a' and 'b', our task is to find the pairs of numbers between a and b [inclusive] whose HCF is the given HCF and LCM is the given LCM

I have written a code with time complexity O(m) where m is the number of integers lying between the range a and b, But on submission i am getting time limit exceeded error

IMO this is the best we can do , can we do better? Here is the code

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

  //function for calculatin gcd
  int gcd( int a,int b){
  int h;
   for(h = a<b?a:b; h >= 1; h--){
    if((a%h == 0) && (b%h == 0))
     break;
   }

   return h;
   }

  int main(){
  int n1,n2,lcm,hcf,cnt = 0;
  cin>>n1>>n2>>hcf>>lcm;//The numbers a,b and hcf and lcm
   for(int i = n1; i <= n2;i++){
   //checking if the number divides the lcm completely  
   if(lcm%i == 0){
    int a = lcm/i;// its other multiplier
    int b = gcd(a,i);//finding their gcd
        //checking if their gcd is equal to given hcf
        if(b == hcf){
         int c = (i*a)/b;//finding the lcm by a*b = lcm*hcf formula and 
                         //checking
          if(c == lcm){
           cnt++;
          }
         }
        }
       }

   cout<<cnt<<endl;
   return 0;
   }

Answer 1

Headers

Use the standard headers, not #include<bits/stdc++.h>. This is intended solely for gcc's internal use, and gratuitously renders your code completely non-portable.

Oh No! Not using namespace std;!

Please don't use using namespace std; It can, will, and does declare an unknown and almost unbounded set of names, many of which 1) you may not know about (it grows constantly), and 2) many of which are really common names that can collide with all sorts of reasonable code, leading to no end of potential problems.

Use the Library

If you're using a current compiler, you probably have std::gcd defined in <numeric>, so you probably don't need to define your own.

Improved Algorithm

To fit the criteria, each number you try must be a multiple of the given gcd (otherwise that wouldn't be the gcd of the number in question). As such, you can start from the smallest number that's a multiple of the gcd, but greater than your lower bound.

For example, if you're given a gcd of 21 and a lower bound of 30, you can quickly find that your starting point is 42, because that's the next number larger than 30 that's also a multiple of 21.

From there, you have to multiply each candidate by numbers that are coprime with each other--if the multipliers weren't coprime, then the common factors would become part of the gcd, and the gcd of the two would no longer be what you were given. So, for example, given a gcd of 21, you could try 21*2 = 42 with 21*3 = 63. Since 2 and 3 are coprime, that would gcd(42,63) would still be 21 (as required).

Answer 2

Style: the indentation is a mess. I realise that this is in part because the StackExchange software converts tabs to spaces, but I can't understand how the entire code ended up indented by two spaces, nor why some lines which should be at the same level of indentation differ by one space.

---

our task is to find the pairs of numbers between a and b [inclusive] whose HCF is the given HCF and LCM is the given LCM

There are a couple of points here which you need to clear up before it's clear that your code is even correct. Firstly, should both of the numbers be in the range \$[a, b]\$ or just one of them? My interpretation would be that both should, and in that case the code is wrong because it doesn't check that lcm/i is in range. Secondly, are these ordered or unordered pairs? I.e. is \$(3, 7)\$ the same pair as \$(7, 3)\$? The code assumes ordered pairs, but I would think that unordered are slightly more likely to be the intent.

---

Names: it's really confusing to use a and b to mean one thing in the description of the program and something completely different in the main function of the code. And it makes it different to write this review without adding to the confusion. I'm going to have to invent some completely new names to avoid ambiguity.

---

IMO this is the best we can do , can we do better?

Yes, easily. HCF contains two important concepts: highest and common. A common factor of \$x\$ and \$y\$ is a factor of both \$x\$ and \$y\$. The highest common factor is the largest number which is a factor of both \$x\$ and \$y\$. So if we're told that the HCF of \$x\$ and \$y\$ is \$h\$, we can rewrite as \$x = sh\$ and \$y = th\$ where \$s\$ and \$t\$ are coprime.

Now, given that the lowest common multiple is \$m\$, we also have that \$m = sth\$, so we can find \$st = \frac{m}{h}\$.

Given \$st\$ and the fact that \$s\$ and \$t\$ are coprime, we can apply the fundamental theorem of arithmetic to say that once we factor \$st\$ into primes as \$p_1^{e_1} p_2^{e_2} \ldots\$ we can assign each prime power in its entirety either to \$s\$ or to \$t\$. This is probably the lesson which the task was intended to teach or reinforce.

Answer 3

We will start by reinforcing some of the things already mentioned in the other answers.

First, do not use the header <bits/stdc++.h>. This has been addressed before on SO in the question Why should I not #include bits/stdc++.h?. Also, using namespace blah is bad practice, regardless of the library/header you are referring to (doesn't have to be std). This too has been addressed on SO in the question Why is “using namespace std” considered bad practice?. Lastly, the overall spacing and naming you have chosen is not very clear, which leads to difficult code readability.

Now, to address the specific problem of finding pairs of numbers in a given range that have a specific LCM and GCD: The code you have provided is not correct.

I believe that one of the best methods for deriving a correct algorithm is by looking at a well-formed example. How do they go about doing that (especially the well-formed part)?

A good place to start is by looking at the definitions associated with our problem and try to find a relationship that we can build off of. As @esote points out in the comments, we are given the property:

$$ \gcd(a, b) \cdot \textrm{lcm}(a, b) = |a \cdot b| $$

Continuing with our well-formed mission, we want to pick our numbers such that we get a decent number of hits. This means that we should avoid cases that we know will give bad results, such as cases:

• \$\gcd(n_1,n_2) > \textrm{lcm}(n_1, n_2)\$
• \$n_1,n_2 > \textrm{lcm}\$
• \$n_1,n_2 < \gcd\$

And many more. We should also look for numbers that have many divisors as this is likely to increase the number of hits. Highly composite numbers are great candidates for this.

Let's set gcd = 12, lcm = 720720, n1 = 100, and n2 = 7000 to see what happens. With this setup, a correct algorithm should return at least 9, if order doesn't matter, which I think should be the case (I agree with @PeterTaylor when he states "but I would think that unordered are slightly more likely to be the intent.").

The 9 pairs are:

1260, 6864
1584, 5460
1680, 5148
1716, 5040
1872, 4620
1980, 4368
2340, 3696
2640, 3276
2772, 3120

It looks like we have found a good example to build our algorithm off of (I will leave it to the reader to prove that these are the only numbers in the given range where \$\gcd = 12\$ and \$\textrm{lcm} = 720720\$). We note that running the OP's algorithm on the example above returns 0.

What are some take-aways from the 9 pairs above? For starters, the suggestion by @JerryCoffin for finding the starting point is good, but we can do much better. According to the method proposed by @JerryCoffin, our starting point would be 108 as it is the first number greater than or equal to 100 that is also divisible by 12. As you can see from the 9 pairs above, the smallest number encountered is much larger than 108 (i.e. 1260).

Why is this? Rearranging the relationship above, we have (given \$a < b\$):

$$ a = \frac{\gcd(a, b) \cdot \textrm{lcm}(a, b)}{b} $$

Which means that the smallest value of \$a\$ is:

$$ \frac{12 \cdot 720720}{7000} \approx 1235 $$

If a < 1235, we can see that that the corresponding value for b would exceed 7000. Now, using the method mentioned by @JerryCoffin of making the starting point divisible by our GCD, we see that 1236 satisfies this condition and should be our starting value.

What about our maximum value? This can be attacked by noticing that we start getting repeated values after we have crossed the threshold:

$$ \sqrt{\gcd \cdot \textrm{lcm}} $$

For example, had we continued on after 2772 above (the last value in the left column), we would have simply obtained 3120, 2772 followed by 3276, 2640, ... 6864, 1260, which is exactly what we already have but in reverse. Now we note that:

$$ 2772 < \sqrt{12 \cdot 720720} \approx 2940 $$

Thus, 2940 will be our ending value.

For our incrementing value, we take the suggestion by @Jerry and use the GCD. Using all of this information together with the algorithm for GCD suggested by @esote, we have the following:

#include <iostream> // For cout, cin, & endl
#include <cmath>    // For sqrt, ceil, min, & max

int myGCD(int u, int v) {
    int r;
    while (v != 0) {
        r = u % v;
        u = v;
        v = r;
    }
    return u;
}

int numPairs(int n1, int n2, int lcm, int hcf) {

    int count = 0;
    int myProd = lcm * hcf;

    // If sqrt(myProd) > n2, then we need to stop at n2
    int myLim = std::min((int) std::sqrt((double) myProd), n2);

    // We ensure that we cover the entire range by taking the
    // max. E.g. if n1 > myProd / n2, we would start at n1
    double myStart = std::max(n1, myProd / n2);
    myStart = std::ceil(myStart / (double) hcf) * hcf;

    for (int i = (int) myStart; i <= myLim; i += hcf)
        if (lcm % i == 0)  // ensure our number is divisible by lcm
            if (myGCD(i, myProd / i) == hcf)  // ensure our pair gives correct gcd
                ++count;

    return count;
}

int main() {
    int n1, n2, lcm, hcf, cnt;
    std::cin >> n1 >> n2 >> lcm >> hcf;
    cnt = numPairs(n1, n2, lcm, hcf);
    std::cout << cnt << std::endl;
    return 0;
}

Running this for the given example promptly returns 9 (here is an ideone link with working code).

Figuring out why OP's algorithm returns bad results:

---

In the OP's algorithm, it returns 0 because of the following line:

int a = lcm/i;// its other multiplier

This should be int a = hcf * lcm / i;. We should also note that this calculated value for a may exceed n2 or fall below n1. To fix this, all we need to do is add a check before the line if(b == hcf){ like so:

if (a <= n2 && a >= n1) {
    if (b == hcf) {

While we are at it, we can save a call to gcd by placing it inside the new condition we added:

if (a <= n2 && a >= n1) {

    int b = gcd(a,i);

    if (b == hcf) {

When we run the new modified OP's code, we obtain 18 as expected (OP is double counting pairs with same values but different orders: here is another ideone link with the fixes).

Benchmarks:

---

Putting both algorithms in the same file and running the main function below, we see that the modified algorithm is over 7000x faster.

#include <ctime>
.
.  // more code here
.

int main() {
    int n1, n2, lcm, hcf, countNoOrder = 0, countAll = 0;
    std::cin >> n1 >> n2 >> lcm >> hcf;
    std::clock_t start_time, end_time;

    start_time = clock();
    for (int i = n1; i < (n1 + 500); ++i)
        countNoOrder += numPairs(i, n2, lcm, hcf);
    end_time = clock();

    std::cout << "Time taken with modified algorithm numPairs : " <<
        end_time - start_time << std::endl;

    start_time = clock();
    for (int i = n1; i < (n1 + 500); ++i)
        countAll += OPAlgo(i, n2, lcm, hcf);
    end_time = clock();

    std::cout << "Time taken with corrected OP algorithm : " <<
        end_time - start_time << std::endl;

    std::cout << "Result for modified algo : " << countNoOrder << std::endl;
    std::cout << "Result for original OP code : " << countAll << std::endl;
    return 0;
}

And with the input given as : 10000 500000 8648640 120, we obtain the following:

Time taken with modified algorithm numPairs : 408
Time taken with corrected OP algorithm : 3006723
Result for modified algo : 3000
Result for original OP code : 6000

Which gives 3006723 / 408 = 7369.41... supporting our claim above (i.e. more than 7000x faster) Here is a link to ideone which shows the benchmarking code.