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

Here's my shot, it only compares any factors with each other once

P <- The Number
theArray <- new array[theData]
factors <- new array[]
isFactor <- new map(init: false)
factorCount <- 0
i <- 0
while i is in theArray
    num <- theArray[i]
    if (isFactor[num])
        skip
    if num modulo P == 0
        isFactor[num] <- true
        j <- 0
        while j is in factors
            if factors[j] * num == P
                return (num, factors[j])
            j++
        factors.push(num)
        factorCount++
    i++

Answer 3

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);
}

Answer 4

This one would work only for integers: Decompose P as product of prime numbers. By dividing these in two groups you can obtain the pairs that gives P as product. Now you just have to check both of them are present in the array, this is where a hash table would be very useful. Also, while creating the hash table, you could also filter the array of repeating values, values that are greater than P, or even values that have prime factors not contained in P.

Answer 5

1.sort the numbers into an array A, removing any zeroes, in O(nlogn) time

2.create an array B such that B[i] = P/A[I] in O(n) time

3.for every B[k] in B, do a binary search in A for that element, takes O(nlogn) time in the worst case

if the element B[k] exists in the array A at position m, then A[k] * A[m] = P otherwise no such pair exists

the total running time is O(nlogn)

Of course this may run into difficulties on a real machine due to floating point error

Answer 6

Not sure if this is the best solution but it works. you can try and optimize it.

public class CombInput { public int ID; public string Value; }

public List GetCombinations(List values) {

        List<CombInput> input = new List<CombInput>();
       List<string> outputvalues = new List<string>();
        int counter = 1;
         foreach (String c in values)
         {
             input.Add(new CombInput { ID = counter, Value = c });

             counter++;
         }
        var Output = from i in input
                    select i;

        string Final = Output.Select(query => query.Value).Aggregate((a, b) => a + "|" + b);

        while (!Output.ToList().Exists(s=>s.Value.ToString()==Final))
        {
            var store = Output;  
            var  Output1= 
            (from o in Output
                      from v in input
                     where (v.ID < o.ID && !(store.Any(a=>a.Value==v.Value + "|" + o.Value)))
                           select new CombInput { ID = v.ID, Value = v.Value + "|" + o.Value });

            var Outputx = (from s in store select s)
            .Concat
            (from s in Output1.ToList() select s);
            Output = Outputx;
        }


        foreach (var v in Output)
            outputvalues.Add(v.Value);
        return outputvalues.ToList();
    }

public List GetProductCombinations(List nums, int productCriteria) { List input = (from i in nums select i.ToString()).ToList(); input = GetCombinations(input);

        var O = from i in input
                where i.Split('|').ToList().Select(x => Convert.ToInt32(x)).ToList().Aggregate((a, b) => a * b) == productCriteria
                select i;


        List<string> output=new List<string>();
        foreach (string o in O)
        {
            output.Add(o);
        }
        return output;
    }

private void button1_Click(object sender, EventArgs e) {

         List<string> output = new List<string>();
        List<int> nums = new List<int>();
        int[] numsarr ={1,2,3,4,6,7,8,12};
        nums = numsarr.ToList();
        output = GetProductCombinations(nums, 12);

}