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

Question

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

Answer 1

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 if … elif 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