Simply sort the array and check for a[i]+a[i+1] > a[i+2] for i=0 to n-3.
Sanju :) On Sun, Aug 21, 2011 at 7:28 AM, sarvesh saran <aquarian.thun...@gmail.com>wrote: > No idea how to solve the problem except the brute force O(n3) approach.I > am looking for a better solution than this. Because of O(1) complexity you > cannot copy and sort the input. > > > A zero-indexed array A consisting of N integers is given. A triplet (P, Q, > R) is triangular if and > A[P] + A[Q] > A[R], > A[Q] + A[R] > A[P], > A[R] + A[P] > A[Q]. > > For example, consider array A such that > > A[0] = 10 A[1] = 2 A[2] = 5 > A[3] = 1 A[4] = 8 A[5] = 20 > Triplet (0, 2, 4) is triangular. > > public int triangle(int[] A) > > that, given a zero-indexed array A consisting of N integers, returns 1 if > there exists a triangular triplet for this array and returns 0 otherwise. > > Assume that: > > N is an integer within the range [0..100,000]; > each element of array A is an integer within the > range[-2,147,483,648..2,147,483,647]. > For example, given array A such that > > A[0] = 10 A[1] = 2 A[2] = 5 > A[3] = 1 A[4] = 8 A[5] = 20 > the function should return 1, as explained above. Given arrayA such that > > A[0] = 10 A[1] = 50 A[2] = 5 > A[3] = 1 > the function should return 0. > Expected worst-case time complexity: O(n log n) > Expected worst-case space complexity: O(1) > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
