Dada una array arr[] que consta de N enteros positivos, la tarea es imprimir todos los pares de elementos de array cuya suma no existe en la array dada. Si no existe tal par, imprima “-1” .
Ejemplos:
Entrada: arr[] = {2, 4, 2, 6}
Salida:
(2, 6)
(4, 6)
(2, 6)
Explicación:
Todos los pares posibles en la array son (2, 4), (2, 2), (2, 6), (4, 2), (4, 6) y (2, 6).
Entre estos, los pares (2, 6), (4, 6) y (2, 6) tienen sumas {8, 10, 8} respectivamente que no están presentes en el arreglo.
Entrada: arr[] = {1, 1, 2, 3}
Salida:
(2, 3)
Explicación:
Todos los pares posibles en la array son (1, 1), (1, 2), (1, 3), ( 1, 2), (1, 3) y (2, 3).
Entre estos, el único par cuya suma no está presente en el arreglo es (2, 3).
Enfoque ingenuo:
el enfoque más simple para resolver el problema es generar todos los pares posibles uno por uno y, para cada par, verificar si su suma existe en la array recorriendo la array. Si se encuentra algún par con su suma existente en la array, imprima el par. De lo contrario, pase al siguiente par.
Tiempo Complejidad: O(N 3 )
Espacio Auxiliar: O(N)
Enfoque Eficiente:
El problema se puede resolver usando un HashSet . Siga los pasos a continuación para resolver el problema:
- Almacene los elementos en el de la array en un HashSet .
- Ahora, recorra todos los elementos de la array y genere todos los pares posibles.
- Para cada par, verifique si la suma de ese par está presente en el HashSet o no. Si es así, imprima el par. De lo contrario, pase al siguiente par.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print all pairs
// with sum not present in the array
void findPair(int arr[], int n)
{
int i, j;
// Corner Case
if (n < 2)
{
cout << "-1" << endl;
}
// Stores the distinct array
// elements
set <int> hashMap;
for(int k = 0; k < n; k++)
{
hashMap.insert(arr[k]);
}
// Generate all possible pairs
for(i = 0; i < n - 1; i++)
{
for(j = i + 1; j < n; j++)
{
// Calculate sum of current pair
int sum = arr[i] + arr[j];
// Check if the sum exists in
// the HashSet or not
if (hashMap.find(sum) == hashMap.end())
{
cout << "(" << arr[i] << ", "
<< arr[j] << ")" << endl;
}
}
}
}
// Driver code
int main()
{
int arr[] = { 2, 4, 2, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
findPair(arr, n);
return 0;
}
// This code is contributed by divyeshrabadiya07
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG {
// Function to print all pairs
// with sum not present in the array
public static void findPair(
int[] arr, int n)
{
int i, j;
// Corner Case
if (n < 2) {
System.out.println("-1");
}
// Stores the distinct array
// elements
HashSet<Integer> hashMap
= new HashSet<Integer>();
for (Integer k : arr) {
hashMap.add(k);
}
// Generate all possible pairs
for (i = 0; i < n - 1; i++) {
for (j = i + 1; j < n; j++) {
// Calculate sum of current pair
int sum = arr[i] + arr[j];
// Check if the sum exists in
// the HashSet or not
if (!hashMap.contains(sum)) {
System.out.println(
"(" + arr[i] + ", "
+ arr[j] + ")");
}
}
}
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 2, 4, 2, 6 };
int n = arr.length;
findPair(arr, n);
}
}
Python3
# Python3 program to implement
# the above approach
# Function to print all pairs
# with sum not present in the array
def findPair(arr, n):
# Corner Case
if (n < 2):
print("-1")
# Stores the distinct array
# elements
hashMap = []
for k in arr:
hashMap.append(k)
# Generate all possible pairs
for i in range (n - 1):
for j in range (i + 1, n):
# Calculate sum of current pair
sum = arr[i] + arr[j]
# Check if the sum exists in
# the HashSet or not
if sum not in hashMap:
print("(", arr[i] , ", ",
arr[j] , ")")
# Driver Code
if __name__ == "__main__":
arr = [ 2, 4, 2, 6 ]
n = len(arr)
findPair(arr, n)
# This code is contributed by ChitraNayal
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to print all pairs
// with sum not present in the array
public static void findPair(int[] arr, int n)
{
int i, j;
// Corner Case
if (n < 2)
{
Console.Write("-1");
}
// Stores the distinct array
// elements
HashSet<int> hashMap = new HashSet<int>();
foreach(int k in arr)
{
hashMap.Add(k);
}
// Generate all possible pairs
for(i = 0; i < n - 1; i++)
{
for(j = i + 1; j < n; j++)
{
// Calculate sum of current pair
int sum = arr[i] + arr[j];
// Check if the sum exists in
// the HashSet or not
if (!hashMap.Contains(sum))
{
Console.Write("(" + arr[i] +
", " + arr[j] +
")\n");
}
}
}
}
// Driver Code
public static void Main(string[] args)
{
int[] arr = { 2, 4, 2, 6 };
int n = arr.Length;
findPair(arr, n);
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to print all pairs
// with sum not present in the array
function findPair(arr, n)
{
var i, j;
// Corner Case
if (n < 2)
{
document.write( "-1");
}
// Stores the distinct array
// elements
var hashMap = new Set();
for(var k = 0; k < n; k++)
{
hashMap.add(arr[k]);
}
// Generate all possible pairs
for(i = 0; i < n - 1; i++)
{
for(j = i + 1; j < n; j++)
{
// Calculate sum of current pair
var sum = arr[i] + arr[j];
// Check if the sum exists in
// the HashSet or not
if (!hashMap.has(sum))
{
document.write( "(" + arr[i] + ", "
+ arr[j] + ")<br>");
}
}
}
}
// Driver code
var arr = [2, 4, 2, 6];
var n = arr.length;
findPair(arr, n);
// This code is contributed by famously.
</script>
(2, 6) (4, 6) (2, 6)
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)