Problem 1: Suppose you are given an array A of length n and a number z. Find an
ID: 3867236 • Letter: P
Question
Problem 1: Suppose you are given an array A of length n and a number z. Find an algorithm that determines whether there are any two numbers x and y in the array A such that x + y == z. If so, your algorithm should return those numbers; otherwise, it can return NIL. Your algorithm should run in time O(nlg(n)) and use no more than O(n) storage.
Problem 1: Suppose you are given an array A of length n and a number z. Find an algorith m that determines whether there are any two numbers x and y in the array A such that x + y = z. If so, your algorithm should return those numbers; otherwise, it can return NIL. Your algorithm than O(n) storage.Explanation / Answer
For this algorithm we will use a hash table. A hash table is a data structure where elements are stored as a key and value pair. For example hash(key) = value, maps the key to the value.
x + y = z.
z is specified to us already. So if we find an x in the array and if we want to know whether there is another number such that its sum with x is z, we should check for whether there is z - x in the array as well. If yes then x + (z-x) = z. So the other number is z-x.
A formal algorithm to do so is as follows:
1. For i in range(0,n):
hash(A[i]) = i
2. For i in range(0,n);
if hash(z - x) != i:
return x, z-x
3. return null