# Find pairs in an array that when multiplied to each other gives you sum x

So this is the pseudo code I came up with but the run time is very slow. Is there a way to write this code to get it in terms of O(n)?

First for loop (starts at 0) grabs the first value of the array and the second for loop is nested inside the first for loop (starts at j =i+1). The second for loop runs through and checks if the second value times the first value is equivalent to x, if not, then there are no pairs.

How would I write this to get the run time down to O(n)?

• Can you edit the question to include a description of what algorithmic task you're trying to achieve? What is the input, and what is the desired output? I can't understand what the title is trying to say, and the title isn't the right place to put critical details: the title should be a summary of the question, but you should include all relevant information in the body. In the body of your question you have space to provide a careful explanation of what you're trying to achieve. – D.W. Oct 2 '15 at 16:57
• Also, note that you can use Markdown and LaTeX to format your pseudocode. That might be easier to read than an English description of some pseudocode. – D.W. Oct 2 '15 at 16:58
• Multiply would be a product not a sum – paparazzo Feb 4 '17 at 12:35

You can use a hash map to index already visited elements:

for ai in A
if hash[x/ai] // product = x
hash[ai] = true
end


Which is $\mathcal{O}(n)$ in time.

I'm not sure that $O(n)$ is possible. A good trick is to sort the array (in $O(n\log n)$), then have 2 pointers in to the array, one at the start and one at the end. These two numbers give you the smallest number times the biggest number. What does it mean if the resulting product is smaller (or bigger) than the target?

I can think of O(nlogn) complexity. Sort the array in O(nlogn) time, have two pointers( say head and tail ), head pointing to the first element and tail pointing to the last element of the sorted array. Now, run a for loop i.e O(n) , in which multiply the head and the tail element, if (product = sum) then output head and tail elements, else if (product < sum) then increment head. Else decrement tail.

• That's essentially Tom's answer. – Raphael Oct 2 '15 at 20:10
• Tom hadn't explained as to what would be done if the product was lesser or greater than the sum. – Mohammad Yaqoob Oct 2 '15 at 20:13
• Yes, probably he did not want to encourage the problem-dumpy style of the question (which is what full answers do). The idea should be enough for an asker who wants to learn, i.e. is willing to think independently. – Raphael Oct 2 '15 at 20:14
• Oops. True. But was just trying to help as much as possible. – Mohammad Yaqoob Oct 2 '15 at 20:16
• And that is appreciated. :) (Note that once you have earned some rep, you can comment on others' posts to propose clarifications. Even now, you can propose edits. Not that this applied here, but I thought you should know.) – Raphael Oct 2 '15 at 20:24