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).

Question

Engineering

Jaidyn Mayer

20 July, 20:43

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).

+4

Answers (1)

Know the Answer?

Shaun · Answer 1

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