CareerCup

Do in-place sorting...and follow this algorithm
i =0;
n is length of array
while(i<n){
if( (a[i]*a[n])==number){
return i and n as pair;
}else{
if( (a[i]*a[n])< number){
++i;
}else{
--n;
}
}
}

return no such pair;


Complexity O(nlogn)

Hash all the elements in the integer array. Now search Product/number in the hash, this is O(1) operation, So on the whole it takes O(N).

1. Sort the array.
2. for each element find (product/element) is the array by using binary search.
3. If u find such element the your pair would be element & (product/element).

Binary search won't work here. Binary search aliminate half of element in each pass. It could be possible that one of element is from that list.

i guess first solution above will work

@Anonymous-April12
u didn't take into account that integers could be negative. so the sorting and search should be based on absolute vales . Then the code works fine..

take the factors of product .. let say the product is 12 .. its factors are 1 2 3 4 6 12
So your first element in the pairs should be one among them ,
lets take 1 first and see if there is any 12 in the array , if yes then that is a pair (1,12) , if not there is no such pair
lets take 2 and see if there is any 6 in the array , if yes then ( 2,6) else none
take 3 and see if there is any 4 in the arry , if yes then ( 3,4) else none

similarly we can continue for other factors of the product .. here there is no extra memory needed

If no extra space, then its a O(N^2) solution.

Something like this should work:

Sort the array using quicksort.
Let the give number be n.
Have one pointer at the beginning(i) and one at the end(j).
while(i<j){
If a[i]*a[j]=n //result is(a[i],a[j])
else if a[i]*a[j]>n
j--
else
i++; }