LCM Triplet Geeks For Geeks

Problem Link:

https://practice.geeksforgeeks.org/problems/lcm-triplet1501/1

(It is also the problem of the day for 20-11-2022.)

Solution:

class Solution {

    long lcmTriplets(long N) {

        if(N<=2){

            return N;

        }

        else if((N&1)==0){

            if(N%3==0){

                N--;

                return N*(N-1)*(N-2);

            }

            return N*(N-1)*(N-3);

        }

        return N*(N-1)*(N-2);

    }

}

Time Complexity: O(log n)[GFG Time:2.22]

Space Complexity:O(1)

Auxiliary Space:O(1)

Total Test Cases:1000105

Approach Used:

Here we observe carefully.

Then we notice one thing we need to return the multiplication of three numbers as an answer.

Now the only thing is we need to identify what are those three numbers.

So for that, we have different cases.

If we see that the number is 2 or less than that then that number itself will be the answer.

eg for 2 it will be 2 2 1 or 2 2 2 or 2 1 1 as all return the same value but it can't be 2 1 0 as it will give 0.

similarly, for n=1 and n=0 the answer would be n

If we have numbered 11 then the answer will be 11 10 9 and they will have the maximum lcm value as compared to other triplets.

So simply for odd numbers, we can say that ans=N*(N-1)*(N-2) is so because no value will share any common factor between them due to which the lcm value will be maximum.

Now even cases 

if n=10 then if we return 10 9 8 then the answer will be 720 however it should not be as 8 and 10 have common factors so the answer returned is 720 as simple multiplication but when we will carry out lcm of these three numbers ie 10 9 8 then it will be 360 which is significantly less than 720 while if we take other triplets as 10 9 7 then it will be 630 which is a valid answer.

So by the above discussion, it is clear that we can not take n, n-1, and n-2 as triplet members for even numbers because after every consecutive gap of 2 there will be even numbers which will share common factors due to which the value of lcm will not be maximum.

So to rectify this we return N*(N-1)*(N-3) as the answer.

example as verified for 10 9 and 7 ie 630 which is the maximum and 7 and 10 have no common factors.

However, the twist is with those numbers are divisible by 3 or multiple of 3 as 12 24 36.

for 12 the multiplication will be 12*11*10 which returns the answer as 1320 however again 12 and 10 have common factors due to which the actual lcm should be 660 however we can have some other values as maximum.

So for that, we do some random trials

12 11 10 -> 660

12 11 9-> 396

11 11 10-> 110

11 10 9-> 990 

11 10 8-> 880

11 10 7-> 770

10 9 8->720

----

----

---

Now all values will decrease down so the maximum value is 990 which is 11 10 9

but our input was 12 

so N=12

N=N-1 ---->  N=12-1  ---> N=11

answer N*(N-1)*(N-2)

It is so because by decreasing 1 from n we have converted it from even to odd and the common factor of 3 is also removed.

Question?

Then for all even cases why don't we decrease n by 1 and convert even to odd and apply the formula for odd?

Ex taking the case of n=16 

if we decrease by 1 then

n=16-1=15   ans = 15*14*13 = 2730

and if we keep it 16 and apply n*(n-1)*(n-3)

n=16   and ans=16*15*13= 3120

So clearly the maximum id is 3120 and hence we apply only this formula of n*(n-1)*(n-3)

"Thanks For Reading.😇"

"Share Further To Increase Knowledge Treasure.😊"