2
\$\begingroup\$

Given a number n, the task is to complete the function which returns an integer denoting the smallest number evenly divisible by each number from 1 to n.

I have solved it using the following function:

long long getSmallestDivNum(long long n)
{
   //number should be multiplier of n
    bool found = true;
    int i = 2;
    while(1)
    {
        long long r = n*i;
        found = true;
        for(int j=2;j<=n;j++)
        {
            if( r % j != 0)
            {
                found  = false;
            }
        }
        if(found != true)
        {
            i++;
        }
        else
        {
            return r;
        }
    }
}

But I am getting a time-limit-exceeded-error like this:

Run Time Error Time Limit of 5 seconds exceeded.

When I execute the code in my local NetBeans, it works fine with a runtime of 62ms.

\$\endgroup\$
  • \$\begingroup\$ "But I am getting a time-limit-exceeded-error like, Run Time Error Time Limit of 5 seconds exceeded." If you are asking about fixing broken code, this isn't the place. Where are you running it that it is timing out? \$\endgroup\$ – Ron Beyer Nov 14 '16 at 15:25
  • \$\begingroup\$ @RonBeyer: Probably his code is working, but the third party coding site he is submitting to is rejecting it for being too slow. \$\endgroup\$ – Brian Nov 14 '16 at 20:15
  • \$\begingroup\$ @RonBeyer :Yes the code is taking too much time as said by the Brian \$\endgroup\$ – Anil Nov 15 '16 at 4:53
3
\$\begingroup\$

Your solution to the problem is "check every number to see if it has that property", but that's a lot of numbers. You can do a lot better.

Let me give you a big hint.

Suppose you want find the solution for n == 9. Suppose you had the solution for n == 8 is 840. Don't worry about how you know that.

Given the fact that 840 is the smallest number that is divisible by 1, 2, 3, 4, 5, 6, 7 and 8, and that 9 is 3 times 3, how do you find a number that is divisible by 1, 2, 3, 4, 5, 6, 7, 8 and 9? Plainly multiplying 840 by 9 gives a number that is too large, because 9 is already 3 x 3. We only need to multiply by 3. So the solution for 9 is 2520.

Now suppose we want to find the solution for 10. We already know the solution for 9, and hey, it is already divisible by 10. So we're done.

Now suppose we want to find the solution for 11. 2520 is not divisible by 11, and 11 is prime. So we have to multiply by 11.

What about 12? 12 is 3 x 4, and we already have a number that is divisible by both 3 and 4, so the solution for 11 is the same as the solution for 12.

And so on.

So is it now clear how to solve this problem efficiently?

UPDATE

Apparently it was not clear.

Think about it this way.

  • The solution for 2 is 2.
  • The solution for 3 needs to have a factor of 3, but the solution for 2 has no factor of 3. So the solution for 3 is 2 x 3.
  • The solution for 4 needs two factors of 2. The solution for 3 has only one factor of 2, so we add an additional factor of two: 2 x 3 x 2.
  • The solution for 5 needs a factor of 5, but we don't have one in the solution for 4. So 2 x 3 x 2 x 5.
  • The solution for 6 needs a factor of 2 and a factor of 3. The solution for 5 has a 2 and a 3 already, so 2 x 3 x 2 x 5 works for 6.
  • The solution for 7 needs a factor of 7, but the solution for 6 doesn't have one. So 2 x 3 x 2 x 5 x 7.
  • The solution for 8 needs three factors of 2, but the solution for 7 only has two. So 2 x 3 x 2 x 5 x 7 x 2.
  • The solution for 9 needs two factors of 3, but the solution for 8 only has one. So 2 x 3 x 2 x 5 x 7 x 2 x 3.
  • The solution for 10 needs a factor of 2 and a factor of 5. The solution for 9 already has those. So 2 x 3 x 2 x 5 x 7 x 2 x 3.
  • Now do you see the pattern?
\$\endgroup\$
  • \$\begingroup\$ Hello Eric, As u said, again i have to calculate it for (n-1) which is the same as calculating for n.Is it correct? \$\endgroup\$ – Anil Nov 14 '16 at 15:57
  • \$\begingroup\$ @SubSea: No. The question is: if you already know the solution for n-1, can you quickly calculate the solution for n? If you can solve that problem, then you can solve the problem for any n. \$\endgroup\$ – Eric Lippert Nov 14 '16 at 18:24
  • \$\begingroup\$ Hello Eric,Can you please look into the answer i have posted. \$\endgroup\$ – Anil Nov 15 '16 at 14:13
1
\$\begingroup\$

Note: This is not a solution because there are better algorithms then the naive approach you have taken. Google it to find more.

I will review the code for you about what should have been taken care of:

  • long long getSmallestDivNum(long long n) The argument is long long n: Should you support it or should it just be int. Please check the problem you are solving. If YES, then how are you handling the max value for long long.
  • Do you need to support negative numbers? If no, rule that out.
  • What were your test cases? Did you check for 0, 1 to start with.

Now lets get to the algorithm: - I hope you understand the intention is to find LCM of numbers from 1 to N. (This will help you find a better algorithm). - Do you know prime numbers are not divisible by any other than 1 and that number. Use that. - The max value of this problem for any value n is 1*2*3*4*....n. Use that.

Coming to your question: Its good that it failed because it its a hint that there is a better algorithm :) For larger values of n, your algorithm will face "Time limit exceeded" exception.

\$\endgroup\$
  • \$\begingroup\$ Thanks for reviewing my code.long long n should be handled and iam not supporting any negative value and i have checked with the test cases u have mentioned. \$\endgroup\$ – Anil Nov 14 '16 at 15:52
0
\$\begingroup\$

What you're trying to do (as @thepace already noted) is computing the LCM of some numbers. Computing the LCM is extensible, so to speak, so \$LCM(A, B, C)\$ can be computed as \$LCM(LCM(A, B), C)\$ (and so on, for as many numbers as needed).

The LCM is typically computed as: \$(A\cdot B)\over GCD(A, B)\$

There are quite a few different ways of computing the GCD. One fairly simple one is Euclid's algorithm, which can be implemented in C++ code something like this:

unsigned GCD(unsigned u, unsigned v) {
    while ( v != 0) {
        unsigned r = u % v;
        u = v;
        v = r;
    }
    return u;
}

This method of computing the LCM is generally quite a bit faster than methods that rely on finding all the prime factors of A and B (since prime factorization can be quite slow by itself).

\$\endgroup\$
  • \$\begingroup\$ While each statement in this answer is individually true, it points in the wrong direction for solving the OP's problem. \$LCM \{ i | 1 \le i \le n \}\$ is not at all the same problem as the LCM of a set of random integers. The correct solution for OP's problem is finding prime factors; the problem setter almost certainly expected answers to use a sieve of Erastophenes and then compute a product of maximal prime powers, and that is much faster than folding a pairwise LCM. \$\endgroup\$ – Peter Taylor Nov 15 '16 at 9:31
  • \$\begingroup\$ @PeterTaylor: That may be true, but it's basically irrelevant. This method is fast enough that it'll overflow a 64-bit integer long before it runs out of CPU time (on my machine it's using <2 ms of CPU time before it overflows). If there's a problem here it's that the A*B term can lead to premature overflow, so this wouldn't finish for a value that other methods could (in the same size of integer). Using a sieve for the sake of speed would be premature optimization. \$\endgroup\$ – Jerry Coffin Nov 15 '16 at 16:59
  • \$\begingroup\$ I did my timing tests using a BigInteger implementation because I don't know what long long is on OP's platform (or, perhaps more to the point, on the test platform). \$\endgroup\$ – Peter Taylor Nov 15 '16 at 17:28
  • \$\begingroup\$ @PeterTaylor: You're welcome to do what you wish, of course--but there's essentially no possibility of long long being anything other than 64 bits. Smaller isn't allowed; larger is allowed, but I'm reasonably certain it doesn't actually exist. Hardly matters though. The sequence grows geometrically, so even if long long were immense--say 1024 or 2048 bits, we'd still overflow long before we used up even close to 5 seconds of CPU time. Short of mandating arbitrary precision integers, pairwise LCM is more than adequate (and much simpler than a sieve). \$\endgroup\$ – Jerry Coffin Nov 15 '16 at 17:52
0
\$\begingroup\$

i think i have implemented @Eric Lippert algorithm as below,i hope this is readable,

#include<iostream>
#include<vector>
#include<map>
#include<math.h>
using namespace std;
void findfactorsandsolution(int num, std::map<int, int>& factorsofeach, std::map<int, int>& factors)
{
      int i, j, isPrime, k = 0;
      int divisor = 2;
      //find the factors of each number
      while (num>1)
      {
           while (num%divisor == 0)
           {
                //add the factor and how many times it has been come
                 factorsofeach[divisor]++;
                 num = num / divisor;
           }
           divisor++;
      }
      //insert to a solution map
      factors.insert(factorsofeach.begin(), factorsofeach.end());
      //check for multiple occurance of a factor where it has to be considered
      std::map<int, int>::iterator itf = factorsofeach.begin();
      std::map<int, int>::iterator itfactors;
      for (; itf != factorsofeach.end(); itf++)
      {
           itfactors = factors.find(itf->first);
           //this done when we get factors of 4 as 2 x 2 and update the solution map with this count of 2
           if (itfactors != factors.end() && itfactors->second < itf->second)
           {

                 itfactors->second = itf->second;
           }
      }
}
int main()
{
      int n = 10;
      std::vector<int> sols; int k = 0;
      std::map<int, int> factors;
      //iterate for 1 to n
      for (int i = 1; i <= n; i++)
      {
           std::map<int, int> factorsofeach;
           findfactorsandsolution(i, factorsofeach, factors);
      }
      //add the factors to solution list
      std::map<int, int>::iterator itmap = factors.begin();
      long long res = 1;
      for (; itmap != factors.end(); itmap++)
      {
           res *= pow(itmap->first, itmap->second);
      }
      cout << res;
      return 0;
}

if we see the code,even this also uses two loops ,loop within a loop but executes fine and also it has more operations than the code which i have written in the question.What is correct here.

\$\endgroup\$
  • \$\begingroup\$ @Eric Lippert, can you please help me with this... \$\endgroup\$ – Anil Nov 15 '16 at 14:11
  • \$\begingroup\$ Your code looks pretty reasonable. There's an isPrime which is never used, and I might have divided it up into smaller helper functions but it looks correct to me. If you wanted to make it faster you could note that if divisor > 2 then you can increment it by 2 instead of 1. And you could note that if divisor * divisor > num then num has to be prime. Both would get you out of that loop sooner. \$\endgroup\$ – Eric Lippert Nov 15 '16 at 14:39
  • \$\begingroup\$ Alternatively, you could precompute a large array of prime numbers and simply use that array in your program, rather than attempting to recompute the same primes for the divisors over and over again. \$\endgroup\$ – Eric Lippert Nov 15 '16 at 14:41
  • \$\begingroup\$ @EricLippert But i think the number of operations are more here than the code i have posted in question.How it is faster than that.Please tell. \$\endgroup\$ – Anil Nov 15 '16 at 15:12
  • \$\begingroup\$ Well, here's how you can figure it out. Instrument both programs so that you increment a counter every time you do an addition, multiplication, subtraction, division or remainder operation. Then run your programs for n = 1, 2, 3, 4, 5, ... up to say 100. And then produce a graph showing how the counter grows in one program compared to the other. You will then know which program does more operations, rather than guessing. You're a computer programmer; write a program to answer your question. \$\endgroup\$ – Eric Lippert Nov 15 '16 at 16:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.