Find the maximum value $LCM$ pair in the sequence where $LCM(a, b)$ means the smallest positive integer that is divisible by both.

Question

Problem Statement: Given a sequence $S$ of $N$ positive numbers, calculate the $\max\limits_{1 \le i < j \le n} LCM(a_i,a_j)$, where $LCM(a, b)$ is the smallest positive integer that is divisible by both $a$ and $b$.

For Example:
$S$ = 13 35 77
Answer: 1001

$S$ = 1 2 4 8 16 32
Answer: 32

$S$ = 12 9 1 8
Answer: 72

Constraints:
$2 \leq N \leq 10^{5}$
$1 \leq a_{i} \leq 10^{5}$
Sequence $S$ is not-necessarily sorted.

This problem was recently asked in one of the programming contests and I came up with a brute-force approach that has a time complexity (worst-case) of $O(N^{2}log(ab))$.

The idea behind the brute force approach was, generate all the ordered pairs of the given sequence $S$ and keep track of maximum LCM and in last print the largest LCM.

But as the size of the sequence increases, the algorithm will be slower, for e.g. when $N = 10^5$, the brute force approach will take $10^{10}$ computations to find the answer.

However, I was wondering, is there an efficient way of solving the problem?

P.S. Although the problem is related to programming, I thought that the actual solution was inherently math, so it was more reasonable to post it here, rather than, say, StackOverflow.

Answer 1

$\DeclareMathOperator{\lcm}{lcm}$I don't have a proof that this always runs quickly, but heuristically and in tests this tends to find the answer within a few dozen operations (plus a sorting and deduplication step).

First, sort (ascending or descending, I'll use descending below) the input and remove duplicates.

Call the resulting list $a$ and let $n$ be its length. Initialize $ans$ to zero (it always contains the maximum lcm we've found so far). Iterate over $i$ from $0$ to $n - 1$ and $j$ from $i$ to $n - 1$. We'll end up skipping most of this, so it'll be much less than $O(n^2)$ (at least conjecturally).

If $a_i^2 \leq ans$, then for any $x, y \leq a_i$, $\lcm(x, y) \leq x * y \leq a_i^2 \leq ans$, so there's no point in continuing the iteration. Any other pair later in the iteration will have an lcm less than or equal to the maximum we've found, so we're done.

Similarly, if $a_i * a_j \leq ans$, then for any $y \leq a_j$, $\lcm(a_i, y) \leq a_i * y \leq a_i * a_j \leq ans$. This means for the remaining $j$'s, the lcm will always be less than or equal to $ans$, so we can move to the next $i$.

If we haven't skipped to the next iteration, les $ans$ be the maximum of $ans$ and $\lcm(a_i, a_j)$.

Finally, once the iteration is finished (or we ended it early), $ans$ contains the result.

In pseudocode,

Input: a = list of positive integers

sort a descending
remove duplicates from a

ans = 0
for i from 0 to len(a) - 1

    if a[i] * a[i] <= ans
        break

    for j from i to len(a) - 1
        if a[i] * a[j] <= ans
            break
        ans = max(ans, lcm(a[i], a[j]))

return ans

In practice, for random lists following the constraints, I never iterated over more than a few dozen $(i, j)$ pairs before the program ended. The worst case I can think of is that the list is a sequence of prime powers, in which case we'll iterate over all the pairs of half the list. But with the bound on size, the worst case is with $\lfloor log_2(100,000) \rfloor = 16 $ different powers of $2$, so we'd only have $8 \cdot 9 / 2 = 36$ pairs to iterate over.

---

Edit: With less random inputs, this can have very poor performance. For example, even random inputs where all the $a_i$ are even will cause huge issues.