thanks a lot sanjay! will try that immediately. I have another problem to solve. It has a rather long description? Can I send you an email for it instead?
thanks, Sarvesh On Sun, Aug 21, 2011 at 8:59 PM, Sanjay Rajpal <srn...@gmail.com> wrote: > after sorting the array, check if the sum of first two elements in sorted > array is > third element, if it is true, then all the conditions will hold, > otherwise proceed with 2nd,3rd and 4th element. > > keep doing till u find a triplet, there u break out of the loop. > Sanju > :) > > > > On Sun, Aug 21, 2011 at 8:24 AM, sarvesh saran <aquarian.thun...@gmail.com > > wrote: > >> Hi Sanjay, >> >> Yes. That makes sense. >> >> What do I do after the array is sorted? >> >> >> thanks, >> Sarvesh >> >> >> On Sun, Aug 21, 2011 at 8:40 PM, Sanjay Rajpal <srn...@gmail.com> wrote: >> >>> if u r saying i/p array can't be modified and complexity O(n logn)time >>> and O(1) space, then i dont there exists any way to do that. >>> >>> if complexity is not the matter, then brute force way of three nested >>> loops is the solution O(n^3) since here the original array will not be >>> modified. >>> >>> >>> Sanju >>> :) >>> >>> >>> >>> On Sun, Aug 21, 2011 at 7:48 AM, sarvesh saran < >>> aquarian.thun...@gmail.com> wrote: >>> >>>> Hi, >>>> >>>> I have posted this in stackoverflow. So you may choose to join here as >>>> well (this question was asked in an adobe written test) >>>> >>>> >>>> http://stackoverflow.com/questions/7138874/find-triangular-triplet-in-an-array >>>> >>>> thanks, >>>> Sarvesh >>>> >>>> >>>> On Sun, Aug 21, 2011 at 8:09 PM, sarvesh saran < >>>> aquarian.thun...@gmail.com> wrote: >>>> >>>>> Hi Sanjay >>>>> >>>>> I think i forgot to mention that in my original post..so sorry about >>>>> that. It is a constant array and should not be modified. >>>>> >>>>> thanks, >>>>> Sarvesh >>>>> >>>>> >>>>> >>>>> >>>>> On Sun, Aug 21, 2011 at 8:08 PM, sarvesh saran < >>>>> aquarian.thun...@gmail.com> wrote: >>>>> >>>>>> 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. >>>> >>> >>> -- >>> 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.
