Dada una array de enteros no negativos y un número x, encuentre un par en la array cuyo producto sea el más cercano a x.
Ejemplos:
Input : arr[] = [2, 3, 5, 9]
x = 47
Output : {5, 9}
Input : arr[] = [2, 3, 5, 9]
x = 8
Output : {2, 5}
Método 1
Una solución simple es considerar cada par y realizar un seguimiento del par más cercano (la diferencia absoluta entre el producto del par yx es mínima). Finalmente, imprima el par más cercano. La complejidad temporal de esta solución es O( 
)
Método 2 O(n Registro n)
- Ordenar la array
- Inicialice una variable diff como infinita (Diff se usa para almacenar la diferencia entre un par y x). Necesitamos encontrar la diferencia mínima.
- Recorra la array y para cada i, haga lo siguiente:
- Encuentre el límite inferior para x/arr[i] en el subarreglo a la derecha de arr[i], es decir, en el subarreglo arr[i+1..n-1]. Que se denote por l.
- Encuentre el límite superior para x/arr[i] en el subarreglo a la derecha de arr[i], es decir, en el subarreglo arr[i+1..n-1]. Que se denote por u.
- Si min(abs((arr[i] * l) – x), abs((arr[i] * u) – x)) < diff, entonces actualice diff y resulte
Método 3 O(n for sorted)
Una solución eficiente puede encontrar el par en tiempo O(n). El siguiente es el algoritmo detallado.
1) Initialize a variable diff as infinite
(Diff is used to store the difference
between pair and x). We need to find
the minimum diff.
2) Initialize two index variables l and r
in the given sorted array.
(a) Initialize first to the leftmost index:
l = 0
(b) Initialize second the rightmost index:
r = n-1
3) Loop while l < r.
(a) If abs((arr[l] * arr[r]) - x) < diff
then update diff and result
(b) Else if((arr[l] * arr[r]) < x) then
l++
(c) Else r--
La siguiente es la implementación del algoritmo anterior.
C++
// Simple C++ program to find the pair with
// product closest to a given no.
#include <bits/stdc++.h>
using namespace std;
// Prints the pair with product closest to x
void printClosest(int arr[], int n, int x)
{
int res_l, res_r; // To store indexes of result pair
// Initialize left and right indexes and
// difference between pair product and x
int l = 0, r = n - 1, diff = INT_MAX;
// While there are elements between l and r
while (r > l) {
// Check if this pair is closer than
// the closest pair so far
if (abs(arr[l] * arr[r] - x) < diff) {
res_l = l;
res_r = r;
diff = abs(arr[l] * arr[r] - x);
}
// If this pair has more product,
// move to smaller values.
if (arr[l] * arr[r] > x)
r--;
else // Move to larger values
l++;
}
cout << " The closest pair is "
<< arr[res_l] << " and " << arr[res_r];
}
// Driver program to test above functions
int main()
{
int arr[] = { 2, 3, 5, 9 }, x = 8;
int n = sizeof(arr) / sizeof(arr[0]);
printClosest(arr, n, x);
return 0;
}
Java
// Simple Java program to find
// the pair with product closest
// to a given no.
import java.io.*;
class GFG
{
// Prints the pair with
// product closest to x
static void printClosest(int arr[],
int n, int x)
{
// To store indexes of result pair
int res_l = 0, res_r = 0;
// Initialize left and right
// indexes and difference
// between pair product and x
int l = 0, r = n - 1, diff = Integer.MAX_VALUE;
// While there are
// elements between l and r
while (r > l)
{
// Check if this pair is closer
// than the closest pair so far
if (Math.abs(arr[l] * arr[r] - x) < diff)
{
res_l = l;
res_r = r;
diff = Math.abs(arr[l] * arr[r] - x);
}
// If this pair has more product,
// move to smaller values.
if (arr[l] * arr[r] > x)
r--;
// Move to larger values
else
l++;
}
System.out.print("The closest pair is ");
System.out.print (arr[res_l] +
" and " +
arr[res_r]);
}
// Driver Code
public static void main (String[] args)
{
int arr[] = {2, 3, 5, 9};
int x = 8;
int n = arr.length;
printClosest(arr, n, x);
}
}
// This code is contributed by anuj_67.
Python3
# Simple Python3 program to find
# the pair with product closest
# to a given no.
import sys
# Prints the pair with
# product closest to x
def printClosest(arr, n, x):
# To store indexes
# of result pair
res_l = 0;
res_r = 0;
# Initialize left and right
# indexes and difference
# between pair product and x
l = 0;
r = n - 1;
diff = sys.maxsize;
# While there are elements
# between l and r
while (r > l):
# Check if this pair is
# closer than the closest
# pair so far
if (abs(arr[l] *
arr[r] - x) < diff):
res_l = l;
res_r = r;
diff = abs(arr[l] *
arr[r] - x);
# If this pair has more
# product, move to smaller
# values.
if (arr[l] * arr[r] > x):
r = r - 1;
# Move to larger values
else:
l = l + 1;
print("The closest pair is", arr[res_l] ,
"and", arr[res_r]);
# Driver Code
arr = [2, 3, 5, 9];
x = 8;
n = len(arr);
printClosest(arr, n, x);
# This code is contributed
# by rahul
C#
// Simple C# program to find
// the pair with product closest
// to a given no.
using System;
class GFG
{
// Prints the pair with
// product closest to x
static void printClosest(int []arr,
int n, int x)
{
// To store indexes of result pair
int res_l = 0, res_r = 0;
// Initialize left and right
// indexes and difference
// between pair product and x
int l = 0, r = n - 1,
diff = int.MaxValue;
// While there are
// elements between l and r
while (r > l)
{
// Check if this pair is closer
// than the closest pair so far
if (Math.Abs(arr[l] *
arr[r] - x) < diff)
{
res_l = l;
res_r = r;
diff = Math.Abs(arr[l] *
arr[r] - x);
}
// If this pair has more product,
// move to smaller values.
if (arr[l] * arr[r] > x)
r--;
// Move to larger values
else
l++;
}
Console.Write("The closest pair is ");
Console.Write (arr[res_l] +
" and " +
arr[res_r]);
}
// Driver Code
public static void Main ()
{
int []arr = {2, 3, 5, 9};
int x = 8;
int n = arr.Length;
printClosest(arr, n, x);
}
}
// This code is contributed by anuj_67.
PHP
<?php
// Simple PHP program to find
// the pair with product closest
// to a given no.
// Prints the pair with
// product closest to x
function printClosest($arr, $n, $x)
{
// To store indexes
// of result pair
$res_l; $res_r;
// Initialize left and right
// indexes and difference
// between pair product and x
$l = 0; $r = $n - 1; $diff = PHP_INT_MAX;
// While there are elements
// between l and r
while ($r > $l)
{
// Check if this pair is
// closer than the closest
// pair so far
if (abs($arr[$l] *
$arr[$r] - $x) < $diff)
{
$res_l = $l;
$res_r = $r;
$diff = abs($arr[$l] *
$arr[$r] - $x);
}
// If this pair has more
// product, move to smaller
// values.
if ($arr[$l] * $arr[$r] > $x)
$r--;
// Move to larger values
else
$l++;
}
echo " The closest pair is " ,
$arr[$res_l] , " and " ,
$arr[$res_r];
}
// Driver Code
$arr = array(2, 3, 5, 9);
$x = 8;
$n = count($arr);
printClosest($arr, $n, $x);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Simple Javascript program to find the pair with
// product closest to a given no.
// Prints the pair with product closest to x
function printClosest(arr, n, x)
{
var res_l, res_r; // To store indexes of result pair
// Initialize left and right indexes and
// difference between pair product and x
var l = 0, r = n - 1, diff = 10000000000;
// While there are elements between l and r
while (r > l) {
// Check if this pair is closer than
// the closest pair so far
if (Math.abs(arr[l] * arr[r] - x) < diff) {
res_l = l;
res_r = r;
diff = Math.abs(arr[l] * arr[r] - x);
}
// If this pair has more product,
// move to smaller values.
if (arr[l] * arr[r] > x)
r--;
else // Move to larger values
l++;
}
document.write( " The closest pair is "
+ arr[res_l] + " and " + arr[res_r]);
}
// Driver program to test above functions
var arr = [2, 3, 5, 9 ], x = 8;
var n = arr.length;
printClosest(arr, n, x);
</script>
Producción :
The closest pair is 2 and 5
Publicación traducida automáticamente
Artículo escrito por aganjali10 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA