We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Loading...
  1. Practice
  2. Algorithms
  3. Implementation
  4. Between Two Sets
  5. Discussions

Between Two Sets

  • askarovdaulet + 6 comments

    why not

    for (int i=f;i<=l;i+=f)

    instead of

    for(int i = f, j =2; i<=l; i=f*j,j++)

    ? Otherwise a very nice solution :)

    • moelldav + 2 comments

      "Count the number of multiples of LCM that evenly divides the GCD." is the same as "Cound the divisors of (GCD/LCM)" This will make the loop much easier.

      Also notice that if (GCD/LCM) is not in integer, the result is 0.

      • ryanlue + 0 comments

        How exactly is one different from the other?

        My approach was as follows:

        1. Divide GCD by LCM.
        2. Prime factorize the quotient.
        3. Count all unique combinations of (1..n) prime factors, where n is the total number of prime factors.
        4. Add 1 for the base case (LCM * 1).
      • ranjan_shubham31 + 0 comments

        your modification to the above said approach will give wrong answer. as all mulitples of lcm will not evenly divide the gcd. so you will have to check each multiple individually.

    • alex_pn + 2 comments

      Another suggestion to reduce the number of loop iterations

      for (int i=f;i*i<l;i+=f)

      then double the count and add 1 if i*i==l

      • abhiroyg + 0 comments

        For the problem's testcase (f=4, l=16), won't your loop give count as 1 ?

      • anashukla17 + 0 comments

        why is it i*i?

    • m4manishpushkar + 0 comments

      because the value of i will be getting doubled for getting next factor easily.

    • chandramnataraj1 + 0 comments

      i can only be multiples of lcm(a), that is why j starts at 2 and increases

    • ayusofayush + 0 comments
      [deleted]
    • lemanisar23 + 0 comments

      thank you so much for your advise askarovdaulet