Here is an O(N^2) algorithm:
1. Sort both A and B. (O(NlogN) or O(N^2), either will work)
2. For each element C[k] in C, find if there is such (i,j) pair that
A[i] + B[j] = -C[k]:
Start with i = 0 and j = N-1, and loop through the following:
a. if A[i] + B[j] > -C[k], then j = j-1;
b
we can use binary search algorithm to find the "z"
( sorting ll take O(n log n ) but it is very less compared to n^2 * log n )
-- Prashant Kulkarni
On Wed, Dec 15, 2010 at 3:32 PM, Ankur Murarka
wrote:
> wouldn't your algo take n^3 time as well given the fact that the lists are
> not sorted?
@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 wrote:
> Hi,
> Very good question.
>
> i think very knows brute-force soln of n^3 time complexity.
>
> here is a alternative method/s
wouldn't your algo take n^3 time as well given the fact that the lists are
not sorted? searching for the matching value fr z should be taking O(n) time
and to do so for each pair of x and y shall take O(n^2).
Please correct me if i got something wrong here
On Wed, Dec 15, 2010 at 11:44 AM, Prashan
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
no not sorted
On 15 December 2010 11:37, Anand wrote:
> @Divya, I think you ask this question before. Not sure of the answer though
> :)
>
>
> On Tue, Dec 14, 2010 at 9:06 PM, Soumya Prasad Ukil > wrote:
>
>> Are the linked list sorted?
>>
>>
>> On 14 December 2010 05:33, divya wrote:
>>
>>> G
@Divya, I think you ask this question before. Not sure of the answer though
:)
On Tue, Dec 14, 2010 at 9:06 PM, Soumya Prasad Ukil
wrote:
> Are the linked list sorted?
>
>
> On 14 December 2010 05:33, divya wrote:
>
>> Given three lists: A, B and C of length n each. Write a function which
>> ret
Are the linked list sorted?
On 14 December 2010 05:33, divya 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
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.
