CODEWITHSUNDEEP
javaalgorithmperformancetimetime-limiting
yobro97
yobro97

Reputation: 1145

Number of ways one cannot make a triangle?

Given n and an array of n positive integers, the number of ways one can choose three numbers such that they cannot form a triangle is needed.

Example: 

3  
4 2 10

Answer: 

1

My approach (in JAVA)

int[] arr = new int[n];//list of the numbers given
int count=0;//count of all such triplets
for(int i=0;i<n;i++)
    arr[i]=sc.nextInt();
Arrays.sort(arr);
for(int i=n-1;i>=0;i--)
{
    int j=0;
    int k= i-1;
     while(j<k && k>=0)
     {
         if(arr[i]>=arr[j]+arr[k])//condition for no triangle formation
          {
              count++;
              j++;//checking the next possible triplet by varying the third number
          }
          else if(arr[i]<arr[j]+arr[k])
          {
              j=0;
              k--;//now varying the second number if no such third number exists
          }
     }
}
System.out.println(count);

My algorithm:

After sorting the list I am trying to find all the numbers less then arr[i] such that arr[i]>=arr[j]+arr[k], in which case the triangle will not form.

But I am getting timed-out for this solution. Could anyone suggest a better approach to this problem?

Upvotes: 1

Views: 241

Answers (2)

xenteros
xenteros

Reputation: 15842

The appropriate pseudo-code would be:

SORT array //nlogn
INT counter = n*(n-1)*(n-2)/6;
FOR i = n - 1; i >= 2; i-- DO //largest length in a triangle - there must be two lower
    currentLargestNumber = array[i];
    FOR j = i - 1; j >= 1; j-- DO
        BINARY SEARCH FOR SMALLEST k for which array[k] + array[j] > array[i]
        counter -= j - k;
        IF nothingAddedInTheLastIteration DO
            BREAK;
        END_IF
    END_FOR
    IF nothingAddedInTheLastIteration DO
        BREAK;
    END_IF
END_FOR

I assumed that there won't be input with more then 3 identical values. If there is such possibility remove unnecessary values.

In each loop you should check if any triangle was added. If not, break this loop.

Upvotes: 3

Yerken
Yerken

Reputation: 1942

The problem can be solved using two pointer technique, but instead of counting how many triplets cannot form a triangle, we will look for the opposite and at the end subtract the result from C(n,3) = (n)(n-1)(n-2)/6. Let's sort the array arr, arr[0] < arr[1] .. < arr[n-1]. And for a given pair i < j find index k > j, s.t. arr[i] + arr[j] <= arr[k] and arr[i] + arr[j] > arr[k-1]. This will result in additional k - j -1 triplets (triplets are : {i,j,j+1},{i,j,j+2},..,{i,j,k-1}. Now notice that whenever we increase j, we don't need to reset the value of k, which helps to keep the total time complexity O(n^2). 

//arr is already sorted
long triangles = 0;
for(int i = 0; i < n-2; i++){
   int k = i + 2;
   for(int j = i + 1; j < n; j++){
      while(arr[i] + arr[j] > arr[k] && k < n){
         k++;
      }
      triangles += k-j-1;
   }
} 
long answer = n*(n-1)*(n-2)/6 - triangles;

Upvotes: 1

Related Questions