+1 for dave's solution.i will also do the same
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://youtube.com/amolsharma99
On Tue, Aug 23,
A[0] = 10A[1] = 2A[2] = 5
A[3] = 1A[4] = 8A[5] = 20
Triplet 10,5,8 is triangular.
Dave, do your solution do it?
On Tue, Aug 23, 2011 at 11:55 AM, Amol Sharma amolsharm...@gmail.comwrote:
+1 for dave's solution.i will also do the same
--
Amol Sharma
Third Year
mofified array will be
C[0]=1 C[1]=2 C[2]=5 C[3]=8 C[4]=10 C[5]=20
@saurabh: obviously it does!
@Dave: no need of extra space also u can use quicksort. I think if
u r using extra space, U can do it in linear time using radixsort
(correct me if I'm wrong).
On Aug 23, 11:44 am, Raghavan
@dave: sorry I overlooked the constraint u cannot modify the array
space is mandatory then.
On Aug 23, 12:07 pm, darklord darklord@gmail.com wrote:
mofified array will be
C[0]=1 C[1]=2 C[2]=5 C[3]=8 C[4]=10 C[5]=20
@saurabh: obviously it does!
@Dave: no need of extra space also u
This problem is already discussed in one of the earlier posts.
Sanju
:)
On Tue, Aug 23, 2011 at 12:15 AM, darklord darklord@gmail.com wrote:
@dave: sorry I overlooked the constraint u cannot modify the array
space is mandatory then.
On Aug 23, 12:07 pm, darklord
@Saurabh: If you can use O(n) extra space, make a copy of the array
and sort it: O(n log n). Then, if there is a solution, there will be a
solution of the form (a[i], a[i+1], a[i+2]), where 0 = i n-2,
which can be checked with a simple for loop: O(n). Thus, the
complexity is O(n log n).
Dave