CODEWITHSUNDEEP
calgorithmmergesort
guptasaanika
guptasaanika

Reputation: 137

Ubuntu giving me wrong output

I am facing a very unusual problem. This is the program I made using merge sort to print the number which is repeated the maximum number of times.

#include<stdio.h>
int n;
int merge(int a[],int low,int mid,int high){
    int i=low,j=mid+1,c[n],k=low;
    while((i<=mid) && (j<=high)){
        if(a[i]<=a[j]){
            c[k]=a[i];
            i=i+1;
            k=k+1;
        }

        else{
            c[k]=a[j];
            k=k+1;
            j=j+1;
        }
    }

    while(i<=mid){
        c[k]=a[i];
        i=i+1;
        k=k+1;
    }

    while(j<=high){
        c[k]=a[j];
        j=j+1;
        k=k+1;
    }

    for(i=low;i<=high;i++){
        a[i]=c[i];
    }
    return 0;
}


int mergeSort(int a[],int low,int high){
    int mid=0;
    if(low<high){
        mid=(low+high)/2;

        mergeSort(a,low,mid);
        mergeSort(a,mid+1,high);

        merge(a,low,mid,high);
    }
    return 0;
}

int main(){
    int i,a[n];
    printf("\nEnter the size of array:\n");
    scanf("%d",&n);
    printf("\nEnter the elements:\n");
    for(i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    mergeSort(a,0,n-1);
    printf("\nThe array after merge sort is-\n");
    for(i=0;i<n;i++){
        printf("%d ",a[i]);
    }
    i=0;
    int j=i+1,count=1,maxCount=1,flag=0,f=0;
    int arr1[n],arr2[n];
    //printf("%d ",n);
    while(i<(n-1) && j<n){
        j=i+1;
        while(a[i]==a[j]){
            count++;
            j++;
        }
        //printf("%d %d %d %d %d\n",count,a[i],a[j],i,j);
        if(count>1 && count>=maxCount){
            //printf("%d repeated %d times",a[i],count);
            arr1[f]=count;
            arr2[f]=a[i];
            flag=1;
            f++;
            maxCount=count;
        }
        i=j;
        count=1;
    }
    for(i=0;i<f;i++){
        if(arr1[i]==maxCount)
            printf("\n%d repeated %d times\n",arr2[i],arr1[i]);
    }
    if(flag==0){
        printf("\nNo repetitions\n");
    }
    return 0;
}

When running this program on Ubuntu, I'm getting this output-

When running the exact same program on GeeksforGeeks IDE with the same inputs[But on hackerrank IDE for the same input I'm getting the right output.]2, I'm getting the same erroneous output-

Please explain why the same program is working only on hackerrank IDE. Is it because of the time complexity? Which according to me is nlogn and is optimized. Or is it because of the space complexity? Please explain. Thanks.

Upvotes: 0

Views: 93

Answers (1)

Thomas Padron-McCarthy
Thomas Padron-McCarthy

Reputation: 27632

There is at least one error in the program:

int i,a[n];
printf("\nEnter the size of array:\n");
scanf("%d",&n);

When the array a is created, n is not yet set.

n (which is a variable with extern storage) is initialized to zero, so your array will have size zero. Since you then put items in it, you are storing data outside of its allocated space, and this is undefined behaviour. Anything can happen, and that can be different on different platforms.

Upvotes: 2

Related Questions