For GCD AND LCM question I wrote following code,
#include
using namespace std;
int main()
{
int a[1001]={},b[1001]={},n,minimum[1001]={},gcd[1001]={},lcm[1001]={};
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i]>>b[i];
if(a[i]>b[i])
{
minimum[i]=b[i];
}
else
{
minimum[i]=a[i];
}
for(int j=minimum[i];j>=1;j--)
{
if(a[i]%j==0&&b[i]%j==0)
{
gcd[i]=j;
break;
}
}
lcm[i]=(a[i]*b[i])/(gcd[i]);
}
for(int i=0;i<n;i++)
{
cout<<gcd[i]<<" "<<lcm[i];
cout<<endl;
}
return 0;
}
here is the problem link : FLOW016 Problem - CodeChef
Can you please tell what is the error ,please.
Okay, your approach is correct. But there are few problems.
- Time limit - Check Euler method to find gcd.
- Integer overflow - Your lcm might exceed int limits
thank you very much, just completed writing euler method
sorry but can you help me with this,
#include
using namespace std;
int hcf(int a,int b)
{
int rem,div,gcd,num,lcm;
if(a>b)
{
num=a;
div=b;
}
else
{
num=b;
div=a;
}
while(rem>0)
{
rem=num%div;
num=div;
div=rem;
}
gcd=num;
return gcd;
}
int lcm(int a,int b)
{
long long int lcm1;
lcm1=(a*b)/hcf(a,b);
return lcm1;
}
int main()
{
long long int a[1001]={},b[1001]={},t;
cin>>t;
for(int i=0;i<t;i++)
{
cin>>a[i]>>b[i];
}
for(int i=0;i<t;i++)
{
cout<<hcf(a[i],b[i])<<" "<<lcm(a[i],b[i]);
cout<<endl;
}
return 0;
}
in this it is showing wrong answer for the above question.
Return type of your lcm function is still int. Plus when you multiply two ints, the result be an int. so do something like (1ll * a * b) or declare a and b to be long long.