Sort the array first and then check for the given conditions. Sorting the array takes O(nlog n) in the worst case.
Sanjay Kumar B.Tech Final Year Department of Computer Engineering National Institute of Technology Kurukshetra Kurukshetra - 136119 Haryana, India On Tue, Aug 16, 2011 at 6:16 PM, Raghavan <its...@gmail.com> wrote: > > 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) > > > -- > Thanks and Regards, > Raghavan KL > > > > > -- > Thanks and Regards, > Raghavan KL > > -- > 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.
