Question

Given an unsorted array of distinct positive integers A[1..n] in the range between 1 and 10000 and an integer i in the same range. Here n can be arbitrary large. You want to find out whether there are 2 elements of the array that add up to i. Give an algorithm that runs in time O(n).

Answer 1

Answer:

Explanation:

Arbitrary means That no restrictions where placed on the number rather still each number is finite and has finite length. For the answer to the question--

Find(A,n,i)

for j =0 to 10000 do

frequency[j]=0

for j=1 to n do

frequency[A[j]]= frequency[A[j]]+1

for j =1 to n do

if i>=A[j] then

if (i-A[j])!=A[j] and frequency[i-A[j]]>0 then

return true

else if (i-A[j])==A[j] and frequency[j-A[j]]>1 then

return true

else

if (A[j]-i)!=A[j] and frequency[A[j]-i]>0 then

return true

else if (A[j]-i)==A[j] and frequency[A[j]-i]>1 then

return true

return false