CareerCup

use hash table,
in linear time.

Let N = given number
1. Sort the array into ascending order. O(n logn)
2. For every number(n) in the array search for (N-n) using Binary
search. [n* O(logn) = O(n logn)]
3. If found : return success
else failure
Total runtime = O(n logn)

Nice solution!
Works for negative numbers, positive and their mix in the array..

Sort array A of n numbers
Keep one pointer p at n/2 number
Keep second pointer q at n/2+1 number
Take sum of the two numbers S = A[p]+A[q]
while(p>=0 and q<n)
{
if(A[p]==A[q])
return true
while(S>N&&p>0)//N is required sum
{
p--;
S=A[p]+A[q];
}
while(S<N&&q<n-1)
{
q++;
S=A[p]+A[q];
}
}
return false;
End

How can we use the hash table. Can anyone plese explain??

a). Sort the array in O(NlogN) time.
b). Start i=0 and j=last element. and lets call the sum required to be S.
c). Calculate a[i] + a[j] and
1). If a[i] + a[j] > S, then decrement j
2). If a[i] + a[j] < S, then increment i
3). If a[i] == a[j], you have the answer
d). repeat until i < j.

using hash table:
(assume the given number is N)

for each number in the array:
- check if there is a key (N-number) in the hash table
- insert it to hash table as the number is the key

linear time

1). Sort the array. (NlogN)
2). For each number x, find s-x using binery search. (N*logN).

Not any better. But an alternative.

the smart answer is to use binary search after sorting the list.

sort the array(O(nlogn))
keep two index variables one at each end of the sorted array
if the sum of values at the two indices is less than given value increment left variable ;else if it is greater than given value decrement the right variable; else,
we have found the variables.
continue this until the two index variables cross in which case no two integers sum up to given value.