2
\$\begingroup\$

Here is the Question. Find the largest GCD of the input variable with the values of an array.

Inputs are as follows:- First-line contains two integers, N and Q.

Second-line contains N integers which form the arr[].

Next, Q lines contain an integer M, the time in seconds she wishes to go back.

#include <stdio.h>

int main(){
    int n,q;
    scanf("%d %d", &n,&q);
    int a[n];
    int gcdn[n];
    for (int i = 0;i < n; i++) {
        scanf("%d",&a[i]);      }
    while (q>0){
        q--;
        int x;
        int max = 0;
        scanf("%d",&x);
        max = gcd(a[0],x);
        for(int i=0;i<n;i++) {
            int t = gcd(a[i],x);
            if(t > max)
                max = t;
        }
        printf("%d \n",max);
    }

}

int gcd (int a, int b) {
    if (b==0)
        return a;
    else 
        return gcd(b, a%b);
}

How can I make this code better in terms of competitive programming? And what other languages can make this code better and more efficient?

\$\endgroup\$
  • \$\begingroup\$ Rewrite your sentence about M. It doesn't make sense as is. \$\endgroup\$ – David G. Jan 23 at 22:18
  • 1
    \$\begingroup\$ There is a good review of the code, however, this question might be listed as off-topic because the code would not compile using most compilers (item 3 in the answer). \$\endgroup\$ – pacmaninbw Jan 23 at 22:38
3
\$\begingroup\$
  1. gcdn[] is unused.

  2. if n==0, you access a non-existent array element, and even if it isn't, you do the GCD with a[0] twice.

  3. gcd() is called before it is declared, which is bad style and can mess up optimization.

  4. you might think about whether the M or arr[] elements are likely to be larger. The order you pass values to gcd() can reduce by one loop if you guess right.

  5. The tail recursion on gcd() should be OK as long as you optimize.

\$\endgroup\$
  • \$\begingroup\$ If you think the code won't compile you should flag the question and indicate that the code is broken. You gave a good answer, but since the code is broken it should not have been answered. \$\endgroup\$ – pacmaninbw Jan 23 at 22:43
  • 3
    \$\begingroup\$ @pacmaninbw: No, this code compiles and runs. It gave what looked like correct results. Remember, unlike C++, C does allow implicit declaration. \$\endgroup\$ – David G. Jan 23 at 23:07
  • \$\begingroup\$ Thanks, I was actually trying to optimize the code, earlier I used gcdn array to store all the gcds found and then to get the max, but later I decided to calculate max at the time it was being calculated but actually forgot to remove the gcdn declaration. can you please explain a bit about how can I better optimize my loops to make them shorter? Any advice on that will be really helpful! \$\endgroup\$ – Rajnish Kaushik Jan 24 at 6:52
  • \$\begingroup\$ @RajnishKaushik: The loops seem fine. You might consider for (;q;q--) or while (q--), but neither one will speed up the optimized code. \$\endgroup\$ – David G. Jan 24 at 14:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.