1

I am being given the lengths of a few lines and I am required to find how many of those will form a triangle

The Input is like this

7 
1 4 13 2 25 6 11

where 7 is the no. of lines and the following lines contains length of all the lines.

This is what my code looks like at its core

    for(int i=0;i<n-2;i++){ //n is the total no. of lines given initially
        for(int j=i+1;j<n-1;j++){
            for(int k=j+1;k<n;k++){
                if(l[i]+l[j]>l[k]){
                    noOfTriangles++;
                }else{
                    break;
                }   
            }
        }
    }

And even though the code works as expected, right now it takes time of the order of n^3 which exceeds the time limit for some inputs . Anyway I could optimise it?

EDIT: I forgot to mention I have first sorted my array before implementing nested-for loop.

Krash
  • 2,085
  • 3
  • 13
  • 36
  • what do u want, total possible triangles combinations or the maximum number of triangles that can be made using all lines?? – Rajeev Singh Feb 27 '17 at 12:57
  • You may first sort your input. – Jarod42 Feb 27 '17 at 12:57
  • Maybe a sorted array like on [this question](http://stackoverflow.com/questions/11227809/why-is-it-faster-to-process-a-sorted-array-than-an-unsorted-array) could be a good approach. I would recommend to add the tags `optimization` and `performance`. – izlin Feb 27 '17 at 12:59
  • I forgot to mention that I have sorted the input before using the nested loops. – Krash Feb 27 '17 at 13:01
  • @RajeevSingh Maximum number of triangles possible taking 3 lines at a time. – Krash Feb 27 '17 at 13:05

0 Answers0