product of two number in a array

Given a array of n distinct integer. Find all pairs of x,y in the array such that z(given) = x * y...do it witho开发者_开发知识库ut sorting and in a most efficient manner..

[edit] Integer are within range of int i.e 0-65536 and numbers are non negative if that helps. Dont want to sort coz it will take a lot of time. Storage space is not a issue.

Here is linear time hash based solution:

Let hash be an array of size 65537 initilized to 0.

foreach element ele in Array

    if ele != 0
        hash[product/ele] = ele
    end-if

    if hash[ele] != 0 AND ele * hash[ele] == product
        print ele, product/ele
    end-if

end-foreach

There aren't any super efficient ways of doing this. The best I can think of is O(n^2):

Have an auxiliary function that takes a number (a) and a list, and goes through every element (b) checking a*b = z and saving the pair if it is.

Go through every element of your original list, and if a particular element (x) divides z (ie z % x = 0) then send x and the remainder of the list after x to the auxiliary function.

UPDATE:

I'm giving an O(n^2) solution because the question did not specify unique pairs. If only unique pairs are desired, this should be added to the question. Also, my solution assumes the order of pairs doesn't matter, which is another detail that should be clarified.

Iterate through the array...if an element x can divide z (ie z % x == 0), check if it's other factor y=(z/x) exists in the HashTable....

If it does, then you found a pair...else just add it to the hashTable and continue...