Not a Triangle:Wrong answer

general
, ,
1

In the problem Not a Triangle , i have used c language and followed the algo :

1.Sort the array using merge sort in ascending order.
2.find the smallest index of array such that it is a[index] >a[i]+a[j] so chosen using binary search.

here is the code :

#include<stdio.h>

void sort(int a[] ,int start1 ,int end1 ,int start2 ,int end2)//part of merge sort
{

        int temp[end1-start1 +1 + end2-start2+1 ];
        int i=start1,j=start2,count=0;

        while(i<=end1 && j<=end2)
        {
                if(a[i]<=a[j])
                    temp[count++]=a[i++];
                else
                    temp[count++]=a[j++];


        }

        for(;i<=end1;++i)
            temp[count++]=a[i];

        for(;j<=end2;++j)
            temp[count++]=a[j];

        for(i=0;i<count;++i)
            a[i+start1]=temp[i];


}

void mergesort(int a[] ,int start,int end)
{
        if(start==end)
            return;

        int middle =(start+end)/2;

        mergesort(a,start,middle);
        mergesort(a,middle+1,end);
        sort(a,start,middle,middle+1,end);

}

int binarysearch(int a[] ,int start ,int end ,int key)
{

        int middle;

        while(start<=end)
        {
            middle=(start+end)/2;

            if(a[middle]==key)
                return middle;

            if(a[middle]<key)
                start=middle+1;

            if(a[middle]>key)
                end=middle-1;


        }

        return start;//this gives the index where the number > key starts as key is not present in array



}

int main()
{
        int n,i,j,count;

        scanf("%d",&n);

        while(n!=0)
        {
            int a[n];
            count=0;

            for(i=0;i<n;++i)
                scanf("%d",&a[i]);

            mergesort(a,0,n-1);


            /******** In case you want to print the sorted array************
            printf("\n");
            for(i=0;i<n;++i)
                printf("%d, ",a[i]);
            printf("\n");

            ****************************************************************/

            for(i=0;i<n;++i)
                for(j=i+1;j<n;++j)
                   count=count+n-binarysearch(a,j+1,n-1,a[i]+a[j]+1); // one more than a[i]+a[j] as that will contradict as the set as triangle

            printf("%d\n",count);
            scanf("%d",&n);

        }

        return 0;
}
2

Binary search wont work if you have repeated values.

e.g.

6

1 2 4 4 4 4

correct ans is 4 but your code gives 3

1 Like