PROBLEM LINK-MXMLCM Problem - CodeChef
MY SOLUTION-
#include <bits/stdc++.h>
#include
#include
#include
#include
using namespace std;
long long gcd(long long a, long long b)
{
if(b==0)
{
return a;
}
else
return gcd(b,a%b);
}
int main()
{
int t;
cin>>t;
while(t–)
{
long long n,m;
long long lcm=1;
cin>>n>>m;
for(int i=0;i<n;i++)
{
long long a;
cin>>a;
lcm=(lcm*a)/(gcd(lcm,a));
}
if((lcm%m)==0){
if(m!=1)
cout<<m-1<<endl;
else
cout<<m<<endl;
}
else
cout<<m<<endl;
}
return 0;
}
Ur algorithm is not general friend. It will satisfy only few cases,
Try this ,I hope u understand the code .
import java.util.Scanner;
public class MaxLCM {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t-- > 0) {
int n = sc.nextInt();
int m = sc.nextInt();
int a[] = new int[n];
for (int j = 0; j < n; j++) {
a[j] = sc.nextInt();
}
System.out.println(maxLcm(a, m));
}
sc.close();
}
public static int maxLcm(int a[], int m) {
if (m == 1 && m == 2) {
return 1;
}
int ans = 0;
long maxLCM = 0;
long lcm = a[0];
long gcd = a[0];
for (int i = 1; i < a.length; i++) {
gcd = GCD(a[i], lcm);
lcm = (lcm * a[i]) / gcd;
}
for (int k = 1; k <= m; k++) {
gcd = GCD(k, lcm);
if ((lcm * k) / gcd > maxLCM) {
maxLCM = (lcm * k) / gcd;
ans = k;
}
}
return ans;
}
public static long GCD(long a, long b) {
if (b == 0) return a;
return GCD(b, a % b);
}
}
Bro, i am still not able to understand where my approach is wrong .Can you please give a case where my code will fail?
1 Like
Ur code will run good if the number previous to m is prime because it will not be factorised further
Try this case bro
3 9
2 5 9
I guess it may give wrong output as far as I understood ur code.
Yes bro got it, thanks a lot.
1 Like