Given two integers L and R, the task is to find a pair of integers from the range [L, R] having LCM within the range [L, R] as well. If no such pair can be obtained, then print -1. If multiple pairs exist, print any one of them.
Examples:
Input: L = 13, R = 69
Output: X =13, Y = 26
Explanation: LCM(x, y) = 26 which satisfies the conditions L ? x < y ? R and L <= LCM(x, y) <= RInput: L = 1, R = 665
Output: X = 1, Y = 2
Naive Approach: The simplest approach is to generate every pair between L and R and compute their LCM. Print a pair having LCM between the range L and R. If no pair is found to have LCM in the given range, print “-1”.
Time Complexity: O(N)
Auxiliary Space: O(1)
Efficient Approach: The problem can be solved by using the Greedy technique based on the observation that LCM(x, y) is at least equal to 2*x which is LCM of (x, 2*x). Below are the steps to implement the approach:
- Select the value of x as L and compute the value of y as 2*x
- Check if y is less than R or not.
- If y is less than R then print the pair (x, y)
- Else print “-1”
Below is the implementation of the above approach:
C++
// 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 codeint main(){ int l = 13, r = 69; // Function call lcmpair(l, r); return 0;} |
Java
// Java implementation of the above approachimport 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 codepublic static void main(String[] args){ int l = 13, r = 69; // Function call lcmpair(l, r);}}// This code is contributed by 29AjayKumar |
Python3
# 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 Codel = 13r = 69# Function calllcmpair(l, r)# This code is contributed by Shivam Singh |
C#
// C# implementation of the above approachusing 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 codepublic static void Main(String[] args){ int l = 13, r = 69; // Function call lcmpair(l, r);}}// This code is contributed by shikhasingrajput |
Javascript
<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
Time Complexity: O(1)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
