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.
