@sharad
Can you explain the O(n*n) + O(n) space algorithm that you
mentioned?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email
@senthilnathan
prepare a hash table for the third array
now pick any element 4m array 1 add it to 1 element of array 2 now try to
find -(m+n) in hash table
since every element of arr1 will be sum to every arr of array2 and lookup in
hash table to be O(1)
so overall complexity will be O(n2)
@ Amir:
I think you cannot find two numbers in B and C such that their sum is -A[k]
in O(n) in all cases with the logic that you mentioned.
for instance you can try with :
A : 2 7 8 10
B :-2, 0, 1, 9
C: -7 -2 1 3
On Wed, Jun 16, 2010 at 5:56 AM, Amir hossein Shahriari
@algoose chase: you're right thx for the test case
On Wed, Jun 16, 2010 at 11:45 AM, Algoose Chase harishp...@gmail.comwrote:
@ Amir:
I think you cannot find two numbers in B and C such that their sum is -A[k]
in O(n) in all cases with the logic that you mentioned.
for instance you can try
sort array c only.
now select every pair from array a nd b ( o(n2))
for every pair find the element from c which gives sum of the three element
0. ( search using binary search as c is sorted)
so the algo is O (n^2 logn))
On 16 June 2010 13:47, Amir hossein Shahriari
@^ he has already asked to optimize n^2logn solution
On Wed, Jun 16, 2010 at 5:25 PM, divya jain sweetdivya@gmail.comwrote:
sort array c only.
now select every pair from array a nd b ( o(n2))
for every pair find the element from c which gives sum of the three element
0. ( search using
plzzz comment on this question
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more
sort all arrays
for each number in A , A[k]
find two numbers in B and C such that their sum is -A[k]
this can be done in O(n) time:
set i at the beginning of B and j at the end of C
while in or j=0
if ( B[i] + C[j] == -A[k] ) return true
if ( B[i] + C[j] -A[k] ) increase i
else decrease
Given three lists: A, B and C of length n each. Write a function which
returns true if any 3 three numbers (1 from each list), sum up to
zero. Else return false, if there is no such combination.
both o(n2)+o(n)space
and o(n2logn)+o(1)space
are trivial but can we optimise more
--
You received
