Given an integer X, the task is to find two integers A and B such that sum of these two numbers is X and the LCM of A and B is maximum.
Examples:
Input: X = 15
Output: 7 8
Explanation:
7 + 8 = 15 and LCM(7, 8) = 56 is the maximum possible.Input: X = 30
Output: 13 17
Explanation:
13 + 17 = 30 and LCM(13, 17) = 221 is the maximum possible.
Naive Approach: The simplest approach is to use Two Pointers to find the pair of integers A and B with a given sum X and maximum possible LCM. Below are the steps:
- Initialize A and B as 1 and X–1 respectively.
- Run a loop, while, A is less than and equal to B.
- At each iteration calculate the LCM of A and B, then increment A by 1 and decrement B by 1.
- Print the A and B corresponding to the maximum LCM.
Time Complexity: O(N)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above naive approach the idea is to use some mathematical observations. The LCM of two co-prime integers is equal to the product of the two integers. Thus, the problem can be simplified to finding two co-prime integers A and B such that A+B = X and A×B is maximum. Below are the steps:
- If X is odd, then A = floor(X/2) and B = floor(X/2) + 1.
- Otherwise, if X is even, then
- If floor(X/2) is even, then A = floor(X/2) – 1 and B = floor(X/2) + 1.
- Otherwise, if floor(X/2) is odd, then A = floor(X/2) – 2 and B = floor(X/2) + 2.
Below is the implementation of the above approach:
C++
// C++ program of the above approach#include <bits/stdc++.h>using namespace std;// Function that print two numbers with// the sum X and maximum possible LCMvoid maxLCMWithGivenSum(int X){ // variables to store the result int A, B; // If X is odd if (X & 1) { A = X / 2; B = X / 2 + 1; } // If X is even else { // If floor(X/2) is even if ((X / 2) % 2 == 0) { A = X / 2 - 1; B = X / 2 + 1; } // If floor(X/2) is odd else { A = X / 2 - 2; B = X / 2 + 2; } } // Print the result cout << A << " " << B << endl;}// Driver Codeint main(){ // Given Number int X = 30; // Function call maxLCMWithGivenSum(X); return 0;} |
Java
// Java program of the above approach import java.util.*;class GFG{// Function that print two numbers with// the sum X and maximum possible LCMstatic void maxLCMWithGivenSum(int X){ // Variables to store the result int A, B; // If X is odd if ((X & 1) == 1) { A = X / 2; B = X / 2 + 1; } // If X is even else { // If floor(X/2) is even if ((X / 2) % 2 == 0) { A = X / 2 - 1; B = X / 2 + 1; } // If floor(X/2) is odd else { A = X / 2 - 2; B = X / 2 + 2; } } // Print the result System.out.println(A + " " + B); }// Driver codepublic static void main(String[] args){ // Given number int X = 30; // Function call maxLCMWithGivenSum(X); }}// This code is contributed by offbeat |
Python3
# Python3 program for the above approach # Function that print two numbers with # the sum X and maximum possible LCM def maxLCMWithGivenSum(X): # If X is odd if X % 2 != 0: A = X / 2 B = X / 2 + 1 # If X is even else: # If floor(X/2) is even if (X / 2) % 2 == 0: A = X / 2 - 1 B = X / 2 + 1 # If floor(X/2) is odd else: A = X / 2 - 2 B = X / 2 + 2 # Print the result print(int(A), int(B), end = " ")# Driver Code if __name__ == '__main__': # Given Number X = 30 # Function call maxLCMWithGivenSum(X)# This code is contributed by virusbuddah_ |
C#
// C# program of the above approach using System;class GFG{// Function that print two numbers with// the sum X and maximum possible LCMstatic void maxLCMWithGivenSum(int X){ // Variables to store the result int A, B; // If X is odd if ((X & 1) == 1) { A = X / 2; B = X / 2 + 1; } // If X is even else { // If floor(X/2) is even if ((X / 2) % 2 == 0) { A = X / 2 - 1; B = X / 2 + 1; } // If floor(X/2) is odd else { A = X / 2 - 2; B = X / 2 + 2; } } // Print the result Console.WriteLine(A + " " + B); }// Driver codepublic static void Main(String[] args){ // Given number int X = 30; // Function call maxLCMWithGivenSum(X); }}// This code is contributed by sapnasingh4991 |
Javascript
<script>// Javascript program of the above approach// Function that print two numbers with// the sum X and maximum possible LCMfunction maxLCMWithGivenSum(X){ // variables to store the result let A, B; // If X is odd if (X & 1) { A = X / 2; B = X / 2 + 1; } // If X is even else { // If floor(X/2) is even if ((X / 2) % 2 == 0) { A = X / 2 - 1; B = X / 2 + 1; } // If floor(X/2) is odd else { A = X / 2 - 2; B = X / 2 + 2; } } // Print the result document.write(A + " " + B + "<br>");}// Driver Code // Given Number let X = 30; // Function call maxLCMWithGivenSum(X);// This code is contributed by Manoj</script> |
13 17
Time Complexity: O(1)
Auxiliary Space: O(1)
Approach#2: Using math
This approach used in this code is a brute-force method to find the two numbers with the given sum X that have the maximum possible LCM. The code checks all possible pairs of numbers that sum up to X and calculates their LCM using the math.gcd() function. The code keeps track of the maximum LCM found so far and returns the pair of numbers that gives this maximum LCM.
Algorithm
1. Initialize a variable max_lcm to 0.
2. Loop over all possible pairs of numbers (i, j) such that i < j and i + j = X.
3. Calculate the LCM of i and j using the formula (i*j) // math.gcd(i, j).
4. If the calculated LCM is greater than max_lcm, update max_lcm and the pair of numbers num1 and num2 accordingly.
5. Return the pair of numbers num1 and num2.
C++
#include <iostream>#include <algorithm>#include <numeric>using namespace std;pair<int, int> findNumbersWithLCM(int X) { int maxLCM = 0; pair<int, int> result; for (int i = 1; i < X; i++) { for (int j = i + 1; j < X; j++) { if (i + j == X) { int lcm = (i * j) / __gcd(i, j); // Calculate LCM using the gcd function if (lcm > maxLCM) { maxLCM = lcm; result = {i, j}; } } } } return result;}int main() { int X = 30; pair<int, int> result = findNumbersWithLCM(X); cout << result.first << " " << result.second << endl; return 0;} |
Python3
import mathdef find_numbers_with_lcm(X): max_lcm = 0 for i in range(1, X): for j in range(i+1, X): if i + j == X: lcm = (i*j) // math.gcd(i, j) if lcm > max_lcm: max_lcm = lcm num1, num2 = i, j return num1, num2X = 30num1, num2 = find_numbers_with_lcm(X)print(num1, num2) |
Javascript
// Javascript code for the above approachfunction calculateGCD(a, b) { while (b !== 0) { const temp = b; b = a % b; a = temp; } return a;}function findNumbersWithLCM(X) { let maxLCM = 0; let num1 = 0; let num2 = 0; for (let i = 1; i < X; i++) { for (let j = i + 1; j < X; j++) { if (i + j === X) { const gcd = calculateGCD(i, j); const lcm = (i * j) / gcd; if (lcm > maxLCM) { maxLCM = lcm; num1 = i; num2 = j; } } } } return [num1, num2];}const X = 30;const [num1, num2] = findNumbersWithLCM(X);console.log(num1, num2); |
13 17
Time Complexity: O(X^2) because it loops over all possible pairs of numbers (i, j) such that i < j and i + j = X.
Auxiliary Space: O(1) because it uses only a fixed number of variables regardless of the value of X.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
