We’d love to hear any feedback or comment from you!

###### Engineering · Computer Science
Question details

C Programming Language

Problem is to create a program that will find the greatest GCD in an array of numbers. I can get the correct answers but my problem is efficiency and the checking software marks my answer wrong with the reason: TIMELIMIT. Code attempted is given below.

#include<stdio.h>

int gcd(int n1, int n2)
{
int i, gcd;
for(i=1; i <= n1 && i <= n2; ++i)
{
if(n1%i==0 && n2%i==0)
gcd = i;
}
return gcd;
}

int findGGCD(int arr[], int n)
{
int i, j;
int ggcd = 0;
for (i = 0; i < n-1; i++)
{
for (j = i; j < n-1; j++)
{
int k;
//arr[i], arr[j+1]
if(arr[i] > arr[j+1] && arr[j+1]!=0)
{
k = gcd(arr[j+1], arr[i] % arr[j+1]);
}
else if(arr[i] > arr[j+1] && arr[j+1]==0)
{
k = arr[i];
}
else
{
k = gcd(arr[i], arr[j+1]);
}

if(k > ggcd)
{
ggcd = k;
}
}
}
return ggcd;
}

int main()
{
int cases;
scanf("%d", &cases);
if(cases<1 || cases>100)
{
return 1;
}
for(int q = 1; q<= cases; q++)
{
int n;
scanf(" %d", &n);
if(n<2 || n>100)
{
return 1;
}
int ggcd;
int arr[n];
for(int i = 0; i<n; i++)
{
scanf(" %d", &arr[i]);
if(arr[i]<1 || arr[i]>1000000000)
{
return 1;
}
}
ggcd = findGGCD(arr, n);
printf("Case #%d: %lld ", q, ggcd);
}
}