Dada una array arr[] de tamaño N y un número entero K , la tarea es encontrar el número de pares distintos en la array cuya suma es igual a K.
Ejemplos:
Entrada: arr[] = { 5, 6, 5, 7, 7, 8 }, K = 13
Salida: 2
Explicación:
Los pares con suma K( = 13) son { (arr[0], arr[5]), (arr[1], arr[3]), (arr[1], arr[4]) }, es decir, {(5, 8), (6, 7), (6, 7)}.
Por lo tanto, pares distintos con suma K( = 13) son { (arr[0], arr[5]), (arr[1], arr[3]) }.
Por lo tanto, la salida requerida es 2.Entrada: arr[] = { 2, 6, 7, 1, 8, 3 }, K = 10
Salida : 2
Explicación:
Los pares distintos con suma K( = 10) son { (arr[0], arr[4]) , (arr[2], arr[5]) }.
Por lo tanto, la salida requerida es 2.
Enfoque ingenuo: el enfoque más simple para resolver este problema es utilizar la técnica Two Pointer . La idea es ordenar la array y eliminar todos los elementos duplicados consecutivos de la array dada . Finalmente, cuente los pares en la array dada cuya suma es igual a K . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos cntPairs , para almacenar el recuento de pares distintos de la array con suma K.
- Ordena la array en orden creciente .
- Inicialice dos variables, digamos i = 0 , j = N – 1 como el índice de los punteros izquierdo y derecho para atravesar la array.
- Atraviese la array y verifique las siguientes condiciones:
- Si arr[i] + arr[j] == K: elimine elementos de array duplicados consecutivos e incremente cntPairs en 1 . Actualice i = i + 1 y j = j – 1 .
- Si arr[i] + arr[j] < K entonces actualice i = i + 1 .
- De lo contrario, actualice j = j – 1 .
- Finalmente, imprima el valor de cntPairs .
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 count distinct pairs
// in array whose sum equal to K
int cntDisPairs(int arr[],
int N, int K)
{
// Stores count of distinct pairs
// whose sum equal to K
int cntPairs = 0;
// Sort the array
sort(arr, arr + N);
// Stores index of
// the left pointer
int i = 0;
// Stores index of
// the right pointer
int j = N - 1;
// Calculate count of distinct
// pairs whose sum equal to K
while (i < j) {
// If sum of current pair
// is equal to K
if (arr[i] + arr[j] == K) {
// Remove consecutive duplicate
// array elements
while (i < j && arr[i] == arr[i + 1]) {
// Update i
i++;
}
// Remove consecutive duplicate
// array elements
while (i < j && arr[j] == arr[j - 1]) {
// Update j
j--;
}
// Update cntPairs
cntPairs += 1;
// Update i
i++;
// Update j
j--;
}
// if sum of current pair
// less than K
else if (arr[i] + arr[j] < K) {
// Update i
i++;
}
else {
// Update j
j--;
}
}
return cntPairs;
}
// Driver Code
int main()
{
int arr[] = { 5, 6, 5, 7, 7, 8 };
int N = sizeof(arr) / sizeof(arr[0]);
int K = 13;
cout << cntDisPairs(arr, N, K);
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to count distinct pairs
// in array whose sum equal to K
static int cntDisPairs(int arr[],
int N, int K)
{
// Stores count of distinct pairs
// whose sum equal to K
int cntPairs = 0;
// Sort the array
Arrays.sort(arr);
// Stores index of
// the left pointer
int i = 0;
// Stores index of
// the right pointer
int j = N - 1;
// Calculate count of distinct
// pairs whose sum equal to K
while (i < j) {
// If sum of current pair
// is equal to K
if (arr[i] + arr[j] == K) {
// Remove consecutive duplicate
// array elements
while (i < j && arr[i] == arr[i + 1]) {
// Update i
i++;
}
// Remove consecutive duplicate
// array elements
while (i < j && arr[j] == arr[j - 1]) {
// Update j
j--;
}
// Update cntPairs
cntPairs += 1;
// Update i
i++;
// Update j
j--;
}
// if sum of current pair
// less than K
else if (arr[i] + arr[j] < K) {
// Update i
i++;
}
else {
// Update j
j--;
}
}
return cntPairs;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 5, 6, 5, 7, 7, 8 };
int N = arr.length;
int K = 13;
System.out.print(cntDisPairs(arr, N, K));
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to implement # the above approach # Function to count distinct pairs # in array whose sum equal to K def cntDisPairs(arr, N, K): # Stores count of distinct pairs # whose sum equal to K cntPairs = 0 # Sort the array arr = sorted(arr) # Stores index of # the left pointer i = 0 # Stores index of # the right pointer j = N - 1 # Calculate count of distinct # pairs whose sum equal to K while (i < j): # If sum of current pair # is equal to K if (arr[i] + arr[j] == K): # Remove consecutive duplicate # array elements while (i < j and arr[i] == arr[i + 1]): # Update i i += 1 # Remove consecutive duplicate # array elements while (i < j and arr[j] == arr[j - 1]): # Update j j -= 1 # Update cntPairs cntPairs += 1 # Update i i += 1 # Update j j -= 1 # If sum of current pair # less than K elif (arr[i] + arr[j] < K): # Update i i += 1 else: # Update j j -= 1 return cntPairs # Driver Code if __name__ == '__main__': arr = [ 5, 6, 5, 7, 7, 8 ] N = len(arr) K = 13 print(cntDisPairs(arr, N, K)) # This code is contributed by mohit kumar 29
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to count distinct pairs
// in array whose sum equal to K
static int cntDisPairs(int []arr,
int N, int K)
{
// Stores count of distinct pairs
// whose sum equal to K
int cntPairs = 0;
// Sort the array
Array.Sort(arr);
// Stores index of
// the left pointer
int i = 0;
// Stores index of
// the right pointer
int j = N - 1;
// Calculate count of distinct
// pairs whose sum equal to K
while (i < j)
{
// If sum of current pair
// is equal to K
if (arr[i] + arr[j] == K)
{
// Remove consecutive duplicate
// array elements
while (i < j && arr[i] == arr[i + 1])
{
// Update i
i++;
}
// Remove consecutive duplicate
// array elements
while (i < j && arr[j] == arr[j - 1])
{
// Update j
j--;
}
// Update cntPairs
cntPairs += 1;
// Update i
i++;
// Update j
j--;
}
// If sum of current pair
// less than K
else if (arr[i] + arr[j] < K)
{
// Update i
i++;
}
else
{
// Update j
j--;
}
}
return cntPairs;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 5, 6, 5, 7, 7, 8 };
int N = arr.Length;
int K = 13;
Console.WriteLine(cntDisPairs(arr, N, K));
}
}
// This code is contributed by jana_sayantan
Javascript
<script>
// javascript program to implement
// the above approach
// Function to count distinct pairs
// in array whose sum equal to K
function cntDisPairs(arr,N , K)
{
// Stores count of distinct pairs
// whose sum equal to K
var cntPairs = 0;
// Sort the array
arr.sort();
// Stores index of
// the left pointer
var i = 0;
// Stores index of
// the right pointer
var j = N - 1;
// Calculate count of distinct
// pairs whose sum equal to K
while (i < j) {
// If sum of current pair
// is equal to K
if (arr[i] + arr[j] == K) {
// Remove consecutive duplicate
// array elements
while (i < j && arr[i] == arr[i + 1]) {
// Update i
i++;
}
// Remove consecutive duplicate
// array elements
while (i < j && arr[j] == arr[j - 1]) {
// Update j
j--;
}
// Update cntPairs
cntPairs += 1;
// Update i
i++;
// Update j
j--;
}
// if sum of current pair
// less than K
else if (arr[i] + arr[j] < K) {
// Update i
i++;
}
else {
// Update j
j--;
}
}
return cntPairs;
}
// Driver Code
var arr = [ 5, 6, 5, 7, 7, 8 ];
var N = arr.length;
var K = 13;
document.write(cntDisPairs(arr, N, K));
// This code contributed by shikhasingrajput
</script>
Producción:
2
Complejidad de tiempo: O(N * log(N))
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar utilizando hashing. Siga los pasos a continuación para resolver el problema:
- Use dos conjuntos, uno para números y otro para pares vistos antes.
- Recorra la array y vea si (target – arr[i]) está presente en set y arr[i] no está presente en seen .
- En caso afirmativo, agregue tanto arr[i] como (target – arr[i]) en seen y agregue uno para contar.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
#include <bits/stdc++.h>
using namespace std;
int cntDisPairs(vector<int> arr, int target) {
unordered_set<int> set;
unordered_set<int> seen;
int count = 0;
for(int num : arr) {
if(set.find(target-num) != set.end() && seen.find(num) == seen.end() ) {
count++;
seen.insert(num);
seen.insert(target-num);
}
set.insert(num);
}
return count;
}
int main()
{
vector<int> arr = { 1, 5, 1, 5};
int K = 6;
cout << cntDisPairs(arr, K);
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG
{
// Function to count distinct pairs
// in array whose sum equal to K
static int cntDisPairs(int arr[],
int N, int K)
{
// Stores count of distinct pairs
// whose sum equal to K
int cntPairs = 0;
// Store frequency of each distinct
// element of the array
HashMap<Integer,Integer> cntFre = new HashMap<Integer,Integer>();
for (int i = 0; i < N; i++)
{
// Update frequency
// of arr[i]
if(cntFre.containsKey(arr[i]))
cntFre.put(arr[i], cntFre.get(arr[i]) + 1);
else
cntFre.put(arr[i], 1);
}
// Traverse the map
for (Map.Entry<Integer,Integer> it : cntFre.entrySet())
{
// Stores key value
// of the map
int i = it.getKey();
// If i is the half of K
if (2 * i == K)
{
// If frequency of i
// greater than 1
if (cntFre.get(i) > 1)
cntPairs += 2;
}
else
{
if (cntFre.containsKey(K - i))
{
// Update cntPairs
cntPairs += 1;
}
}
}
// Update cntPairs
cntPairs = cntPairs / 2;
return cntPairs;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 5, 6, 5, 7, 7, 8 };
int N = arr.length;
int K = 13;
System.out.print(cntDisPairs(arr, N, K));
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 program to implement
# the above approach
# Function to count distinct pairs
# in array whose sum equal to K
def cntDisPairs(arr, N, K):
# Stores count of distinct pairs
# whose sum equal to K
cntPairs = 0
# Store frequency of each distinct
# element of the array
cntFre = {}
for i in arr:
# Update frequency
# of arr[i]
if i in cntFre:
cntFre[i] += 1
else:
cntFre[i] = 1
# Traverse the map
for key, value in cntFre.items():
# Stores key value
# of the map
i = key
# If i is the half of K
if (2 * i == K):
# If frequency of i
# greater than 1
if (cntFre[i] > 1):
cntPairs += 2
else:
if (cntFre[K - i]):
# Update cntPairs
cntPairs += 1
# Update cntPairs
cntPairs = cntPairs / 2
return cntPairs
# Driver Code
arr = [ 5, 6, 5, 7, 7, 8 ]
N = len(arr)
K = 13
print(int(cntDisPairs(arr, N, K)))
# This code is contributed by Dharanendra L V
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to count distinct pairs
// in array whose sum equal to K
static int cntDisPairs(int []arr,
int N, int K)
{
// Stores count of distinct pairs
// whose sum equal to K
int cntPairs = 0;
// Store frequency of each distinct
// element of the array
Dictionary<int,int> cntFre = new Dictionary<int,int>();
for (int i = 0; i < N; i++)
{
// Update frequency
// of arr[i]
if(cntFre.ContainsKey(arr[i]))
cntFre[arr[i]] = cntFre[arr[i]] + 1;
else
cntFre.Add(arr[i], 1);
}
// Traverse the map
foreach (KeyValuePair<int,int> it in cntFre)
{
// Stores key value
// of the map
int i = it.Key;
// If i is the half of K
if (2 * i == K)
{
// If frequency of i
// greater than 1
if (cntFre[i] > 1)
cntPairs += 2;
}
else
{
if (cntFre.ContainsKey(K - i))
{
// Update cntPairs
cntPairs += 1;
}
}
}
// Update cntPairs
cntPairs = cntPairs / 2;
return cntPairs;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 5, 6, 5, 7, 7, 8 };
int N = arr.Length;
int K = 13;
Console.Write(cntDisPairs(arr, N, K));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// javascript program to implement
// the above approach
// Function to count distinct pairs
// in array whose sum equal to K
function cntDisPairs(arr , N , K) {
// Stores count of distinct pairs
// whose sum equal to K
var cntPairs = 0;
// Store frequency of each distinct
// element of the array
var cntFre =new Map();
for (i = 0; i < N; i++) {
// Update frequency
// of arr[i]
if (cntFre.has(arr[i]))
cntFre.set(arr[i], cntFre.get(arr[i]) + 1);
else
cntFre.set(arr[i], 1);
}
// Traverse the map
for (var it of cntFre) {
// Stores key value
// of the map
var i = it[0];
// If i is the half of K
if (2 * i == K) {
// If frequency of i
// greater than 1
if (cntFre[i] > 1)
cntPairs += 2;
}
else {
if (cntFre.has(K - i)) {
// Update cntPairs
cntPairs += 1;
}
}
}
// Update cntPairs
cntPairs = cntPairs / 2;
return cntPairs;
}
// Driver Code
var arr = [ 5, 6, 5, 7, 7, 8 ];
var N = arr.length;
var K = 13;
document.write(cntDisPairs(arr, N, K));
// This code is contributed by umadevi9616
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por IshwarGupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA