Find two numbers in sorted array whose product is close to N

Given a sorted array of numbers, is there a good algorithm for finding two numbers in that array whose product is as close as possible to a given number N?

I know that there is a good O(n) (?) algorithm for the related problem of finding two numbers that sum to a given number N. You begin with ptr1 at the start of the array and ptr2 at the end, and if *ptr1 + *ptr2 > N you decrement ptr2, else increment ptr1.

But for multiplication, it feels possible this method could "miss" the optimal solution by overshooting it somehow? Is there a good way to solve the multiplication variant in something that isn't just O(n^2)?

• Often times, problems that involve multiplication can be turned into problems for addition by taking the logarithm. Oct 24 '19 at 23:28
• Oh I see! That's pretty clever. So I guess my intuition is here is just completely wrong. It seems you can solve this in just the same way as the sum-variant by imagining you have taken the log of everything. Actually, this makes me wonder if this is true for any function of two variables that is monotonic in either one (holding the other variable fixed)? That seems true of both sum and product. Oct 24 '19 at 23:35
• Only works for numbers > 0 though, so if there's negative numbers involved you'll have to make case distinctions based on sign Oct 24 '19 at 23:36
• (Then again, the approach "known" for addition/sum works for multiplication/product without taking the logarithm, too - only thing used is monotonicity.) Oct 25 '19 at 3:01
• @greybeard: In case of addition also I think it might miss an optimal solution. Because here we don't have to find pair of value which has sum exactly equal to given value. May be I'm misunderstanding your approach. Can you elaborate more so that I can verify weather I'm talking about same approach as yours. Oct 25 '19 at 4:37

This answer is compilation of above comments but this include reasoning why this algorithm works.

1. find(A, val)
2.    start = 1
3.    end = A.length
4.    minn = (start,end)                //minn is pair used to store answer
5.    minnErr =   |A[start]*A[end]-val|        //minnErr is difference between best
//pair of values seen so far and targate value.
6.    while(start < end)
7.        if (|A[start]*A[end]-val| < minnErr) //if this pair of values is
//even better than remember it.
8.            minnErr = |A[start]*A[end]-val|
9.            minn = (start, end)

10.       if A[start]*A[end] > val:              // here
11.           end = end - 1
12.       elif A[start]*A[end] < val:
13.           start = start + 1
14.       else:
15.              break
16. return minn

Algorithm works as follows:

here answer is pair of indices of element of array which has product closest to target value.

• We keep two pointers $$start$$ and $$end$$. Which are initialized to $$1$$ and $$array\space size$$ respectively.
• Now in every iteration we compare $$A[start] * A[end]$$ with $$minnErr$$.
• If current pair have better solution than we record it.
• If $$A[start]*A[end] < val$$ than we increase $$start$$ by $$1$$. Now note that all $$(i,j): i< start, j\le end$$ can never be solution because for any such $$(i,j)$$ we have $$A[i]*A[j] \le A[start]*A[end] < val$$.

• if $$A[start]*A[end] > val$$ than we decrease $$end$$ by $$1$$. Now here(considering decremented value of $$end$$) all $$(i,j): i\ge start, j>end$$ can never be solution because for any such $$(i,j)$$ we have $$A[i]*A[j] \ge A[start]*A[end] > val$$.

• if $$A[start]*A[end] = val$$ than we stop here as this is best solution.

credits: @G. Bach, @greybeard

Vimal’s answer is a start. In real live you want to get it right if no product is within a billion of val, and you want to get it right if the arrays contain negative values, or if val is negative itself.