An O(n) solution exists only for the cases where we need to find TWO numbers
in an array whose sum =X .
start from the first element of the array and keep a hashtable to store the
potential pairs. We will check if sum – (a[i]) already exists in the
Hashtable. If yes, we have a pair (a[i], value from hashtable) as the pair
with the sum. If no, we store a[i] in the hashtable.
array a= {1,2,3,4,5,6,7,8} and sum = 6.
6 – 1 = 5 — found in Hashtable H ? No – store it in H. H will contain (1)
6 –2 = 4 – found in Hashtable H ? No – store it in H. H will contain (1, 2)
6 –3 = 4 – found in Hashtable H ? No – store it in H. H will contain (1, 2,
3)
6 –4 = 2 – found in Hashtable H ? Yes – now we have a pair (a[i] , found in
H) – (4,2)
6 –5 = 1 – found in Hashtable H ? Yes – now we have a pair (a[i] , found in
H) – (5,1)
On Sun, Aug 7, 2011 at 10:23 PM, Prakash D <[email protected]> wrote:
> is there a faster algo than O(n^2)?
>
>
> On Sun, Aug 7, 2011 at 4:14 PM, raj kumar <[email protected]> wrote:
>
>> similar to make change dp problem
>>
>> --
>> 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.
