tashageek

 Profile Answers by tashageek 

• Jun 7th, 2008

 

if you hold an array of size M initialized to 0. you can go once over a and for each a[i] set arr[a[i]] to be 1. Then you can loop from M down to 1 and check whether arr[M-j]&&arr[j] if so return true if loop is finished return false. Same could be done using a hash table instead of an array (will save memory)

tashageek

 Profile Answers by tashageek 

• Jun 7th, 2008

 

actually using a hash there is a better solution . you inititate the hash with all values from a. and then you go over a again and check if the complementry of a[j] ie M-a[j] is in the hash. this way the complexity is O(n) and not O(M+n)

guitarfox

 Profile Answers by guitarfox 

• Jun 19th, 2008

 

a(x) + a(y) = MGiven a1, a2, .... a(n) integers & M, return true or false if there exist a(x) + a(y) = M

Once you're done, do it using a hash table.

actually using a hash there is a better solution . you inititate the hash with all values from a. and then you go over a again and check if the complementry of a[j] ie M-a[j] is in the hash. this way the complexity is O(n) and not O(M+n)

You are almost there.

consider the following algrithm

for( i = 0 ; i < n ++ i)
{
     diff = M - a(i);
    if ( search( a(i), hash ) )  /* see if a(i) is in the hash table */
    {
        return true;  /* if found, return true */
    }
    else
    {
        insert( diff, hash);    /* if not found, insert the complementary of a(i) in the table */
    }
}

so that you only have to go through list a() once to acomplish the task.

If the list contains the objective, you don't even have to see the end of the a list ;)