Given a set of numbers,find the pair which has the least LCM(Lowest Common Multiple)

Question

I used this approach.

1. Found all possible nC2 pairs possible for n numbers.
2. Then individually found thier LCM by computing their GCD and dividing the product of the two numbers by thier GCD.
3. Also maintained a variable which contained the least LCM value computed till then and finally output it.

But this naive approach seems inefficient when the number values are very large (~10^9) since time complexity of GCD will depend on the magnitude of the number. Also it will be infeasible for very large values of N. Is there any other better approach to this problem?

Answer 1

I don't think there is an efficient algorithm for this.

You can always use heuristics and simple which will definitely work for this problem.

On average, for most arrays, the pair of numbers will be like a,b(a<b) where LCM(a,b) ~ O(b), i.e. most of a's factors are contained in b and hence LCM will be approximately of O(b).

Hence on average, LCM will not be very large and similar to elements of the arrays.

So, Idea is to sort the array, and try with smaller a,b first in increasing order. And when b > lcm_so_far .

Thanks

Answer 2

For a large number of digits, an efficient implementation of the Euclidean algorithm (https://en.wikipedia.org/wiki/Euclidean_algorithm#Algorithmic_efficiency) for finding the GCD is the best route I can think of. There is no fast, general algorithm for prime factorization so using that to reduce the problem won't help the run time. I'm not aware of any fast reductions that would help with this.

Addressing large N, I think this is what others have been getting at:

1. Sort the array
2. Start with lowest values and calculate LCMs (using the Euclidean algorithm for example for the GCD part) with a short circuit: stop processing once the LCM of the remaining pairs cannot be less than the best found so far. Note that, for two numbers in the sorted set, b < c,the lower bound of the LCM is (b * c) / b = c (this occurs when b divides c). See working code below (short_lcm version).

There are other optimizations that can be made to this (such as not writing it in python :) ) but this demonstrates the algorithm improvement:

import fractions

def lcm(a, b):
    return abs(a * b) / fractions.gcd(a, b)

def short_lcm(a):
    a = sorted(a)

    iterations = 0
    cur_lcm = lcm(a[0], a[1])
    first = a[0]
    second = a[1]
    for i in range(0, len(a)):
        #Best case for remaining pairs
        if i < len(a) - 1 and a[i + 1] >= cur_lcm: break

        for j in range(i + 1, len(a)): #Starting at i + 1 avoids duplicates
            if a[j] >= cur_lcm: break  #Best case for remaining pairs

            iterations += 1

            test = lcm(a[i], a[j])
            if test < cur_lcm:
                cur_lcm = test
                first = a[i]
                second = a[j]

    if iterations < 1: iterations = 1

    print("Lowest LCM pair is (%d, %d): %d. Found in %d iterations" % (
                first, second, cur_lcm, iterations))

def long_lcm(a):
    iterations = 0
    cur_lcm = lcm(a[0], a[1])
    first = a[0]
    second = a[1]
    for i in range(0, len(a)):
        for j in range(i + 1, len(a)):     #Starting at i + 1 avoids duplicates
            iterations += 1

             test = lcm(a[i], a[j])
            if test < cur_lcm:
                cur_lcm = test
                first = a[i]
                second = a[j]

    print("Lowest LCM pair is (%d, %d): %d. Found in %d iterations" % (
                first, second, cur_lcm, iterations))

if __name__ == '__main__':
    from random import randint
    import time

    a = [randint(1, 1000) for r in xrange(100)]

    #Only print the list if it's relatively short
    if len(a) < 20: print a

    #Try all pairs
    start = time.clock()
    long_lcm(a)
    print "Slow version time: %f\n" % (time.clock() - start)

    start = time.clock()
    short_lcm(a)
    print "Fast version time: %f" % (time.clock() - start)