For a week and a half in small raids we have been thinking how to solve it. Maybe someone here can :)

Two arrays of natural numbers are given: x and y (both arrays are non-decreasing) and a positive integer Q

Find numbers from these arrays such that x[i] * y[j] as close to Q as possible.

The complexity should not exceed O(n+m) , where n and m are the size of the arrays.

  • x [i] * y [i] no typo here? - ReinRaus
  • I don't know if this is a typo. Here I meant that both elements must be from different arrays. Thank you for noticing, this could further confuse :) - alex91
  • Should it be something so as not to confuse? x [k] * y [m] - ReinRaus
  • Yes. It will do. Any thoughts on a solution? We tried to go from different sides of both arrays, it seems that the solution is not bad, I can’t understand how to go on there. - alex91
  • one
    @ReinRaus: post as answer? - VladD

2 answers 2

We look through one array from the head, the other from the tail.
Moving along the second array from the tail to the head, keeping two values ​​- the current work and the previous one
when the current work is less than Q, then we find which product is closer to the desired one - the current, previous or previously saved as the nearest
move the first array from head to tail by one position and repeat the movement along the second array until the current work again becomes less than Q
When the first array is complete, then the closest one will be found with complexity i + j

UPD
JavaScript implementation http://jsfiddle.net/ReinRaus/nK5Nz/
UPD2
Fixed bugs and code flaws

  • @ReinRaus, but I understand the answer is "closest", this is one of the array values. You do not have the number 96 in the array, but the result is it. - dlarchikov
  • But how do arr1 values ​​affect the result? i are keys in your implementation. jsfiddle.net/oceog/nK5Nz/4 :) - zb '
  • jsfiddle.net/oceog/nK5Nz/5 here is the revised version, the only thing is that for some reason it gives undefined at Q> 9802 - zb '19
  • jsfiddle.net/oceog/nK5Nz/9 does not work very well. - zb '
  • one
    @eicto, I'm sorry, I was in a hurry and didn’t replace i everywhere with arr1 [i] Corrected code - ReinRaus

I went through the @ReinRaus algorithm, fixed the errors.

 function nearest(arr1,arr2,Q){ var _i=arr1.length-1, _j=arr2.length-1, mind=Math.abs(Q-arr1[_i]*arr2[_j]); for (var i=0,j=arr2.length-1;i<arr1.length;i++) { while (j>0){ d=Math.abs(Q-arr1[i]*arr2[j]); if(d<mind){ mind=d; _i=i; _j=j; } if(arr1[i]*arr2[j]<Q)break; j--; } } return arr1[_i]*arr2[_j]; }

to try