MAXIMIZE LCM Giving wrong answer verdict...test cases are running well

1

my code is given below
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long

int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
int findLCM(int a, int b)
{
return (a*b)/gcd(a, b);
}

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

int main()
{ int t;
cin>>t;
while(t–)
{
int n,m;cin>>n>>m;
int arr[n];
for(int i=0;i<n;i++)
cin>>arr[i];
int k = findlcm(arr, n);
vector v(m);
for(int i=0;i<m;i++)
{
v[i] = findLCM(k, i+1);
}
int ma = *max_element(v.begin(), v.end());
int index = 0;
for(int i=0;i<m;i++)
{
if(v[i]==ma)
{
index = i+1;
break;
}
}
cout<<index<<endl;
}
return 0;
}

2

Your answer is overflowing . Calculate it another way.

3

same WA wid me , I also did the same way!!

4

when u are calculating the lcm its been sure of overflow ( 10 ** 4 numbers of order 10 ** 4 take any 6 primes of order 10**3 it will overflow) … thats why it is giving wrong answer … think it rather by storing the count of prime factors …

5

Your soluion will result in an overflow. Try using factorization as every number can be expressed as the product of primes. Look at this once. I think it will be clear.
(CodeChef: Practical coding for everyone)

1 Like
6

Can someone please explain why it is overflowing as i also did it in the same way !!!

1 Like
8

If the array consisits of only prime numbers less than 10000, then the lcm will simply be product of all numbers, which is not possible to store in any data type. Thus results in an overflow(undesired lcm)

1 Like