Given a range of positive integers from l to r. Find such a pair of integers (x, y) that l <= x, y <= r, x != y and x divide y.
If there are multiple pairs, you need to find any one of them.
Examples:
Input : 1 10
Output : 1 2
Input : 2 4
Output : 2 4
The brute force solution is to traverse through the given range of (l, r) and find the first occurrence where x divides y and x!=y.This solution is feasible if the difference between l and r is small.
Time Complexity of this solution is O((r-l)*(r-l)).
Following are codes based on brute force solutions.
C++
#include <bits/stdc++.h>
using namespace std;
void findpair(int l, int r)
{
int c = 0;
for (int i = l; i <= r; i++) {
for (int j = i + 1; j <= r; j++) {
if (j % i == 0 && j != i) {
cout << i << ", " << j;
c = 1;
break;
}
}
if (c == 1)
break;
}
}
int main()
{
int l = 1, r = 10;
findpair(l, r);
}
|
Java
class GFG
{
static void findpair(int l, int r)
{
int c = 0;
for (int i = l; i <= r; i++)
{
for (int j = i + 1; j <= r; j++)
{
if (j % i == 0 && j != i)
{
System.out.println( i +", " + j);
c = 1;
break;
}
}
if (c == 1)
break;
}
}
public static void main(String args[])
{
int l = 1, r = 10;
findpair(l, r);
}
}
|
Python 3
def findpair(l, r):
c = 0
for i in range(l, r + 1):
for j in range(i + 1, r + 1):
if (j % i == 0 and j != i):
print( i, ", ", j)
c = 1
break
if (c == 1):
break
if __name__ == "__main__":
l = 1
r = 10
findpair(l, r)
|
C#
using System;
class GFG
{
static void findpair(int l, int r)
{
int c = 0;
for (int i = l; i <= r; i++)
{
for (int j = i + 1; j <= r; j++)
{
if (j % i == 0 && j != i)
{
Console.Write( i + ", " + j);
c = 1;
break;
}
}
if (c == 1)
break;
}
}
static void Main()
{
int l = 1, r = 10;
findpair(l, r);
}
}
|
PHP
<?php
function findpair($l, $r)
{
$c = 0;
for ($i = $l; $i <= $r; $i++)
{
for ($j = $i + 1; $j <= $r; $j++)
{
if ($j % $i == 0 && $j != $i)
{
echo($i . ", " . $j);
$c = 1;
break;
}
}
if ($c == 1)
break;
}
}
$l = 1; $r = 10;
findpair($l, $r);
?>
|
Javascript
<script>
function findpair(l,r)
{
let c = 0;
for (let i = l; i <= r; i++)
{
for (let j = i + 1; j <= r; j++)
{
if (j % i == 0 && j != i)
{
document.write( i +", " + j+"<br>");
c = 1;
break;
}
}
if (c == 1)
break;
}
}
let l = 1, r = 10;
findpair(l, r);
</script>
|
Efficient Solution:
The problem can be solved in O(1) time complexity if you find the value of l and 2l.
Explanation:
1) As we know, the smallest value of y/x you can have is 2 and if any greater value is in the range, then 2 is also in the given range.
2) The difference between x and 2x also increases when you increase the value of x. So l and 2l will be the minimum pair to fall in the given range.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
void findpair(int l, int r)
{
int ans1 = l;
int ans2 = 2 * l;
cout << ans1 << ", " << ans2 << endl;
}
int main()
{
int l = 1, r = 10;
findpair(l, r);
}
|
Java
class GFG
{
static void findpair(int l, int r)
{
int ans1 = l;
int ans2 = 2 * l;
System.out.println( ans1 + ", " + ans2 );
}
public static void main(String args[])
{
int l = 1, r = 10;
findpair(l, r);
}
}
|
Python3
def findpair(l, r):
ans1 = l
ans2 = 2 * l
print(ans1, ", ", ans2)
if __name__ == '__main__':
l, r = 1, 10
findpair(l, r)
|
C#
using System;
class GFG
{
static void findpair(int l, int r)
{
int ans1 = l;
int ans2 = 2 * l;
Console.WriteLine( ans1 + ", " + ans2 );
}
public static void Main()
{
int l = 1, r = 10;
findpair(l, r);
}
}
|
PHP
<?php
function findpair($l, $r)
{
$ans1 = $l;
$ans2 = 2 * $l;
echo ($ans1 . ", " . $ans2);
}
$l = 1; $r = 10;
findpair($l, $r);
?>
|
Javascript
<script>
function findpair(l,r)
{
let ans1 = l;
let ans2 = 2 * l;
document.write( ans1 + ", " + ans2 );
}
let l = 1, r = 10;
findpair(l, r);
</script>
|
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!
