Problem:
https://www.hackerrank.com/challenges/john-and-gcd-list/problem
Explanation:
GCD(B[1],B[2]) =A[1] that is A[1] divides B[2]
GCD(B[2],B[3]) =A[2] that is A[2] also divides B[2]
so B[2] must be divisible by both A[1] and A[2].
as LCM of A[1],A[2] will be divisible by both A[1] and A[2].
Therefore B[2] must be a multiple of LCM(A[1],A[2])
Since in the question, they wanted minimum value of B[2]
So, B[2] = LCM(A[1],A[2])
#include<stdio.h>
int gcd(int,int);
int lcm(int,int);
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,i;
scanf("%d",&n);
int a[n];
for(i=0 ; i<n ; i++)
scanf("%d",&a[i]);
printf("%d ",a[0]);
for(i=0 ; i<n-1 ; i++)
{
if(a[i+1] >a[i])
printf("%d ",lcm(a[i+1],a[i]));
else
printf("%d ",lcm(a[i],a[i+1]));
}
printf("%d\n",a[n-1]);
}
return 0;
}
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
int lcm(int a, int b)
{
return (a*b)/gcd(a,b);
}
No comments:
Post a Comment