CareerCup

This is brute force right?

Where are you sorting or checking for triangle inequality?

Could you please give some explanation for the above code. Its difficult to understand.

10 , 9.5 , 9 , 8 , 5 , 2,0.5

int getAllTriangles(int input[])
{
if(input.length<3)
return 0;
int count=0;
sort(input); //assume merge sort
for(int i=0;i<input.length-2;i++)
{
for(j=i+1;j<input.length-1;j++)
{
int index=BinarySearch(input,j,input.length-1); //returns the index of that number
if(index!=-1)
count=count+index-j;
}
}

}

int BinarySearch(int input[],int low,int high)
{
if(low>high)
return -1;
int k=input[low]-input[high];
int mid=(low+high)/2;
if(k<input[mid] && k>=input[mid+1] && mid+1<=high)
return mid;
else if(k<input[mid-1] && k>=input[mid] && mid-1>=low)
return mid-1;
else if(k<input[mid])
return BinarySearch(input,mid+1,high);
else
return BinarySearch(input,low,mid-1);
}

Your algorithm seems partly right. Could you please elaborate in the form of a pseudocode. I believe i,j,k all three can be iterated over the array. So TC is O(n^3) right? My approach was on similar lines but i was doing a binary search to find the 3rd element. The TC I got then was n^2logn. Anyone with a better and simpler approach?

Here is my solution:
char getSmallestLarge(char [] list,char c)
{
SmallestCharacter sc=new SmallestCharacter();
return sc.BinarySearchChar(list,c,0,list.length-1);
}

char BinarySearchChar(char[] list,char c,int low,int high)
{
if(low>high)
return ' ';
if(high-low+1==2)
{
if(list[low]<=c && list[high]>c)
return list[high];

return list[0];
}
if(high-low+1==3)
{
if(list[low]==c)
return list[low+1];
if(list[low+1]==c)
return list[low+2];
if(list[low]<c && list[low+1]>c)
return list[low+1];
if(list[low+1]<c && list[low+2]>c)
return list[low+2];
//default case
return list[0];
}
int mid=low+high/2;
if(list[mid]==c)
return list[mid+1];
else if (list[mid-1]<c && list[mid]>c)
return list[mid];
else if(list[mid]<c && list[mid+1]>c)
return list[mid+1];
else if(list[mid]>c)
return BinarySearchChar(list,c,0,mid-1);
else if(list[mid]<c)
return BinarySearchChar(list,c,mid+1,high);

return list[0];
}

Please test your code for input char arr []={'a','c','e','g','i','j'}; and char c='f'.
O/p should be 'g' but your code gives o/p as 'i'