Given two numbers L and R, the task is to find two distinct minimum positive integers X and Y such that whose LCM lies in the range [L, R]. If there doesn’t exist any value of X and Y then print “-1”.
Examples:
Input: L = 3, R = 8
Output: x = 3, y=6
Explanation:
LCM of 3 and 6 is 6 which is in range 3, 8Input: L = 88, R = 90
Output: -1
Explanation:
Minimum possible x and y are 88 and 176 respectively, but 176 is greater than 90.
Approach: The idea is to choose the value of X and Y in such a way that their LCM lies in the given range [L, R]. Below are the steps:
- For the minimum value of X choose L as the minimum value as this is the minimum value in the given range.
- Now for the value of Y choose 2*L as this is the minimum value of Y whose LCM is L.
- Now if the above two values of X and Y lie in the range [L, R], then this is required pair of integers with minimum possible values of X and Y.
- Otherwise, print “-1” as there doesn’t exist any other pair.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find two distinct numbers// X and Y s.t. their LCM lies between// L and R and X, Y are minimum possiblevoid answer(int L, int R){ // Check if 2*L lies in range L, R if (2 * L <= R) // Print the answer cout << L << ", " << 2 * L << "\n"; else cout << -1;}// Driver Codeint main(){ // Given value of ranges int L = 3, R = 8; // Function call answer(L, R); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG{// Function to find two distinct numbers// X and Y s.t. their LCM lies between// L and R and X, Y are minimum possiblestatic void answer(int L, int R){ // Check if 2*L lies in range L, R if (2 * L <= R) // Print the answer System.out.println(L + ", " + (2 * L)); else System.out.println("-1");}// Driver Codepublic static void main(String[] args){ // Given value of ranges int L = 3, R = 8; // Function call answer(L, R);}} // This code is contributed by sanjoy_62 |
Python3
# Python3 program for the above approach# Function to find two distinct numbers# X and Y s.t. their LCM lies between# L and R and X, Y are minimum possibledef answer(L, R): # Check if 2*L lies in range L, R if (2 * L <= R): # Print the answer print(L, ",", 2 * L) else: print(-1)# Driver Code# Given value of rangesL = 3R = 8# Function callanswer(L, R)# This code is contributed by sanjoy_62 |
C#
// C# program for the above approachusing System;class GFG{// Function to find two distinct numbers// X and Y s.t. their LCM lies between// L and R and X, Y are minimum possiblestatic void answer(int L, int R){ // Check if 2*L lies in range L, R if (2 * L <= R) // Print the answer Console.WriteLine(L + ", " + (2 * L)); else Console.WriteLine("-1");}// Driver Codepublic static void Main(){ // Given value of ranges int L = 3, R = 8; // Function call answer(L, R);}}// This code is contributed by sanjoy_62 |
Javascript
<script>// JavaScript program for the above approach// Function to find two distinct numbers// X and Y s.t. their LCM lies between// L and R and X, Y are minimum possiblefunction answer(L, R){ // Check if 2*L lies in range L, R if (2 * L <= R) // Print the answer document.write(L + ", " + 2 * L + "<br>"); else document.write(-1);}// Driver Code // Given value of ranges let L = 3, R = 8; // Function call answer(L, R);// This code is contributed by Manoj.</script> |
Output:
3, 6
Time Complexity: O(1)
Auxiliary Space: O(1)
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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
