Hello Divya
Here goes my algorithm:
Approach 1:
Sort C array - O(N Log N)
For each element in A with each element in B
- Try to find -(A[i] + B[j]) in C array using Binary Search -
- If found print A[i], B[i], C[k]
Total Time Complexity = O(Nlog N) + O(N^2 log N) = O(N^2 log N)
Approach 2:
If there is O(N) Space available then modify the above algo as
follows:
Instead of sorting, store all elements in C in a hashtable
Remaining thing is same.
Time Complexity : O(N^2) and Space Complexity - O(N)
On Dec 15, 3:23 pm, Soumya Prasad Ukil <ukil.sou...@gmail.com> wrote:
> @prashant
>
> How does log(n) come in your algo? I think yours is O(n^3).
> Using Hashtable,if allowed, reduces complexity.
>
> On 14 December 2010 22:14, Prashant Kulkarni <prashant.r.k...@gmail.com>wrote:
>
>
>
>
>
> > Hi,
> > Very good question.
>
> > i think very knows brute-force soln of n^3 time complexity.
>
> > here is a alternative method/soln of O(n^2 * log(n)) time complexity Algo
>
> > 1) pick any number from list A (One by one)...... let say 'x'
>
> > 2) pick any number from list B (one by one )...... let say 'y'
>
> > 3) z=x+y
>
> > 4)look for 'z' in the list by considering all numbers as unsigned if u
> > found then check sign of that number it be opposite of 'z' if so return 1
> > else 0
>
> > [above steps is repeated for all elements]
>
> > *correct me if I am wrong*
>
> > --
> > Prashant Kulkarni
> > IISc Bangalore
>
> > On Wed, Dec 15, 2010 at 10:36 AM, Soumya Prasad Ukil <
> > ukil.sou...@gmail.com> wrote:
>
> >> Are the linked list sorted?
>
> >> On 14 December 2010 05:33, divya <sweetdivya....@gmail.com> wrote:
>
> >>> 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.
>
> >>> --
> >>> 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<algogeeks%2bunsubscr...@googlegroups.com>
> >>> .
> >>> For more options, visit this group at
> >>>http://groups.google.com/group/algogeeks?hl=en.
>
> >> --
> >> regards,
> >> soumya prasad ukil
>
> >> --
> >> 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<algogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> regards,
> soumya prasad ukil- Hide quoted text -
>
> - Show quoted text -
--
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 options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
