The question:
Suppose you are given a set P of integers and another integer x. We wish to use a T(nlgn) algorithm to decide whether there are 2 integers in P and the product (multiplication) of these two integers equals to x. Show your algorithm. (You can use pseudo code or by illustration only)
My answer:
Var x;
Function equate(list m)
If(length.m >=1)
Var l.list, r.list;
Var int middle = length.m /2;
For(int i = 0; i < middle; i++)
For(int j = 1;j < middle; j++)
l.list(i)*l.list(j)
if(l.list(i)*l.list(j) =x)
print l.list(i), l.list(j)
For(int i = middle; i < m; i++)
For(int j = middle; j < m; j++)
r.list(i)*r.list(j)
if(r.list(i)*r.list(j) = x)
print r.list(i),r.list(j)
I want to make sure if this is correct! If I have to change something please show me on my code what I have to change, and explain! Thanks!
Comments
I don't think your function is correct. Looks like you tried to write a kind of recursive function which does not call itself. And where are you r and l lists filled in ? If it was corrected, I think you would be in n square. Else the solution is pretty simple: sort your list in ascending order (saving the initial indices in each element). Takes nlogn. Then parse the list and if number x(i) divides P, let y = P/x, then seek y in the sorted list, (find j so that x(j)=y), in logn time. So nlogn + n*logn, so all in all it's nlogn