Question

Let A[1..n] be an array of positive integers (A may not be sorted). Pinocchio claims that there exists an O(n)-time algorithm that decides if there are two integers in A whose sum is 1000. Is Pinocchio right, or will his nose grow? If you say Pinocchio is right, explain how it can be done in O(n) time; otherwise, argue why it is impossible.

Answer 1

`Hey,

Note: Brother if you have any queries related the answer please do comment. I would be very happy to resolve all your queries.

Yes, Pinocchio is correct!
We required an extra space which takes O(n) space complexity and we iterated the array twice by both with respective to n i.e O(n) time complexity. 
hence the time complexity is O(n).

Algorithm

(Use Hashing)
This method works in O(n) time.

1) Initialize an empty hash table s.
2) Do following for each element A[i] in A[]
   (a)    If s[1000 - A[i]] is set then print the pair (A[i], 1000 - A[i])
   (b)    Insert A[i] into s.

Kindly revert for any queries

Thanks.