Floating Point exception

[dhayden]

I had some more thoughts on this. Ignoring the 64 bit overflow, can we improve the program?

First, there's a bug in findlcm. It won't work when you exclude item 0. Change lines 12 and 13 to

    int64_t ans = 1;
    for (j=0; j<i; j++)

It's a tiny bit slower, but this version of findlcm is a lot clearer:

int64_t
findlcm(int64_t arr[], int64_t n, int64_t i)
{
    int64_t ans = 1;
    for (int64_t j = 0; j < n; ++j) {
        if (j == i) continue;
        ans = ((arr[j]) / (gcd(arr[j], ans))) * (ans);
    }
    return ans;
}

Second, what exactly do you need to output? Is it the index of the number to remove, or the actual LCM when you remove the number? If you only need to print the index then you can use a different algorithm. In other words, you can figure out which number to remove without actually computing the LCM of all of them. Maybe this is the point of the problem: to be impractical to solve the obvious way, so you have to find a more clever algorithm.

[lastchance]

#include<iostream>
#include<fstream>
#include<vector>
#include<cassert>
using namespace std;

//======================================================================

int gcd( int a, int b )
{
   int q;

   while ( b > 0 )
   {
      q = b;
      b = a % q;
      a = q;
   }
   return q;
}

//======================================================================

vector<int> getNumbers()
{
   // Specified (for checking)
   vector<int> V = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };    // lcm is 2520
                                                         // removing 7 minimises LCM
   // Or read from file
// vector<int> V;
// int num;
// ifstream in( "numbers.txt" );
// while ( in >> num ) V.push_back( num );
// in.close();

   return V;
}

//======================================================================

int main()
{
   vector<int> V = getNumbers();
   int N = V.size();                   assert( N > 1 );


   int maxReductionFactor = 0;
   int pos = -1;

   for ( int i = 0; i < N; i++ )
   {
      int reductionFactor = V[i];
      for ( int j = 0; j < N; j++ )
      {
         if ( j == i ) continue;
         reductionFactor /= gcd( V[j], reductionFactor );
         if ( reductionFactor == 1 ) break;
      }
      if ( reductionFactor > maxReductionFactor )
      {
         maxReductionFactor = reductionFactor;
         pos = i;
      }
   }
   
   cout << "LCM will be minimised by removing value " << V[pos] << " at index " << pos << '\n';
   cout << "(Remember that indices start from 0)\n";
}

//====================================================================== 

LCM will be minimised by removing value 7 at index 6
(Remember that indices start from 0)

[maryt]

@dhayden
its exactly as you say. There is a better way to solve the problem than the current one.

@lastchance
Extremely thankful for you code.

Thank you all for your answers.

I get this error because there is a better algorithm to solve this problem.
I run out of time for big input which is impossible to be calculated efficiently.

I will take into consideration all the given answers to find a better algorithm.

Thank you for your time and valuable advice!

[maryt]

@lastchance

Your code is excellent! Thank you very much!! It works perfectly giving the right input for 50000 numbers lets say.

I will adjust my code, as I want to print both the minimum lcm and the index of the element.

Thanks a lot!

[dhayden]

While adjusting your code, check for overflow. Given what I found earlier, Frankly, I'd be stunned if it doesn't overflow by hundreds or thousands of digits. Can post a subset of the 50,000 numbers?

[lastchance]

@maryt

Please do not bother trying to print the minimum lcm, at least not as a single number.

Have a look at the results below.

First case (as coded below): numbers 1, 2, 3, ..., 9, 10

LCM will be minimised by removing value 7 at index 6

The LCM of ALL the numbers is ...
7 x 4 x 9 x 10
This is 2520

The minimum LCM following removal of one element is ...
4 x 9 x 10
This is 360

Now change the code so that NMAX = 100 (i.e. numbers 1, 2, 3, ..., 99, 100)

LCM will be minimised by removing value 97 at index 96

The LCM of ALL the numbers is ...
53 x 59 x 61 x 67 x 71 x 73 x 37 x 79 x 41 x 83 x 17 x 43 x 29 x 89 x 13 x 23 x 31 x 47 x 19 x 4 x 97 x 49 x 99 x 100
This would overflow the size of this integer type

The minimum LCM following removal of one element is ...
53 x 59 x 61 x 67 x 71 x 73 x 37 x 79 x 41 x 83 x 17 x 43 x 29 x 89 x 13 x 23 x 31 x 47 x 19 x 4 x 49 x 99 x 100
This would overflow the size of this integer type

#include<iostream>
#include<fstream>
#include<vector>
#include<cassert>
#include<limits>
using namespace std;

int NMAX = 10;

//======================================================================

int gcd( int a, int b )
{
   int q = 1;

   while ( b > 0 )
   {
      q = b;
      b = a % q;
      a = q;
   }
   return q;
}

//======================================================================

vector<int> getNumbers()
{
   vector<int> V;

   // Specified (for checking)
   for ( int n = 1; n <= NMAX; n++ ) V.push_back( n );
                                                      
   // Or read from file
// int num;
// ifstream in( "numbers.txt" );
// while ( in >> num ) V.push_back( num );
// in.close();

   return V;
}

//======================================================================

void writeLCM( vector<int> V )                                       // deliberate pass by value
{
   using INT = unsigned long long;
   INT MAX = numeric_limits<INT>::max();                             // maximum value of this type
   
   int N = V.size();
   for ( int i = 0; i < N - 1; i++ )
   {
      for ( int j = i + 1; j < N; j++ ) V[i] /= gcd( V[i], V[j] );   // remove any factors available later
   }
   
   INT lcm = 1;
   bool first = true;
   bool overflow = false;
   for ( int value : V )
   {
      if ( value == 1 ) continue;                                    // don't bother with trivials

      if ( !first ) cout << " x ";
      cout << value;   first = false;

      if ( MAX / value < lcm ) overflow = true;                      // pre-empt overflow
      else                     lcm *= value;                         // or update lcm
   }
   if ( first ) cout << 1;
   cout << '\n';

   if ( overflow ) cout << "This would overflow the size of this integer type\n";
   else            cout << "This is " << lcm << '\n';
}

//======================================================================

int main()
{
   vector<int> V = getNumbers();
   int N = V.size();   assert( N > 1 );


   int maxReductionFactor = 0;
   int pos = -1;

   for ( int i = 0; i < N; i++ )
   {
      int reductionFactor = V[i];
      for ( int j = 0; j < N; j++ )
      {
         if ( j == i ) continue;
         reductionFactor /= gcd( V[j], reductionFactor );
         if ( reductionFactor == 1 ) break;
      }
      if ( reductionFactor > maxReductionFactor )
      {
         maxReductionFactor = reductionFactor;
         pos = i;
      }
   }
   
   cout << "LCM will be minimised by removing value " << V[pos] << " at index " << pos << '\n';

   cout << "\nThe LCM of ALL the numbers is ...\n";
   writeLCM( V );

   cout << "\nThe minimum LCM following removal of one element is ...\n";
   V.erase( V.begin() + pos );
   writeLCM( V );
}

//======================================================================  

[maryt]

thank you very much @lastchance for your time! You've been extremely helpful!