Given an integer, N, the task is to find the maximum LCM (Least Common Multiple) that can be obtained from four numbers less than or equal to N (4 ? N).
Note: Duplicate numbers can be used.
Examples:
Input: N = 4
Output: 12
Explanation: The four numbers can be [4, 4, 3, 2] or [4, 4, 4, 3]. It can be shown that 12 is the maximum LCM of four numbers that can be obtained from numbers less than or equal to 4.Input: N = 5
Output: 60
Explanation: The four numbers can be [5, 5, 4, 3] or [5, 4, 3, 2], etc. 60 is the maximum that can be obtained.
Approach: This problem can be solved using Greedy Algorithm:
Since we want to maximize LCM we need to think of numbers such that they are coprime with each other as LCM of coprime numbers is maximum as they have no factor common except 1.
LCM = product of numbers / GCD
To maximize LCM we need to reduce GCD, thus choosing coprime numbers where GCD is 1 is the best option.
- Initialize ans as N*N-1 as N and N-1 are always coprime.
- Also Initialize a counter variable count = 1 to count 4 numbers, Since we have already chosen two of them we need to count two more numbers.
- Now start iterating i from N-2 till 1 and check if i is coprime with variable ans then include it in the 4 numbers and increment the counter by 1.
- If N is odd we have got our answer at the end of this loop.
- If N is even considered the max of ans obtained and the answer for N – 1.
Below is the implementation of the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;long long maxLCM(long long N){ if (N <= 2) return N; if (N == 3) return 6; if (N == 4) return 12; long long ans = N; long long i = N - 1; int cnt = 1; while (i > 1 and cnt < 4) { if (__gcd(ans, i) == 1) { cnt++; ans *= i; } i--; } if ((N % 2) == 0) ans = max(ans, maxLCM(N - 1)); return ans;}// Driver codeint main(){ int N = 5; int M = 4; // Function Call cout << maxLCM(N) << endl; cout << maxLCM(M) << endl; return 0;} |
Java
// Java code for the above approach:import java.io.*;class GFG { static long maxLCM(long N) { if (N <= 2) { return N; } if (N == 3) { return 6; } if (N == 4) { return 12; } long ans = N; long i = N - 1; int cnt = 1; while (i > 1 && cnt < 4) { if (gcd(ans, i) == 1) { cnt++; ans *= i; } i--; } if ((N % 2) == 0) { ans = Math.max(ans, maxLCM(N - 1)); } return ans; } // gcd method static long gcd(long a, long b) { if (b == 0) { return a; } return gcd(b, a % b); } public static void main(String[] args) { long N = 5; long M = 4; // Function Call System.out.println(maxLCM(N)); System.out.println(maxLCM(M)); }}// This code is contributed by lokesh. |
Python3
# Python3 code for the above approachimport math# This Function will returns the maximum value of the# LCM of any four integers less than or equal to Ndef maxLCM(N): if N <= 2: return N if N == 3: return 6 if N == 4: return 12 ans = N i = N - 1 cnt = 1 while i > 1 and cnt < 4: if math.gcd(ans, i) == 1: cnt += 1 ans *= i i -= 1 if N % 2 == 0: ans = max(ans, maxLCM(N - 1)) return ans# Driver codeN = 5M = 4# Function Callprint(maxLCM(N))print(maxLCM(M))#This code is contributed by nikhilsainiofficial546 |
C#
// C# code for the above approach:using System;public class GFG{ static long maxLCM(long N) { if (N <= 2) { return N; } if (N == 3) { return 6; } if (N == 4) { return 12; } long ans = N; long i = N - 1; int cnt = 1; while (i > 1 && cnt < 4) { if (gcd(ans, i) == 1) { cnt++; ans *= i; } i--; } if ((N % 2) == 0) { ans = Math.Max(ans, maxLCM(N - 1)); } return ans; } // gcd method static long gcd(long a, long b) { if (b == 0) { return a; } return gcd(b, a % b); } static public void Main (){ // Code long N = 5; long M = 4; // Function Call Console.WriteLine(maxLCM(N)); Console.WriteLine(maxLCM(M)); }}// This code is contributed by lokeshmvs21. |
Javascript
// Javascript code for the above approach:function gcd(a, b){ // Everything divides 0 if(b == 0){ return a; } return gcd(b, a % b);}function maxLCM( N){ if (N <= 2) return N; if (N == 3) return 6; if (N == 4) return 12; let ans = N; let i = N - 1; let cnt = 1; while (i > 1 && cnt < 4) { if (gcd(ans, i) == 1) { cnt++; ans *= i; } i--; } if ((N % 2) == 0) ans = Math.max(ans, maxLCM(N - 1)); return ans;}// Driver codelet N = 5;let M = 4;// Function Callconsole.log(maxLCM(N));console.log(maxLCM(M));// This code is contributed by poojaagarwal2. |
60 12
Time Complexity: O(log(max(N)))
Auxiliary Space: O(1)
Related Articles:
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
