Se le da una array de n enteros y un entero K. Encuentre el número total de pares no ordenados {i, j} tales que el valor absoluto de (ai + aj – K), es decir, |ai + aj – k| es mínimo posible donde i != j.
Ejemplos:
Input : arr[] = {0, 4, 6, 2, 4},
K = 7
Output : Minimal Value = 1
Total Pairs = 5
Explanation : Pairs resulting minimal value are :
{a1, a3}, {a2, a4}, {a2, a5}, {a3, a4}, {a4, a5}
Input : arr[] = {4, 6, 2, 4} , K = 9
Output : Minimal Value = 1
Total Pairs = 4
Explanation : Pairs resulting minimal value are :
{a1, a2}, {a1, a4}, {a2, a3}, {a2, a4}
Una solución simple es iterar sobre todos los pares posibles y para cada par verificaremos si el valor de (ai + aj – K) es menor que nuestro valor actual más pequeño de no. Entonces, como resultado de la condición anterior, tenemos un total de tres casos:
- abs( ai + aj – K) > más pequeño : no haga nada ya que este par no contará en el valor mínimo posible.
- abs(ai + aj – K) = más pequeño : incrementa el conteo del par resultante del valor mínimo posible.
- abs( ai + aj – K) < más pequeño : actualiza el valor más pequeño y establece el conteo en 1.
C++
// CPP program to find number of pairs and minimal
// possible value
#include<bits/stdc++.h>
using namespace std;
// function for finding pairs and min value
void pairs(int arr[], int n, int k)
{
// initialize smallest and count
int smallest = INT_MAX;
int count=0;
// iterate over all pairs
for (int i=0; i<n; i++)
for(int j=i+1; j<n; j++)
{
// is abs value is smaller than smallest
// update smallest and reset count to 1
if ( abs(arr[i] + arr[j] - k) < smallest )
{
smallest = abs(arr[i] + arr[j] - k);
count = 1;
}
// if abs value is equal to smallest
// increment count value
else if (abs(arr[i] + arr[j] - k) == smallest)
count++;
}
// print result
cout << "Minimal Value = " << smallest << "\n";
cout << "Total Pairs = " << count << "\n";
}
// driver program
int main()
{
int arr[] = {3, 5, 7, 5, 1, 9, 9};
int k = 12;
int n = sizeof(arr) / sizeof(arr[0]);
pairs(arr, n, k);
return 0;
}
Java
// Java program to find number of pairs
// and minimal possible value
import java.util.*;
class GFG {
// function for finding pairs and min value
static void pairs(int arr[], int n, int k)
{
// initialize smallest and count
int smallest = Integer.MAX_VALUE;
int count=0;
// iterate over all pairs
for (int i=0; i<n; i++)
for(int j=i+1; j<n; j++)
{
// is abs value is smaller than
// smallest update smallest and
// reset count to 1
if ( Math.abs(arr[i] + arr[j] - k) <
smallest )
{
smallest = Math.abs(arr[i] + arr[j]
- k);
count = 1;
}
// if abs value is equal to smallest
// increment count value
else if (Math.abs(arr[i] + arr[j] - k)
== smallest)
count++;
}
// print result
System.out.println("Minimal Value = " +
smallest);
System.out.println("Total Pairs = " +
count);
}
/* Driver program to test above function */
public static void main(String[] args)
{
int arr[] = {3, 5, 7, 5, 1, 9, 9};
int k = 12;
int n = arr.length;
pairs(arr, n, k);
}
}
// This code is contributed by Arnav Kr. Mandal.
Python3
# Python3 program to find number of pairs
# and minimal possible value
# function for finding pairs and min value
def pairs(arr, n, k):
# initialize smallest and count
smallest = 999999999999
count = 0
# iterate over all pairs
for i in range(n):
for j in range(i + 1, n):
# is abs value is smaller than smallest
# update smallest and reset count to 1
if abs(arr[i] + arr[j] - k) < smallest:
smallest = abs(arr[i] + arr[j] - k)
count = 1
# if abs value is equal to smallest
# increment count value
elif abs(arr[i] + arr[j] - k) == smallest:
count += 1
# print result
print("Minimal Value = ", smallest)
print("Total Pairs = ", count)
# Driver Code
if __name__ == '__main__':
arr = [3, 5, 7, 5, 1, 9, 9]
k = 12
n = len(arr)
pairs(arr, n, k)
# This code is contributed by PranchalK
C#
// C# program to find number
// of pairs and minimal
// possible value
using System;
class GFG
{
// function for finding
// pairs and min value
static void pairs(int []arr,
int n, int k)
{
// initialize
// smallest and count
int smallest = 0;
int count = 0;
// iterate over all pairs
for (int i = 0; i < n; i++)
for(int j = i + 1; j < n; j++)
{
// is abs value is smaller
// than smallest update
// smallest and reset
// count to 1
if (Math.Abs(arr[i] +
arr[j] - k) < smallest )
{
smallest = Math.Abs(arr[i] +
arr[j] - k);
count = 1;
}
// if abs value is equal
// to smallest increment
// count value
else if (Math.Abs(arr[i] +
arr[j] - k) ==
smallest)
count++;
}
// print result
Console.WriteLine("Minimal Value = " +
smallest);
Console.WriteLine("Total Pairs = " +
count);
}
// Driver Code
public static void Main()
{
int []arr = {3, 5, 7,
5, 1, 9, 9};
int k = 12;
int n = arr.Length;
pairs(arr, n, k);
}
}
// This code is contributed
// by anuj_67.
PHP
<?php
// PHP program to find number of
// pairs and minimal possible value
// function for finding pairs
// and min value
function pairs($arr, $n, $k)
{
// initialize smallest and count
$smallest = PHP_INT_MAX;
$count = 0;
// iterate over all pairs
for ($i = 0; $i < $n; $i++)
for($j = $i + 1; $j < $n; $j++)
{
// is abs value is smaller than smallest
// update smallest and reset count to 1
if ( abs($arr[$i] + $arr[$j] - $k) < $smallest )
{
$smallest = abs($arr[$i] + $arr[$j] - $k);
$count = 1;
}
// if abs value is equal to smallest
// increment count value
else if (abs($arr[$i] +
$arr[$j] - $k) == $smallest)
$count++;
}
// print result
echo "Minimal Value = " , $smallest , "\n";
echo "Total Pairs = ", $count , "\n";
}
// Driver Code
$arr = array (3, 5, 7, 5, 1, 9, 9);
$k = 12;
$n = sizeof($arr);
pairs($arr, $n, $k);
// This code is contributed by aj_36
?>
Javascript
<script>
// Javascript program to find number of pairs and minimal
// possible value
// function for finding pairs and min value
function pairs(arr, n, k)
{
// initialize smallest and count
var smallest = 1000000000;
var count=0;
// iterate over all pairs
for (var i=0; i<n; i++)
for(var j=i+1; j<n; j++)
{
// is Math.abs value is smaller than smallest
// update smallest and reset count to 1
if ( Math.abs(arr[i] + arr[j] - k) < smallest )
{
smallest = Math.abs(arr[i] + arr[j] - k);
count = 1;
}
// if Math.abs value is equal to smallest
// increment count value
else if (Math.abs(arr[i] + arr[j] - k) == smallest)
count++;
}
// print result
document.write( "Minimal Value = " + smallest + "<br>");
document.write( "Total Pairs = " + count + "<br>");
}
// driver program
var arr = [3, 5, 7, 5, 1, 9, 9];
var k = 12;
var n = arr.length;
pairs(arr, n, k);
</script>
Producción:
Minimal Value = 0 Total Pairs = 4
Complejidad de tiempo: O(n 2 ) donde n es el número de elementos en la array.
Espacio Auxiliar : O(1)
Una solución eficiente es utilizar un árbol de búsqueda binario autoequilibrado (que se implementa en conjunto en C++ y TreeSet en Java). Podemos encontrar el elemento más cercano en el tiempo O (log n) en el mapa.
C++
// C++ program to find number of pairs
// and minimal possible value
#include<bits/stdc++.h>
using namespace std;
// function for finding pairs and min value
void pairs(int arr[], int n, int k)
{
// initialize smallest and count
int smallest = INT_MAX, count = 0;
set<int> s;
// iterate over all pairs
s.insert(arr[0]);
for (int i=1; i<n; i++)
{
// Find the closest elements to k - arr[i]
int lower = *lower_bound(s.begin(),
s.end(),
k - arr[i]);
int upper = *upper_bound(s.begin(),
s.end(),
k - arr[i]);
// Find absolute value of the pairs formed
// with closest greater and smaller elements.
int curr_min = min(abs(lower + arr[i] - k),
abs(upper + arr[i] - k));
// is abs value is smaller than smallest
// update smallest and reset count to 1
if (curr_min < smallest)
{
smallest = curr_min;
count = 1;
}
// if abs value is equal to smallest
// increment count value
else if (curr_min == smallest )
count++;
s.insert(arr[i]);
} // print result
cout << "Minimal Value = " << smallest <<"\n";
cout << "Total Pairs = " << count <<"\n";
}
// driver program
int main()
{
int arr[] = {3, 5, 7, 5, 1, 9, 9};
int k = 12;
int n = sizeof(arr) / sizeof(arr[0]);
pairs(arr, n, k);
return 0;
}
Java
// Java program to find number of pairs
// and minimal possible value
import java.util.*;
class GFG {
// function for finding pairs and min value
static void pairs(int arr[], int n, int k)
{
// initialize smallest and count
int smallest = Integer.MAX_VALUE;
int count = 0;
// iterate over all pairs
for (int i = 0; i < n; i++)
for(int j = i + 1; j < n; j++)
{
// is abs value is smaller than
// smallest update smallest and
// reset count to 1
if ( Math.abs(arr[i] + arr[j] - k) <
smallest )
{
smallest = Math.abs(arr[i] + arr[j]
- k);
count = 1;
}
// if abs value is equal to smallest
// increment count value
else if (Math.abs(arr[i] + arr[j] - k)
== smallest)
count++;
}
// print result
System.out.println("Minimal Value = " +
smallest);
System.out.println("Total Pairs = " +
count);
}
/* Driver program to test above function */
public static void main(String[] args)
{
int arr[] = {3, 5, 7, 5, 1, 9, 9};
int k = 12;
int n = arr.length;
pairs(arr, n, k);
}
}
// This code is contributed by Rajput-Ji
C#
// C# program to find number of pairs
// and minimal possible value
using System;
public class GFG {
// function for finding pairs and min value
static void pairs(int []arr, int n, int k)
{
// initialize smallest and count
int smallest = int.MaxValue;
int count = 0;
// iterate over all pairs
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
{
// is abs value is smaller than
// smallest update smallest and
// reset count to 1
if (Math.Abs(arr[i] + arr[j] - k) < smallest) {
smallest = Math.Abs(arr[i] + arr[j] - k);
count = 1;
}
// if abs value is equal to smallest
// increment count value
else if (Math.Abs(arr[i] + arr[j] - k) == smallest)
count++;
}
// print result
Console.WriteLine("Minimal Value = " + smallest);
Console.WriteLine("Total Pairs = " + count);
}
/* Driver program to test above function */
public static void Main(String[] args)
{
int []arr = { 3, 5, 7, 5, 1, 9, 9 };
int k = 12;
int n = arr.Length;
pairs(arr, n, k);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// javascript program to find number of pairs
// and minimal possible value
// function for finding pairs and min value
function pairs(arr , n , k)
{
// initialize smallest and count
var smallest = Number.MAX_VALUE;
var count = 0;
// iterate over all pairs
for (i = 0; i < n; i++)
for (j = i + 1; j < n; j++)
{
// is abs value is smaller than
// smallest update smallest and
// reset count to 1
if (Math.abs(arr[i] + arr[j] - k) < smallest) {
smallest = Math.abs(arr[i] + arr[j] - k);
count = 1;
}
// if abs value is equal to smallest
// increment count value
else if (Math.abs(arr[i] + arr[j] - k) == smallest)
count++;
}
// print result
document.write("Minimal Value = " + smallest);
document.write("<br/>Total Pairs = " + count);
}
/* Driver program to test above function */
var arr = [ 3, 5, 7, 5, 1, 9, 9 ];
var k = 12;
var n = arr.length;
pairs(arr, n, k);
// This code is contributed by Rajput-Ji
</script>
Producción:
Minimal Value = 0 Total Pairs = 4
Complejidad de tiempo: O (n Log n)
Espacio Auxiliar: O(n) para almacenar elementos en el conjunto
Este artículo es una contribución de Shivam Pradhan (anuj_charm) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA