LCM Triplet

JavaView on GFG

Time: O(1)

Space: O(1)

Problem Overview

Find triplet with maximum LCM.

See our study guide for structured GFG and LeetCode practice.

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?