LCM Triplet

JavaView on GFG

Time: O(1)

Space: O(1)

Intuition

Find triplet with maximum LCM. LCM is maximized by largest three consecutive integers or similar.

Algorithm

1Check triplets near n: (n,n-1,n-2), (n,n-1,n-3) when n-2 is even, etc. Compute LCM for candidates.

Common Pitfalls

•Do not just pick three largest; even numbers reduce LCM. Check a few candidate triplets near n.

LCM Triplet.java

Java

// Approach: For any n>=3 the answer is among {n, n-1, n-2} or {n, n-1, n-3} or similar small cases.
// Time: O(1) Space: O(1)
class Solution {
    int lcmTriplets(int n) {
        int ans;

        if (n < 3)
            ans = n;
        // If n is odd, the product of the top 3 numbers gives maximum LCM
        else if (n % 2 != 0)
            ans = n * (n - 1) * (n - 2);
        // If n is even and not divisible by 3, use n, n-1, n-3
        else if (n % 3 != 0)
            ans = n * (n - 1) * (n - 3);
        // If n is even and divisible by 3, use n-1, n-2, n-3
        else
            ans = (n - 1) * (n - 2) * (n - 3);

        return ans;
    }
}

Was this solution helpful?