Light OJ 1307 - Counting Triangles Solution

The time complexity can be greatly reduced using Two Pointer methods in just two nested loops.

• Approach: First sort the array, and run a nested loop, fix an index and then try to fix an upper and lower index within which we can use all the lengths to form a triangle with that fixed index.
• Algorithm:
  1. Sort the array and then take three variables l, r and i, pointing to start, end-1 and array element starting from end of the array.
  2. Traverse the array from end (n-1 to 1), and for each iteration keep the value of l = 0 and r = i-1
  3. Now if a triangle can be formed using arr[l] and arr[r] then triangles can obviously formed
     from a[l+1], a[l+2]…..a[r-1], arr[r] and a[i], because the array is sorted , which can be directly calculated using (r-l). and then decrement the value of r and continue the loop till l is less than r
  4. If triangle cannot be formed using arr[l] and arr[r] then increment the value of r and continue the loop till l is less than r
  5. So the overall complexity of iterating
     through all array elements reduces.

 

Solution in C++:

///**********ALLAH IS ALMIGHTY************///
///AH Tonmoy
///Department of CSE,23rd batch
///Islamic University,Bangladesh

1. #include<bits/stdc++.h>
2. using namespace std;
3. int main()
4. {
5.     int n,i,t,k;
6.     cin>>t;
7.     for(k=1; k<=t; k++)
8.     {
9.         cin>>n;
10.         int ar[n+1];
11.         for(i=0; i<n; i++)
12.         {
13.             cin>>ar[i];
14.         }
15.         sort(ar,ar+n);
16.         int l,r;
17.         int cnt=0;
18.         for(i=n-1; i>=1; i--)
19.         {
20.             l=0;
21.             r=i-1;
22.             while(r>l)
23.             {
24.                 if(ar[l]+ar[r]>ar[i])
25.                 {
26.                     cnt+=(r-l);
27.                     r--;
28.                 }
29.                 else
30.                     l++;
31.             }
32.  
33.         }
34.         printf("Case %d: %d\n",k,cnt);
35.     }
36.     return 0;
37. }