Dada una array de enteros distintos, imprima todos los pares que tengan un valor positivo y un valor negativo de un número que existe en la array.
Nota: No importa el orden de los pares.
Ejemplos:
Input: arr[] = { 1, -3, 2, 3, 6, -1 }
Output: -1 1 -3 3
Input: arr[] = { 4, 8, 9, -4, 1, -1, -8, -9 }
Output: -1 1 -4 4 -8 8 -9 9
Un enfoque ingenuo es ejecutar dos bucles, es decir, considere cada elemento de la array usando el bucle externo y busque su valor positivo/negativo correspondiente en la array usando un bucle interno. Del mismo modo, encuentra todos los pares. La complejidad temporal de este enfoque será O( n 2 ).
Un mejor enfoque es usar la ordenación , es decir, primero ordenar la array y luego, para cada elemento negativo, hacer una búsqueda binaria para encontrar su contraparte (+ cinco números). Si lo encuentra, imprima ese par. Si el elemento actual es positivo, rompa ese ciclo ya que después de eso habrá todos los números positivos.
C++
// CPP program to find pairs of positive
// and negative values present in an array.
#include <bits/stdc++.h>
using namespace std;
void printPairs(int arr[], int n)
{
bool pair_exists = false;
// Sort the array
sort(arr, arr + n);
// Traverse the array
for (int i = 0; i < n; i++) {
// For every arr[i] < 0 element,
// do a binary search for arr[i] > 0.
if (arr[i] < 0) {
// If found, print the pair.
if (binary_search(arr, arr + n, -arr[i])) {
cout << arr[i] << ", " << -arr[i] << endl;
pair_exists = true;
}
}
else
break;
}
if (pair_exists == false)
cout << "No such pair exists";
}
// Driver code
int main()
{
int arr[] = { 4, 8, 9, -4, 1, -1, -8, -9 };
int n = sizeof(arr) / sizeof(arr[0]);
printPairs(arr, n);
return 0;
}
Java
// Java program to find pairs
// of positive and negative
// values present in an array.
import java.util.*;
class GFG
{
static void printPairs(int arr[], int n)
{
boolean pair_exists = false;
// Sort the array
Arrays.sort(arr);
// Traverse the array
for (int i = 0; i < n; i++)
{
// For every arr[i] < 0 element,
// do a binary search for arr[i] > 0.
if (arr[i] < 0)
{
// If found, print the pair.
if (java.util.Arrays.binarySearch(arr, -arr[i])!=-1)
{
System.out.println(arr[i] + ", " + -arr[i] );
pair_exists = true;
}
}
else
break;
}
if (pair_exists == false)
System.out.println("No such pair exists");
}
// Driver code
public static void main(String args[])
{
int arr[] = { 4, 8, 9, -4, 1, -1, -8, -9 };
int n =arr.length;
printPairs(arr, n);
}
}
// This code is contributed
// by Arnab Kundu
Python 3
# Python3 program to find pairs of positive
# and negative values present in an array.
# function for binary search
def binary_search(a, x, lo=0, hi=None):
if hi is None:
hi = len(a)
while lo < hi:
mid = (lo+hi)//2
midval = a[mid]
if midval < x:
lo = mid+1
elif midval > x:
hi = mid
else:
return mid
return -1
def printPairs(arr, n):
pair_exists = False
# Sort the array
arr.sort()
# Traverse the array
for i in range(n):
# For every arr[i] < 0 element,
# do a binary search for arr[i] > 0.
if (arr[i] < 0):
# If found, print the pair.
if (binary_search(arr,-arr[i])):
print(arr[i] , ", " , -arr[i])
pair_exists = True
else:
break
if (pair_exists == False):
print("No such pair exists")
# Driver code
if __name__=='__main__':
arr = [ 4, 8, 9, -4, 1, -1, -8, -9 ]
n = len(arr)
printPairs(arr, n)
# this code is contributed by ash264
C#
// C# program to find pairs
// of positive and negative
// values present in an array.
using System;
public class GFG{
static void printPairs(int []arr, int n)
{
bool pair_exists = false;
// Sort the array
Array.Sort(arr);
// Traverse the array
for (int i = 0; i < n; i++)
{
// For every arr[i] < 0 element,
// do a binary search for arr[i] > 0.
if (arr[i] < 0)
{
// If found, print the pair.
if (Array.BinarySearch(arr, -arr[i])!=-1)
{
Console.WriteLine(arr[i] + ", " + -arr[i] );
pair_exists = true;
}
}
else
break;
}
if (pair_exists == false)
Console.WriteLine("No such pair exists");
}
// Driver code
public static void Main()
{
int []arr = { 4, 8, 9, -4, 1, -1, -8, -9 };
int n =arr.Length;
printPairs(arr, n);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to find pairs of positive
// and negative values present in an array.
function printPairs(arr, n) {
let pair_exists = false;
// Sort the array
arr.sort((a, b) => a - b);
// Traverse the array
for (let i = 0; i < n; i++) {
// For every arr[i] < 0 element,
// do a binary search for arr[i] > 0.
if (arr[i] < 0) {
// If found, print the pair.
if (arr.includes(-arr[i])) {
document.write(arr[i] + ", " + -arr[i] + "<br>");
pair_exists = true;
}
}
else
break;
}
if (pair_exists == false)
document.write("No such pair exists");
}
// Driver code
let arr = [4, 8, 9, -4, 1, -1, -8, -9];
let n = arr.length;
printPairs(arr, n);
</script>
Producción:
-9, 9 -8, 8 -4, 4 -1, 1
Complejidad de tiempo: O (nlogn)
Un enfoque eficiente es usar hashing . A continuación se detallan los pasos necesarios:
- Comience a atravesar la array.
- Almacene todos los valores positivos en un conjunto desordenado.
- Compruebe para cada elemento negativo, si su elemento positivo correspondiente existe en el conjunto o no.
- En caso afirmativo, imprima el par
- Además, mantenga una bandera para verificar si no existe tal par.
C++
// CPP program to find pairs of positive
// and negative values present in an array
#include <bits/stdc++.h>
using namespace std;
// Function to print pairs of positive
// and negative values present in the array
void printPairs(int arr[], int n)
{
unordered_set<int> pairs;
bool pair_exists = false;
// Store all the positive elements
// in the unordered_set
for (int i = 0; i < n; i++)
if (arr[i] > 0)
pairs.insert(arr[i]);
// Start traversing the array
for (int i = 0; i < n; i++) {
// Check if the positive value of current
// element exists in the set or not
if (arr[i] < 0)
if (pairs.find(-arr[i]) != pairs.end())
{ // Print that pair
cout << arr[i] << ", " << -arr[i] << endl;
pair_exists = true;
}
}
if (pair_exists == false)
cout << "No such pair exists";
}
// Driver code
int main()
{
int arr[] = { 4, 8, 9, -4, 1, -1, -8, -9 };
int n = sizeof(arr) / sizeof(arr[0]);
printPairs(arr, n);
return 0;
}
Java
// Java program to find pairs of positive
// and negative values present in an array
import java.util.*;
class GFG
{
// Function to print pairs of positive
// and negative values present in the array
static void printPairs(int arr[], int n)
{
Set<Integer> pairs = new HashSet<Integer>();
boolean pair_exists = false;
// Store all the positive elements
// in the unordered_set
for (int i = 0; i < n; i++)
if (arr[i] > 0)
pairs.add(arr[i]);
// Start traversing the array
for (int i = 0; i < n; i++)
{
// Check if the positive value of current
// element exists in the set or not
if (arr[i] < 0)
if (pairs.contains(-arr[i]))
{
// Print that pair
System.out.println(arr[i] + ", " + -arr[i]);
pair_exists = true;
}
}
if (pair_exists == false)
System.out.println("No such pair exists");
}
// Driver code
public static void main(String args[])
{
int arr[] = { 4, 8, 9, -4, 1, -1, -8, -9 };
int n = arr.length;
printPairs(arr, n);
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 program to find pairs of positive
# and negative values present in an array
# Function to print pairs of positive
# and negative values present in the array
def printPairs(arr, n):
pairs = set()
pair_exists = False
# Store all the positive elements
# in the unordered_set
for i in range(0, n):
if arr[i] > 0:
pairs.add(arr[i])
# Start traversing the array
for i in range(0, n):
# Check if the positive value of current
# element exists in the set or not
if arr[i] < 0:
if (-arr[i]) in pairs:
# Print that pair
print("{}, {}".format(arr[i], -arr[i]))
pair_exists = True
if pair_exists == False:
print("No such pair exists")
# Driver code
if __name__ == "__main__":
arr = [4, 8, 9, -4, 1, -1, -8, -9]
n = len(arr)
printPairs(arr, n)
# This code is contributed by Rituraj Jain
C#
// C# program to find pairs of positive
// and negative values present in an array
using System;
using System.Collections.Generic;
class GFG
{
// Function to print pairs of positive
// and negative values present in the array
static void printPairs(int []arr, int n)
{
HashSet<int> pairs = new HashSet<int>();
bool pair_exists = false;
// Store all the positive elements
// in the unordered_set
for (int i = 0; i < n; i++)
if (arr[i] > 0)
pairs.Add(arr[i]);
// Start traversing the array
for (int i = 0; i < n; i++)
{
// Check if the positive value of current
// element exists in the set or not
if (arr[i] < 0)
if (pairs.Contains(-arr[i]))
{
// Print that pair
Console.WriteLine(arr[i] + ", " + -arr[i]);
pair_exists = true;
}
}
if (pair_exists == false)
Console.WriteLine("No such pair exists");
}
// Driver code
public static void Main(String []args)
{
int []arr = { 4, 8, 9, -4, 1, -1, -8, -9 };
int n = arr.Length;
printPairs(arr, n);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript program to find pairs of positive
// and negative values present in an array
// Function to print pairs of positive
// and negative values present in the array
function printPairs(arr,n)
{
let pairs = new Set();
let pair_exists = false;
// Store all the positive elements
// in the unordered_set
for (let i = 0; i < n; i++)
if (arr[i] > 0)
pairs.add(arr[i]);
// Start traversing the array
for (let i = 0; i < n; i++)
{
// Check if the positive value of current
// element exists in the set or not
if (arr[i] < 0)
if (pairs.has(-arr[i]))
{
// Print that pair
document.write(arr[i] + ", " + -arr[i]+"<br>");
pair_exists = true;
}
}
if (pair_exists == false)
document.write("No such pair exists");
}
// Driver code
let arr=[4, 8, 9, -4, 1, -1, -8, -9];
let n = arr.length;
printPairs(arr, n);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
-4, 4 -1, 1 -8, 8 -9, 9
Complejidad de tiempo: O(n)
Publicación traducida automáticamente
Artículo escrito por Aashish Chauhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA