Find the smallest divisible number for the given input 'n' such that number is evenly divisible by 1 to n

Question

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.

Answer 1

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?

Answer 2

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.

Answer 3

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).

Answer 4

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.