# Finding whether there exists a pair of numbers in a set having a given product

Devise an algorithm that will operate on a number x and a set of n distinct numbers such that in $O(n \lg n)$ time, the algorithm indicates whether or not there are two numbers in the set that have a product of x. Explain why your algorithm works.

My algorithm:

1. Sort the set //$O(n \lg n)$
2. For every element in the set check if x % element =0 // $O(n)$
3. If so check if the dividend x/element exists in the set // $O(\lg n)$
4. If dividend exists and is not equal to element, the two numbers in the set (element and dividend) have a product of x.

This algorithm works because it only returns true when the condition(x=element*dividend where element and dividend are in the set) to be satisfied is met. And upon quick Analysis we can see that the algorithm is running at $O(n\lg n)$ for the sort and $O(n)*(\lg n)$ for checking if the two elements exists. Therefore it is running at $O(n \lg n) + O(n \lg n) = O(2n \lg n) = O(n \lg n)$

Can I have some feedback on my solution — whether you think it is correct or not and where you think it can be improved?

def findIfProdExists(x,items):
items = mergeSort(items) # O(nlgn)
for item in items:
if(item!=0):
if x%item ==0:
if item!=x/item and find(x/item,items):  #binary Search O(lgn)
return True
return False

def mergeSort(aList):
size = len(aList)
first = aList[:int(size/2)]
second = aList[int(size/2):]

if(size ==1):
return aList
if(size ==2):
if(aList[1]<aList[0]):
return list([aList[1],aList[0]])
else:
return aList
else:
return merge(mergeSort(first),mergeSort(second))

def merge(list1,list2):
newList =[]
i1 =0
i2 =0
while i1<len(list1) and i2 <len(list2) :
if list1[i1] <list2[i2] :
newList.append(list1[i1])
i1+=1
elif list1[i1]>list2[i2] :
newList.append(list2[i2])
i2+=1
else:
newList.append(list1[i1])
i1+=1
newList.extend(list1[i1:] +list2[i2:])
return newList

def find(x,items):
lo = 0
hi = len(items)
while lo<hi:
mid = (lo + hi) // 2
if x == items[mid]:
return True
elif x < items[mid]:
hi = mid
else:
lo = mid + 1
return False

• Your program doesn't work for me: I get NameError: name 'mergeSort' is not defined. Mar 22, 2015 at 10:40
• Sorry about that I was just demonstrating the algorithm. I'll include the mergeSort Code so you may test. Mar 22, 2015 at 10:58
• Optionally you could use python's built in sort method on the list since from the python wiki wiki.python.org/moin/TimeComplexity it also has a time complexity of O(nlgn) Mar 22, 2015 at 11:01
• Thanks for that. But it still doesn't work for me. Now I get NameError: name 'find' is not defined. Mar 22, 2015 at 11:17
• The question said the set should have unique numbers Mar 22, 2015 at 11:24

The algorithm description is good, but the implementation of find is $O(n)$, so the overall runtime is actually $O(n^2)$.

Detailed review follows:

1. There are no docstrings. What does each function do? How do I call it? What does it return? Are there any constraints on the parameters, for example do the inputs have to be sorted? or do they have to be free of duplicates?

2. It's not necessary in Python to have parentheses around the condition of if statement, and it's best to omit them.

3. According to the analysis, find needs to be $O(\log n)$, but the actual implementation is $O(n)$. Here's a demonstration:

>>> from timeit import timeit
>>> for p in range(2, 8):
...     items = list(range(10**p))
...     '{:f}'.format(timeit(lambda:find(0, items), number=1))
...
0.000012
0.000022
0.000077
0.001386
0.038858
0.417670


The reason for this is the copying in the recursive calls. In Python, the list slice items[mid:] has to be copied, and the time taken to do this is proportional to the number of items in the copy. See the time complexity page on the Python wiki.

4. In order to avoid copying in find, it's best to keep indexes into the part of the sequence which might contain the item we're looking for:

def find(x, items):
"""Return True if x is an element of the sequence items, assuming
items is sorted.

"""
lo = 0
hi = len(items)
while lo < hi:
mid = (lo + hi) // 2
if x == items[mid]: return True
elif x < items[mid]: hi = mid
else: lo = mid + 1
return False

5. Python has a built-in module bisect for binary search of sorted sequences, and using this module it's possible to write find like this:

from bisect import bisect_left

def find(x, items):
"""Return True if x is an element of the sequence items, assuming
items is sorted.

"""
i = bisect_left(items, x)
return i < len(items) and items[i] == x

6. The corrected version of find locates an element in a sorted list in time $O(\log n)$. But it's possible to do better than that using a set. Set lookup has average complexity $O(1)$.

7. The implementation of merge goes into an infinite loop if list1 and list2 have a common item. This was easy for me to spot because there is an ifelif with no else at the end. When code has a sequence of conditions like this, it's always worth asking, "what happens if none of the conditions apply?"

8. Python has a built-in function heapq.merge for merging sorted iterables into a single sorted iterator, and a built-in function sorted for sorting an iterable (using a variant of mergesort, as it happens). These are fast and well-tested implementations, and (except as an exercise) they should be used in preference to writing your own.

9. In findIfProdExists the division x/item is computed twice in some cases. It would be better to compute it once and remember the value.

10. In findIfProdExists the cheap test item!=x/item is computed after the expensive test find(x/item,items). It's usually best to compute cheap cases first so that if they fail the expensive test can be avoided altogether.

Putting all this together, I'd implement the algorithm like this:

def product_pair(x, items):
"""Return True if there is a pair of distinct elements in the iterable
items whose product is x. Return False otherwise.

"""
items = set(items)
for item in items:
if item != 0 and x % item == 0:
y = x / item
if y != item and y in items:
return True
return False

• Quick question though set lookup has a time complexity of $O(1)$ on average and $O(n)$ in the worst case according to the Python wiki. Doesn't that mean that in the worst case the algorithm would have a quadratic running time ? Mar 22, 2015 at 18:22
• Yes, it's theoretically possible that many elements have the same hash, but in practice this is not worth worrying about unless the elements come from an untrusted source. Mar 22, 2015 at 18:28
• Ok I see, but after making the suggested fixes to merge and find functions, is your implementation still optimal compared to sorting then doing a binary search ? Mar 22, 2015 at 18:31
• Why not do a performance comparison and see for yourself? Mar 22, 2015 at 18:33
• think i can answer my own question. on average it would be because yours would have a Time complexity of $O(n)$ right ? Mar 22, 2015 at 18:33