CareerCup

//
// 1. Brute force
//
// Computation time = N^3
//
bool hasTriangle1(int[] A)
{
  for (i = 0; i < N; i++)
  {
    for (j = 0; j < N; j++)
    {
      for (k = 0; k < N; k++)
      {
         // Need to skip cases where any two of i, j, k are equal

         // Now check conditions
         if (A[i] + A[j] > A[k] &&
             A[i] + A[k] > A[j] &&
             A[j] + A[k] > A[i)
         {
            return true;       // found one triangle!
         }
      }
    }
  }

  return false;                // not found any
} 


//
// 2. Use a property of triangle: 
//    If the sum of the smaller two sides > the longest side, it is.
//    (The other two conditions are automatically met)
//    Otherwise, it is NOT!
//
//    e.g. {1, 8, 10} ==> 1 + 8 < 10, so it is NOT a triangle
//         {3, 8, 10} ==> 3 + 8 > 10, so it is a triangle
//
//    Sort the array first, then iterate through the sorted array
//    as follows. Total computation time O(N^2)

bool hasTriangle2(int[] A)
{
   // Sort A[N] in ascending order => Computation time = O(NlogN)

   // iterate through ==> Computation time = O(N^2)
   for (i = 0; i < N - 2; i++)
   {
      for (j = i + 1; j < N - 1; j++)
      {
         if (A[i] + A[j] > A[j + 1])
         {
            return true;       // found one triangle!
         }
      }
   }

   return false;                // not found any
}

Sort the array in descending order.
starting from i=0
Check whether a[i+1] + a[i+2] > a[i]
if yes( return true)
else increment i.
if i is the last position, return false

Correct me if I am wrong but Sorting approach can't work as the indices returned would correspond to post sorted array and we have to return indices corresponding to presorted array...

Please somebody submit write code

public static void main(String[] args) {
try {
BufferedReader br = new BufferedReader(new InputStreamReader(
System.in));
String s = br.readLine();
String arr[] = s.split(" ");
int A[] = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
A[i] = new Integer(arr[i]);
}
Arrays.sort(A);
for (int i = 0; i < A.length; i++) {
for (int j = i + 1; j < A.length - 1; j++) {
if (A[i] + A[j] > A[j + 1]) {
if (A[j + 1] + A[j] > A[i]) {
if (A[j + 1] + A[i] > A[j]) {
System.out.println(1);
System.out.println(A[i] +" "+ A[j] +" "+ A[j + 1]);
System.exit(1);
}
}
}
}
}
System.out.println(0);

} catch (Exception e) {
e.printStackTrace();
}
}

#include<iostream>
#include <algorithm>
using namespace std;

int triangle ( const vector<int> &A ) {
//write your code here
unsigned int i=0;
vector <int> c;
c=A;
sort(c.begin(),c.end());
for(i=0;i<c.size();i++)
{
if( (c[i]+c[i+1])>c[i+2] && (c[i+1]+c[i+2])>c[i] && (c[i+2]+c[i])>c[i+1] )
{
if ((i+2)<=c.size() )
return 1;
}
}

return 0;
}