Задачка на алгоритм для ниндзя

#алгоритм

Уже полторы недели небольшими набегами думаем, как её решить. Может быть, тут кто-то
сможет :)
Даны два массива натуральных чисел: x и y (оба массива неубывающие), и натуральное
число Q. 
Найти такие числа из этих массивов, что x[i] * y[j] максимально близко к Q.
Сложность не должна превышать O(n+m), где n и m — размеры массивов.    

Ответы

Ответ 1

Просматриваем один массив с головы, другой с хвоста.
Передвигаемся по второму массиву из хвоста в голову, сохраняя два значения- текущее
произведение и предыдущее
когда текущее произведение меньше Q, то находим какое произведение ближе к искомому-
текущее, предыдущее или ранее сохраненное как наиближайшее
сдвигаем первый массив из головы в хвост на одну позицию и повторяем  движение по
второму массиву, пока опять текущее произведение не станет меньше Q
Когда первый массив будет весь пройден то наиближайшее будет найдено при сложности i+j


UPD
Реализация на JavaScript  http://jsfiddle.net/ReinRaus/nK5Nz/
UPD2
Исправил ошибки и недочеты кода


Ответ 2

Перебрал алгоритм @ReinRaus, исправил ошибки.
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;i0){
      d=Math.abs(Q-arr1[i]*arr2[j]);
      if(d