Genere un par de enteros de un rango [L, R] cuyo LCM también se encuentre dentro del rango

Dados dos números enteros L y R , la tarea es encontrar un par de números enteros del rango [L, R] que también tengan LCM dentro del rango [L, R]. Si no se puede obtener tal par, imprima -1 . Si existen varios pares, imprima cualquiera de ellos.

Ejemplos:

Entrada: L =13, R = 69
Salida: X =13, Y = 26
Explicación: LCM(x, y) = 26 que satisface las condiciones L ≤ x < y ≤ R y L <= LCM(x, y) < = R

Entrada: L = 1, R = 665
Salida: X = 1, Y = 2

Enfoque ingenuo: el enfoque más simple es generar cada par entre L y R y calcular su LCM . Imprima un par que tenga LCM entre el rango L y R . Si no se encuentra ningún par que tenga MCM en el rango dado, imprima “-1” .

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

Enfoque eficiente: el problema se puede resolver usando la técnica Greedy basada en la observación de que LCM (x, y) es al menos igual a 2*x , que es LCM de (x, 2*x) . A continuación se detallan los pasos para implementar el enfoque:

1. Seleccione el valor de x como L y calcule el valor de y como 2*x
2. Compruebe si y es menor que R o no.
3. Si y es menor que R, imprima el par (x, y)
4. De lo contrario, escriba «-1»

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

// C++ implementation of the above approach
#include <iostream>
using namespace std;
 
void lcmpair(int l, int r)
{
    int x, y;
    x = l;
    y = 2 * l;
 
    // Checking if any pair is possible
    // or not in range(l, r)
    if (y > r) {
 
        // If not possible print(-1)
        cout << "-1\n";
    }
    else {
 
        // Print LCM pair
        cout << "X = " << x << " Y = "
             << y << "\n";
    }
}
 
// Driver code
int main()
{
    int l = 13, r = 69;
 
    // Function call
    lcmpair(l, r);
    return 0;
}

// Java implementation of the above approach
import java.util.*;
 
class GFG{
 
static void lcmpair(int l, int r)
{
    int x, y;
    x = l;
    y = 2 * l;
 
    // Checking if any pair is possible
    // or not in range(l, r)
    if (y > r)
    {
         
        // If not possible print(-1)
        System.out.print("-1\n");
    }
    else
    {
         
        // Print LCM pair
        System.out.print("X = " + x +
                        " Y = " + y + "\n");
    }
}
 
// Driver code
public static void main(String[] args)
{
    int l = 13, r = 69;
 
    // Function call
    lcmpair(l, r);
}
}
 
// This code is contributed by 29AjayKumar

# Python3 implementation of the above approach
def lcmpair(l, r):
 
    x = l
    y = 2 * l
 
    # Checking if any pair is possible
    # or not in range(l, r)
    if(y > r):
 
        # If not possible print(-1)
        print(-1)
    else:
         
        # Print LCM pair
        print("X = {} Y = {}".format(x, y))
 
# Driver Code
l = 13
r = 69
 
# Function call
lcmpair(l, r)
 
# This code is contributed by Shivam Singh

// C# implementation of the above approach
using System;
class GFG{
 
static void lcmpair(int l, int r)
{
    int x, y;
    x = l;
    y = 2 * l;
 
    // Checking if any pair is possible
    // or not in range(l, r)
    if (y > r)
    {       
        // If not possible print(-1)
        Console.Write("-1\n");
    }
    else
    {       
        // Print LCM pair
        Console.Write("X = " + x +
                      " Y = " + y + "\n");
    }
}
 
// Driver code
public static void Main(String[] args)
{
    int l = 13, r = 69;
 
    // Function call
    lcmpair(l, r);
}
}
 
// This code is contributed by shikhasingrajput

<script>
// javascript implementation of the above approach
 
    function lcmpair(l , r) {
        var x, y;
        x = l;
        y = 2 * l;
 
        // Checking if any pair is possible
        // or not in range(l, r)
        if (y > r) {
 
            // If not possible print(-1)
            document.write("-1\n");
        } else {
 
            // Print LCM pair
            document.write("X = " + x + " Y = " + y + "\n");
        }
    }
 
    // Driver code
        var l = 13, r = 69;
 
        // Function call
        lcmpair(l, r);
 
// This code is contributed by aashish1995
</script>

X = 13 Y = 26

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