0
$\begingroup$

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)?

$\endgroup$
8
  • $\begingroup$ Often times, problems that involve multiplication can be turned into problems for addition by taking the logarithm. $\endgroup$
    – G. Bach
    Oct 24 '19 at 23:28
  • $\begingroup$ 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. $\endgroup$ Oct 24 '19 at 23:35
  • $\begingroup$ Only works for numbers > 0 though, so if there's negative numbers involved you'll have to make case distinctions based on sign $\endgroup$
    – G. Bach
    Oct 24 '19 at 23:36
  • 1
    $\begingroup$ (Then again, the approach "known" for addition/sum works for multiplication/product without taking the logarithm, too - only thing used is monotonicity.) $\endgroup$
    – greybeard
    Oct 25 '19 at 3:01
  • $\begingroup$ @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. $\endgroup$ Oct 25 '19 at 4:37
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

So you don’t start with minnErr = one billion. You start with minn = (1,1) and minnErr = error for a[1], a[1].

Then you split the array into positive and negative numbers. You examine the product of the smallest positive numbers, the largest negative numbers, and the largest negative times the smallest positive.

When that is done, if val > 0, you examine pairs of positive numbers, and pairs of negative numbers as before. But if val < 0, then you examine the products of negative and positive numbers, starting with the smallest negative and smallest positive numbers and proceeding to the largest ones. The order of the numbers must be reversed for this.

(Why so complicated? Say val = 1. If the positive numbers at all around 1,000 and the negative ones around -10^12 with the exception of one value -0.001, then the closest is -0.001 * 1000 = -1 even though it is negative).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.