CODEWITHSUNDEEP
cpointersfor-loop
ptushev
ptushev

Reputation: 177

Odd behavior in my code for a certain test case

The program is supposed to swap neighbouring elements which don't have a common denominator, and an element can only be swapped once. When i run the program, pretty much for any input works fine. Except for this one:

100 //input for number of elements

48 92 76 93 17 38 59 34 53 99 58 20 50 0 38 37 16 36 91 12 59 1 76 82 20 76 7 72 13 70 64 23 81 70 41 69 11 0 16 41 37 83 41 99 73 79 4 38 24 32 87 38 95 24 77 30 61 13 89 67 87 76 22 31 67 31 25 90 6 76 21 43 40 55 72 91 91 28 18 58 72 71 83 22 99 23 86 58 75 53 69 29 5 55 46 8 98 55 19 46 //the elements

For this input, the program hangs and prints nothing. Does someone know what is going on in this particular case?

#include <stdio.h>
int nzd(int a, int b)
{
    if(a==b || b==0) 
        return a;
    if(a>b) 
        return nzd(a-b, b);
    return nzd(a, b-a);
}
int swap(int *niza, int i)
{
    int temp;
    temp=*(niza+i);
    *(niza+i)=*(niza+i+1);
    *(niza+i+1)=temp;
}
int main()
{
    int a[100], n, i;
    scanf("%d", &n);
    for(i=0; i<n; i++)
    {
        scanf("%d", &a[i]);
    }
    for(i=0; i<n; i++)
    {
        if(i+1==n) continue;
        if(nzd(a[i], a[i+1])==1)
        {
            swap(a, i);
            i++;
        }
    }
    for(i=0; i<n; i++)
    {
        printf("%d ", a[i]);
    }
    return 0;
}

Upvotes: 2

Views: 47

Answers (2)

Ctx
Ctx

Reputation: 18420

Your function nzd() fails to handle the case a == 0 correctly and gets stuck in an endless loop. You need to handle this case, too:

int nzd(int a, int b)
{
    if(a==b || a==0 || b==0) 
        return a;
    if(a>b) 
        return nzd(a-b, b);
    return nzd(a, b-a);
}

Upvotes: 2

dbush
dbush

Reputation: 224972

Your gcd function checks for the case of b==0 but not the case for a==0. Because you skip that check, you end up calling nzd(0, b-0); which is exactly the same as the prior call. This puts you in an infinite recursion loop which will eventually cause a stack overflow.

Add the check for this case in your function:

if(a==b || b==0 || a == 0)

Also, a faster implementation of gcd, called Euclid's algorithm, is as follows:

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

Upvotes: 3

Related Questions