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;
}
``````

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
//