Encuentra dos números con la suma dada y el máximo posible MCM

Dado un entero X , la tarea es encontrar dos enteros A y B tales que la suma de estos dos números sea X y el MCM de A y B sea máximo.

Ejemplos:

Entrada: X = 15
Salida: 7 8
Explicación: 
7 + 8 = 15 y LCM(7, 8) = 56 es el máximo posible. 

Entrada: X = 30 
Salida: 13 17
Explicación:
13 + 17 = 30 y LCM(13, 17) = 221 es el máximo posible.

Enfoque ingenuo: el enfoque más simple es usar dos punteros para encontrar el par de números enteros A y B con una suma X dada y el máximo LCM posible . A continuación se muestran los pasos:

• Inicialice A y B como 1 y X – 1 respectivamente.
• Ejecute un ciclo, mientras que A es menor e igual que B .
• En cada iteración, calcule el MCM de A y B, luego incremente A en 1 y disminuya B en 1 .
• Imprime la A y la B correspondientes al MCM máximo.

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Enfoque eficiente: para optimizar el enfoque ingenuo anterior, la idea es utilizar algunas observaciones matemáticas. El MCM de dos enteros coprimos es igual al producto de los dos enteros. Por lo tanto, el problema se puede simplificar para encontrar dos enteros coprimos A y B tales que A+B = X y A×B sea máximo. A continuación se muestran los pasos:

• Si X es impar, entonces A = piso (X/2) y B = piso (X/2) + 1 .
• De lo contrario, si X es par, entonces
  • Si el piso ( X /2) es par, entonces A = piso (X/2) – 1 y B = piso (X/2) + 1 .
  • De lo contrario, si el piso ( X /2) es impar, entonces A = piso (X/2) – 2 y B = piso (X/2) + 2 .
     

A continuación se muestra la implementación del enfoque anterior:

// 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 LCM
void 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 Code
int main()
{
    // Given Number
    int X = 30;
 
    // Function call
    maxLCMWithGivenSum(X);
    return 0;
}

// Java program of the above approach
import java.util.*;
 
class GFG{
 
// Function that print two numbers with
// the sum X and maximum possible LCM
static 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 code
public static void main(String[] args)
{
     
    // Given number
    int X = 30;
 
    // Function call
    maxLCMWithGivenSum(X);
}
}
 
// This code is contributed by offbeat

# 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# program of the above approach
using System;
class GFG{
 
// Function that print two numbers with
// the sum X and maximum possible LCM
static 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 code
public static void Main(String[] args)
{
     
    // Given number
    int X = 30;
 
    // Function call
    maxLCMWithGivenSum(X);
}
}
 
// This code is contributed by sapnasingh4991

<script>
 
// Javascript program of the above approach
 
// Function that print two numbers with
// the sum X and maximum possible LCM
function 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

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)