2
$\begingroup$

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.

$\endgroup$
11
  • $\begingroup$ This question was already asked. However, do you know other information about the possible sequences? From you examples it seems that all elements are distinct, is it an assumption? If not, you could improve your search by removing all duplicate elements in linear time. $\endgroup$
    – Riccardo
    Commented Apr 30, 2020 at 7:49
  • $\begingroup$ @RiccardoAllegrone I have searched for the question before asking but I didn't get anything. $\endgroup$
    – strikersps
    Commented Apr 30, 2020 at 9:04
  • $\begingroup$ @RiccardoAllegrone All the elements of the sequence are distinct. $\endgroup$
    – strikersps
    Commented Apr 30, 2020 at 9:04
  • $\begingroup$ Ok, are there bounds on the entries and/or on the length of sequences? For example, if entries are $\le 1000$ (and distinct) and you have a sequence with length $1000$, then you know that all numbers from $1$ to $1000$ are in the sequence, so in constant time you can return $999*1000$. $\endgroup$
    – Riccardo
    Commented Apr 30, 2020 at 10:24
  • $\begingroup$ @RiccardoAllegrone I have added the constraints part of the problem statement. $\endgroup$
    – strikersps
    Commented Apr 30, 2020 at 11:40

1 Answer 1

1
$\begingroup$

$\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.

$\endgroup$
5
  • $\begingroup$ Can you look at the python code (pastebin.com/uZ8cDf5b) which I have written on the basis of the pseudocode which you provided? If the code is correct, then it's not giving the correct answer. $\endgroup$
    – strikersps
    Commented Apr 30, 2020 at 14:34
  • $\begingroup$ The loops should be nested. You have two separate loops for i and j, but the j loop should be inside the i loop. $\endgroup$
    – SCappella
    Commented Apr 30, 2020 at 19:39
  • $\begingroup$ Also, you're missing the dedup step, which can cause bad behavior if the list is all the same number, for example. $\endgroup$
    – SCappella
    Commented Apr 30, 2020 at 19:46
  • $\begingroup$ Sorry, I have updated it (pastebin.com/epQuDkaN), but still, the program is slow. $\endgroup$
    – strikersps
    Commented May 1, 2020 at 8:39
  • $\begingroup$ Slow with what inputs? As noted, it does pretty well with purely random inputs, but fails when the inputs are crafted to foil this exact approach. $\endgroup$
    – SCappella
    Commented May 1, 2020 at 8:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .