given a number p , find two elements in array whose product = P

Question

I am looking for solution for :

Given a array and a number P , find two numbers in array whose product equals P.

Looking for solution better than O(n*2) . I am okay with using extra space or other datastructure .Any help is appreciated ?

Answer 1

Make a pass through the array, and add the elements to a Hashtable. For each element x added, check whether P/x already exists in the Hashtable - if it does then x and P/x is one of your solutions. This'd be about as optimal as you'll get.

Answer 2

You can try a sliding window approach. First sort all the numbers increasingly, and then use two integers begin and end to index the current pair of numbers. Initialize begin to 0 and end to the last position. Then compare the product of v[begin] and v[end] with P:

• If it is equal, you found the answer.
• If it is lower, you must find a bigger product, move begin forward.
• If it is higher, you must find a smaller product, move end backward.

Here is a C++ code with this idea implemented. This solution is O(n*log(n)) because of the sorting, if you can assume the data is sorted then you can skip the sorting for an O(n) solution.

pair<int, int> GetProductPair(vector<int>& v, int P) {
  sort(v.begin(), v.end());
  int begin = 0, end = static_cast<int>(v.size()) - 1;
  while (begin < end) {
    const int prod = v[begin] * v[end];
    if (prod == P) return make_pair(begin, end);
    if (prod < P) ++begin;
    else --end;
  }
  return make_pair(-1, -1);
}