Given number p, find two elements in the array whose product = P

Question

I am looking for a solution for:

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

We are looking for a solution better than O (n * 2). I'm fine using extra space or another data structure. Any help is appreciated?

Answer 1

You can try the sliding window approach. Sort all the numbers first, 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 have found the answer.
• If it is lower, you should find a larger product, move begin forward.
• If it is higher, you should find a smaller product, move end back.

Here is the C ++ code with this idea. This solution is O (n * log (n)) due to sorting, if you can assume that the data is sorted, you can skip sorting to solve O (n).

 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 2

Pass through the array and add elements to the Hashtable. For each x element added, check if P / x exists in the Hashtable - if so, x and P / x are one of your solutions. It will be as optimal as you.

Answer 3

This one will only work for integers: Decompose P as the product of primes. Dividing them into two groups, you can get pairs that give P as a product. Now you just need to check that both of them are present in the array, this is where the hash table would be very useful. In addition, by creating a hash table, you can also filter an array of duplicate values ​​whose values ​​are greater than P, or even values ​​that have simple coefficients not contained in P.

Answer 4

1. Sort numbers into array A by deleting any zeros at O ​​(nlogn) time

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

3. for each B [k] in B, do a binary search in for this 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, such a pair does not exist

total running time O (nlogn)

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

Answer 5

• Create a hash that will be populated in the next steps.
• Iterate over the elements of an array in turn. Say the current item is n
  • If the number P is exactly divisible by n
    • check if n is one of the hash values. If so, then this key, value is the two numbers that we are looking for, and we can break.
    • If n is not in the hash values, then add n, x to the hash, where n * x = P
  • If the number P is inaccurately divided by n, then continue with the next element of the array
• If we reach the end of the array, then there are no two numbers in the array whose product is P

This algo has O (n)

Answer 6

O (n + P) solution, ignoring case P equal to 0.

 #include <stdio.h> #include <iostream> #include <vector> using namespace std; int main(){ auto arr = new vector<int>(); int P, numOfEle, ele; cout << "The number of elements to be entered: " << endl; cin >> numOfEle; cout << "Please enter the elements: " << endl; for (int i = 0; i < numOfEle; i++){ cin >> ele; arr->push_back(ele); } cout << "Please enter P: " << endl; cin >> P; //O(n+P) solution, ignoring the case of P equal to 0 bool* factorsInNeed = new bool[P]; for (int i = 0; i < P; i++) factorsInNeed[i] = false; for (auto i : *arr){ if (i != 0 && P/(double)i == P/i){ //if divisble if (factorsInNeed[i]){ cout << "A solution: " << i << " & " << P/i << endl; break; } factorsInNeed[P/i] = true; } } } 

Answer 7

 public boolean factors_Of_Product_In_Array(int a[],int product,int factorsLimit) { int i = 0,count = 0; boolean flag = false; if(factorsLimit==0) flag = false; //If product value is zero - only verify if there is any '0' value in array else if(product==0) { for(i=0;i<a.length;i++) { if(a[i]==0) flag = true; } } //If product value is 1 - Verify at least factorsLimit number of 1 should be present in array else if(product==1) { for(i=0;i<a.length;i++) { if(a[i]==0) count=count+1; } if(count==factorsLimit)//Verifying if the number of 1 is equal to number of factors required flag = true; } else { for(i=0; i<a.length && count!=factorsLimit ;i++) { if(product%a[i]==0) { product = product/a[i]; count = count+1; System.out.println(" "+a[i]+" "); } } if(count==factorsLimit) flag = true; } return flag; } 

Answer 8

Here is my picture, 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 9

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<string> GetCombinations(List<string> 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<string> GetProductCombinations(List<int> nums, int productCriteria) { List<string> 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); } 

Answer 10

void PrintPairOfProduct (int arr [], int size, int k) {

  int i,temp[MAX]; memset(temp,1,MAX); for(i=0;i<size;++i) { if(k % arr[i] == 0 && temp[arr[i]] != -1 && temp[k/arr[i]] != -1) { if((temp[k/arr[i]] * arr[i]) == k) { printf("Product of %d * %d = %d",k/arr[i],arr[i],k);`` temp[k/arr[i]] = -1; temp[arr[i]] = -1; } temp[arr[i]] = arr[i]; 

}}

Answer 11

 #include<stdio.h> int main() { int arr[]={2,15,4,5,6,7}; const int c = 30; int i = 0,j=1; int num =0; while ( i<= 6 ) { num = arr[i] * arr[j]; if ( num == 30) { printf("Pairs[%d,%d]\t",arr[i],arr[j]); } if (j == 5 ) { i = i+1; j = i + 1; if (j==6) { break; } else { continue; } } j= j+1; } return 0; }