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.
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>
|