hey vijay finding the two numbers if the array is sorted is known try to find for if the array is not sorted....
any one can help me in finding this
On 12/19/05, Vijay Venkat Raghavan N <[EMAIL PROTECTED]> wrote:
Hi,
I guess this has already been discuss in this forum before. Anyways let me give my algo here. Let us assume that the array is sorted in ascending order WLOG.
let low=1 and high=n index the first and last elements
while(low<high)
{
if a[low]+a[high] == z, done, so break off
if a[low]+a[high]<z need to increase sum, so low++;
3rd case, u need to decrease, so high--
}
hope this helps.
-Vijay
On 12/19/05, Uppala Babu <[EMAIL PROTECTED] > wrote:Hash map takes extra space if you want O(1) search..
Otherwise .. it takes time... any another solution...
in O(n) time with no extra space.. ;-)
On 12/19/05, Hemanth < [EMAIL PROTECTED] > wrote:
This answer is something like a bit vector based one.
Assume that the array is int[] num.
for(int i = 0; i < num.length; i++)
{
int otherNum = z - num[i];
// Search in a hashmap we maintain for 'otherNum'
// if 'otherNum' is present, then we are done
// else add 'num[i]' to the hashmap and proceed
// to the next iteration.
}
--
Arise awoke stop not till the goal is reached
