-2

My task is in the title.

I guess a good start could be to use a hash function that seperates all number >Z from all numbers smaller Z. That would take O(n) time. But afterwards I would need to sort all Elements

Olf
  • 374
  • 1
  • 20
DGIS
  • 111
  • 7
  • What is exactly the input and output? Is it given an array A of (?) numbers and an integer Z, is there two elements X and Y in A s.t. X+Y=Z ? – Olf May 31 '19 at 14:51
  • With my teacher I'm never 100% sure what he wants but I think there is an Array A given with numbers, int for example, and I'm supposed to write an algorithm which checks if there are any numbers X and Y s.t. X+Y=Z. Z is a random number. Can I sum two numbers in my array somehow s.t. I get Z. – DGIS May 31 '19 at 15:27
  • Yes so basically Dr Phil answer works. – Olf Jun 03 '19 at 14:55

1 Answers1

1

Given To paraphrase the question: given an array a with n numeric elements and a number Z find whether there are to elements a[x], a[y] such that a[x]+[y]=Z.

Approach: To do it in O(n) you could add each element to the array to a hash-set. - O(n).

Then another loop to check if Z-a[i] exists in the set another O(n) total O(n).

You can even combine the insertion and the check and do a few optimizations but it will still be O(n)

Dr Phil
  • 833
  • 6
  • 18
  • If that's indeed the question, then it's a duplicate. – Olf May 31 '19 at 14:58
  • @Olf if it is a duplicate can you link to the other answer/question? – Dr Phil May 31 '19 at 16:33
  • 1
    plenty : https://stackoverflow.com/questions/4720271/find-a-pair-of-elements-from-an-array-whose-sum-equals-a-given-number?rq=1https://stackoverflow.com/questions/5630363/find-two-elements-in-an-array-that-sum-to-k https://stackoverflow.com/questions/3815116/given-two-arrays-a-and-b-find-all-pairs-of-elements-a1-b1-such-that-a1-belong https://stackoverflow.com/questions/8373614/how-can-i-find-two-elements-in-an-array-that-sum-to-k – Olf Jun 03 '19 at 09:06
  • Good. Another paraphrasing – Dr Phil Jun 03 '19 at 13:08
  • I found a good solution I think. Thanks for your help :). But the links are not the same question I think. My task explicitly says "use Hashing". Non of the links use Hashing. – DGIS Jun 03 '19 at 15:59