Dado un rango de números enteros positivos de l a r. Encuentre un par de enteros (x, y) tal que l <= x, y <= r, x != y y x divida a y.
Si hay varios pares, debe encontrar cualquiera de ellos.
Ejemplos:
Input : 1 10 Output : 1 2 Input : 2 4 Output : 2 4
La solución de fuerza bruta es atravesar el rango dado de (l, r) y encontrar la primera ocurrencia donde x divide a y yx!=y. Esta solución es factible si la diferencia entre l y r es pequeña.
La complejidad temporal de esta solución es O((rl)*(rl)).
Los siguientes son códigos basados en soluciones de fuerza bruta.
C++
// C++ implementation of the approach
#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
// Java implementation of the approach
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;
}
}
// Driver code
public static void main(String args[])
{
int l = 1, r = 10;
findpair(l, r);
}
}
// This code is contributed by Arnab Kundu
Python 3
# Python 3 implementation of the approach 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 # Driver Code if __name__ == "__main__": l = 1 r = 10 findpair(l, r) # This code is contributed by ita_c
C#
// C# implementation of the approach
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;
}
}
// Driver code
static void Main()
{
int l = 1, r = 10;
findpair(l, r);
}
}
// This code is contributed by mits
PHP
<?php
// PHP implementation of the approach
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;
}
}
// Driver code
$l = 1; $r = 10;
findpair($l, $r);
// This code is contributed
// by Code_Mech.
?>
Javascript
<script>
// JavaScript implementation of the approach
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;
}
}
// Driver code
let l = 1, r = 10;
findpair(l, r);
// This code is contributed by avanitrachhadiya2155
</script>
1, 2
Solución eficiente:
el problema se puede resolver en complejidad de tiempo O(1) si encuentra el valor de l y 2l.
Explicación:
1) Como sabemos, el valor más pequeño de y/x que puede tener es 2 y si cualquier valor mayor está en el rango, entonces 2 también está en el rango dado.
2) La diferencia entre x y 2x también aumenta cuando aumentas el valor de x. Entonces, l y 2l serán el par mínimo para caer en el rango dado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the possible pair
void findpair(int l, int r)
{
// ans1, ans2 store value of x
// and y respectively
int ans1 = l;
int ans2 = 2 * l;
cout << ans1 << ", " << ans2 << endl;
}
// Driver Code
int main()
{
int l = 1, r = 10;
findpair(l, r);
}
Java
// Java implementation of the approach
class GFG
{
// Function to return the possible pair
static void findpair(int l, int r)
{
// ans1, ans2 store value of x
// and y respectively
int ans1 = l;
int ans2 = 2 * l;
System.out.println( ans1 + ", " + ans2 );
}
// Driver Code
public static void main(String args[])
{
int l = 1, r = 10;
findpair(l, r);
}
}
// This code is contruibuted by Arnab Kundu
Python3
# Python3 implementation of the approach # Function to return the possible pair def findpair(l, r): # ans1, ans2 store value of x # and y respectively ans1 = l ans2 = 2 * l print(ans1, ", ", ans2) # Driver Code if __name__ == '__main__': l, r = 1, 10 findpair(l, r) # This code is contributed # by 29AjayKumar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the possible pair
static void findpair(int l, int r)
{
// ans1, ans2 store value of x
// and y respectively
int ans1 = l;
int ans2 = 2 * l;
Console.WriteLine( ans1 + ", " + ans2 );
}
// Driver Code
public static void Main()
{
int l = 1, r = 10;
findpair(l, r);
}
}
// This code is contruibuted by Ryuga
PHP
<?php
// PHP implementation of the approach
// Function to return the possible pair
function findpair($l, $r)
{
// ans1, ans2 store value of x
// and y respectively
$ans1 = $l;
$ans2 = 2 * $l;
echo ($ans1 . ", " . $ans2);
}
// Driver Code
$l = 1; $r = 10;
findpair($l, $r);
// This code contributed by Rajput-Ji
?>
Javascript
<script>
// Javascript implementation of the approach
// Function to return the possible pair
function findpair(l,r)
{
// ans1, ans2 store value of x
// and y respectively
let ans1 = l;
let ans2 = 2 * l;
document.write( ans1 + ", " + ans2 );
}
// Driver Code
let l = 1, r = 10;
findpair(l, r);
// This code is contributed by rag2127
</script>
1, 2
Publicación traducida automáticamente
Artículo escrito por akhand_mishra y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA