Hi Sanjay, The input is a constant vector. So it cannot be modified. Space requirement is O(1) so it cannot be copied.
thanks, Sarvesh On Sun, Aug 21, 2011 at 8:04 PM, Sanjay Rajpal <srn...@gmail.com> wrote: > By O(1) we mean that we can use variables, can't use something that equals > size of the i/p array. > > Use Quick sort, sorting is done in-place which O(n log n) in time, and O(1) > in space. > Sanju > :) > > > > On Sun, Aug 21, 2011 at 7:31 AM, sarvesh saran <aquarian.thun...@gmail.com > > wrote: > >> Hi Sanjay, >> >> *Because of O(1) complexity you cannot copy and sort the input array. >> >> *thanks, >> Sarvesh >> * >> * >> >> On Sun, Aug 21, 2011 at 8:00 PM, Sanjay Rajpal <srn...@gmail.com> wrote: >> >>> 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. >>> >> >> -- >> 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. > -- 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.
