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 <[email protected]> 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 <[email protected] > > 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 < >> [email protected]> 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 < >>> [email protected]> 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 <[email protected]>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 < >>>>> [email protected]> 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 <[email protected]>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 < >>>>>>> [email protected]> 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 [email protected]. >>>>>>>> To unsubscribe from this group, send email to >>>>>>>> [email protected]. >>>>>>>> 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 [email protected]. >>>>>>> To unsubscribe from this group, send email to >>>>>>> [email protected]. >>>>>>> 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 [email protected]. >>>>>> To unsubscribe from this group, send email to >>>>>> [email protected]. >>>>>> 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 [email protected]. >>>>> To unsubscribe from this group, send email to >>>>> [email protected]. >>>>> 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
