csTechie

One Comment

1. syam says:

   October 28, 2009 at 8:57 pm

   Using a Hashmap
   1. Use a hashmap H
   2. for each A[i] in A set H[S-A[i]]=i  [n Times]
   3. for each A[i] in A check whether A[i] exists in H
           if yes print A[i] and A[H[A[i]]] as the answer. [n Times]
   Total Complexity O(2n)=O(n) provided Hashing functions have O(1) complexity.
   Note: just to see if 2 elements add up to S we can use a Hashtable as well.
   And then an extra iteration to find the 2 elements in another pass.
   
   Solution by Sorting
   1. Sort the array A
   2. 2 pointers f and l
   3. f set to front element of the array
   4. l set to last element of the array
   5. REPEAT till fS)l=l-1
   6. If execution reaches here print NO SUCH 2 NUMBERS EXISTS